001: package prefuse.util.collections;
002:
003: import java.util.Collections;
004: import java.util.Comparator;
005: import java.util.Iterator;
006:
007: /**
008: * Sorted map implementation using a red-black tree to map from Object keys to
009: * int values.
010: *
011: * @author <a href="http://jheer.org">jeffrey heer</a>
012: */
013: public class ObjectIntTreeMap extends AbstractTreeMap implements
014: ObjectIntSortedMap {
015:
016: // dummy entry used as wrapper for queries
017: private ObjectEntry dummy = new ObjectEntry(null,
018: Integer.MIN_VALUE, NIL, 0);
019: private Comparator cmp = null;
020:
021: // ------------------------------------------------------------------------
022: // Constructors
023:
024: public ObjectIntTreeMap() {
025: this (null, false);
026: }
027:
028: public ObjectIntTreeMap(boolean allowDuplicates) {
029: this (null, allowDuplicates);
030: }
031:
032: public ObjectIntTreeMap(Comparator comparator) {
033: this (comparator, false);
034: }
035:
036: public ObjectIntTreeMap(Comparator comparator,
037: boolean allowDuplicates) {
038: super (null, allowDuplicates);
039: this .cmp = (comparator == null ? super .comparator()
040: : comparator);
041: }
042:
043: /**
044: * @see java.util.SortedMap#comparator()
045: */
046: public Comparator comparator() {
047: return cmp;
048: }
049:
050: // ------------------------------------------------------------------------
051: // SortedMap Methods
052:
053: /**
054: * @see java.util.Map#containsKey(java.lang.Object)
055: */
056: public boolean containsKey(Object key) {
057: return find(key, 0) != NIL;
058: }
059:
060: /**
061: * @see java.util.Map#get(java.lang.Object)
062: */
063: public int get(Object key) {
064: Entry ret = find(key, 0);
065: return (ret == NIL ? Integer.MIN_VALUE : ret.val);
066: }
067:
068: /**
069: * @see java.util.Map#put(java.lang.Object, java.lang.Object)
070: */
071: public int put(Object key, int value) {
072: Entry t = root;
073: lastOrder = 0;
074:
075: if (t == NIL) {
076: incrementSize(true);
077: root = new ObjectEntry(key, value, NIL, lastOrder);
078: return Integer.MIN_VALUE;
079: }
080:
081: dummy.key = key;
082: dummy.order = Integer.MAX_VALUE;
083:
084: while (true) {
085: int cmp = compare(dummy, t);
086: if (cmp == 0) {
087: return t.setValue(value);
088: } else if (cmp < 0) {
089: if (t.left != NIL) {
090: t = t.left;
091: } else {
092: incrementSize(lastOrder == 0);
093: t.left = new ObjectEntry(key, value, t, lastOrder);
094: fixUpInsert(t.left);
095: return Integer.MIN_VALUE;
096: }
097: } else { // cmp > 0
098: if (t.right != NIL) {
099: t = t.right;
100: } else {
101: incrementSize(lastOrder == 0);
102: t.right = new ObjectEntry(key, value, t, lastOrder);
103: fixUpInsert(t.right);
104: return Integer.MIN_VALUE;
105: }
106: }
107: }
108: }
109:
110: /**
111: * @see java.util.Map#remove(java.lang.Object)
112: */
113: public int remove(Object key) {
114: // remove the last instance with the given key
115: Entry x;
116: if (allowDuplicates)
117: x = findPredecessor(key, Integer.MAX_VALUE);
118: else
119: x = find(key, 0);
120:
121: if (x == NIL)
122: return Integer.MIN_VALUE;
123:
124: int val = x.val;
125: remove(x);
126: return val;
127: }
128:
129: public int remove(Object key, int val) {
130: // remove the last instance with the given key
131: Entry x = findCeiling(key, 0);
132: if (x != NIL
133: && ((key == null && x.getKey() != null) || (key != null && !x
134: .getKey().equals(key))))
135: x = successor(x);
136: if (x == NIL
137: || ((key == null && x.getKey() != null) || (key != null && !x
138: .getKey().equals(key))))
139: return Integer.MIN_VALUE;
140:
141: for (; x.val != val && x != NIL; x = successor(x))
142: ;
143: if (x == NIL)
144: return Integer.MIN_VALUE;
145:
146: remove(x);
147: return val;
148: }
149:
150: /**
151: * @see java.util.SortedMap#firstKey()
152: */
153: public Object firstKey() {
154: return minimum(root).getKey();
155: }
156:
157: /**
158: * @see java.util.SortedMap#lastKey()
159: */
160: public Object lastKey() {
161: return maximum(root).getKey();
162: }
163:
164: // -- Collection view methods ---------------------------------------------
165:
166: public Iterator keyIterator() {
167: return new KeyIterator();
168: }
169:
170: public Iterator keyRangeIterator(Object fromKey, boolean fromInc,
171: Object toKey, boolean toInc) {
172: Entry start, end;
173:
174: if (fromKey == toKey
175: && (fromKey == MIN_KEY || fromKey == MAX_KEY))
176: return Collections.EMPTY_LIST.iterator();
177:
178: boolean bmin = (fromKey == MIN_KEY || toKey == MAX_KEY);
179: boolean bmax = (fromKey == MAX_KEY || toKey == MIN_KEY);
180:
181: if (!bmax && (bmin || cmp.compare(fromKey, toKey) <= 0)) {
182: start = findCeiling(fromKey, (fromInc ? 0
183: : Integer.MAX_VALUE));
184: end = findCeiling(toKey, (toInc ? Integer.MAX_VALUE : 0));
185: } else {
186: start = findCeiling(fromKey, (fromInc ? Integer.MAX_VALUE
187: : 0));
188: start = predecessor(start);
189: end = findCeiling(toKey, (toInc ? 0 : Integer.MAX_VALUE));
190: end = predecessor(end);
191: }
192: return new KeyIterator(start, end);
193: }
194:
195: public IntIterator valueRangeIterator(Object fromKey,
196: boolean fromInc, Object toKey, boolean toInc) {
197: return new ValueIterator((EntryIterator) keyRangeIterator(
198: fromKey, fromInc, toKey, toInc));
199: }
200:
201: // ------------------------------------------------------------------------
202: // Internal Binary Search Tree / Red-Black Tree methods
203: // Adapted from Cormen, Leiserson, and Rivest's Introduction to Algorithms
204:
205: protected int compare(Entry e1, Entry e2) {
206: Object k1 = e1.getKey(), k2 = e2.getKey();
207:
208: if (k1 == k2 && (k1 == MIN_KEY || k1 == MAX_KEY)) {
209: return 0;
210: } else if (k1 == MIN_KEY || k2 == MAX_KEY) {
211: return -1;
212: } else if (k1 == MAX_KEY || k2 == MIN_KEY) {
213: return 1;
214: }
215:
216: int c = cmp.compare(e1.getKey(), e2.getKey());
217: if (allowDuplicates) {
218: if (c == 0) {
219: c = (e1.order < e2.order ? -1
220: : (e1.order > e2.order ? 1 : 0));
221: lastOrder = 1 + (c < 0 ? e1.order : e2.order);
222: }
223: }
224: return c;
225: }
226:
227: private Entry find(Object key, int order) {
228: dummy.key = key;
229: dummy.order = order;
230: Entry e = find(dummy);
231: dummy.key = null;
232: return e;
233: }
234:
235: private Entry findPredecessor(Object key, int order) {
236: dummy.key = key;
237: dummy.order = order;
238: Entry e = findPredecessor(dummy);
239: dummy.key = null;
240: return e;
241: }
242:
243: private Entry findCeiling(Object key, int order) {
244: dummy.key = key;
245: dummy.order = order;
246: Entry e = findCeiling(dummy);
247: dummy.key = null;
248: return e;
249: }
250:
251: // ========================================================================
252: // Inner classes
253:
254: // ------------------------------------------------------------------------
255: // Entry class - represents a Red-Black Tree Node
256:
257: static class ObjectEntry extends AbstractTreeMap.Entry {
258: Object key;
259:
260: public ObjectEntry(Object key, int val) {
261: super (val);
262: this .key = key;
263: }
264:
265: public ObjectEntry(Object key, int val, Entry parent, int order) {
266: super (val, parent, order);
267: this .key = key;
268: }
269:
270: public Object getKey() {
271: return key;
272: }
273:
274: public void copyFields(Entry x) {
275: super .copyFields(x);
276: this .key = x.getKey();
277: }
278:
279: }
280:
281: } // end of class DuplicateTreeMap
|