001: package prefuse.util.collections;
002:
003: /**
004: * Sorted map implementation using a red-black tree to map from long keys to
005: * int values.
006: *
007: * @author <a href="http://jheer.org">jeffrey heer</a>
008: */
009: public class LongIntTreeMap extends AbstractTreeMap implements
010: LongIntSortedMap {
011:
012: // dummy entry used as wrapper for queries
013: private LongEntry dummy = new LongEntry(Long.MIN_VALUE,
014: Integer.MAX_VALUE, NIL, 0);
015:
016: // ------------------------------------------------------------------------
017: // Constructors
018:
019: public LongIntTreeMap() {
020: this (null, false);
021: }
022:
023: public LongIntTreeMap(boolean allowDuplicates) {
024: this (null, allowDuplicates);
025: }
026:
027: public LongIntTreeMap(LiteralComparator comparator) {
028: this (comparator, false);
029: }
030:
031: public LongIntTreeMap(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(long key) {
052: return find(key, 0) != NIL;
053: }
054:
055: /**
056: * @see java.util.Map#get(java.lang.Object)
057: */
058: public int get(long 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(long key, int value) {
067: Entry t = root;
068: lastOrder = 0;
069:
070: if (t == NIL) {
071: incrementSize(true);
072: root = new LongEntry(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 LongEntry(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 LongEntry(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(long 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(long key, int val) {
125: // remove the last instance with the given key
126: Entry x = findCeiling(key, 0);
127: if (x != NIL && x.getLongKey() != key)
128: x = successor(x);
129: if (x == NIL || x.getLongKey() != 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: /**
142: * @see java.util.SortedMap#firstKey()
143: */
144: public long firstKey() {
145: return minimum(root).getLongKey();
146: }
147:
148: /**
149: * @see java.util.SortedMap#lastKey()
150: */
151: public long lastKey() {
152: return maximum(root).getLongKey();
153: }
154:
155: // -- Collection view methods ---------------------------------------------
156:
157: public LiteralIterator keyIterator() {
158: return new KeyIterator();
159: }
160:
161: public LiteralIterator keyRangeIterator(long fromKey,
162: boolean fromInc, long toKey, boolean toInc) {
163: Entry start, end;
164:
165: if (cmp.compare(fromKey, toKey) <= 0) {
166: start = findCeiling(fromKey, (fromInc ? 0
167: : Integer.MAX_VALUE));
168: end = findCeiling(toKey, (toInc ? Integer.MAX_VALUE : 0));
169: } else {
170: start = findCeiling(fromKey, (fromInc ? Integer.MAX_VALUE
171: : 0));
172: start = predecessor(start);
173: end = findCeiling(toKey, (toInc ? 0 : Integer.MAX_VALUE));
174: end = predecessor(end);
175: }
176: return new KeyIterator(start, end);
177: }
178:
179: public IntIterator valueRangeIterator(long fromKey,
180: boolean fromInc, long toKey, boolean toInc) {
181: return new ValueIterator((EntryIterator) keyRangeIterator(
182: fromKey, fromInc, toKey, toInc));
183: }
184:
185: // ------------------------------------------------------------------------
186: // Internal Binary Search Tree / Red-Black Tree methods
187: // Adapted from Cormen, Leiserson, and Rivest's Introduction to Algorithms
188:
189: protected int compare(Entry e1, Entry e2) {
190: int c = cmp.compare(e1.getLongKey(), e2.getLongKey());
191: if (allowDuplicates && c == 0) {
192: c = (e1.order < e2.order ? -1 : (e1.order > e2.order ? 1
193: : 0));
194: lastOrder = 1 + (c < 0 ? e1.order : e2.order);
195: }
196: return c;
197: }
198:
199: private Entry find(long key, int order) {
200: dummy.key = key;
201: dummy.order = order;
202: Entry e = find(dummy);
203: return e;
204: }
205:
206: private Entry findPredecessor(long key, int order) {
207: dummy.key = key;
208: dummy.order = order;
209: Entry e = findPredecessor(dummy);
210: return e;
211: }
212:
213: private Entry findCeiling(long key, int order) {
214: dummy.key = key;
215: dummy.order = order;
216: Entry e = findCeiling(dummy);
217: return e;
218: }
219:
220: // ========================================================================
221: // Inner classes
222:
223: // ------------------------------------------------------------------------
224: // Entry class - represents a Red-Black Tree Node
225:
226: static class LongEntry extends AbstractTreeMap.Entry {
227: long key;
228:
229: public LongEntry(long key, int val) {
230: super (val);
231: this .key = key;
232: }
233:
234: public LongEntry(long key, int val, Entry parent, int order) {
235: super (val, parent, order);
236: this .key = key;
237: }
238:
239: public long getLongKey() {
240: return key;
241: }
242:
243: public Object getKey() {
244: return new Long(key);
245: }
246:
247: public boolean keyEquals(Entry e) {
248: return (e instanceof LongEntry && key == ((LongEntry) e).key);
249: }
250:
251: public boolean equals(Object o) {
252: if (!(o instanceof LongEntry))
253: return false;
254:
255: LongEntry e = (LongEntry) o;
256: return (key == e.key && val == e.val);
257: }
258:
259: public int hashCode() {
260: int khash = (int) (key ^ (key >>> 32));
261: int vhash = val;
262: return khash ^ vhash ^ order;
263: }
264:
265: public String toString() {
266: return key + "=" + val;
267: }
268:
269: public void copyFields(Entry x) {
270: super .copyFields(x);
271: this .key = x.getLongKey();
272: }
273:
274: }
275:
276: // ------------------------------------------------------------------------
277: // Iterators
278:
279: private class KeyIterator extends AbstractTreeMap.KeyIterator {
280: public KeyIterator() {
281: super ();
282: }
283:
284: public KeyIterator(Entry start, Entry end) {
285: super (start, end);
286: }
287:
288: public boolean isLongSupported() {
289: return true;
290: }
291:
292: public long nextLong() {
293: return nextEntry().getLongKey();
294: }
295: }
296:
297: } // end of class LongIntTreeMap
|