|
1 package prefuse.util.collections;
2
3
9 public class LongIntTreeMap extends AbstractTreeMap implements LongIntSortedMap {
10
11 private LongEntry dummy =
13 new LongEntry(Long.MIN_VALUE, Integer.MAX_VALUE, NIL, 0);
14
15
18 public LongIntTreeMap() {
19 this(null, false);
20 }
21
22 public LongIntTreeMap(boolean allowDuplicates) {
23 this(null, allowDuplicates);
24 }
25
26 public LongIntTreeMap(LiteralComparator comparator) {
27 this(comparator, false);
28 }
29
30 public LongIntTreeMap(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(long key) {
52 return find(key, 0) != NIL;
53 }
54
55
58 public int get(long key) {
59 Entry ret = find(key, 0);
60 return ( ret == NIL ? Integer.MIN_VALUE : ret.val );
61 }
62
63
66 public int put(long key, int value) {
67 Entry t = root;
68 lastOrder = 0;
69
70 if (t == NIL) {
71 incrementSize(true);
72 root = new LongEntry(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 LongEntry(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 LongEntry(key, value, t, lastOrder);
98 fixUpInsert(t.right);
99 return Integer.MIN_VALUE;
100 }
101 }
102 }
103 }
104
105
108 public int remove(long 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(long key, int val) {
125 Entry x = findCeiling(key, 0);
127 if ( x!=NIL && x.getLongKey() != key )
128 x = successor(x);
129 if (x==NIL || x.getLongKey()!=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 long firstKey() {
142 return minimum(root).getLongKey();
143 }
144
145
148 public long lastKey() {
149 return maximum(root).getLongKey();
150 }
151
152
154 public LiteralIterator keyIterator() {
155 return new KeyIterator();
156 }
157
158 public LiteralIterator keyRangeIterator(long fromKey, boolean fromInc,
159 long 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(long fromKey, boolean fromInc,
176 long 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.getLongKey(), e2.getLongKey());
188 if ( allowDuplicates && c == 0 ) {
189 c = (e1.order < e2.order ? -1 : (e1.order > e2.order ? 1 : 0));
190 lastOrder = 1 + (c < 0 ? e1.order : e2.order);
191 }
192 return c;
193 }
194
195 private Entry find(long key, int order) {
196 dummy.key = key;
197 dummy.order = order;
198 Entry e = find(dummy);
199 return e;
200 }
201
202 private Entry findPredecessor(long key, int order) {
203 dummy.key = key;
204 dummy.order = order;
205 Entry e = findPredecessor(dummy);
206 return e;
207 }
208
209 private Entry findCeiling(long key, int order) {
210 dummy.key = key;
211 dummy.order = order;
212 Entry e = findCeiling(dummy);
213 return e;
214 }
215
216
219
222 static class LongEntry extends AbstractTreeMap.Entry {
223 long key;
224
225 public LongEntry(long key, int val) {
226 super(val);
227 this.key = key;
228 }
229
230 public LongEntry(long key, int val, Entry parent, int order) {
231 super(val, parent, order);
232 this.key = key;
233 }
234
235 public long getLongKey() {
236 return key;
237 }
238
239 public Object  getKey() {
240 return new Long (key);
241 }
242
243 public boolean keyEquals(Entry e) {
244 return (e instanceof LongEntry && key == ((LongEntry)e).key);
245 }
246
247 public boolean equals(Object o) {
248 if (!(o instanceof LongEntry))
249 return false;
250
251 LongEntry e = (LongEntry)o;
252 return (key == e.key && val == e.val);
253 }
254
255 public int hashCode() {
256 int khash = (int)(key^(key>>>32));
257 int vhash = val;
258 return khash ^ vhash ^ order;
259 }
260
261 public String toString() {
262 return key + "=" + val;
263 }
264
265 public void copyFields(Entry x) {
266 super.copyFields(x);
267 this.key = x.getLongKey();
268 }
269
270 }
271
272
275 private class KeyIterator extends AbstractTreeMap.KeyIterator {
276 public KeyIterator() {
277 super();
278 }
279 public KeyIterator(Entry start, Entry end) {
280 super(start, end);
281 }
282 public boolean isLongSupported() {
283 return true;
284 }
285 public long nextLong() {
286 return nextEntry().getLongKey();
287 }
288 }
289
290 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.