[freenet-dev] [freenet-cvs] r19230 - in trunk/freenet: src/freenet/support test/freenet/support

[Matthew Toseland]

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 : http://emu.freenetproject.org/pipermail/devl/attachments/20080414/5e7549c9/attachment.pgp