We do actually have an implementation of binarySearch, i think in Fields. The
reason was that java's version doesn't take (offset, length), and in some
cases (RequestCooldownQueue iirc), we need to search with them.
I suggest you coalesce the two, and test the resulting function.
On Saturday 12 April 2008 15:01, j16sdiz at freenetproject.org wrote:
> 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
>
> _______________________________________________
> cvs mailing list
> cvs at freenetproject.org
> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20080414/5e7549c9/attachment.pgp>
