001: package prefuse.util.collections;
002:
003: /**
004: * Sorted map implementation using a red-black tree to map from int keys to
005: * int values.
006: *
007: * @author <a href="http://jheer.org">jeffrey heer</a>
008: */
009: public class IntIntTreeMap extends AbstractTreeMap implements
010: IntIntSortedMap {
011:
012: // dummy entry used as wrapper for queries
013: private IntEntry dummy = new IntEntry(Integer.MIN_VALUE,
014: Integer.MAX_VALUE, NIL, 0);
015:
016: // ------------------------------------------------------------------------
017: // Constructors
018:
019: public IntIntTreeMap() {
020: this (null, false);
021: }
022:
023: public IntIntTreeMap(boolean allowDuplicates) {
024: this (null, allowDuplicates);
025: }
026:
027: public IntIntTreeMap(LiteralComparator comparator) {
028: this (comparator, false);
029: }
030:
031: public IntIntTreeMap(LiteralComparator comparator,
032: boolean allowDuplicates) {
033: super (comparator, allowDuplicates);
034: }
035:
036: // ------------------------------------------------------------------------
037: // SortedMap Methods
038:
039: /**
040: * @see java.util.Map#clear()
041: */
042: public void clear() {
043: ++modCount;
044: size = 0;
045: root = NIL;
046: }
047:
048: /**
049: * @see java.util.Map#containsKey(java.lang.Object)
050: */
051: public boolean containsKey(int key) {
052: return find(key, 0) != NIL;
053: }
054:
055: /**
056: * @see java.util.Map#get(java.lang.Object)
057: */
058: public int get(int key) {
059: Entry ret = find(key, 0);
060: return (ret == NIL ? Integer.MIN_VALUE : ret.val);
061: }
062:
063: /**
064: * @see java.util.Map#put(java.lang.Object, java.lang.Object)
065: */
066: public int put(int key, int value) {
067: Entry t = root;
068: lastOrder = 0;
069:
070: if (t == NIL) {
071: incrementSize(true);
072: root = new IntEntry(key, value, NIL, lastOrder);
073: return Integer.MIN_VALUE;
074: }
075:
076: dummy.key = key;
077: dummy.order = Integer.MAX_VALUE;
078:
079: while (true) {
080: int cmp = compare(dummy, t);
081: if (cmp == 0) {
082: return t.setValue(value);
083: } else if (cmp < 0) {
084: if (t.left != NIL) {
085: t = t.left;
086: } else {
087: incrementSize(lastOrder == 0);
088: t.left = new IntEntry(key, value, t, lastOrder);
089: fixUpInsert(t.left);
090: return Integer.MIN_VALUE;
091: }
092: } else { // cmp > 0
093: if (t.right != NIL) {
094: t = t.right;
095: } else {
096: incrementSize(lastOrder == 0);
097: t.right = new IntEntry(key, value, t, lastOrder);
098: fixUpInsert(t.right);
099: return Integer.MIN_VALUE;
100: }
101: }
102: }
103: }
104:
105: /**
106: * @see java.util.Map#remove(java.lang.Object)
107: */
108: public int remove(int key) {
109: // remove the last instance with the given key
110: Entry x;
111: if (allowDuplicates)
112: x = findPredecessor(key, Integer.MAX_VALUE);
113: else
114: x = find(key, 0);
115:
116: if (x == NIL)
117: return Integer.MIN_VALUE;
118:
119: int val = x.val;
120: remove(x);
121: return val;
122: }
123:
124: public int remove(int key, int val) {
125: // remove the last instance with the given key
126: Entry x = findCeiling(key, 0);
127: if (x != NIL && x.getIntKey() != key)
128: x = successor(x);
129: if (x == NIL || x.getIntKey() != key)
130: return Integer.MIN_VALUE;
131:
132: for (; x.val != val && x != NIL; x = successor(x))
133: ;
134: if (x == NIL)
135: return Integer.MIN_VALUE;
136:
137: remove(x);
138: return val;
139: }
140:
141: public int getLast(int key) {
142: Entry ret = findPredecessor(key, Integer.MAX_VALUE);
143: return (ret == NIL || ((IntEntry) ret).key != key ? Integer.MIN_VALUE
144: : ret.val);
145: }
146:
147: public int getPreviousValue(int key, int value) {
148: Entry cur = find(key, value);
149: return predecessor(cur).val;
150: }
151:
152: public int getNextValue(int key, int value) {
153: Entry cur = find(key, value);
154: return successor(cur).val;
155: }
156:
157: /**
158: * @see java.util.SortedMap#firstKey()
159: */
160: public int firstKey() {
161: return minimum(root).getIntKey();
162: }
163:
164: /**
165: * @see java.util.SortedMap#lastKey()
166: */
167: public int lastKey() {
168: return maximum(root).getIntKey();
169: }
170:
171: // -- Collection view methods ---------------------------------------------
172:
173: public LiteralIterator keyIterator() {
174: return new KeyIterator();
175: }
176:
177: public LiteralIterator keyRangeIterator(int fromKey,
178: boolean fromInc, int toKey, boolean toInc) {
179: Entry start, end;
180:
181: if (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(int fromKey, boolean fromInc,
196: int 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: int c = cmp.compare(e1.getIntKey(), e2.getIntKey());
207: if (allowDuplicates && c == 0) {
208: c = (e1.order < e2.order ? -1 : (e1.order > e2.order ? 1
209: : 0));
210: lastOrder = 1 + (c < 0 ? e1.order : e2.order);
211: }
212: return c;
213: }
214:
215: private Entry find(int key, int order) {
216: dummy.key = key;
217: dummy.order = order;
218: Entry e = find(dummy);
219: return e;
220: }
221:
222: private Entry findPredecessor(int key, int order) {
223: dummy.key = key;
224: dummy.order = order;
225: Entry e = findPredecessor(dummy);
226: return e;
227: }
228:
229: private Entry findCeiling(int key, int order) {
230: dummy.key = key;
231: dummy.order = order;
232: Entry e = findCeiling(dummy);
233: return e;
234: }
235:
236: // ========================================================================
237: // Inner classes
238:
239: // ------------------------------------------------------------------------
240: // Entry class - represents a Red-Black Tree Node
241:
242: static class IntEntry extends AbstractTreeMap.Entry {
243: int key;
244:
245: public IntEntry(int key, int val) {
246: super (val);
247: this .key = key;
248: }
249:
250: public IntEntry(int key, int val, Entry parent, int order) {
251: super (val, parent, order);
252: this .key = key;
253: }
254:
255: public int getIntKey() {
256: return key;
257: }
258:
259: public Object getKey() {
260: return new Integer(key);
261: }
262:
263: public boolean keyEquals(Entry e) {
264: return (e instanceof IntEntry && key == ((IntEntry) e).key);
265: }
266:
267: public boolean equals(Object o) {
268: if (!(o instanceof IntEntry))
269: return false;
270:
271: IntEntry e = (IntEntry) o;
272: return (key == e.key && val == e.val);
273: }
274:
275: public int hashCode() {
276: int khash = key;
277: int vhash = val;
278: return khash ^ vhash ^ order;
279: }
280:
281: public String toString() {
282: return key + "=" + val;
283: }
284:
285: public void copyFields(Entry x) {
286: super .copyFields(x);
287: this .key = x.getIntKey();
288: }
289:
290: }
291:
292: // ------------------------------------------------------------------------
293: // Iterators
294:
295: private class KeyIterator extends AbstractTreeMap.KeyIterator {
296: public KeyIterator() {
297: super ();
298: }
299:
300: public KeyIterator(Entry start, Entry end) {
301: super (start, end);
302: }
303:
304: public boolean isIntSupported() {
305: return true;
306: }
307:
308: public int nextInt() {
309: return nextEntry().getIntKey();
310: }
311: }
312:
313: } // end of class IntIntTreeMap
|