001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
003: */
004: package com.tc.util;
005:
006: import com.tc.object.ObjectID;
007:
008: import java.util.AbstractSet;
009: import java.util.ArrayList;
010: import java.util.Collection;
011: import java.util.Iterator;
012: import java.util.List;
013: import java.util.NoSuchElementException;
014:
015: /**
016: * TODO May 31, 2006: 1) Make this set special case things like addAll() removeAll() etc if the passed in collection is
017: * also an ObjectIDSet 2) Make this set optimized for worst case scenario too. (like for storing ObjectIDs 1, 3, 5, 7, 9
018: * etc.
019: */
020: public class ObjectIDSet extends AbstractSet implements Cloneable {
021: private final List ranges;
022: private int size = 0;
023:
024: public ObjectIDSet() {
025: ranges = new ArrayList();
026: // ranges = new LinkedList();
027: }
028:
029: public ObjectIDSet(Collection c) {
030: if (c instanceof ObjectIDSet) {
031: ObjectIDSet oidSet = (ObjectIDSet) c;
032: // fast way to clone
033: size = oidSet.size();
034: ranges = new ArrayList(oidSet.ranges.size());
035: for (int i = 0; i < oidSet.ranges.size(); i++) {
036: ranges.add(((Range) oidSet.ranges.get(i)).clone());
037: }
038: return;
039: } else {
040: ranges = new ArrayList();
041: addAll(c);
042: }
043: }
044:
045: public Object clone() {
046: return new ObjectIDSet(this );
047: }
048:
049: public Iterator iterator() {
050: return new ObjectIDSetIterator();
051: }
052:
053: public int size() {
054: return size;
055: }
056:
057: public boolean remove(ObjectID id) {
058: long lid = id.toLong();
059: int index = findIndex(lid);
060: if (index < 0)
061: return false;
062: return removeObjectIDAt(lid, index);
063: }
064:
065: // THis is a private method and no checks are done
066: private boolean removeObjectIDAt(long lid, int index) {
067: size--;
068: Range r = (Range) ranges.get(index);
069: if (r.start == lid && r.end == lid + 1) {
070: ranges.remove(index);
071: return true;
072: }
073:
074: if (r.start == lid) {
075: r.start = r.start + 1;
076: } else if (r.end == lid + 1) {
077: r.end = r.end - 1;
078: } else if (r.start < lid && lid < r.end) {
079: Range newRange = new Range(lid + 1, r.end);
080: r.end = lid;
081:
082: Assert.eval(newRange.start != newRange.end);
083: ranges.add(index + 1, newRange);
084: } else {
085: Assert.failure("Called with the wrong the index : " + index
086: + " for lid : " + lid);
087: }
088:
089: return true;
090: }
091:
092: public boolean add(ObjectID id) {
093: long lid = id.toLong();
094:
095: int index = 0;
096: int low = 0;
097: int high = ranges.size() - 1;
098:
099: // if it's empty add and retrun;
100: if (ranges.size() == 0) {
101: ranges.add(index, new Range(lid, lid + 1));
102: size++;
103: return true;
104: }
105:
106: // If it's an add at the end;
107: Range lr = (Range) ranges.get(high);
108: if (lid == lr.end) {
109: lr.end++;
110: size++;
111: return true;
112: }
113:
114: // if this thing goes on the end just add it
115: if (lr.end + 1 < lid) {
116: ranges.add(new Range(lid, lid + 1));
117: size++;
118: return true;
119: }
120:
121: Range fr = (Range) ranges.get(0);
122: if (lid < fr.start - 1) {
123: ranges.add(index, new Range(lid, lid + 1));
124: size++;
125: return true;
126: }
127:
128: while (low <= high) {
129: index = low + high >> 1;
130: Range r = (Range) ranges.get(index);
131:
132: if (r.end < lid) {
133: low = index + 1;
134: } else {
135: high = index - 1;
136: }
137:
138: if (r.contains(lid))
139: return false;// exists
140: if (r.end == lid) {
141: r.addToEnd();
142: while (++index < ranges.size()) {
143: Range n = (Range) ranges.get(index);
144: if (n.start == r.end) {
145: r.end = n.end;
146: ranges.remove(index);
147: } else {
148: break;
149: }
150: }
151: size++;
152: return true;
153: }
154: if (r.start - 1 == lid) {
155: r.addToStart();
156: size++;
157: while (--index >= 0) {
158: Range pr = (Range) ranges.get(index);
159: if (pr.end == r.start) {
160: r.start = pr.start;
161: ranges.remove(index);
162: } else {
163: break;
164: }
165: }
166: return true;
167: }
168: }
169: size++;
170: Range ir = (Range) ranges.get(index);
171: Range newRange = new Range(lid, lid + 1);
172: if (ir.end < lid) {
173: ranges.add(index + 1, newRange);
174: } else {
175: ranges.add(index, newRange);
176: }
177: return true;
178: }
179:
180: public static class Range implements Cloneable {
181: public long start;
182: public long end;
183:
184: public String toString() {
185: return "Range(" + start + "," + end + ")";
186: }
187:
188: public Range(long start, long end) {
189: this .start = start;
190: this .end = end;
191: }
192:
193: public void addToEnd() {
194: end++;
195: }
196:
197: public void addToStart() {
198: start--;
199: }
200:
201: public boolean contains(long id) {
202: return id >= start && id < end;
203: }
204:
205: public Object clone() {
206: return new Range(start, end);
207: }
208: }
209:
210: private int findIndex(long lid) {
211:
212: int index = 0;
213: int low = 0;
214: int high = ranges.size() - 1;
215:
216: // if it's empty add and retrun;
217: if (ranges.size() == 0) {
218: return -1;
219: }
220:
221: // if this thing goes on the end
222: Range lr = (Range) ranges.get(ranges.size() - 1);
223: if (lr.end <= lid) {
224: return -1;
225: }
226: if (lr.contains(lid)) {
227: return high;
228: }
229:
230: Range fr = (Range) ranges.get(0);
231: if (lid < fr.start) {
232: return -1;
233: }
234: if (fr.contains(lid))
235: return 0;
236:
237: while (low <= high) {
238: index = low + high >> 1;
239: Range r = (Range) ranges.get(index);
240:
241: if (r.end < lid) {
242: low = index + 1;
243: } else {
244: high = index - 1;
245: }
246:
247: if (r.contains(lid))
248: return index;
249: }
250: return -1;
251: }
252:
253: public class ObjectIDSetIterator implements Iterator {
254: private int range;
255: private int offset;
256: private ObjectID current;
257: public int visited = 0;
258:
259: public boolean hasNext() {
260: return !(range >= ranges.size());
261: }
262:
263: public Object next() {
264: if (range >= ranges.size())
265: throw new NoSuchElementException();
266: visited++;
267: Range r = (Range) ranges.get(range);
268: current = new ObjectID(r.start + offset);
269: if (r.start + offset + 1 < r.end) {
270: offset++;
271: } else {
272: offset = 0;
273: range++;
274: }
275:
276: return current;
277: }
278:
279: public void remove() {
280: if (current == null)
281: throw new IllegalStateException();
282: int b4size = ranges.size();
283: // ObjectIDSet.this.remove(current);
284: ObjectIDSet.this .removeObjectIDAt(current.toLong(),
285: (offset == 0 ? range - 1 : range));
286: if (b4size > ranges.size()) {
287: // Case 1: Last returned ObjectID was the only one contained in that Range.
288: Assert.assertEquals(0, offset);
289: range--;
290: } else if (b4size == ranges.size()) {
291: // Case 2: Last returned ObjectID was either the first or the last of the range.
292: if (offset == 1) {
293: // It was the first
294: offset = 0;
295: } else {
296: // It was the last. So no change
297: Assert.assertEquals(0, offset);
298: }
299: } else {
300: // Case 3 : b4size < ranges.size(); Last returned ObjectIDSet was some where in the middle.
301: range++;
302: Assert.assertTrue(offset != 0);
303: offset = 0;
304: }
305: }
306: }
307:
308: public boolean contains(Object o) {
309: return findIndex(((ObjectID) o).toLong()) >= 0;
310: }
311:
312: public boolean add(Object arg0) {
313: return add((ObjectID) arg0);
314: }
315:
316: public boolean remove(Object o) {
317: return remove((ObjectID) o);
318: }
319:
320: public void clear() {
321: this .size = 0;
322: ranges.clear();
323: }
324: }
|