|
1 package prefuse.util.collections;
2
3
9 public class FloatIntTreeMap extends AbstractTreeMap implements FloatIntSortedMap {
10
11 private FloatEntry dummy =
13 new FloatEntry(Float.MIN_VALUE, Integer.MAX_VALUE, NIL, 0);
14
15
18 public FloatIntTreeMap() {
19 this(null, false);
20 }
21
22 public FloatIntTreeMap(boolean allowDuplicates) {
23 this(null, allowDuplicates);
24 }
25
26 public FloatIntTreeMap(LiteralComparator comparator) {
27 this(comparator, false);
28 }
29
30 public FloatIntTreeMap(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(float key) {
52 return find(key, 0) != NIL;
53 }
54
55
58 public int get(float key) {
59 Entry ret = find(key, 0);
60 return ( ret == NIL ? Integer.MIN_VALUE : ret.val );
61 }
62
63
66 public int put(float key, int value) {
67 Entry t = root;
68 lastOrder = 0;
69
70 if (t == NIL) {
71 incrementSize(true);
72 root = new FloatEntry(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 FloatEntry(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 FloatEntry(key, value, t, lastOrder);
98 fixUpInsert(t.right);
99 return Integer.MIN_VALUE;
100 }
101 }
102 }
103 }
104
105
108 public int remove(float 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(float key, int val) {
125 Entry x = findCeiling(key, 0);
127 if ( x!=NIL && x.getFloatKey() != key )
128 x = successor(x);
129 if (x==NIL || x.getFloatKey()!=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 float firstKey() {
142 return minimum(root).getFloatKey();
143 }
144
145
148 public float lastKey() {
149 return maximum(root).getFloatKey();
150 }
151
152
154 public LiteralIterator keyIterator() {
155 return new KeyIterator();
156 }
157
158 public LiteralIterator keyRangeIterator(float fromKey, boolean fromInc,
159 float 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(float fromKey, boolean fromInc,
176 float 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.getFloatKey(), e2.getFloatKey());
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(float 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(float 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(float 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 FloatEntry extends AbstractTreeMap.Entry {
225 float key;
226
227 public FloatEntry(float key, int val) {
228 super(val);
229 this.key = key;
230 }
231
232 public FloatEntry(float key, int val, Entry parent, int order) {
233 super(val, parent, order);
234 this.key = key;
235 }
236
237 public float getFloatKey() {
238 return key;
239 }
240
241 public Object  getKey() {
242 return new Float (key);
243 }
244
245 public boolean keyEquals(Entry e) {
246 return (e instanceof FloatEntry && key == ((FloatEntry)e).key);
247 }
248
249 public boolean equals(Object o) {
250 if (!(o instanceof FloatEntry))
251 return false;
252
253 FloatEntry e = (FloatEntry)o;
254 return (key == e.key && val == e.val);
255 }
256
257 public int hashCode() {
258 int khash = Float.floatToIntBits(key);
259 int vhash = val;
260 return khash ^ vhash ^ order;
261 }
262
263 public String toString() {
264 return key + "=" + val;
265 }
266
267 public void copyFields(Entry x) {
268 super.copyFields(x);
269 this.key = x.getFloatKey();
270 }
271
272 }
273
274
277 private class KeyIterator extends AbstractTreeMap.KeyIterator {
278 public KeyIterator() {
279 super();
280 }
281 public KeyIterator(Entry start, Entry end) {
282 super(start, end);
283 }
284 public boolean isFloatSupported() {
285 return true;
286 }
287 public float nextFloat() {
288 return nextEntry().getFloatKey();
289 }
290 }
291
292 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.