001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright
003: * notice. All rights reserved.
004: */
005: package com.tc.util;
006:
007: import com.tc.exception.ImplementMe;
008: import com.tc.object.ObjectID;
009:
010: import java.io.Externalizable;
011: import java.io.IOException;
012: import java.io.ObjectInput;
013: import java.io.ObjectOutput;
014: import java.util.AbstractSet;
015: import java.util.ArrayList;
016: import java.util.Collection;
017: import java.util.Iterator;
018: import java.util.NoSuchElementException;
019:
020: /**
021: * This class is a an attempt to meet the shortcomings of ObjectIDSet. Mainly the performance of adds and removes when
022: * the ObjectIDs are non-contiguous. It uses a balanced tree internally to store ranges instead of an arraylist
023: */
024: public class ObjectIDSet2 extends AbstractSet implements Externalizable {
025:
026: private final AATree ranges;
027: private int size = 0;
028:
029: public ObjectIDSet2() {
030: ranges = new AATree();
031: }
032:
033: public ObjectIDSet2(Collection c) {
034: this ();
035: if (c instanceof ObjectIDSet2) {
036: ObjectIDSet2 other = (ObjectIDSet2) c;
037: // fast way to clone
038: this .size = other.size();
039: for (Iterator i = other.ranges.iterator(); i.hasNext();) {
040: this .ranges.insert((Range) ((Range) i.next()).clone());
041: }
042: return;
043: } else {
044: addAll(c);
045: }
046: }
047:
048: public void readExternal(ObjectInput in) throws IOException {
049: int _size = in.readInt();
050: this .size = _size;
051: while (_size > 0) {
052: long start = in.readLong();
053: long end = in.readLong();
054: Range r = new Range(start, end);
055: this .ranges.insert(r);
056: _size -= r.size();
057: }
058: }
059:
060: public void writeExternal(ObjectOutput out) throws IOException {
061: out.writeInt(size);
062: for (Iterator i = ranges.iterator(); i.hasNext();) {
063: Range r = (Range) i.next();
064: out.writeLong(r.start);
065: out.writeLong(r.end);
066: }
067: }
068:
069: public Iterator iterator() {
070: return new ObjectIDSetIterator();
071: }
072:
073: public int size() {
074: return size;
075: }
076:
077: public boolean contains(ObjectID id) {
078: long lid = id.toLong();
079: return (ranges.find(new MyLong(lid)) != null);
080: }
081:
082: public boolean remove(ObjectID id) {
083: long lid = id.toLong();
084:
085: Range current = (Range) ranges.find(new MyLong(lid));
086: if (current == null) {
087: // Not found
088: return false;
089: }
090: Range newRange = current.remove(lid);
091: if (newRange != null) {
092: ranges.insert(newRange);
093: } else if (current.isNull()) {
094: ranges.remove(current);
095: }
096: size--;
097: return true;
098: }
099:
100: public boolean add(ObjectID id) {
101: long lid = id.toLong();
102:
103: // Step 1 : Check if the previous number is present, if so add to the same Range.
104: Range prev = (Range) ranges.find(new MyLong(lid - 1));
105: if (prev != null) {
106: boolean isAdded = prev.add(lid);
107: if (isAdded) {
108: Range next = (Range) ranges
109: .remove((new MyLong(lid + 1)));
110: if (next != null)
111: prev.merge(next);
112: size++;
113: }
114: return isAdded;
115: }
116:
117: // Step 2 : Check if the next number is present, if so add to the same Range.
118: Range next = (Range) ranges.find((new MyLong(lid + 1)));
119: if (next != null) {
120: boolean isAdded = next.add(lid);
121: if (isAdded)
122: size++;
123: return isAdded;
124: }
125:
126: // Step 3: Add a new range for just this number.
127: boolean isAdded = ranges.insert(new Range(lid, lid));
128: if (isAdded)
129: size++;
130: return isAdded;
131: }
132:
133: public String toString() {
134: StringBuffer sb = new StringBuffer("ObjectIDSet2 [");
135: for (Iterator i = ranges.iterator(); i.hasNext();) {
136: sb.append(' ').append(i.next());
137: }
138: return sb.append(']').toString();
139: }
140:
141: /**
142: * Ranges store the elements stored in the tree. The range is inclusive.
143: */
144: private static class Range implements Cloneable, Comparable {
145: public long start;
146: public long end;
147:
148: public String toString() {
149: return "Range(" + start + "," + end + ")";
150: }
151:
152: public long size() {
153: return (isNull() ? 0 : end - start + 1); // since it is all inclusive
154: }
155:
156: public boolean isNull() {
157: return start > end;
158: }
159:
160: public Range remove(long lid) {
161: if (lid < start || lid > end) {
162: throw new AssertionError(
163: "Ranges : Illegal value passed to remove : "
164: + this + " remove called for : " + lid);
165: }
166: if (start == lid) {
167: start++;
168: return null;
169: } else if (end == lid) {
170: end--;
171: return null;
172: } else {
173: Range newRange = new Range(lid + 1, end);
174: end = lid - 1;
175: return newRange;
176: }
177: }
178:
179: public void merge(Range other) {
180: if (start == other.end + 1) {
181: start = other.start;
182: } else if (end == other.start - 1) {
183: end = other.end;
184: } else {
185: throw new AssertionError(
186: "Ranges : Merge is called on non contiguous value : "
187: + this + " and other Range is " + other);
188: }
189: }
190:
191: public boolean add(long lid) {
192: if (lid == start - 1) {
193: start--;
194: return true;
195: } else if (lid == end + 1) {
196: end++;
197: return true;
198: } else if (lid >= start && lid <= end) {
199: return false;
200: } else {
201: throw new AssertionError(
202: "Ranges : Add is called on non contiguous value : "
203: + this + " but trying to add " + lid);
204: }
205: }
206:
207: public Range(long start, long end) {
208: this .start = start;
209: this .end = end;
210: }
211:
212: public Object clone() {
213: return new Range(start, end);
214: }
215:
216: public int compareTo(Object o) {
217: if (o instanceof Range) {
218: Range other = (Range) o;
219: if (start < other.start)
220: return -1;
221: else if (start == other.start)
222: return 0;
223: else
224: return 1;
225: } else {
226: long n = ((MyLong) o).longValue();
227: if (end < n)
228: return -1;
229: else if (n < start)
230: return 1;
231: else
232: return 0;
233: }
234: }
235: }
236:
237: // This class is used as a key for lookup.
238: private static final class MyLong implements Comparable {
239: final long number;
240:
241: public MyLong(long number) {
242: this .number = number;
243: }
244:
245: public long longValue() {
246: return number;
247: }
248:
249: public int compareTo(Object o) {
250: if (o instanceof Range) {
251: Range r = (Range) o;
252: if (number < r.start)
253: return -1;
254: else if (number > r.end)
255: return 1;
256: else
257: return 0;
258: } else {
259: long other = ((MyLong) o).longValue();
260: if (number < other)
261: return -1;
262: else if (number > other)
263: return 1;
264: else
265: return 0;
266: }
267: }
268:
269: public String toString() {
270: return "MyLong@" + System.identityHashCode(this ) + "("
271: + number + ")";
272: }
273: }
274:
275: private class ObjectIDSetIterator implements Iterator {
276:
277: Iterator nodes;
278: Range current;
279: int idx = 0;
280:
281: public ObjectIDSetIterator() {
282: nodes = ranges.iterator();
283: if (nodes.hasNext())
284: current = (Range) nodes.next();
285: }
286:
287: public boolean hasNext() {
288: return nodes.hasNext()
289: || (current != null && (current.start + idx) <= current.end);
290: }
291:
292: public Object next() {
293: if (current == null)
294: throw new NoSuchElementException();
295: ObjectID oid = new ObjectID(current.start + idx);
296: if (current.start + idx == current.end) {
297: idx = 0;
298: if (nodes.hasNext()) {
299: current = (Range) nodes.next();
300: } else {
301: current = null;
302: }
303: } else {
304: idx++;
305: }
306: return oid;
307: }
308:
309: // This is a little tricky as the tree might balance itself.
310: public void remove() {
311: throw new ImplementMe();
312: }
313: }
314:
315: /*
316: * Because of the short comings of the iterator (it cant perform remove), this method is overridden
317: */
318: public boolean removeAll(Collection c) {
319: boolean modified = false;
320: if (size() > c.size()) {
321: for (Iterator i = c.iterator(); i.hasNext();)
322: modified |= remove(i.next());
323: } else {
324: // XXX :; yuck !!
325: ArrayList toRemove = new ArrayList();
326: for (Iterator i = iterator(); i.hasNext();) {
327: Object o = i.next();
328: if (c.contains(o)) {
329: toRemove.add(o);
330: modified = true;
331: }
332: }
333: for (Iterator i = toRemove.iterator(); i.hasNext();) {
334: remove(i.next());
335: }
336: }
337: return modified;
338: }
339:
340: /*
341: * Because of the short comings of the iterator (it cant perform remove), this method is overridden
342: */
343: public boolean retainAll(Collection c) {
344: boolean modified = false;
345: ObjectIDSet2 toRemove = new ObjectIDSet2();
346: Iterator e = iterator();
347: while (e.hasNext()) {
348: Object o = e.next();
349: if (!c.contains(o)) {
350: toRemove.add(o);
351: modified = true;
352: }
353: }
354: for (Iterator i = toRemove.iterator(); i.hasNext();) {
355: remove(i.next());
356: }
357: return modified;
358: }
359:
360: public boolean contains(Object o) {
361: if (o instanceof ObjectID) {
362: return contains((ObjectID) o);
363: } else {
364: return false;
365: }
366: }
367:
368: public boolean add(Object arg0) {
369: return add((ObjectID) arg0);
370: }
371:
372: public boolean remove(Object o) {
373: if (o instanceof ObjectID) {
374: return remove((ObjectID) o);
375: } else {
376: return false;
377: }
378: }
379:
380: public void clear() {
381: this .size = 0;
382: ranges.clear();
383: }
384:
385: }
|