Author: j16sdiz
Date: 2008-04-12 14:01:07 +0000 (Sat, 12 Apr 2008)
New Revision: 19230
Modified:
trunk/freenet/src/freenet/support/SortedLongSet.java
trunk/freenet/test/freenet/support/SortedLongSetTest.java
Log:
make SortedLongSet accept Long.MAX_VALUE
Modified: trunk/freenet/src/freenet/support/SortedLongSet.java
===================================================================
--- trunk/freenet/src/freenet/support/SortedLongSet.java 2008-04-12
13:53:10 UTC (rev 19229)
+++ trunk/freenet/src/freenet/support/SortedLongSet.java 2008-04-12
14:01:07 UTC (rev 19230)
@@ -48,7 +48,7 @@
* @return <code>true</code>, if <code>num</code> exist.
*/
public synchronized boolean contains(long num) {
- int x = Arrays.binarySearch(data, num);
+ int x = binarySearch(num);
if(x >= 0)
return true;
else
@@ -62,7 +62,7 @@
* the item to be removed
*/
public synchronized void remove(long item) {
- int x = Arrays.binarySearch(data, item);
+ int x = binarySearch(item);
if(x >= 0) {
if(x < length-1)
System.arraycopy(data, x+1, data, x,
length-x-1);
@@ -98,12 +98,12 @@
/**
* Add the item, if it (or an item of the same number) is not already
- * present. <strong>This method does not accept
<code>Long.MAX_VALUE</code>.</strong>
+ * present.
*
* @return <code>true</code>, if we added the item.
*/
public synchronized boolean push(long num) {
- int x = Arrays.binarySearch(data, num);
+ int x = binarySearch(num);
if(x >= 0) return false;
// insertion point
x = -x-1;
@@ -114,14 +114,12 @@
/**
* Add the item.
*
- * <strong>This method does not accept
<code>Long.MAX_VALUE</code>.</strong>
- *
* @throws {@link IllegalArgumentException}
* if the item already exist
* @return <code>true</code>, if we added the item.
*/
public synchronized void add(long num) {
- int x = Arrays.binarySearch(data, num);
+ int x = binarySearch(num);
if(x >= 0) throw new IllegalArgumentException(); // already
exists
// insertion point
x = -x-1;
@@ -179,4 +177,21 @@
return output;
}
+ private int binarySearch(long key) {
+ int low = 0;
+ int high = length - 1;
+
+ while (low <= high) {
+ int mid = (low + high) >> 1;
+ long midVal = data[mid];
+
+ if (midVal < key)
+ low = mid + 1;
+ else if (midVal > key)
+ high = mid - 1;
+ else
+ return mid; // key found
+ }
+ return -(low + 1); // key not found.
+ }
}
Modified: trunk/freenet/test/freenet/support/SortedLongSetTest.java
===================================================================
--- trunk/freenet/test/freenet/support/SortedLongSetTest.java 2008-04-12
13:53:10 UTC (rev 19229)
+++ trunk/freenet/test/freenet/support/SortedLongSetTest.java 2008-04-12
14:01:07 UTC (rev 19230)
@@ -8,13 +8,7 @@
* @author sdiz
*/
public class SortedLongSetTest extends TestCase {
- /*
- * FIXME use Long.MAX_VALUE , not MAX_VALUE - 1
- */
- private final static long[] testArray = {
- 10, 8, 6, 2, 0, 1, 11,
- Long.MAX_VALUE - 1, 4, 7, 5, 3, Long.MIN_VALUE
- };
+ private final static long[] testArray = { 10, 8, 6, 2, 0, 1, 11,
Long.MAX_VALUE, 4, 7, 5, 3, Long.MIN_VALUE };
protected SortedLongSet perpare(long[] array) {
SortedLongSet set = new SortedLongSet();
@@ -60,7 +54,7 @@
// Contain
assertTrue(set.contains(0L));
assertTrue(set.contains(3L));
- assertTrue(set.contains(Long.MAX_VALUE - 1));
+ assertTrue(set.contains(Long.MAX_VALUE));
assertTrue(set.contains(Long.MIN_VALUE));
// Not contain
