KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > tc > util > ObjectIDSet


1 /*
2  * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
3  */
4 package com.tc.util;
5
6 import com.tc.object.ObjectID;
7
8 import java.util.AbstractSet JavaDoc;
9 import java.util.ArrayList JavaDoc;
10 import java.util.Collection JavaDoc;
11 import java.util.Iterator JavaDoc;
12 import java.util.List JavaDoc;
13 import java.util.NoSuchElementException JavaDoc;
14
15 /**
16  * TODO May 31, 2006: 1) Make this set special case things like addAll() removeAll() etc if the passed in collection is
17  * also an ObjectIDSet 2) Make this set optimized for worst case scenario too. (like for storing ObjectIDs 1, 3, 5, 7, 9
18  * etc.
19  */
20 public class ObjectIDSet extends AbstractSet JavaDoc implements Cloneable JavaDoc {
21   private final List JavaDoc ranges;
22   private int size = 0;
23
24   public ObjectIDSet() {
25     ranges = new ArrayList JavaDoc();
26 // ranges = new LinkedList();
27 }
28
29   public ObjectIDSet(Collection JavaDoc c) {
30     if (c instanceof ObjectIDSet) {
31       ObjectIDSet oidSet = (ObjectIDSet) c;
32       // fast way to clone
33 size = oidSet.size();
34       ranges = new ArrayList JavaDoc(oidSet.ranges.size());
35       for (int i = 0; i < oidSet.ranges.size(); i++) {
36         ranges.add(((Range) oidSet.ranges.get(i)).clone());
37       }
38       return;
39     } else {
40       ranges = new ArrayList JavaDoc();
41       addAll(c);
42     }
43   }
44
45   public Object JavaDoc clone() {
46     return new ObjectIDSet(this);
47   }
48
49   public Iterator JavaDoc iterator() {
50     return new ObjectIDSetIterator();
51   }
52
53   public int size() {
54     return size;
55   }
56
57   public boolean remove(ObjectID id) {
58     long lid = id.toLong();
59     int index = findIndex(lid);
60     if (index < 0) return false;
61     return removeObjectIDAt(lid, index);
62   }
63
64   // THis is a private method and no checks are done
65 private boolean removeObjectIDAt(long lid, int index) {
66     size--;
67     Range r = (Range) ranges.get(index);
68     if (r.start == lid && r.end == lid + 1) {
69       ranges.remove(index);
70       return true;
71     }
72
73     if (r.start == lid) {
74       r.start = r.start + 1;
75     } else if (r.end == lid + 1) {
76       r.end = r.end - 1;
77     } else if(r.start < lid && lid < r.end ) {
78       Range newRange = new Range(lid + 1, r.end);
79       r.end = lid;
80
81       Assert.eval(newRange.start != newRange.end);
82       ranges.add(index + 1, newRange);
83     } else {
84       Assert.failure("Called with the wrong the index : " + index + " for lid : " + lid);
85     }
86
87     return true;
88   }
89
90   public boolean add(ObjectID id) {
91     long lid = id.toLong();
92
93     int index = 0;
94     int low = 0;
95     int high = ranges.size() - 1;
96
97     // if it's empty add and retrun;
98 if (ranges.size() == 0) {
99       ranges.add(index, new Range(lid, lid + 1));
100       size++;
101       return true;
102     }
103
104     // If it's an add at the end;
105 Range lr = (Range) ranges.get(high);
106     if (lid == lr.end) {
107       lr.end++;
108       size++;
109       return true;
110     }
111
112     // if this thing goes on the end just add it
113 if (lr.end + 1 < lid) {
114       ranges.add(new Range(lid, lid + 1));
115       size++;
116       return true;
117     }
118
119     Range fr = (Range) ranges.get(0);
120     if (lid < fr.start - 1) {
121       ranges.add(index, new Range(lid, lid + 1));
122       size++;
123       return true;
124     }
125
126     while (low <= high) {
127       index = low + high >> 1;
128       Range r = (Range) ranges.get(index);
129
130       if (r.end < lid) {
131         low = index + 1;
132       } else {
133         high = index - 1;
134       }
135
136       if (r.contains(lid)) return false;// exists
137 if (r.end == lid) {
138         r.addToEnd();
139         while (++index < ranges.size()) {
140           Range n = (Range) ranges.get(index);
141           if (n.start == r.end) {
142             r.end = n.end;
143             ranges.remove(index);
144           } else {
145             break;
146           }
147         }
148         size++;
149         return true;
150       }
151       if (r.start - 1 == lid) {
152         r.addToStart();
153         size++;
154         while (--index >= 0) {
155           Range pr = (Range) ranges.get(index);
156           if (pr.end == r.start) {
157             r.start = pr.start;
158             ranges.remove(index);
159           } else {
160             break;
161           }
162         }
163         return true;
164       }
165     }
166     size++;
167     Range ir = (Range) ranges.get(index);
168     Range newRange = new Range(lid, lid + 1);
169     if (ir.end < lid) {
170       ranges.add(index + 1, newRange);
171     } else {
172       ranges.add(index, newRange);
173     }
174     return true;
175   }
176
177   public static class Range implements Cloneable JavaDoc {
178     public long start;
179     public long end;
180
181     public String JavaDoc toString() {
182       return "Range(" + start + "," + end + ")";
183     }
184
185     public Range(long start, long end) {
186       this.start = start;
187       this.end = end;
188     }
189
190     public void addToEnd() {
191       end++;
192     }
193
194     public void addToStart() {
195       start--;
196     }
197
198     public boolean contains(long id) {
199       return id >= start && id < end;
200     }
201
202     public Object JavaDoc clone() {
203       return new Range(start, end);
204     }
205   }
206
207   private int findIndex(long lid) {
208
209     int index = 0;
210     int low = 0;
211     int high = ranges.size() - 1;
212
213     // if it's empty add and retrun;
214 if (ranges.size() == 0) { return -1; }
215
216     // if this thing goes on the end
217 Range lr = (Range) ranges.get(ranges.size() - 1);
218     if (lr.end <= lid) { return -1; }
219     if (lr.contains(lid)) { return high; }
220
221     Range fr = (Range) ranges.get(0);
222     if (lid < fr.start) { return -1; }
223     if (fr.contains(lid)) return 0;
224
225     while (low <= high) {
226       index = low + high >> 1;
227       Range r = (Range) ranges.get(index);
228
229       if (r.end < lid) {
230         low = index + 1;
231       } else {
232         high = index - 1;
233       }
234
235       if (r.contains(lid)) return index;
236     }
237     return -1;
238   }
239
240   public class ObjectIDSetIterator implements Iterator JavaDoc {
241     private int range;
242     private int offset;
243     private ObjectID current;
244     public int visited = 0;
245
246     public boolean hasNext() {
247       return !(range >= ranges.size());
248     }
249
250     public Object JavaDoc next() {
251       if (range >= ranges.size()) throw new NoSuchElementException JavaDoc();
252       visited++;
253       Range r = (Range) ranges.get(range);
254       current = new ObjectID(r.start + offset);
255       if (r.start + offset + 1 < r.end) {
256         offset++;
257       } else {
258         offset = 0;
259         range++;
260       }
261
262       return current;
263     }
264
265     public void remove() {
266       if (current == null) throw new IllegalStateException JavaDoc();
267       int b4size = ranges.size();
268       // ObjectIDSet.this.remove(current);
269 ObjectIDSet.this.removeObjectIDAt(current.toLong(), (offset == 0 ? range -1 : range));
270       if (b4size > ranges.size()) {
271         // Case 1: Last returned ObjectID was the only one contained in that Range.
272 Assert.assertEquals(0, offset);
273         range--;
274       } else if (b4size == ranges.size()) {
275         // Case 2: Last returned ObjectID was either the first or the last of the range.
276 if (offset == 1) {
277           // It was the first
278 offset = 0;
279         } else {
280           // It was the last. So no change
281 Assert.assertEquals(0, offset);
282         }
283       } else {
284         // Case 3 : b4size < ranges.size(); Last returned ObjectIDSet was some where in the middle.
285 range++;
286         Assert.assertTrue(offset != 0);
287         offset = 0;
288       }
289     }
290   }
291
292   public boolean contains(Object JavaDoc o) {
293     return findIndex(((ObjectID) o).toLong()) >= 0;
294   }
295
296   public boolean add(Object JavaDoc arg0) {
297     return add((ObjectID) arg0);
298   }
299
300   public boolean remove(Object JavaDoc o) {
301     return remove((ObjectID) o);
302   }
303
304   public void clear() {
305     this.size = 0;
306     ranges.clear();
307   }
308 }
309
Popular Tags