KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > util > collections > DoubleIntTreeMap


1 package prefuse.util.collections;
2
3 /**
4  * Sorted map implementation using a red-black tree to map from double keys to
5  * int values.
6  *
7  * @author <a HREF="http://jheer.org">jeffrey heer</a>
8  */

9 public class DoubleIntTreeMap extends AbstractTreeMap implements DoubleIntSortedMap {
10     
11     // dummy entry used as wrapper for queries
12
private DoubleEntry dummy =
13         new DoubleEntry(Double.MIN_VALUE, Integer.MAX_VALUE, NIL, 0);
14         
15     // ------------------------------------------------------------------------
16
// Constructors
17

18     public DoubleIntTreeMap() {
19         this(null, false);
20     }
21     
22     public DoubleIntTreeMap(boolean allowDuplicates) {
23         this(null, allowDuplicates);
24     }
25     
26     public DoubleIntTreeMap(LiteralComparator comparator) {
27         this(comparator, false);
28     }
29     
30     public DoubleIntTreeMap(LiteralComparator comparator,
31                                boolean allowDuplicates)
32     {
33         super(comparator, allowDuplicates);
34     }
35     
36     // ------------------------------------------------------------------------
37
// SortedMap Methods
38

39     /**
40      * @see java.util.Map#clear()
41      */

42     public void clear() {
43         ++modCount;
44         size = 0;
45         root = NIL;
46     }
47
48     /**
49      * @see java.util.Map#containsKey(java.lang.Object)
50      */

51     public boolean containsKey(double key) {
52         return find(key, 0) != NIL;
53     }
54
55     /**
56      * @see java.util.Map#get(java.lang.Object)
57      */

58     public int get(double key) {
59         Entry ret = find(key, 0);
60         return ( ret == NIL ? Integer.MIN_VALUE : ret.val );
61     }
62
63     /**
64      * @see java.util.Map#put(java.lang.Object, java.lang.Object)
65      */

66     public int put(double key, int value) {
67         Entry t = root;
68         lastOrder = 0;
69         
70         if (t == NIL) {
71             incrementSize(true);
72             root = new DoubleEntry(key, value, NIL, lastOrder);
73             return Integer.MIN_VALUE;
74         }
75
76         dummy.key = key;
77         dummy.order = Integer.MAX_VALUE;
78         
79         while (true) {
80             int cmp = compare(dummy, t);
81             if (cmp == 0) {
82                 return t.setValue(value);
83             } else if (cmp < 0) {
84                 if (t.left != NIL) {
85                     t = t.left;
86                 } else {
87                     incrementSize(lastOrder==0);
88                     t.left = new DoubleEntry(key, value, t, lastOrder);
89                     fixUpInsert(t.left);
90                     return Integer.MIN_VALUE;
91                 }
92             } else { // cmp > 0
93
if (t.right != NIL) {
94                     t = t.right;
95                 } else {
96                     incrementSize(lastOrder==0);
97                     t.right = new DoubleEntry(key, value, t, lastOrder);
98                     fixUpInsert(t.right);
99                     return Integer.MIN_VALUE;
100                 }
101             }
102         }
103     }
104
105     /**
106      * @see java.util.Map#remove(java.lang.Object)
107      */

108     public int remove(double 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(double key, int val) {
125         // remove the last instance with the given key
126
Entry x = findCeiling(key, 0);
127         if ( x!=NIL && x.getDoubleKey() != key )
128             x = successor(x);
129         if (x==NIL || x.getDoubleKey()!=key) return Integer.MIN_VALUE;
130
131         for ( ; x.val != val && x != NIL; x = successor(x) );
132         if (x == NIL) return Integer.MIN_VALUE;
133         
134         remove(x);
135         return val;
136     }
137
138     /**
139      * @see java.util.SortedMap#firstKey()
140      */

141     public double firstKey() {
142         return minimum(root).getDoubleKey();
143     }
144     
145     /**
146      * @see java.util.SortedMap#lastKey()
147      */

148     public double lastKey() {
149         return maximum(root).getDoubleKey();
150     }
151     
152     // -- Collection view methods ---------------------------------------------
153

154     public LiteralIterator keyIterator() {
155         return new KeyIterator();
156     }
157     
158     public LiteralIterator keyRangeIterator(double fromKey, boolean fromInc,
159                                             double toKey, boolean toInc)
160     {
161         Entry start, end;
162         
163         if ( cmp.compare(fromKey, toKey) <= 0 ) {
164             start = findCeiling(fromKey, (fromInc ? 0 : Integer.MAX_VALUE));
165             end = findCeiling(toKey, (toInc? Integer.MAX_VALUE : 0));
166         } else {
167             start = findCeiling(fromKey, (fromInc ? Integer.MAX_VALUE : 0));
168             start = predecessor(start);
169             end = findCeiling(toKey, (toInc ? 0 : Integer.MAX_VALUE));
170             end = predecessor(end);
171         }
172         return new KeyIterator(start, end);
173     }
174     
175     public IntIterator valueRangeIterator(double fromKey, boolean fromInc,
176                                           double toKey, boolean toInc)
177     {
178         return new ValueIterator(
179                 (EntryIterator)keyRangeIterator(fromKey,fromInc,toKey,toInc));
180     }
181     
182     // ------------------------------------------------------------------------
183
// Internal Binary Search Tree / Red-Black Tree methods
184
// Adapted from Cormen, Leiserson, and Rivest's Introduction to Algorithms
185

186     protected int compare(Entry e1, Entry e2) {
187         int c = cmp.compare(e1.getDoubleKey(), e2.getDoubleKey());
188         if ( allowDuplicates ) {
189             if ( c == 0 ) {
190                 c = (e1.order < e2.order ? -1 : (e1.order > e2.order ? 1 : 0));
191                 lastOrder = 1 + (c < 0 ? e1.order : e2.order);
192             }
193         }
194         return c;
195     }
196     
197     private Entry find(double key, int order) {
198         dummy.key = key;
199         dummy.order = order;
200         Entry e = find(dummy);
201         return e;
202     }
203     
204     private Entry findPredecessor(double key, int order) {
205         dummy.key = key;
206         dummy.order = order;
207         Entry e = findPredecessor(dummy);
208         return e;
209     }
210     
211     private Entry findCeiling(double key, int order) {
212         dummy.key = key;
213         dummy.order = order;
214         Entry e = findCeiling(dummy);
215         return e;
216     }
217     
218     // ========================================================================
219
// Inner classes
220

221     // ------------------------------------------------------------------------
222
// Entry class - represents a Red-Black Tree Node
223

224     static class DoubleEntry extends AbstractTreeMap.Entry {
225         double key;
226         
227         public DoubleEntry(double key, int val) {
228             super(val);
229             this.key = key;
230         }
231         
232         public DoubleEntry(double key, int val, Entry parent, int order) {
233             super(val, parent, order);
234             this.key = key;
235         }
236         
237         public double getDoubleKey() {
238             return key;
239         }
240         
241         public Object JavaDoc getKey() {
242             return new Double JavaDoc(key);
243         }
244         
245         public boolean keyEquals(Entry e) {
246             return (e instanceof DoubleEntry && key == ((DoubleEntry)e).key);
247         }
248         
249         public boolean equals(Object JavaDoc o) {
250             if (!(o instanceof DoubleEntry))
251                 return false;
252             
253             DoubleEntry e = (DoubleEntry)o;
254             return (key == e.key && val == e.val);
255         }
256
257         public int hashCode() {
258             long k = Double.doubleToLongBits(key);
259             int khash = (int)(k^(k>>>32));
260             int vhash = val;
261             return khash ^ vhash ^ order;
262         }
263
264         public String JavaDoc toString() {
265             return key + "=" + val;
266         }
267         
268         public void copyFields(Entry x) {
269             super.copyFields(x);
270             this.key = x.getDoubleKey();
271         }
272         
273     }
274     
275     // ------------------------------------------------------------------------
276
// Iterators
277

278     private class KeyIterator extends AbstractTreeMap.KeyIterator {
279         public KeyIterator() {
280             super();
281         }
282         public KeyIterator(Entry start, Entry end) {
283             super(start, end);
284         }
285         public boolean isDoubleSupported() {
286             return true;
287         }
288         public double nextDouble() {
289             return nextEntry().getDoubleKey();
290         }
291     }
292     
293 } // end of class DoubleIntTreeMap
294
Popular Tags