|
1 package prefuse.util.collections;
2
3
9 public class DoubleIntTreeMap extends AbstractTreeMap implements DoubleIntSortedMap {
10
11 private DoubleEntry dummy =
13 new DoubleEntry(Double.MIN_VALUE, Integer.MAX_VALUE, NIL, 0);
14
15
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
39
42 public void clear() {
43 ++modCount;
44 size = 0;
45 root = NIL;
46 }
47
48
51 public boolean containsKey(double key) {
52 return find(key, 0) != NIL;
53 }
54
55
58 public int get(double key) {
59 Entry ret = find(key, 0);
60 return ( ret == NIL ? Integer.MIN_VALUE : ret.val );
61 }
62
63
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 { 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
108 public int remove(double key) {
109 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 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
141 public double firstKey() {
142 return minimum(root).getDoubleKey();
143 }
144
145
148 public double lastKey() {
149 return maximum(root).getDoubleKey();
150 }
151
152
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
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
221
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  getKey() {
242 return new Double (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 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 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
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 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.