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