|
1
4 package com.tc.util;
5
6 import com.tc.exception.ImplementMe;
7 import com.tc.object.ObjectID;
8
9 import java.util.AbstractSet  ;
10 import java.util.ArrayList ;
11 import java.util.Collection ;
12 import java.util.Iterator ;
13 import java.util.NoSuchElementException ;
14
15
19 public class ObjectIDSet2 extends AbstractSet {
20
21 private final AATree ranges;
22 private int size = 0;
23
24 public ObjectIDSet2() {
25 ranges = new AATree();
26 }
27
28 public ObjectIDSet2(Collection c) {
29 this();
30 if (c instanceof ObjectIDSet2) {
31 ObjectIDSet2 other = (ObjectIDSet2) c;
32 this.size = other.size();
34 for (Iterator i = other.ranges.iterator(); i.hasNext();) {
35 this.ranges.insert((Range) ((Range) i.next()).clone());
36 }
37 return;
38 } else {
39 addAll(c);
40 }
41 }
42
43 public Iterator iterator() {
44 return new ObjectIDSetIterator();
45 }
46
47 public int size() {
48 return size;
49 }
50
51 public boolean contains(ObjectID id) {
52 long lid = id.toLong();
53 return (ranges.find(new MyLong(lid)) != null);
54 }
55
56 public boolean remove(ObjectID id) {
57 long lid = id.toLong();
58
59 Range current = (Range) ranges.find(new MyLong(lid));
60 if (current == null) {
61 return false;
63 }
64 Range newRange = current.remove(lid);
65 if (newRange != null) {
66 ranges.insert(newRange);
67 } else if (current.isNull()) {
68 ranges.remove(current);
69 }
70 size--;
71 return true;
72 }
73
74 public boolean add(ObjectID id) {
75 long lid = id.toLong();
76
77 Range prev = (Range) ranges.find(new MyLong(lid - 1));
79 if (prev != null) {
80 boolean isAdded = prev.add(lid);
81 if (isAdded) {
82 Range next = (Range) ranges.remove((new MyLong(lid + 1)));
83 if (next != null) prev.merge(next);
84 size++;
85 }
86 return isAdded;
87 }
88
89 Range next = (Range) ranges.find((new MyLong(lid + 1)));
91 if (next != null) {
92 boolean isAdded = next.add(lid);
93 if (isAdded) size++;
94 return isAdded;
95 }
96
97 boolean isAdded = ranges.insert(new Range(lid, lid));
99 if (isAdded) size++;
100 return isAdded;
101 }
102
103 public String toString() {
104 StringBuffer sb = new StringBuffer ("ObjectIDSet2 [");
105 for (Iterator i = ranges.iterator(); i.hasNext();) {
106 sb.append(' ').append(i.next());
107 }
108 return sb.append(']').toString();
109 }
110
111
114 private static class Range implements Cloneable , Comparable {
115 public long start;
116 public long end;
117
118 public String toString() {
119 return "Range(" + start + "," + end + ")";
120 }
121
122 public boolean isNull() {
123 return start > end;
124 }
125
126 public Range remove(long lid) {
127 if (lid < start || lid > end) { throw new AssertionError ("Ranges : Illegal value passed to remove : " + this
128 + " remove called for : " + lid); }
129 if (start == lid) {
130 start++;
131 return null;
132 } else if (end == lid) {
133 end--;
134 return null;
135 } else {
136 Range newRange = new Range(lid + 1, end);
137 end = lid - 1;
138 return newRange;
139 }
140 }
141
142 public void merge(Range other) {
143 if (start == other.end + 1) {
144 start = other.start;
145 } else if (end == other.start - 1) {
146 end = other.end;
147 } else {
148 throw new AssertionError ("Ranges : Merge is called on non contigues value : " + this + " and other Range is "
149 + other);
150 }
151 }
152
153 public boolean add(long lid) {
154 if (lid == start - 1) {
155 start--;
156 return true;
157 } else if (lid == end + 1) {
158 end++;
159 return true;
160 } else if (lid >= start && lid <= end) {
161 return false;
162 } else {
163 throw new AssertionError ("Ranges : Add is called on non contigues value : " + this + " but trying to add "
164 + lid);
165 }
166 }
167
168 public Range(long start, long end) {
169 this.start = start;
170 this.end = end;
171 }
172
173 public Object clone() {
174 return new Range(start, end);
175 }
176
177 public int compareTo(Object o) {
178 if (o instanceof Range) {
179 Range other = (Range) o;
180 if (start < other.start) return -1;
181 else if (start == other.start) return 0;
182 else return 1;
183 } else {
184 long n = ((MyLong) o).longValue();
185 if (end < n) return -1;
186 else if (n < start) return 1;
187 else return 0;
188 }
189 }
190 }
191
192 private static final class MyLong implements Comparable {
194 final long number;
195
196 public MyLong(long number) {
197 this.number = number;
198 }
199
200 public long longValue() {
201 return number;
202 }
203
204 public int compareTo(Object o) {
205 if (o instanceof Range) {
206 Range r = (Range) o;
207 if (number < r.start) return -1;
208 else if (number > r.end) return 1;
209 else return 0;
210 } else {
211 long other = ((MyLong) o).longValue();
212 if (number < other) return -1;
213 else if (number > other) return 1;
214 else return 0;
215 }
216 }
217
218 public String toString() {
219 return "MyLong@" + System.identityHashCode(this) + "(" + number +")" ;
220 }
221 }
222
223 private class ObjectIDSetIterator implements Iterator {
224
225 Iterator nodes;
226 Range current;
227 int idx = 0;
228
229 public ObjectIDSetIterator() {
230 nodes = ranges.iterator();
231 if (nodes.hasNext()) current = (Range) nodes.next();
232 }
233
234 public boolean hasNext() {
235 return nodes.hasNext() || (current != null && (current.start + idx) <= current.end);
236 }
237
238 public Object next() {
239 if (current == null) throw new NoSuchElementException ();
240 ObjectID oid = new ObjectID(current.start + idx);
241 if (current.start + idx == current.end) {
242 idx = 0;
243 if (nodes.hasNext()) {
244 current = (Range) nodes.next();
245 } else {
246 current = null;
247 }
248 } else {
249 idx++;
250 }
251 return oid;
252 }
253
254 public void remove() {
256 throw new ImplementMe();
257 }
258 }
259
260
263 public boolean removeAll(Collection c) {
264 boolean modified = false;
265 if (size() > c.size()) {
266 for (Iterator i = c.iterator(); i.hasNext();)
267 modified |= remove(i.next());
268 } else {
269 ArrayList toRemove = new ArrayList ();
271 for (Iterator i = iterator(); i.hasNext();) {
272 Object o = i.next();
273 if (c.contains(o)) {
274 toRemove.add(o);
275 modified = true;
276 }
277 }
278 for (Iterator i = toRemove.iterator(); i.hasNext();) {
279 remove(i.next());
280 }
281 }
282 return modified;
283 }
284
285
288 public boolean retainAll(Collection c) {
289 boolean modified = false;
290 ArrayList toRemove = new ArrayList (c.size());
292 Iterator e = iterator();
293 while (e.hasNext()) {
294 Object o = e.next();
295 if (!c.contains(o)) {
296 toRemove.add(o);
297 modified = true;
298 }
299 }
300 for (Iterator i = toRemove.iterator(); i.hasNext();) {
301 remove(i.next());
302 }
303 return modified;
304 }
305
306 public boolean contains(Object o) {
307 if (o instanceof ObjectID) {
308 return contains((ObjectID) o);
309 } else {
310 return false;
311 }
312 }
313
314 public boolean add(Object arg0) {
315 return add((ObjectID) arg0);
316 }
317
318 public boolean remove(Object o) {
319 if (o instanceof ObjectID) {
320 return remove((ObjectID) o);
321 } else {
322 return false;
323 }
324 }
325
326 public void clear() {
327 this.size = 0;
328 ranges.clear();
329 }
330
331 }
332 |
Popular Tags |
Java API By Example, From Geeks To Geeks.