trove4j-commit — commit logs for trove CVS projects

[Trove4j-commit] CVS: trove/test/gnu/trove/set/hash THashSetTest.java, 1.1.2.1, 1.1.2.2 TPrimitiveHashSetTest.java, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/test/gnu/trove/set/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14944/test/gnu/trove/set/hash

Modified Files:
      Tag: TROVE_3_WORKING
	THashSetTest.java TPrimitiveHashSetTest.java 
Log Message:
Implement TPrimitiveHashIterators.  Nearly full text coverage, many bugs found and fixed in process,

Index: THashSetTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/set/hash/Attic/THashSetTest.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** THashSetTest.java	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- THashSetTest.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 28,34 ****
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
! import java.util.Arrays;
! import java.util.HashSet;
! import java.util.Set;
  
  
--- 28,32 ----
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
! import java.util.*;
  
  
***************
*** 37,41 ****
   * Created: Sat Nov  3 10:33:15 2001
   *
!  * @author Eric D. Friedman, Rob Eden, Jeff Randall
   * @version $Id$
   */
--- 35,41 ----
   * Created: Sat Nov  3 10:33:15 2001
   *
!  * @author Eric D. Friedman
!  * @author Rob Eden
!  * @author Jeff Randall
   * @version $Id$
   */
***************
*** 58,61 ****
--- 58,81 ----
  
  
+     public void testConstructors() throws Exception {
+         Set<String> set = new THashSet<String>();
+         assertNotNull( set );
+ 
+         String[] strings = {"a", "b", "c", "d"};
+         set.addAll( Arrays.asList( strings ) );
+ 
+         Set<String> copy = new THashSet<String>( set );
+         assertTrue( "set not a copy: " + set + ", " + copy, set.equals( copy ) );
+ 
+         Set<String> another = new THashSet<String>( 20 );
+         another.addAll( Arrays.asList( strings ) );
+         assertTrue( "set not equal: " + set + ", " + copy, set.equals( another ) );
+ 
+         another = new THashSet<String>( 2, 1.0f );
+         another.addAll( Arrays.asList( strings ) );
+         assertTrue( "set not equal: " + set + ", " + copy, set.equals( another ) );
+     }
+ 
+ 
      public void testIsEmpty() throws Exception {
          Set<String> s = new THashSet<String>();
***************
*** 77,80 ****
--- 97,101 ----
  
  
+     @SuppressWarnings({"ForLoopReplaceableByForEach"})
      public void testContainsAll() throws Exception {
          Set<String> s = new THashSet<String>();
***************
*** 86,89 ****
--- 107,151 ----
          assertTrue( "containsAll failed: " + s,
                  s.containsAll( Arrays.asList( o ) ) );
+ 
+         String[] more = {"Hello World", "Goodbye World", "Hello Goodbye", "Not There"};
+         assertFalse( "containsAll failed: " + s,
+                 s.containsAll( Arrays.asList( more ) ) );
+     }
+ 
+ 
+     public void testRetainAll() throws Exception {
+         Set<String> set = new THashSet<String>();
+         String[] strings = {"Hello World", "Goodbye World", "Hello Goodbye", "Remove Me"};
+         set.addAll( Arrays.asList( strings ) );
+         for ( String string : strings ) {
+             assertTrue( string, set.contains( string ) );
+         }
+ 
+         String[] retain = {"Hello World", "Goodbye World", "Hello Goodbye"};
+         assertTrue( "retainAll failed: " + set,
+                 set.retainAll( Arrays.asList( retain ) ) );
+         assertTrue( "containsAll failed: " + set,
+                 set.containsAll( Arrays.asList( retain ) ) );
+     }
+ 
+ 
+     public void testRemoveAll() throws Exception {
+         Set<String> set = new THashSet<String>();
+         String[] strings = {"Hello World", "Goodbye World", "Hello Goodbye", "Keep Me"};
+         set.addAll( Arrays.asList( strings ) );
+         for ( String string : strings ) {
+             assertTrue( string, set.contains( string ) );
+         }
+ 
+         String[] remove = {"Hello World", "Goodbye World", "Hello Goodbye"};
+         assertTrue( "removeAll failed: " + set,
+                 set.removeAll( Arrays.asList( remove ) ) );
+         assertTrue( "removeAll failed: " + set,
+                 set.containsAll( Arrays.asList( "Keep Me" ) ) );
+ 
+         for ( String element : remove ) {
+             assertFalse( element + " still in set: " + set, set.contains( element ) );
+         }
+         assertEquals( 1, set.size() );
      }
  
***************
*** 103,106 ****
--- 165,183 ----
          assertTrue( "One was not removed", s.remove( "One" ) );
          assertTrue( "One was not removed", !s.contains( "One" ) );
+         assertTrue( "Two was removed", s.contains( "Two" ) );
+         assertEquals( 1, s.size() );
+     }
+ 
+ 
+     public void testRemoveObjectNotInSet() throws Exception {
+         Set<String> set = new THashSet<String>();
+         set.add( "One" );
+         set.add( "Two" );
+         assertTrue( "One was not added", set.contains( "One" ) );
+         assertTrue( "One was not removed", set.remove( "One" ) );
+         assertTrue( "One was not removed", !set.contains( "One" ) );
+         assertTrue( "Two was removed", set.contains( "Two" ) );
+         assertFalse( "Three was removed (non-existant)", set.remove( "Three" ) );
+         assertEquals( 1, set.size() );
      }
  
***************
*** 119,123 ****
      public void testClear() throws Exception {
          Set<String> s = new THashSet<String>();
!         s.addAll( Arrays.asList( new String[]{"one", "two", "three"} ) );
          assertEquals( "size was not 3", 3, s.size() );
          s.clear();
--- 196,200 ----
      public void testClear() throws Exception {
          Set<String> s = new THashSet<String>();
!         s.addAll( Arrays.asList( "one", "two", "three" ) );
          assertEquals( "size was not 3", 3, s.size() );
          s.clear();
***************
*** 126,143 ****
  
  
-     // TODO: implement after serialzation is implemented
      public void testSerialize() throws Exception {
! //        Set<String> s = new THashSet<String>();
! //        s.addAll( Arrays.asList( new String[]{"one", "two", "three"} ) );
! //        ByteArrayOutputStream baos = new ByteArrayOutputStream();
! //        ObjectOutputStream oos = new ObjectOutputStream( baos );
! //        oos.writeObject( s );
! //
! //        ByteArrayInputStream bais = new ByteArrayInputStream( baos.toByteArray() );
! //        ObjectInputStream ois = new ObjectInputStream( bais );
! //
! //        THashSet s2 = (THashSet) ois.readObject();
! //
! //        assertEquals( s, s2 );
      }
  
--- 203,219 ----
  
  
      public void testSerialize() throws Exception {
!         Set<String> s = new THashSet<String>();
!         s.addAll( Arrays.asList( "one", "two", "three" ) );
!         ByteArrayOutputStream baos = new ByteArrayOutputStream();
!         ObjectOutputStream oos = new ObjectOutputStream( baos );
!         oos.writeObject( s );
! 
!         ByteArrayInputStream bais = new ByteArrayInputStream( baos.toByteArray() );
!         ObjectInputStream ois = new ObjectInputStream( bais );
! 
!         THashSet s2 = (THashSet) ois.readObject();
! 
!         assertEquals( s, s2 );
      }
  
***************
*** 161,170 ****
          sink[sink.length - 1] = "residue";
          sink[sink.length - 2] = "will be cleared";
!         Object[] res = s.toArray( sink );
  
!         Set copy = new HashSet();
          copy.addAll( Arrays.asList( res ) );
  
!         Set bogey = new HashSet();
          bogey.addAll( Arrays.asList( str ) );
          bogey.add( "residue" );
--- 237,246 ----
          sink[sink.length - 1] = "residue";
          sink[sink.length - 2] = "will be cleared";
!         String[] res = s.toArray( sink );
  
!         Set<String> copy = new HashSet<String>();
          copy.addAll( Arrays.asList( res ) );
  
!         Set<String> bogey = new HashSet<String>();
          bogey.addAll( Arrays.asList( str ) );
          bogey.add( "residue" );
***************
*** 174,178 ****
--- 250,283 ----
  
  
+     @SuppressWarnings({"ToArrayCallWithZeroLengthArrayArgument", "SuspiciousToArrayCall"})
+     public void testToArrayAnotherType() throws Exception {
+         Set<Number> set = new THashSet<Number>();
+         Number[] nums = {1138, 42, 86, 99, 101};
+         set.addAll( Arrays.asList( nums ) );
+ 
+         Integer[] to_int_array_zero = set.toArray( new Integer[0] );
+         assertTrue( "set and array mismatch: " + set +
+                     ", " + Arrays.asList( to_int_array_zero ),
+                 set.containsAll( Arrays.asList( to_int_array_zero ) ) );
  
+         Integer[] to_int_array_size = set.toArray( new Integer[set.size()] );
+         assertTrue( "set and array mismatch: " + set +
+                     ", " + Arrays.asList( to_int_array_size ),
+                 set.containsAll( Arrays.asList( to_int_array_size ) ) );
+ 
+ 
+         Number[] to_num_array_zero = set.toArray( new Number[0] );
+         assertTrue( "set and array mismatch: " + set +
+                     ", " + Arrays.asList( to_num_array_zero ),
+                 set.containsAll( Arrays.asList( to_num_array_zero ) ) );
+ 
+         Number[] to_num_array_size = set.toArray( new Number[set.size()] );
+         assertTrue( "set and array mismatch: " + set +
+                     ", " + Arrays.asList( to_num_array_size ),
+                 set.containsAll( Arrays.asList( to_num_array_size ) ) );
+     }
+ 
+ 
+     @SuppressWarnings({"MismatchedQueryAndUpdateOfCollection"})
      public void testRehashing() throws Exception {
          Set<Integer> s = new THashSet<Integer>();
***************
*** 187,190 ****
--- 292,296 ----
       * general contract for hashcode on java.lang.Object
       */
+     @SuppressWarnings({"MismatchedQueryAndUpdateOfCollection"})
      public void testSomeBadlyWrittenObject() {
          Set<Object> s = new THashSet<Object>();
***************
*** 227,230 ****
--- 333,447 ----
  
  
+     public void testEquals() {
+         String[] strings = {"hi", "bye", "hello", "goodbye"};
+         Set<String> set = new THashSet<String>();
+         set.addAll( Arrays.asList( strings ) );
+         Set<String> other = new THashSet<String>();
+         other.addAll( Arrays.asList( strings ) );
+ 
+         assertTrue( "sets incorrectly not equal: " + set + ", " + other,
+                 set.equals( other ) );
+ 
+         String[] mismatched = {"heyya", "whassup", "seeya", "blargh"};
+         Set<String> unequal = new THashSet<String>();
+         unequal.addAll( Arrays.asList( mismatched ) );
+ 
+         assertFalse( "sets incorrectly equal: " + set + ", " + unequal,
+                 set.equals( unequal ) );
+ 
+         // Change length, different code branch
+         unequal.add( "whee!" );
+         assertFalse( "sets incorrectly equal: " + set + ", " + unequal,
+                 set.equals( unequal ) );
+     }
+ 
+ 
+     public void testEqualsNonSet() {
+         String[] strings = {"hi", "bye", "hello", "goodbye"};
+         Set<String> set = new THashSet<String>();
+         set.addAll( Arrays.asList( strings ) );
+         List<String> other = new ArrayList<String>();
+         other.addAll( Arrays.asList( strings ) );
+ 
+         assertFalse( "sets incorrectly equals list: " + set + ", " + other,
+                 set.equals( other ) );
+ 
+         Map<String, String> map = new HashMap<String, String>();
+         for ( String string : strings ) {
+             map.put( string, string );
+         }
+         assertFalse( "sets incorrectly equals map: " + set + ", " + map,
+                 set.equals( map ) );
+     }
+ 
+ 
+     public void testHashcode() {
+         String[] strings = {"hi", "bye", "hello", "goodbye"};
+         Set<String> set = new THashSet<String>();
+         set.addAll( Arrays.asList( strings ) );
+         Set<String> other = new THashSet<String>();
+         other.addAll( Arrays.asList( strings ) );
+ 
+         assertTrue( "hashcodes incorrectly not equal: " + set + ", " + other,
+                 set.hashCode() == other.hashCode() );
+ 
+         String[] mismatched = {"heyya", "whassup", "seeya", "blargh"};
+         Set<String> unequal = new THashSet<String>();
+         unequal.addAll( Arrays.asList( mismatched ) );
+ 
+         assertFalse( "hashcodes unlikely equal: " + set + ", " + unequal,
+                 set.hashCode() == unequal.hashCode() );
+     }
+ 
+ 
+     public void testCompact() {
+         int max_size = 10000;
+         int reduced_size = 100;
+ 
+         THashSet<Integer> set = new THashSet<Integer>( max_size, 1.0f );
+         for ( int index = 1; index <= max_size; index++ ) {
+             set.add( Integer.valueOf( index ) );
+         }
+         assertEquals( max_size, set.size() );
+         int max_length = set._set.length;
+ 
+         for ( int index = max_size; index > reduced_size; index-- ) {
+             set.remove( Integer.valueOf( index ) );
+         }
+         assertEquals( reduced_size, set.size() );
+ 
+         set.compact();
+         int compacted_length = set._set.length;
+         assertFalse( max_length + " should != " + compacted_length,
+                 max_length == compacted_length );
+     }
+ 
+ 
+     public void testDisabledAutoCompact() {
+         int max_size = 10000;
+         int reduced_size = 100;
+ 
+         THashSet<Integer> set = new THashSet<Integer>( max_size, 1.0f );
+         set.setAutoCompactionFactor( 0.0f );    // Disable
+         for ( int index = 1; index <= max_size; index++ ) {
+             set.add( Integer.valueOf( index ) );
+         }
+         assertEquals( max_size, set.size() );
+         int max_length = set._set.length;
+ 
+         for ( int index = max_size; index > reduced_size; index-- ) {
+             set.remove( Integer.valueOf( index ) );
+         }
+         assertEquals( reduced_size, set.size() );
+         int uncompacted_length = set._set.length;
+         assertEquals( max_length, uncompacted_length );
+ 
+         set.compact();
+         int compacted_length = set._set.length;
+         assertFalse( uncompacted_length + " should != " + compacted_length,
+                 uncompacted_length == compacted_length );
+     }
+ 
+ 
      // in this junk class, all instances hash to the same
      // address, but some objects claim to be equal where

Index: TPrimitiveHashSetTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/set/hash/Attic/TPrimitiveHashSetTest.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** TPrimitiveHashSetTest.java	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- TPrimitiveHashSetTest.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 4,10 ****
--- 4,15 ----
  
  import java.util.*;
+ import java.io.ByteArrayOutputStream;
+ import java.io.ObjectOutputStream;
+ import java.io.ByteArrayInputStream;
+ import java.io.ObjectInputStream;
  
  import gnu.trove.set.TIntSet;
  import gnu.trove.iterator.TIntIterator;
+ import gnu.trove.procedure.TIntProcedure;
  
  
***************
*** 28,31 ****
--- 33,59 ----
  
  
+     public void testConstructors() throws Exception {
+         TIntSet set = new TIntHashSet();
+         assertNotNull( set );
+ 
+         int[] ints = {1138, 42, 86, 99, 101};
+         set.addAll( ints );
+ 
+         TIntSet copy = new TIntHashSet( set );
+         assertTrue( "set not a copy: " + set + ", " + copy, set.equals( copy ) );
+ 
+         TIntSet another = new TIntHashSet( 20 );
+         another.addAll( ints );
+         assertTrue( "set not equal: " + set + ", " + copy, set.equals( another ) );
+ 
+         another = new TIntHashSet( 2, 1.0f );
+         another.addAll( ints );
+         assertTrue( "set not equal: " + set + ", " + copy, set.equals( another ) );
+ 
+         another = new TIntHashSet( ints );
+         assertTrue( "set not equal: " + set + ", " + copy, set.equals( another ) );
+     }
+ 
+ 
      public void testIsEmpty() throws Exception {
          TIntSet s = new TIntHashSet();
***************
*** 44,50 ****
--- 72,80 ----
          s.add( i );
          assertTrue( "contains failed", s.contains( i ) );
+         assertFalse( "contains failed", s.contains( 1000 ) );
      }
  
  
+     @SuppressWarnings({"ForLoopReplaceableByForEach"})
      public void testContainsAll() throws Exception {
  
***************
*** 78,81 ****
--- 108,164 ----
          assertTrue( "containsAll(int[]) failed: " + set,
                  set.containsAll( ints ) );
+ 
+ 
+         int[] failed = {42, 86, 99, 123456};
+ 
+         TIntSet failed_set = new TIntHashSet();
+         failed_set.addAll( failed );
+ 
+         List<Integer> failed_list = new ArrayList<Integer>();
+         for ( int element : failed ) {
+             failed_list.add( element );
+         }
+ 
+         assertFalse( "containsAll(Collection<?>) failed (false positive): " + set,
+                 set.containsAll( failed_list ) );
+ 
+         assertFalse( "containsAll(TIntSet) failed (false positive): " + set,
+                 set.containsAll( failed_set ) );
+ 
+         assertFalse( "containsAll(int[]) failed (false positive): " + set,
+                 set.containsAll( failed ) );
+     }
+ 
+ 
+     public void testAddAll() throws Exception {
+ 
+         int[] ints = {1138, 42, 13, 86, 99, 101};
+ 
+         TIntSet set;
+ 
+         List<Integer> list = new ArrayList<Integer>();
+         for ( int element : ints ) {
+             list.add( Integer.valueOf( element ) );
+         }
+ 
+         set = new TIntHashSet();
+         assertTrue( "addAll(Collection<?>) failed: " + set, set.addAll( list ) );
+         for ( int element : ints ) {
+             assertTrue( "contains failed: ", set.contains( element ) );
+         }
+ 
+         set = new TIntHashSet();
+         assertTrue( "addAll(int[]) failed: " + set, set.addAll( ints ) );
+         for ( int element : ints ) {
+             assertTrue( "contains failed: ", set.contains( element ) );
+         }
+ 
+         TIntSet test_set = new TIntHashSet();
+         assertTrue( "addAll(TIntSet) failed: " + test_set, test_set.addAll( set ) );
+         for ( int element : ints ) {
+             assertTrue( "contains failed: ", set.contains( element ) );
+         }
+ 
+ 
      }
  
***************
*** 83,87 ****
      public void testRetainAll() throws Exception {
  
!         int[] ints = {1138, 42, 13, 86, 99, 101, };
  
          TIntSet set = new TIntHashSet();
--- 166,170 ----
      public void testRetainAll() throws Exception {
  
!         int[] ints = {1138, 42, 13, 86, 99, 101};
  
          TIntSet set = new TIntHashSet();
***************
*** 91,115 ****
          other.addAll( ints );
  
!         List<Integer> ints_list = new ArrayList<Integer>();
!         for ( int element : ints ) {
!             ints_list.add( element );
          }
  
!         for ( int index = 0; index < ints.length; index++ ) {
!             assertTrue( Integer.valueOf( ints[index] ).toString(),
!                     set.contains( ints[index] ) );
          }
  
!         assertTrue( "containsAll(Collection<?>) failed: " + set,
!                 set.containsAll( ints_list ) );
  
!         assertTrue( "containsAll(TIntSet) failed (same set): " + set,
!                 set.containsAll( set ) );
  
!         assertTrue( "containsAll(TIntSet) failed (other set): " + set,
!                 set.containsAll( other ) );
  
!         assertTrue( "containsAll(int[]) failed: " + set,
!                 set.containsAll( ints ) );
      }
  
--- 174,282 ----
          other.addAll( ints );
  
!         int[] to_retain = {13, 86, 99, 1138};
! 
!         TIntSet retain_set = new TIntHashSet();
!         retain_set.addAll( to_retain );
! 
!         List<Integer> retain_list = new ArrayList<Integer>();
!         for ( int element : to_retain ) {
!             retain_list.add( element );
          }
  
!         assertFalse( "retainAll(TIntSet) failed (same set): " + set,
!                 set.retainAll( set ) );
!         // Contains all the original elements
!         assertTrue( set.toString(), set.containsAll( ints ) );
!         assertTrue( retain_set.toString(), retain_set.containsAll( to_retain ) );
! 
!         assertTrue( "retainAll(Collection<?>) failed: " + set,
!                 set.retainAll( retain_list ) );
!         // Contains just the expected elements
!         assertFalse( set.toString(), set.containsAll( ints ) );
!         assertTrue( set.toString(), set.containsAll( to_retain ) );
!         assertTrue( retain_set.toString(), retain_set.containsAll( to_retain ) );
! 
!         // reset the set.
!         set = new TIntHashSet();
!         set.addAll( ints );
!         assertTrue( "retainAll(TIntSet) failed: " + set,
!                 set.retainAll( retain_set ) );
!         // Contains just the expected elements
!         assertFalse( set.toString(), set.containsAll( ints ) );
!         assertTrue( set.toString(), set.containsAll( to_retain ) );
!         assertTrue( retain_set.toString(), retain_set.containsAll( to_retain ) );
! 
!         // reset the set.
!         set = new TIntHashSet();
!         set.addAll( ints );
!         assertTrue( "retainAll(int[]) failed: " + set,
!                 set.retainAll( to_retain ) );
!         // Contains just the expected elements
!         assertFalse( set.toString(), set.containsAll( ints ) );
!         assertTrue( set.toString(), set.containsAll( to_retain ) );
!         assertTrue( retain_set.toString(), retain_set.containsAll( to_retain ) );
!     }
! 
! 
!     public void testRemoveAll() throws Exception {
! 
!         int[] ints = {1138, 42, 13, 86, 99, 101};
! 
!         TIntSet set = new TIntHashSet();
!         set.addAll( ints );
! 
!         TIntSet other = new TIntHashSet();
!         other.addAll( ints );
! 
!         int[] to_remove = {13, 86, 99, 1138};
! 
!         TIntSet remove_set = new TIntHashSet();
!         remove_set.addAll( to_remove );
! 
!         List<Integer> remove_list = new ArrayList<Integer>();
!         for ( int element : to_remove ) {
!             remove_list.add( element );
          }
  
!         int[] remainder = {42, 101};
  
!         try {
!             assertFalse( "removeAll(TIntSet) failed (same set): " + set,
!                     set.removeAll( set ) );
!             fail( "should have thrown ConcurrentModificationException" );
!         }
!         catch ( ConcurrentModificationException cme ) {
!             // expected exception thrown.
!         }
  
!         // reset the set.
!         set = new TIntHashSet();
!         set.addAll( ints );
!         assertTrue( "removeAll(Collection<?>) failed: " + set,
!                 set.removeAll( remove_list ) );
!         // Contains just the expected elements
!         assertTrue( set.toString(), set.containsAll( remainder ) );
!         assertFalse( set.toString(), set.containsAll( to_remove ) );
!         assertTrue( remove_set.toString(), remove_set.containsAll( to_remove ) );
  
!         // reset the set.
!         set = new TIntHashSet();
!         set.addAll( ints );
!         assertTrue( "removeAll(TIntSet) failed: " + set,
!                 set.removeAll( remove_set ) );
!         // Contains just the expected elements
!         assertTrue( set.toString(), set.containsAll( remainder ) );
!         assertFalse( set.toString(), set.containsAll( to_remove ) );
!         assertTrue( remove_set.toString(), remove_set.containsAll( to_remove ) );
! 
!         // reset the set.
!         set = new TIntHashSet();
!         set.addAll( ints );
!         assertTrue( "removeAll(int[]) failed: " + set,
!                 set.removeAll( to_remove ) );
!         // Contains just the expected elements
!         assertTrue( set.toString(), set.containsAll( remainder ) );
!         assertFalse( set.toString(), set.containsAll( to_remove ) );
!         assertTrue( remove_set.toString(), remove_set.containsAll( to_remove ) );
      }
  
***************
*** 129,132 ****
--- 296,312 ----
          assertTrue( "One was not removed", set.remove( 1 ) );
          assertFalse( "One was not removed", set.contains( 1 ) );
+         assertTrue( "Two was also removed", set.contains( 2 ) );
+     }
+ 
+ 
+     public void testRemoveNonExistant() throws Exception {
+         TIntSet set = new TIntHashSet();
+         set.add( 1 );
+         set.add( 2 );
+         assertTrue( "One was not added", set.contains( 1 ) );
+         assertTrue( "One was not removed", set.remove( 1 ) );
+         assertFalse( "One was not removed", set.contains( 1 ) );
+         assertTrue( "Two was also removed", set.contains( 2 ) );
+         assertFalse( "Three was removed (non-existant)", set.remove( 3 ) );
      }
  
***************
*** 152,169 ****
  
  
-     // TODO: implement after serialzation is implemented
      public void testSerialize() throws Exception {
! //        Set<String> s = new THashSet<String>();
! //        s.addAll( Arrays.asList( new String[]{"one", "two", "three"} ) );
! //        ByteArrayOutputStream baos = new ByteArrayOutputStream();
! //        ObjectOutputStream oos = new ObjectOutputStream( baos );
! //        oos.writeObject( s );
! //
! //        ByteArrayInputStream bais = new ByteArrayInputStream( baos.toByteArray() );
! //        ObjectInputStream ois = new ObjectInputStream( bais );
! //
! //        THashSet s2 = (THashSet) ois.readObject();
! //
! //        assertEquals( s, s2 );
      }
  
--- 332,350 ----
  
  
      public void testSerialize() throws Exception {
!         int[] ints = {1138, 42, 86, 99, 101};
! 
!         TIntSet set = new TIntHashSet();
!         set.addAll( ints );
!         ByteArrayOutputStream baos = new ByteArrayOutputStream();
!         ObjectOutputStream oos = new ObjectOutputStream( baos );
!         oos.writeObject( set );
! 
!         ByteArrayInputStream bias = new ByteArrayInputStream( baos.toByteArray() );
!         ObjectInputStream ois = new ObjectInputStream( bias );
! 
!         TIntSet deserialized = (TIntSet) ois.readObject();
! 
!         assertEquals( set, deserialized );
      }
  
***************
*** 180,190 ****
  
  
!     public void testToArrayWithParams() {
          TIntSet set = new TIntHashSet();
          int[] ints = {42, 1138, 13, 86, 99};
          set.addAll( ints );
          int[] sink = new int[ints.length + 2];
          sink[sink.length - 1] = -1;
          sink[sink.length - 2] = -2;
          int[] res = set.toArray( sink );
          assertEquals( set.getNoEntryValue(), res[set.size()] );
--- 361,394 ----
  
  
!     public void testToArrayMatchesIteratorOrder() {
          TIntSet set = new TIntHashSet();
          int[] ints = {42, 1138, 13, 86, 99};
          set.addAll( ints );
+         int[] toarray_ints = set.toArray();
+ 
+         int[] iter_ints = new int[5];
+         TIntIterator iter = set.iterator();
+ 
+         int index = 0;
+         while ( iter.hasNext() ) {
+             iter_ints[index++] = iter.next();
+         }
+ 
+         assertTrue( Arrays.equals( iter_ints, toarray_ints ) );
+     }
+ 
+ 
+     public void testToArrayWithParams() {
+         int no_entry_value = Integer.MIN_VALUE;
+         TIntSet set = new TIntHashSet( 10, 0.5f, no_entry_value );
+         assertEquals( no_entry_value, set.getNoEntryValue() );
+ 
+         int[] ints = {42, 1138, 13, 86, 99};
+         set.addAll( ints );
+ 
          int[] sink = new int[ints.length + 2];
          sink[sink.length - 1] = -1;
          sink[sink.length - 2] = -2;
+ 
          int[] res = set.toArray( sink );
          assertEquals( set.getNoEntryValue(), res[set.size()] );
***************
*** 200,204 ****
          }
          bogey.add( -1 );
!         bogey.add( 0 );
          assertEquals( bogey, copy );
      }
--- 404,408 ----
          }
          bogey.add( -1 );
!         bogey.add( no_entry_value );
          assertEquals( bogey, copy );
      }
***************
*** 206,213 ****
  
      public void testRehashing() throws Exception {
!         Set<Integer> s = new THashSet<Integer>( 10 );
!         for ( int i = 0; i < 10000; i++ ) {
!             s.add( new Integer( i ) );
          }
      }
  
--- 410,419 ----
  
      public void testRehashing() throws Exception {
!         int size = 10000;
!         TIntSet set = new TIntHashSet( 10 );
!         for ( int i = 0; i < size; i++ ) {
!             set.add( i );
          }
+         assertEquals( set.size(), size );
      }
  
***************
*** 218,228 ****
          set.add( 1 );
          set.add( 2 );
  
          TIntIterator iter = set.iterator();
          while ( iter.hasNext() ) {
              int next = iter.next();
!             assertTrue( next == 1 || next == 2 );
          }
      }
  
  }
--- 424,559 ----
          set.add( 1 );
          set.add( 2 );
+         set.add( 3 );
+         set.add( 4 );
  
          TIntIterator iter = set.iterator();
+         assertTrue( "iterator should have a next item", iter.hasNext() );
+ 
+         int last = -1;
          while ( iter.hasNext() ) {
              int next = iter.next();
!             assertTrue( Integer.valueOf( next ).toString(),
!                     next >= 1 && next <= 4 );
!             assertTrue( Integer.valueOf( next ).toString(), next != last );
!             last = next;
          }
+ 
+         assertFalse( "iterator should not have a next item", iter.hasNext() );
+ 
+         assertTrue( "set should contain 1", set.contains( 1 ) );
+         assertTrue( "set should contain 2", set.contains( 2 ) );
+         assertTrue( "set should contain 3", set.contains( 3 ) );
+         assertTrue( "set should contain 4", set.contains( 4 ) );
+         assertEquals( 4, set.size() );
      }
  
+ 
+     public void testIteratorRemove() {
+ 
+         TIntSet set = new TIntHashSet();
+         set.add( 1 );
+         set.add( 2 );
+         set.add( 3 );
+         set.add( 4 );
+ 
+         TIntIterator iter = set.iterator();
+         assertTrue( "iterator should have a next item", iter.hasNext() );
+ 
+         int last = -1;
+         while ( iter.hasNext() ) {
+             int next = iter.next();
+             assertTrue( next >= 1 && next <= 4 );
+             assertTrue( next != last );
+             last = next;
+ 
+             if ( next == 3 ) {
+                 iter.remove();
+             }
+         }
+ 
+         assertFalse( "iterator should not have a next item", iter.hasNext() );
+ 
+         assertFalse( "set should not contain 3", set.contains( 3 ) );
+         assertTrue( "set should contain 1", set.contains( 1 ) );
+         assertTrue( "set should contain 2", set.contains( 2 ) );
+         assertTrue( "set should contain 4", set.contains( 4 ) );
+         assertEquals( 3, set.size() );
+ 
+     }
+ 
+ 
+     public void testForEach() {
+         TIntSet set = new TIntHashSet( 10, 0.5f );
+         int[] ints = {1138, 42, 86, 99, 101};
+         set.addAll( ints );
+ 
+         class ForEach implements TIntProcedure {
+ 
+             TIntSet built = new TIntHashSet();
+ 
+ 
+             public boolean execute( int value ) {
+                 built.add( value );
+                 return true;
+             }
+ 
+ 
+             TIntSet getBuilt() {
+                 return built;
+             }
+         }
+ 
+         ForEach procedure = new ForEach();
+ 
+         set.forEach( procedure );
+         TIntSet built = procedure.getBuilt();
+ 
+         assertEquals( "inequal sizes: " + set + ", " + built, set.size(), built.size() );
+         assertTrue( "inequal sets: " + set + ", " + built, set.equals( built ) );
+     }
+ 
+ 
+     public void testEquals() {
+         int[] ints = {1138, 42, 86, 99, 101};
+         TIntSet set = new TIntHashSet();
+         set.addAll( ints );
+         TIntSet other = new TIntHashSet();
+         other.addAll( ints );
+ 
+         assertTrue( "sets incorrectly not equal: " + set + ", " + other,
+                 set.equals( other ) );
+ 
+         int[] mismatched = {72, 49, 53, 1024, 999};
+         TIntSet unequal = new TIntHashSet();
+         unequal.addAll( mismatched );
+ 
+         assertFalse( "sets incorrectly equal: " + set + ", " + unequal,
+                 set.equals( unequal ) );
+ 
+         // Change length, different code branch
+         unequal.add( 1 );
+         assertFalse( "sets incorrectly equal: " + set + ", " + unequal,
+                 set.equals( unequal ) );
+     }
+ 
+ 
+     public void testHashcode() {
+         int[] ints = {1138, 42, 86, 99, 101};
+         TIntSet set = new TIntHashSet();
+         set.addAll( ints );
+         TIntSet other = new TIntHashSet();
+         other.addAll( ints );
+ 
+         assertTrue( "hashcodes incorrectly not equal: " + set + ", " + other,
+                 set.hashCode() == other.hashCode() );
+ 
+         int[] mismatched = {72, 49, 53, 1024, 999};
+         TIntSet unequal = new TIntHashSet();
+         unequal.addAll( mismatched );
+ 
+         assertFalse( "hashcodes unlikely equal: " + set + ", " + unequal,
+                 set.hashCode() == unequal.hashCode() );
+     }
+ 
+ 
  }

[Trove4j-commit] CVS: trove/templates/gnu/trove/set _E_Set.template, 1.1.2.2, 1.1.2.3

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/set
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14944/templates/gnu/trove/set

Modified Files:
      Tag: TROVE_3_WORKING
	_E_Set.template 
Log Message:
Implement TPrimitiveHashIterators.  Nearly full text coverage, many bugs found and fixed in process,

Index: _E_Set.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/set/Attic/_E_Set.template,v
retrieving revision 1.1.2.2
retrieving revision 1.1.2.3
diff -C2 -d -r1.1.2.2 -r1.1.2.3
*** _E_Set.template	2 Sep 2009 21:52:33 -0000	1.1.2.2
--- _E_Set.template	4 Sep 2009 12:32:33 -0000	1.1.2.3
***************
*** 27,30 ****
--- 27,31 ----
  
  import gnu.trove.iterator.T#E#Iterator;
+ import gnu.trove.procedure.T#E#Procedure;
  
  import java.util.Collection;
***************
*** 274,277 ****
--- 275,288 ----
  
  
+     /**
+      * Executes <tt>procedure</tt> for each element in the set.
+      *
+      * @param procedure a <code>T#E#Procedure</code> value
+      * @return false if the loop over the set terminated because
+      * the procedure returned false for some value.
+      */
+     public boolean forEach( T#E#Procedure procedure );
+ 
+ 
      // Comparison and hashing
  

[Trove4j-commit] CVS: trove/src/gnu/trove/set/hash THashSet.java, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/set/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14944/src/gnu/trove/set/hash

Modified Files:
      Tag: TROVE_3_WORKING
	THashSet.java 
Log Message:
Implement TPrimitiveHashIterators.  Nearly full text coverage, many bugs found and fixed in process,

Index: THashSet.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/set/hash/Attic/THashSet.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** THashSet.java	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- THashSet.java	4 Sep 2009 12:32:34 -0000	1.1.2.2
***************
*** 1,4 ****
--- 1,6 ----
  ///////////////////////////////////////////////////////////////////////////////
  // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
+ // Copyright (c) 2009, Rob Eden All Rights Reserved.
+ // Copyright (c) 2009, Jeff Randall All Rights Reserved.
  //
  // This library is free software; you can redistribute it and/or
***************
*** 37,44 ****
   * An implementation of the <tt>Set</tt> interface that uses an
   * open-addressed hash table to store its contents.
-  * <p/>
-  * Created: Sat Nov  3 10:38:17 2001
   *
   * @author Eric D. Friedman
   * @version $Id$
   */
--- 39,46 ----
   * An implementation of the <tt>Set</tt> interface that uses an
   * open-addressed hash table to store its contents.
   *
   * @author Eric D. Friedman
+  * @author Rob Eden
+  * @author Jeff Randall
   * @version $Id$
   */
***************
*** 117,120 ****
--- 119,123 ----
  
  
+     @SuppressWarnings({"SimplifiableIfStatement"})
      public boolean equals( Object other ) {
          if ( !( other instanceof Set ) ) {
***************
*** 158,161 ****
--- 161,165 ----
       * @param newCapacity an <code>int</code> value
       */
+     @SuppressWarnings({"unchecked"})
      protected void rehash( int newCapacity ) {
          int oldCapacity = _set.length;
***************
*** 183,186 ****
--- 187,191 ----
       * @return an <code>Object[]</code> value
       */
+     @SuppressWarnings({"unchecked"})
      public Object[] toArray() {
          Object[] result = new Object[size()];
***************
*** 196,199 ****
--- 201,205 ----
       * @return an <code>Object[]</code> value
       */
+     @SuppressWarnings({"unchecked"})
      public <T> T[] toArray( T[] a ) {
          int size = size();
***************
*** 234,237 ****
--- 240,244 ----
       * @return true if the set was modified by the remove operation.
       */
+     @SuppressWarnings({"unchecked"})
      public boolean remove( Object obj ) {
          int index = index( (E) obj );
***************
*** 262,265 ****
--- 269,273 ----
       * @return true if all elements were present in the set.
       */
+     @SuppressWarnings("ForLoopReplaceableByForEach")
      public boolean containsAll( Collection<?> collection ) {
          for ( Iterator i = collection.iterator(); i.hasNext(); ) {
***************
*** 321,330 ****
       * @return true if the set was modified by the retain all operation
       */
      public boolean retainAll( Collection<?> collection ) {
          boolean changed = false;
          int size = size();
!         Iterator it;
! 
!         it = iterator();
          while ( size-- > 0 ) {
              if ( !collection.contains( it.next() ) ) {
--- 329,337 ----
       * @return true if the set was modified by the retain all operation
       */
+     @SuppressWarnings({"SuspiciousMethodCalls"})
      public boolean retainAll( Collection<?> collection ) {
          boolean changed = false;
          int size = size();
!         Iterator<E> it = iterator();
          while ( size-- > 0 ) {
              if ( !collection.contains( it.next() ) ) {
***************
*** 339,343 ****
      public String toString() {
          final StringBuilder buf = new StringBuilder( "{" );
!         forEach( new TObjectProcedure() {
              private boolean first = true;
  
--- 346,350 ----
      public String toString() {
          final StringBuilder buf = new StringBuilder( "{" );
!         forEach( new TObjectProcedure<E>() {
              private boolean first = true;
  
***************
*** 370,381 ****
  
          // ENTRIES
!         // TODO: implement
! //        SerializationProcedure writeProcedure = new SerializationProcedure( out );
! //        if ( !forEach( writeProcedure ) ) {
! //            throw writeProcedure.exception;
! //        }
      }
  
  
      public void readExternal( ObjectInput in )
              throws IOException, ClassNotFoundException {
--- 377,389 ----
  
          // ENTRIES
!         for ( int i = _set.length; i-- > 0; ) {
!             if ( _set[i] != REMOVED && _set[i] != FREE ) {
!                 out.writeObject( _set[i] );
!             }
!         }
      }
  
  
+     @SuppressWarnings({"unchecked"})
      public void readExternal( ObjectInput in )
              throws IOException, ClassNotFoundException {
***************
*** 394,402 ****
  
          // ENTRIES
!         // TODO: implement
! //        while ( size-- > 0 ) {
! //            E val = (E) in.readObject();
! //            add( val );
! //        }
      }
  } // THashSet
--- 402,409 ----
  
          // ENTRIES
!         while ( size-- > 0 ) {
!             E val = (E) in.readObject();
!             add( val );
!         }
      }
  } // THashSet

[Trove4j-commit] CVS: trove/src/gnu/trove/impl/hash TObjectHash.java, 1.1.2.1, 1.1.2.2 TPrimitiveHash.java, 1.1.2.1, 1.1.2.2 THash.java, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/impl/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14944/src/gnu/trove/impl/hash

Modified Files:
      Tag: TROVE_3_WORKING
	TObjectHash.java TPrimitiveHash.java THash.java 
Log Message:
Implement TPrimitiveHashIterators.  Nearly full text coverage, many bugs found and fixed in process,

Index: TObjectHash.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/impl/hash/Attic/TObjectHash.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** TObjectHash.java	2 Sep 2009 21:52:32 -0000	1.1.2.1
--- TObjectHash.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 37,40 ****
--- 37,42 ----
   *
   * @author Eric D. Friedman
+  * @author Rob Eden
+  * @author Jeff Randall
   * @version $Id$
   */
***************
*** 118,121 ****
--- 120,124 ----
       *         the procedure returned false for some value.
       */
+     @SuppressWarnings({"unchecked"})
      public boolean forEach( TObjectProcedure<T> procedure ) {
          Object[] set = _set;
***************
*** 137,140 ****
--- 140,144 ----
       * @return a <code>boolean</code> value
       */
+     @SuppressWarnings({"unchecked"})
      public boolean contains( Object obj ) {
          return index( (T) obj ) >= 0;
***************
*** 254,285 ****
  
      /**
-      * This is the default implementation of TObjectHashingStrategy:
-      * it delegates hashing to the Object's hashCode method.
-      *
-      * @param o for which the hashcode is to be computed
-      * @return the hashCode
-      * @see Object#hashCode()
-      */
-     public final int computeHashCode( T o ) {
-         return o == null ? 0 : o.hashCode();
-     }
- 
- 
-     /**
-      * This is the default implementation of TObjectHashingStrategy:
-      * it delegates equality comparisons to the first parameter's
-      * equals() method.
-      *
-      * @param o1 an <code>Object</code> value
-      * @param o2 an <code>Object</code> value
-      * @return true if the objects are equal
-      * @see Object#equals(Object)
-      */
-     public final boolean equals( T o1, T o2 ) {
-         return o1 == null ? o2 == null : o1.equals( o2 );
-     }
- 
- 
-     /**
       * Convenience methods for subclasses to use in throwing exceptions about
       * badly behaved user objects employed as keys.  We have to throw an
--- 258,261 ----
***************
*** 315,319 ****
          out.writeByte( 0 );
  
-         // TODO: implement
      }
  
--- 291,294 ----
***************
*** 328,332 ****
          in.readByte();
  
-         // TODO: implement
      }
  } // TObjectHash
--- 303,306 ----

Index: TPrimitiveHash.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/impl/hash/Attic/TPrimitiveHash.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** TPrimitiveHash.java	2 Sep 2009 21:52:32 -0000	1.1.2.1
--- TPrimitiveHash.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 42,54 ****
       * FREE, FULL, or REMOVED
       */
!     protected transient byte[] _states;
  
      /* constants used for state flags */
  
      /** flag indicating that a slot in the hashtable is available */
!     protected static final byte FREE = 0;
  
      /** flag indicating that a slot in the hashtable is occupied */
!     protected static final byte FULL = 1;
  
      /**
--- 42,54 ----
       * FREE, FULL, or REMOVED
       */
!     public transient byte[] _states;
  
      /* constants used for state flags */
  
      /** flag indicating that a slot in the hashtable is available */
!     public static final byte FREE = 0;
  
      /** flag indicating that a slot in the hashtable is occupied */
!     public static final byte FULL = 1;
  
      /**
***************
*** 56,60 ****
       * was deleted
       */
!     protected static final byte REMOVED = 2;
  
  
--- 56,60 ----
       * was deleted
       */
!     public static final byte REMOVED = 2;
  
  

Index: THash.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/impl/hash/Attic/THash.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** THash.java	2 Sep 2009 21:52:32 -0000	1.1.2.1
--- THash.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 259,263 ****
       * @param index an <code>int</code> value
       */
-     @SuppressWarnings({"UnusedDeclaration"})
      public void removeAt( int index ) {
          _size--;
--- 259,262 ----
***************
*** 422,426 ****
          _autoCompactionFactor = in.readFloat();
  
- 
          // If we change the laod factor from the default, re-setup
          if ( old_factor != _loadFactor ) {
--- 421,424 ----

[Trove4j-commit] CVS: trove/test/gnu/trove/list/array - New directory

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/test/gnu/trove/list/array
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv24233/test/gnu/trove/list/array

Log Message:
Directory /cvsroot/trove4j/trove/test/gnu/trove/list/array added to the repository

[Trove4j-commit] CVS: trove/templates/gnu/trove/iterator/hash - New directory

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/iterator/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv32680/templates/gnu/trove/iterator/hash

Log Message:
Directory /cvsroot/trove4j/trove/templates/gnu/trove/iterator/hash added to the repository

[Trove4j-commit] CVS: trove/test/gnu/trove/impl/hash THashTest.java, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/test/gnu/trove/impl/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14818/test/gnu/trove/impl/hash

Modified Files:
      Tag: TROVE_3_WORKING
	THashTest.java 
Log Message:
Cleanup warnings, generify.

Index: THashTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/impl/hash/Attic/THashTest.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** THashTest.java	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- THashTest.java	3 Sep 2009 16:17:45 -0000	1.1.2.2
***************
*** 7,15 ****
  
  /**
!  * Created by IntelliJ IDEA.
!  * User: randall
!  * Date: Sep 2, 2009
!  * Time: 2:52:23 PM
!  * To change this template use File | Settings | File Templates.
   */
  public class THashTest extends TestCase {
--- 7,11 ----
  
  /**
!  * tests that need access to internals of THash or THashSet
   */
  public class THashTest extends TestCase {
***************
*** 30,35 ****
  
  
      public void testNormalLoad() throws Exception {
!         THashSet set = new THashSet( 11, 0.5f );
          assertEquals( set._maxSize, 11 );
          for ( int i = 0; i < 12; i++ ) {
--- 26,32 ----
  
  
+     @SuppressWarnings({"MismatchedQueryAndUpdateOfCollection"})
      public void testNormalLoad() throws Exception {
!         THashSet<Integer> set = new THashSet<Integer>( 11, 0.5f );
          assertEquals( set._maxSize, 11 );
          for ( int i = 0; i < 12; i++ ) {
***************
*** 40,45 ****
  
  
      public void testMaxLoad() throws Exception {
!         THashSet set = new THashSet( 11, 1.0f );
          assertEquals( 10, set._maxSize );
          for ( int i = 0; i < 12; i++ ) {
--- 37,43 ----
  
  
+     @SuppressWarnings({"MismatchedQueryAndUpdateOfCollection"})
      public void testMaxLoad() throws Exception {
!         THashSet<Integer> set = new THashSet<Integer>( 11, 1.0f );
          assertEquals( 10, set._maxSize );
          for ( int i = 0; i < 12; i++ ) {
***************
*** 71,75 ****
          assertEquals( f2, set._set[idx] );
          set.remove( f2 );
!         assertEquals( set.REMOVED, set._set[idx] );
          assertEquals( idx, set.insertionIndex( f3 ) );
          set.add( f3 );
--- 69,73 ----
          assertEquals( f2, set._set[idx] );
          set.remove( f2 );
!         assertEquals( THashSet.REMOVED, set._set[idx] );
          assertEquals( idx, set.insertionIndex( f3 ) );
          set.add( f3 );

[Trove4j-commit] CVS: trove/test/gnu/trove/list/linked TLinkedListTest.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/test/gnu/trove/list/linked
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14660/test/gnu/trove/list/linked

Added Files:
      Tag: TROVE_3_WORKING
	TLinkedListTest.java 
Log Message:
Implementation of TLinkedList, TLinkable, and test.

--- NEW FILE: TLinkedListTest.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.list.linked;

import junit.framework.*;

import java.io.*;
import java.util.*;

import gnu.trove.list.TLinkable;
import gnu.trove.procedure.TObjectProcedure;



/**
 * Created: Sat Nov 10 15:57:07 2001
 *
 * @author Eric D. Friedman
 * @author Rob Eden
 * @author Jeff Randall
 * 
 * @version $Id: TLinkedListTest.java,v 1.1.2.1 2009/09/03 16:16:36 upholderoftruth Exp $
 */

@SuppressWarnings({"ForLoopReplaceableByForEach", "ManualArrayToCollectionCopy"})
public class TLinkedListTest extends TestCase {

    protected TLinkedList<Data> list;


    public TLinkedListTest( String name ) {
        super( name );
    }


    public void setUp() throws Exception {
        list = new TLinkedList<Data>();
    }


    public void tearDown() throws Exception {
        list = null;
    }


    public void testAdd() throws Exception {
        Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 )};
        for ( int i = 0; i < data.length; i++ ) {
            list.add( data[i] );
        }
        assertEquals( 3, list.size() );
    }


    public void testInsert() throws Exception {
        Data[] data = {new Data( 2 ), new Data( 4 ), new Data( 6 )};
        for ( int i = 0; i < data.length; i++ ) {
            list.add( data[i] );
        }

        list.insert( 0, new Data( 1 ) );
        list.insert( 2, new Data( 3 ) );
        list.insert( 4, new Data( 5 ) );
        list.insert( list.size(), new Data( 7 ) );

        assertEquals( 7, list.size() );
        for ( int i = 0; i < list.size(); i++ ) {
            assertEquals( i + 1, list.get( i )._val );
        }
    }


    public void testNextIterator() throws Exception {
        Data[] data = new Data[100];
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = new Data( i );
            list.add( data[i] );
        }

        int count = 0;
        for ( Iterator i = list.iterator(); i.hasNext(); ) {
            assertEquals( data[count++], i.next() );
        }
        assertEquals( data.length, count );

        count = 4;
        for ( Iterator i = list.listIterator( 4 ); i.hasNext(); ) {
            assertEquals( data[count++], i.next() );
        }
        assertEquals( data.length, count );
    }


    public void testPreviousIterator() throws Exception {
        Data[] data = new Data[100];
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = new Data( i );
            list.add( data[i] );
        }

        int count = 100;
        for ( ListIterator i = list.listIterator( list.size() );
              i.hasPrevious(); ) {
            assertEquals( data[--count], i.previous() );
        }
        assertEquals( 0, count );

        count = 5;
        for ( ListIterator i = list.listIterator( count ); i.hasPrevious(); ) {
            assertEquals( data[--count], i.previous() );
        }
        assertEquals( 0, count );
    }


    public void testIteratorSet() throws Exception {
        Data[] data = new Data[100];
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = new Data( i );
            list.add( data[i] );
        }

        ListIterator<Data> i;

        i = list.listIterator( 5 );
        i.next();
        Data d = new Data( 999 );
        i.set( d );
        assertEquals( d, list.get( 5 ) );
    }


    public void testRemoveOnlyElementInList() throws Exception {
        Data d = new Data( 0 );
        list.add( d );
        ListIterator i = list.listIterator();
        assertTrue( i.hasNext() );
        assertEquals( d, i.next() );
        i.remove();
        assertTrue( !i.hasNext() );
        assertTrue( !i.hasPrevious() );
        assertEquals( 0, list.size() );
    }


    public void testRemovePrevious() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator i = list.listIterator( list.size() );
        i.previous();
        i.previous();
        i.remove();
        assertEquals( 2, list.size() );
        assertTrue( i.hasPrevious() );
        assertEquals( d[0], i.previous() );
        assertTrue( !i.hasPrevious() );
        assertTrue( i.hasNext() );
        assertEquals( d[0], i.next() );
        assertTrue( i.hasNext() );
        assertEquals( d[2], i.next() );
        assertTrue( !i.hasNext() );
        assertTrue( i.hasPrevious() );
        assertEquals( 2, list.size() );
    }


    public void testRemoveLast() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator i = list.listIterator( list.size() );
        i.previous();
        i.remove();
        assertEquals( 2, list.size() );
        assertTrue( i.hasPrevious() );
        assertTrue( !i.hasNext() );
    }


    public void testRemoveFirst() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator i = list.listIterator( 0 );
        i.next();
        i.remove();
        assertEquals( 2, list.size() );
        assertTrue( !i.hasPrevious() );
        assertTrue( i.hasNext() );
    }


    public void testRemoveNext() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator i = list.listIterator();
        assertTrue( i.hasNext() );
        i.next();
        assertTrue( i.hasNext() );
        assertTrue( i.hasPrevious() );
        i.remove();
        assertEquals( 2, list.size() );
        assertTrue( !i.hasPrevious() );
        assertTrue( i.hasNext() );
        assertEquals( d[1], i.next() );
        assertTrue( i.hasNext() );
        assertEquals( d[2], i.next() );
        assertTrue( i.hasPrevious() );
        assertTrue( !i.hasNext() );
    }


    public void testRemoveThrowsAfterAdd() throws Exception {
        Data d = new Data( 0 );
        list.add( d );
        ListIterator i = list.listIterator();
        boolean didThrow = false;

        try {
            i.remove();
        }
        catch ( IllegalStateException e ) {
            didThrow = true;
        } // end of try-catch
        assertTrue( didThrow );
    }


    public void testRemoveThrowsWithoutPrevious() throws Exception {
        Data d = new Data( 0 );
        list.add( d );
        ListIterator i = list.listIterator( list.size() );
        boolean didThrow = false;

        assertTrue( i.hasPrevious() );
        try {
            i.remove();
        }
        catch ( IllegalStateException e ) {
            didThrow = true;
        } // end of try-catch
        assertTrue( didThrow );
    }


    public void testRemoveThrowsWithoutNext() throws Exception {
        Data d = new Data( 0 );
        list.add( d );
        ListIterator i = list.listIterator();
        boolean didThrow = false;

        assertTrue( i.hasNext() );
        try {
            i.remove();
        }
        catch ( IllegalStateException e ) {
            didThrow = true;
        } // end of try-catch
        assertTrue( didThrow );
    }


    public void testIteratorAddFront() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator<Data> i = list.listIterator();
        Data d1 = new Data( 5 );
        assertTrue( !i.hasPrevious() );
        i.add( d1 );
        assertTrue( i.hasPrevious() );
        assertEquals( d1, i.previous() );
        assertEquals( d1, i.next() );
        assertEquals( d[0], i.next() );
        assertEquals( d1, list.get( 0 ) );
    }


    public void testIteratorAddBack() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator<Data> i = list.listIterator( list.size() );
        Data d1 = new Data( 5 );
        assertEquals( 3, list.size() );
        assertTrue( i.hasPrevious() );
        assertTrue( !i.hasNext() );
        i.add( d1 );
        assertTrue( i.hasPrevious() );
        assertTrue( !i.hasNext() );
        assertEquals( 4, list.size() );

        assertEquals( d1, i.previous() );
        assertEquals( d1, i.next() );
        assertEquals( d1, list.get( 3 ) );
    }


    public void testIteratorAddMiddle() throws Exception {
        Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
        list.addAll( Arrays.asList( d ) );

        ListIterator<Data> i = list.listIterator( 1 );
        Data d1 = new Data( 5 );
        assertEquals( 3, list.size() );
        assertTrue( i.hasPrevious() );
        assertTrue( i.hasNext() );
        i.add( d1 );
        assertTrue( i.hasPrevious() );
        assertTrue( i.hasNext() );
        assertEquals( 4, list.size() );

        assertEquals( d1, i.previous() );
        assertEquals( d1, i.next() );
        assertEquals( d1, list.get( 1 ) );
    }


    public void testIteratorSetSingleElementList() throws Exception {
        Data d1 = new Data( 5 );
        Data d2 = new Data( 4 );
        list.add( d1 );

        ListIterator<Data> i = list.listIterator( 0 );
        i.next();
        i.set( d2 );
        assertEquals( 1, list.size() );
        assertTrue( !i.hasNext() );
        assertTrue( i.hasPrevious() );
        assertEquals( d2, i.previous() );
        assertTrue( i.hasNext() );
        assertTrue( !i.hasPrevious() );
        assertEquals( d2, i.next() );
    }


    public void testIteratorAddEmptyList() throws Exception {
        ListIterator<Data> i = list.listIterator();
        Data d1 = new Data( 5 );
        assertTrue( !i.hasPrevious() );
        assertTrue( !i.hasNext() );
        i.add( d1 );
        assertTrue( i.hasPrevious() );
        assertTrue( !i.hasNext() );
        assertEquals( d1, i.previous() );
        assertEquals( d1, i.next() );
        assertEquals( d1, list.get( 0 ) );
    }


    public void testIteratorRemoveOnNext() throws Exception {
        Data[] data = new Data[100];
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = new Data( i );
            list.add( data[i] );
        }

        ListIterator i;

        i = list.listIterator( 5 );
        i.next();
        i.remove();
        Data d = new Data( 6 );
        assertEquals( d, list.get( 5 ) );
    }


    public void testSerialize() throws Exception {
        TLinkedList<Data> list1 = new TLinkedList<Data>();
        Data[] data = new Data[100];
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = new Data( i );
            list1.add( data[i] );
        }

        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream( baos );
        oos.writeObject( list1 );

        ByteArrayInputStream bais = new ByteArrayInputStream( baos.toByteArray() );
        ObjectInputStream ois = new ObjectInputStream( bais );

        TLinkedList list2 = (TLinkedList) ois.readObject();
        assertEquals( list1, list2 );
    }


    public void testForEach() throws Exception {
        list.add( new Data( 0 ) );
        list.add( new Data( 1 ) );
        list.add( new Data( 2 ) );
        list.add( new Data( 3 ) );
        list.add( new Data( 4 ) );

        // test exiting early
        boolean processed_full_list = list.forEachValue( new TObjectProcedure<Data>() {
            public boolean execute( Data object ) {
                if ( object._val == 2 ) {
                    return false;
                }

                object._val++;

                return true;
            }
        } );
        assertFalse( processed_full_list );

        assertEquals( 1, list.get( 0 )._val );
        assertEquals( 2, list.get( 1 )._val );
        assertEquals( 2, list.get( 2 )._val );
        assertEquals( 3, list.get( 3 )._val );
        assertEquals( 4, list.get( 4 )._val );

        // test full list processing
        processed_full_list = list.forEachValue( new TObjectProcedure<Data>() {
            public boolean execute( Data object ) {
                object._val++;
                return true;
            }
        } );
        assertTrue( processed_full_list );

        assertEquals( 2, list.get( 0 )._val );
        assertEquals( 3, list.get( 1 )._val );
        assertEquals( 3, list.get( 2 )._val );
        assertEquals( 4, list.get( 3 )._val );
        assertEquals( 5, list.get( 4 )._val );
    }


    public void testAddBefore() {
        Data one = new Data( 1 );
        Data three = new Data( 3 );
        Data four = new Data( 4 );
        Data five = new Data( 5 );

        list.add( one );
        list.add( three );
        list.add( four );
        list.add( five );

        list.addBefore( one, new Data( 0 ) );
        list.addBefore( three, new Data( 2 ) );
        list.addBefore( null, new Data( 6 ) );

        System.out.println( "List: " + list );

        // Iterate forward
        int value = -1;
        Data cur = list.getFirst();
        while ( cur != null ) {
            assertEquals( value + 1, cur._val );
            value = cur._val;

            cur = cur.getNext();
        }

        assertEquals( 6, value );

        // Iterate backward
        value = 7;
        cur = list.getLast();
        while ( cur != null ) {
            assertEquals( value - 1, cur._val );
            value = cur._val;

            cur = cur.getPrevious();
        }

        assertEquals( 0, value );
    }


    public void testAddAfter() {
        Data one = new Data( 1 );
        Data three = new Data( 3 );
        Data five = new Data( 5 );

        list.add( one );
        list.add( three );
        list.add( five );

        list.addAfter( one, new Data( 2 ) );
        list.addAfter( three, new Data( 4 ) );
        list.addAfter( five, new Data( 6 ) );
        list.addAfter( null, new Data( 0 ) );

        System.out.println( "List: " + list );

        // Iterate forward
        int value = -1;
        Data cur = list.getFirst();
        while ( cur != null ) {
            assertEquals( value + 1, cur._val );
            value = cur._val;

            cur = cur.getNext();
        }

        assertEquals( 6, value );

        // Iterate backward
        value = 7;
        cur = list.getLast();
        while ( cur != null ) {
            System.out.println( "Itr back: " + cur._val );
            assertEquals( value - 1, cur._val );
            value = cur._val;

            cur = cur.getPrevious();
        }

        assertEquals( 0, value );
    }


    public void testMultipleRemove() {
        Data one = new Data( 1 );
        Data two = new Data( 2 );
        Data three = new Data( 3 );

        list.add( one );
        list.add( two );
        list.add( three );

        list.remove( one );

        assertEquals( 2, list.size() );
        assertEquals( new Data( 2 ), list.get( 0 ) );
        assertEquals( new Data( 3 ), list.get( 1 ) );

        list.remove( one );

        assertEquals( 2, list.size() );
        assertEquals( new Data( 2 ), list.get( 0 ) );
        assertEquals( new Data( 3 ), list.get( 1 ) );

        list.remove( one );

        assertEquals( 2, list.size() );
        assertEquals( new Data( 2 ), list.get( 0 ) );
        assertEquals( new Data( 3 ), list.get( 1 ) );

        list.remove( one );

        assertEquals( 2, list.size() );
        assertEquals( new Data( 2 ), list.get( 0 ) );
        assertEquals( new Data( 3 ), list.get( 1 ) );

        list.remove( one );

        assertEquals( 2, list.size() );
        assertEquals( new Data( 2 ), list.get( 0 ) );
        assertEquals( new Data( 3 ), list.get( 1 ) );
    }


    public void testRemoveFirstAll() {
        list.add( new Data( 1 ) );
        list.add( new Data( 2 ) );
        list.add( new Data( 3 ) );
        list.add( new Data( 4 ) );

        int expected = 1;
        Data data;
        while ( ( data = list.removeFirst() ) != null ) {
            assertEquals( expected, data._val );
            expected++;
        }
        assertTrue( list.isEmpty() );
    }


    public void testRemoveLastAll() {
        list.add( new Data( 1 ) );
        list.add( new Data( 2 ) );
        list.add( new Data( 3 ) );
        list.add( new Data( 4 ) );

        int expected = 4;
        Data data;
        while ( ( data = list.removeLast() ) != null ) {
            assertEquals( expected, data._val );
            expected--;
        }
        assertTrue( list.isEmpty() );
    }


    public void testPastIndexGet() {
        try {
            list.get( 0 );
            fail( "Shouldn't have allowed get of index 0" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // this is good
        }

        try {
            list.get( 1 );
            fail( "Shouldn't have allowed get of index 1" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // this is good
        }

        list.add( new Data( 1 ) );
        list.get( 0 );

        try {
            list.get( 1 );
            fail( "Shouldn't have allowed get of index 1" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // this is good
        }
    }


    static class Data implements TLinkable<Data> {

        protected int _val;


        public Data( int val ) {
            _val = val;
        }


        protected TLinkable<Data> _next;


        // NOTE: use covariant overriding
        /**
         * Get the value of next.
         *
         * @return value of next.
         */
        public Data getNext() {
            return (Data) _next;
        }


        /**
         * Set the value of next.
         *
         * @param next value to assign to next.
         */
        public void setNext( TLinkable<Data> next ) {
            this._next = next;
        }


        protected TLinkable<Data> _previous;


        // NOTE: use covariant overriding
        /**
         * Get the value of previous.
         *
         * @return value of previous.
         */
        public Data getPrevious() {
            return (Data) _previous;
        }


        /**
         * Set the value of previous.
         *
         * @param previous value to assign to previous.
         */
        public void setPrevious( TLinkable<Data> previous ) {
            this._previous = previous;
        }


        public String toString() {
            return "" + _val;
        }


        public boolean equals( Object o ) {
            if ( ! ( o instanceof Data ) )
                return false;
            
            Data that = (Data) o;
            return this._val == that._val;
        }
    }

} // TLinkedListTests

[Trove4j-commit] CVS: trove/src/gnu/trove/list TLinkable.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/list
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14660/src/gnu/trove/list

Added Files:
      Tag: TROVE_3_WORKING
	TLinkable.java 
Log Message:
Implementation of TLinkedList, TLinkable, and test.

--- NEW FILE: TLinkable.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.list;

import java.io.Serializable;



/**
 * Interface for Objects which can be inserted into a TLinkedList.
 *
 * @author Eric D. Friedman
 * @version $Id: TLinkable.java,v 1.1.2.1 2009/09/03 16:16:35 upholderoftruth Exp $
 * @see gnu.trove.list.linked.TLinkedList
 */

public interface TLinkable<T extends TLinkable> extends Serializable {

    /**
     * Returns the linked list node after this one.
     *
     * @return a <code>TLinkable</code> value
     */
    public TLinkable<T> getNext();


    /**
     * Returns the linked list node before this one.
     *
     * @return a <code>TLinkable</code> value
     */
    public TLinkable<T> getPrevious();


    /**
     * Sets the linked list node after this one.
     *
     * @param linkable a <code>TLinkable</code> value
     */
    public void setNext( TLinkable<T> linkable );


    /**
     * Sets the linked list node before this one.
     *
     * @param linkable a <code>TLinkable</code> value
     */
    public void setPrevious( TLinkable<T> linkable );
}// TLinkable

[Trove4j-commit] CVS: trove/src/gnu/trove/list/linked TLinkedList.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/list/linked
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14660/src/gnu/trove/list/linked

Added Files:
      Tag: TROVE_3_WORKING
	TLinkedList.java 
Log Message:
Implementation of TLinkedList, TLinkable, and test.

--- NEW FILE: TLinkedList.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////


package gnu.trove.list.linked;

import gnu.trove.list.TLinkable;
import gnu.trove.procedure.TObjectProcedure;

import java.io.*;
import java.util.AbstractSequentialList;
import java.util.ListIterator;
import java.util.NoSuchElementException;



/**
 * <p>A LinkedList implementation which holds instances of type
 * <tt>TLinkable</tt>.
 * <p/>
 * Using this implementation allows you to get java.util.LinkedList
 * behavior (a doubly linked list, with Iterators that support insert
 * and delete operations) without incurring the overhead of creating
 * <tt>Node</tt> wrapper objects for every element in your list.
 * <p/>
 * The requirement to achieve this time/space gain is that the
 * Objects stored in the List implement the <tt>TLinkable</tt>
 * interface.
 * <p/>
 * The limitations are: <ul>
 * <li>the same object cannot be put into more than one list at the same time.
 * <li>the same object cannot be put into the same list more than once at the same time.
 * <li>objects must only be removed from list they are in.  That is,
 * if you have an object A and lists l1 and l2, you must ensure that
 * you invoke List.remove(A) on the correct list.
 * <li> It is also forbidden to invoke List.remove() with an unaffiliated
 * TLinkable (one that belongs to no list): this will destroy the list
 * you invoke it on.
 * </ul>
 *
 * @author Eric D. Friedman
 * @author Rob Eden
 * @author Jeff Randall
 * @version $Id: TLinkedList.java,v 1.1.2.1 2009/09/03 16:16:36 upholderoftruth Exp $
 * @see gnu.trove.list.TLinkable
 */


public class TLinkedList<T extends TLinkable<T>> extends AbstractSequentialList<T>
        implements Externalizable {

    static final long serialVersionUID = 1L;


    /** the head of the list */
    protected T _head;
    /** the tail of the list */
    protected T _tail;
    /** the number of elements in the list */
    protected int _size = 0;


    /** Creates a new <code>TLinkedList</code> instance. */
    public TLinkedList() {
        super();
    }


    /**
     * Returns an iterator positioned at <tt>index</tt>.  Assuming
     * that the list has a value at that index, calling next() will
     * retrieve and advance the iterator.  Assuming that there is a
     * value before <tt>index</tt> in the list, calling previous()
     * will retrieve it (the value at index - 1) and move the iterator
     * to that position.  So, iterating from front to back starts at
     * 0; iterating from back to front starts at <tt>size()</tt>.
     *
     * @param index an <code>int</code> value
     * @return a <code>ListIterator</code> value
     */
    public ListIterator<T> listIterator( int index ) {
        return new IteratorImpl( index );
    }


    /**
     * Returns the number of elements in the list.
     *
     * @return an <code>int</code> value
     */
    public int size() {
        return _size;
    }


    /**
     * Inserts <tt>linkable</tt> at index <tt>index</tt> in the list.
     * All values > index are shifted over one position to accommodate
     * the new addition.
     *
     * @param index    an <code>int</code> value
     * @param linkable an object of type TLinkable
     */
    public void add( int index, T linkable ) {
        if ( index < 0 || index > size() ) {
            throw new IndexOutOfBoundsException( "index:" + index );
        }
        insert( index, linkable );
    }


    /**
     * Appends <tt>linkable</tt> to the end of the list.
     *
     * @param linkable an object of type TLinkable
     * @return always true
     */
    public boolean add( T linkable ) {
        insert( _size, linkable );
        return true;
    }


    /**
     * Inserts <tt>linkable</tt> at the head of the list.
     *
     * @param linkable an object of type TLinkable
     */
    public void addFirst( T linkable ) {
        insert( 0, linkable );
    }


    /**
     * Adds <tt>linkable</tt> to the end of the list.
     *
     * @param linkable an object of type TLinkable
     */
    public void addLast( T linkable ) {
        insert( size(), linkable );
    }


    /** Empties the list. */
    public void clear() {
        if ( null != _head ) {
            for ( TLinkable<T> link = _head.getNext();
                  link != null;
                  link = link.getNext() ) {
                TLinkable<T> prev = link.getPrevious();
                prev.setNext( null );
                link.setPrevious( null );
            }
            _head = _tail = null;
        }
        _size = 0;
    }


    /**
     * Copies the list's contents into a native array.  This will be a
     * shallow copy: the Tlinkable instances in the Object[] array
     * have links to one another: changing those will put this list
     * into an unpredictable state.  Holding a reference to one
     * element in the list will prevent the others from being garbage
     * collected unless you clear the next/previous links.  <b>Caveat
     * programmer!</b>
     *
     * @return an <code>Object[]</code> value
     */
    public Object[] toArray() {
        Object[] o = new Object[_size];
        int i = 0;
        for ( TLinkable link = _head; link != null; link = link.getNext() ) {
            o[i++] = link;
        }
        return o;
    }


    /**
     * Copies the list to a native array, destroying the next/previous
     * links as the copy is made.  This list will be emptied after the
     * copy (as if clear() had been invoked).  The Object[] array
     * returned will contain TLinkables that do <b>not</b> hold
     * references to one another and so are less likely to be the
     * cause of memory leaks.
     *
     * @return an <code>Object[]</code> value
     */
    public Object[] toUnlinkedArray() {
        Object[] o = new Object[_size];
        int i = 0;
        for ( TLinkable<T> link = _head, tmp; link != null; i++ ) {
            o[i] = link;
            tmp = link;
            link = link.getNext();
            tmp.setNext( null ); // clear the links
            tmp.setPrevious( null );
        }
        _size = 0;              // clear the list
        _head = _tail = null;
        return o;
    }


    /**
     * A linear search for <tt>o</tt> in the list.
     *
     * @param o an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    public boolean contains( Object o ) {
        for ( TLinkable<T> link = _head; link != null; link = link.getNext() ) {
            if ( o.equals( link ) ) {
                return true;
            }
        }
        return false;
    }


    /** {@inheritDoc} */
    @Override
    @SuppressWarnings({"unchecked"})
    public T get( int index ) {
        // Blow out for bogus values
        if ( index < 0 || index >= _size ) {
            throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + _size );
        }

        // Determine if it's better to get there from the front or the back
        if ( index > ( _size >> 1 ) ) {
            int position = _size - 1;
            T node = _tail;

            while ( position > index ) {
                node = (T) node.getPrevious();
                position--;
            }

            return node;
        } else {
            int position = 0;
            T node = _head;

            while ( position < index ) {
                node = (T) node.getNext();
                position++;
            }

            return node;
        }
    }


    /**
     * Returns the head of the list
     *
     * @return an <code>Object</code> value
     */
    public T getFirst() {
        return _head;
    }


    /**
     * Returns the tail of the list.
     *
     * @return an <code>Object</code> value
     */
    public T getLast() {
        return _tail;
    }


    /**
     * Return the node following the given node. This method exists for two reasons:
     * <ol>
     * <li>It's really not recommended that the methods implemented by TLinkable be
     * called directly since they're used internally by this class.</li>
     * <li>This solves problems arising from generics when working with the linked
     * objects directly.</li>
     * </ol>
     * <p/>
     * NOTE: this should only be used with nodes contained in the list. The results are
     * undefined with anything else.
     *
     * @param current The current node
     * @return the node after the current node
     */
    @SuppressWarnings({"unchecked"})
    public T getNext( T current ) {
        return (T) current.getNext();
    }


    /**
     * Return the node preceding the given node. This method exists for two reasons:
     * <ol>
     * <li>It's really not recommended that the methods implemented by TLinkable be
     * called directly since they're used internally by this class.</li>
     * <li>This solves problems arising from generics when working with the linked
     * objects directly.</li>
     * </ol>
     * <p/>
     * NOTE: this should only be used with nodes contained in the list. The results are
     * undefined with anything else.
     *
     * @param current The current node
     * @return the node after the current node
     */
    @SuppressWarnings({"unchecked"})
    public T getPrevious( T current ) {
        return (T) current.getPrevious();
    }


    /**
     * Remove and return the first element in the list.
     *
     * @return an <code>Object</code> value
     */
    @SuppressWarnings({"unchecked"})
    public T removeFirst() {
        T o = _head;

        if ( o == null ) {
            return null;
        }

        T n = (T) o.getNext();
        o.setNext( null );

        if ( null != n ) {
            n.setPrevious( null );
        }

        _head = n;
        if ( --_size == 0 ) {
            _tail = null;
        }
        return o;
    }


    /**
     * Remove and return the last element in the list.
     *
     * @return an <code>Object</code> value
     */
    @SuppressWarnings({"unchecked"})
    public T removeLast() {
        T o = _tail;

        if ( o == null ) {
            return null;
        }

        T prev = (T) o.getPrevious();
        o.setPrevious( null );

        if ( null != prev ) {
            prev.setNext( null );
        }
        _tail = prev;
        if ( --_size == 0 ) {
            _head = null;
        }
        return o;
    }


    /**
     * Implementation of index-based list insertions.
     *
     * @param index    an <code>int</code> value
     * @param linkable an object of type TLinkable
     */
    @SuppressWarnings({"unchecked"})
    protected void insert( int index, T linkable ) {

        if ( _size == 0 ) {
            _head = _tail = linkable; // first insertion
        } else if ( index == 0 ) {
            linkable.setNext( _head ); // insert at front
            _head.setPrevious( linkable );
            _head = linkable;
        } else if ( index == _size ) { // insert at back
            _tail.setNext( linkable );
            linkable.setPrevious( _tail );
            _tail = linkable;
        } else {
            T node = get( index );

            T before = (T) node.getPrevious();
            if ( before != null ) {
                before.setNext( linkable );
            }

            linkable.setPrevious( before );
            linkable.setNext( node );
            node.setPrevious( linkable );
        }
        _size++;
    }


    /**
     * Removes the specified element from the list.  Note that
     * it is the caller's responsibility to ensure that the
     * element does, in fact, belong to this list and not another
     * instance of TLinkedList.
     *
     * @param o a TLinkable element already inserted in this list.
     * @return true if the element was a TLinkable and removed
     */
    @SuppressWarnings({"unchecked"})
    public boolean remove( Object o ) {
        if ( o instanceof TLinkable ) {
            T p, n;
            TLinkable<T> link = (TLinkable<T>) o;

            p = (T) link.getPrevious();
            n = (T) link.getNext();

            if ( n == null && p == null ) { // emptying the list
                // It's possible this object is not something that's in the list. So,
                // make sure it's the head if it doesn't point to anything. This solves
                // problems caused by removing something multiple times.
                if ( o != _head ) {
                    return false;
                }

                _head = _tail = null;
            } else if ( n == null ) { // this is the tail
                // make previous the new tail
                link.setPrevious( null );
                p.setNext( null );
                _tail = p;
            } else if ( p == null ) { // this is the head
                // make next the new head
                link.setNext( null );
                n.setPrevious( null );
                _head = n;
            } else {            // somewhere in the middle
                p.setNext( n );
                n.setPrevious( p );
                link.setNext( null );
                link.setPrevious( null );
            }

            _size--;            // reduce size of list
            return true;
        } else {
            return false;
        }
    }


    /**
     * Inserts newElement into the list immediately before current.
     * All elements to the right of and including current are shifted
     * over.
     *
     * @param current    a <code>TLinkable</code> value currently in the list.
     * @param newElement a <code>TLinkable</code> value to be added to
     *                   the list.
     */
    public void addBefore( T current, T newElement ) {
        if ( current == _head ) {
            addFirst( newElement );
        } else if ( current == null ) {
            addLast( newElement );
        } else {
            TLinkable<T> p = current.getPrevious();
            newElement.setNext( current );
            p.setNext( newElement );
            newElement.setPrevious( p );
            current.setPrevious( newElement );
            _size++;
        }
    }


    /**
     * Inserts newElement into the list immediately after current.
     * All elements to the left of and including current are shifted
     * over.
     *
     * @param current    a <code>TLinkable</code> value currently in the list.
     * @param newElement a <code>TLinkable</code> value to be added to
     *                   the list.
     */
    public void addAfter( T current, T newElement ) {
        if ( current == _tail ) {
            addLast( newElement );
        } else if ( current == null ) {
            addFirst( newElement );
        } else {
            TLinkable<T> n = current.getNext();
            newElement.setPrevious( current );
            newElement.setNext( n );
            current.setNext( newElement );
            n.setPrevious( newElement );
            _size++;
        }
    }


    /**
     * Executes <tt>procedure</tt> for each entry in the list.
     *
     * @param procedure a <code>TObjectProcedure</code> value
     * @return false if the loop over the values terminated because
     *         the procedure returned false for some value.
     */
    @SuppressWarnings({"unchecked"})
    public boolean forEachValue( TObjectProcedure<T> procedure ) {
        T node = _head;
        while ( node != null ) {
            boolean keep_going = procedure.execute( node );
            if ( !keep_going ) {
                return false;
            }

            node = (T) node.getNext();
        }

        return true;
    }


    public void writeExternal( ObjectOutput out ) throws IOException {
        // VERSION
        out.writeByte( 0 );

        // NUMBER OF ENTRIES
        out.writeInt( _size );

        // HEAD
        out.writeObject( _head );

        // TAIL
        out.writeObject( _tail );
    }


    @SuppressWarnings({"unchecked"})
    public void readExternal( ObjectInput in )
            throws IOException, ClassNotFoundException {

        // VERSION
        in.readByte();

        // NUMBER OF ENTRIED
        _size = in.readInt();

        // HEAD
        _head = (T) in.readObject();

        // TAIL
        _tail = (T) in.readObject();
    }


    /** A ListIterator that supports additions and deletions. */
    protected final class IteratorImpl implements ListIterator<T> {

        private int _nextIndex = 0;
        private T _next;
        private T _lastReturned;


        /**
         * Creates a new <code>Iterator</code> instance positioned at
         * <tt>index</tt>.
         *
         * @param position an <code>int</code> value
         */
        @SuppressWarnings({"unchecked"})
        IteratorImpl( int position ) {
            if ( position < 0 || position > _size ) {
                throw new IndexOutOfBoundsException();
            }

            _nextIndex = position;
            if ( position == 0 ) {
                _next = _head;
            } else if ( position == _size ) {
                _next = null;
            } else if ( position < ( _size >> 1 ) ) {
                int pos = 0;
                for ( _next = _head; pos < position; pos++ ) {
                    _next = (T) _next.getNext();
                }
            } else {
                int pos = _size - 1;
                for ( _next = _tail; pos > position; pos-- ) {
                    _next = (T) _next.getPrevious();
                }
            }
        }


        /**
         * Insert <tt>linkable</tt> at the current position of the iterator.
         * Calling next() after add() will return the added object.
         *
         * @param linkable an object of type TLinkable
         */
        public final void add( T linkable ) {
            _lastReturned = null;
            _nextIndex++;

            if ( _size == 0 ) {
                TLinkedList.this.add( linkable );
            } else {
                TLinkedList.this.addBefore( _next, linkable );
            }
        }


        /**
         * True if a call to next() will return an object.
         *
         * @return a <code>boolean</code> value
         */
        public final boolean hasNext() {
            return _nextIndex != _size;
        }


        /**
         * True if a call to previous() will return a value.
         *
         * @return a <code>boolean</code> value
         */
        public final boolean hasPrevious() {
            return _nextIndex != 0;
        }


        /**
         * Returns the value at the Iterator's index and advances the
         * iterator.
         *
         * @return an <code>Object</code> value
         * @throws NoSuchElementException if there is no next element
         */
        @SuppressWarnings({"unchecked"})
        public final T next() {
            if ( _nextIndex == _size ) {
                throw new NoSuchElementException();
            }

            _lastReturned = _next;
            _next = (T) _next.getNext();
            _nextIndex++;
            return _lastReturned;
        }


        /**
         * returns the index of the next node in the list (the
         * one that would be returned by a call to next()).
         *
         * @return an <code>int</code> value
         */
        public final int nextIndex() {
            return _nextIndex;
        }


        /**
         * Returns the value before the Iterator's index and moves the
         * iterator back one index.
         *
         * @return an <code>Object</code> value
         * @throws NoSuchElementException if there is no previous element.
         */
        @SuppressWarnings({"unchecked"})
        public final T previous() {
            if ( _nextIndex == 0 ) {
                throw new NoSuchElementException();
            }

            if ( _nextIndex == _size ) {
                _lastReturned = _next = _tail;
            } else {
                _lastReturned = _next = (T) _next.getPrevious();
            }

            _nextIndex--;
            return _lastReturned;
        }


        /**
         * Returns the previous element's index.
         *
         * @return an <code>int</code> value
         */
        public final int previousIndex() {
            return _nextIndex - 1;
        }


        /**
         * Removes the current element in the list and shrinks its
         * size accordingly.
         *
         * @throws IllegalStateException neither next nor previous
         *                               have been invoked, or remove or add have been invoked after
         *                               the last invocation of next or previous.
         */
        @SuppressWarnings({"unchecked"})
        public final void remove() {
            if ( _lastReturned == null ) {
                throw new IllegalStateException( "must invoke next or previous before invoking remove" );
            }

            if ( _lastReturned != _next ) {
                _nextIndex--;
            }
            _next = (T) _lastReturned.getNext();
            TLinkedList.this.remove( _lastReturned );
            _lastReturned = null;
        }


        /**
         * Replaces the current element in the list with
         * <tt>linkable</tt>
         *
         * @param linkable an object of type TLinkable
         */
        public final void set( T linkable ) {
            if ( _lastReturned == null ) {
                throw new IllegalStateException();
            }

            // need to check both, since this could be the only
            // element in the list.
            if ( _lastReturned == _head ) {
                _head = linkable;
            }

            if ( _lastReturned == _tail ) {
                _tail = linkable;
            }

            swap( _lastReturned, linkable );
            _lastReturned = linkable;
        }


        /**
         * Replace from with to in the list.
         *
         * @param from a <code>TLinkable</code> value
         * @param to   a <code>TLinkable</code> value
         */
        private void swap( T from, T to ) {
            TLinkable<T> p = from.getPrevious();
            TLinkable<T> n = from.getNext();

            if ( null != p ) {
                to.setPrevious( p );
                p.setNext( to );
            }
            if ( null != n ) {
                to.setNext( n );
                n.setPrevious( to );
            }
            from.setNext( null );
            from.setPrevious( null );
        }
    }
} // TLinkedList

[Trove4j-commit] CVS: trove/test/gnu/trove/list/linked - New directory

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/test/gnu/trove/list/linked
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv16985/test/gnu/trove/list/linked

Log Message:
Directory /cvsroot/trove4j/trove/test/gnu/trove/list/linked added to the repository

[Trove4j-commit] CVS: trove/test/gnu/trove/list - New directory

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/test/gnu/trove/list
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv16972/test/gnu/trove/list

Log Message:
Directory /cvsroot/trove4j/trove/test/gnu/trove/list added to the repository

[Trove4j-commit] CVS: trove/src/gnu/trove/list/linked - New directory

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/list/linked
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv16377/src/gnu/trove/list/linked

Log Message:
Directory /cvsroot/trove4j/trove/src/gnu/trove/list/linked added to the repository

[Trove4j-commit] CVS: trove/src/gnu/trove/list - New directory

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/list
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv16352/src/gnu/trove/list

Log Message:
Directory /cvsroot/trove4j/trove/src/gnu/trove/list added to the repository

[Trove4j-commit] CVS: trove/src/gnu/trove/set/hash THashSet.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/set/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/src/gnu/trove/set/hash

Added Files:
      Tag: TROVE_3_WORKING
	THashSet.java 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

--- NEW FILE: THashSet.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.set.hash;

import gnu.trove.impl.hash.TObjectHash;
import gnu.trove.impl.HashFunctions;
import gnu.trove.procedure.TObjectProcedure;
import gnu.trove.procedure.array.ToObjectArrayProceedure;
import gnu.trove.iterator.hash.TObjectHashIterator;

import java.io.*;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.Arrays;
import java.lang.reflect.Array;



/**
 * An implementation of the <tt>Set</tt> interface that uses an
 * open-addressed hash table to store its contents.
 * <p/>
 * Created: Sat Nov  3 10:38:17 2001
 *
 * @author Eric D. Friedman
 * @version $Id: THashSet.java,v 1.1.2.1 2009/09/02 21:52:33 upholderoftruth Exp $
 */

public class THashSet<E> extends TObjectHash<E>
        implements Set<E>, Iterable<E>, Externalizable {

    static final long serialVersionUID = 1L;


    /**
     * Creates a new <code>THashSet</code> instance with the default
     * capacity and load factor.
     */
    public THashSet() {
        super();
    }


    /**
     * Creates a new <code>THashSet</code> instance with a prime
     * capacity equal to or greater than <tt>initialCapacity</tt> and
     * with the default load factor.
     *
     * @param initialCapacity an <code>int</code> value
     */
    public THashSet( int initialCapacity ) {
        super( initialCapacity );
    }


    /**
     * Creates a new <code>THashSet</code> instance with a prime
     * capacity equal to or greater than <tt>initialCapacity</tt> and
     * with the specified load factor.
     *
     * @param initialCapacity an <code>int</code> value
     * @param loadFactor      a <code>float</code> value
     */
    public THashSet( int initialCapacity, float loadFactor ) {
        super( initialCapacity, loadFactor );
    }


    /**
     * Creates a new <code>THashSet</code> instance containing the
     * elements of <tt>collection</tt>.
     *
     * @param collection a <code>Collection</code> value
     */
    public THashSet( Collection<? extends E> collection ) {
        this( collection.size() );
        addAll( collection );
    }


    /**
     * Inserts a value into the set.
     *
     * @param obj an <code>Object</code> value
     * @return true if the set was modified by the add operation
     */
    public boolean add( E obj ) {
        int index = insertionIndex( obj );

        if ( index < 0 ) {
            return false;       // already present in set, nothing to add
        }

        Object old = _set[index];
        _set[index] = obj;

        postInsertHook( old == FREE );
        return true;            // yes, we added something
    }


    public boolean equals( Object other ) {
        if ( !( other instanceof Set ) ) {
            return false;
        }
        Set that = (Set) other;
        if ( that.size() != this.size() ) {
            return false;
        }
        return containsAll( that );
    }


    public int hashCode() {
        HashProcedure p = new HashProcedure();
        forEach( p );
        return p.getHashCode();
    }


    private final class HashProcedure implements TObjectProcedure<E> {

        private int h = 0;


        public int getHashCode() {
            return h;
        }


        public final boolean execute( E key ) {
            h += HashFunctions.hash( key );
            return true;
        }
    }


    /**
     * Expands the set to accommodate new values.
     *
     * @param newCapacity an <code>int</code> value
     */
    protected void rehash( int newCapacity ) {
        int oldCapacity = _set.length;
        Object oldSet[] = _set;

        _set = new Object[newCapacity];
        Arrays.fill( _set, FREE );

        for ( int i = oldCapacity; i-- > 0; ) {
            if ( oldSet[i] != FREE && oldSet[i] != REMOVED ) {
                E o = (E) oldSet[i];
                int index = insertionIndex( o );
                if ( index < 0 ) { // everyone pays for this because some people can't RTFM
                    throwObjectContractViolation( _set[( -index - 1 )], o );
                }
                _set[index] = o;
            }
        }
    }


    /**
     * Returns a new array containing the objects in the set.
     *
     * @return an <code>Object[]</code> value
     */
    public Object[] toArray() {
        Object[] result = new Object[size()];
        forEach( new ToObjectArrayProceedure( result ) );
        return result;
    }


    /**
     * Returns a typed array of the objects in the set.
     *
     * @param a an <code>Object[]</code> value
     * @return an <code>Object[]</code> value
     */
    public <T> T[] toArray( T[] a ) {
        int size = size();
        if ( a.length < size ) {
            a = (T[]) Array.newInstance( a.getClass().getComponentType(), size );
        }

        forEach( new ToObjectArrayProceedure( a ) );

        // If this collection fits in the specified array with room to
        // spare (i.e., the array has more elements than this
        // collection), the element in the array immediately following
        // the end of the collection is set to null. This is useful in
        // determining the length of this collection only if the
        // caller knows that this collection does not contain any null
        // elements.)

        if ( a.length > size ) {
            a[size] = null;
        }

        return a;
    }


    /** Empties the set. */
    public void clear() {
        super.clear();

        Arrays.fill( _set, 0, _set.length, FREE );
    }


    /**
     * Removes <tt>obj</tt> from the set.
     *
     * @param obj an <code>Object</code> value
     * @return true if the set was modified by the remove operation.
     */
    public boolean remove( Object obj ) {
        int index = index( (E) obj );
        if ( index >= 0 ) {
            removeAt( index );
            return true;
        }
        return false;
    }


    /**
     * Creates an iterator over the values of the set.  The iterator
     * supports element deletion.
     *
     * @return an <code>Iterator</code> value
     */
    public Iterator<E> iterator() {
        return new TObjectHashIterator<E>( this );
    }


    /**
     * Tests the set to determine if all of the elements in
     * <tt>collection</tt> are present.
     *
     * @param collection a <code>Collection</code> value
     * @return true if all elements were present in the set.
     */
    public boolean containsAll( Collection<?> collection ) {
        for ( Iterator i = collection.iterator(); i.hasNext(); ) {
            if ( !contains( i.next() ) ) {
                return false;
            }
        }
        return true;
    }


    /**
     * Adds all of the elements in <tt>collection</tt> to the set.
     *
     * @param collection a <code>Collection</code> value
     * @return true if the set was modified by the add all operation.
     */
    public boolean addAll( Collection<? extends E> collection ) {
        boolean changed = false;
        int size = collection.size();

        ensureCapacity( size );
        Iterator<? extends E> it = collection.iterator();
        while ( size-- > 0 ) {
            if ( add( it.next() ) ) {
                changed = true;
            }
        }
        return changed;
    }


    /**
     * Removes all of the elements in <tt>collection</tt> from the set.
     *
     * @param collection a <code>Collection</code> value
     * @return true if the set was modified by the remove all operation.
     */
    public boolean removeAll( Collection<?> collection ) {
        boolean changed = false;
        int size = collection.size();
        Iterator it;

        it = collection.iterator();
        while ( size-- > 0 ) {
            if ( remove( it.next() ) ) {
                changed = true;
            }
        }
        return changed;
    }


    /**
     * Removes any values in the set which are not contained in
     * <tt>collection</tt>.
     *
     * @param collection a <code>Collection</code> value
     * @return true if the set was modified by the retain all operation
     */
    public boolean retainAll( Collection<?> collection ) {
        boolean changed = false;
        int size = size();
        Iterator it;

        it = iterator();
        while ( size-- > 0 ) {
            if ( !collection.contains( it.next() ) ) {
                it.remove();
                changed = true;
            }
        }
        return changed;
    }


    public String toString() {
        final StringBuilder buf = new StringBuilder( "{" );
        forEach( new TObjectProcedure() {
            private boolean first = true;


            public boolean execute( Object value ) {
                if ( first ) {
                    first = false;
                } else {
                    buf.append( "," );
                }

                buf.append( value );
                return true;
            }
        } );
        buf.append( "}" );
        return buf.toString();
    }


    public void writeExternal( ObjectOutput out ) throws IOException {
        // VERSION
        out.writeByte( 1 );

        // NOTE: Super was not written in version 0
        super.writeExternal( out );

        // NUMBER OF ENTRIES
        out.writeInt( _size );

        // ENTRIES
        // TODO: implement
//        SerializationProcedure writeProcedure = new SerializationProcedure( out );
//        if ( !forEach( writeProcedure ) ) {
//            throw writeProcedure.exception;
//        }
    }


    public void readExternal( ObjectInput in )
            throws IOException, ClassNotFoundException {

        // VERSION
        byte version = in.readByte();

        // NOTE: super was not written in version 0
        if ( version != 0 ) {
            super.readExternal( in );
        }

        // NUMBER OF ENTRIES
        int size = in.readInt();
        setUp( size );

        // ENTRIES
        // TODO: implement
//        while ( size-- > 0 ) {
//            E val = (E) in.readObject();
//            add( val );
//        }
    }
} // THashSet

[Trove4j-commit] CVS: trove/templates/gnu/trove/set _E_Set.template, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/set
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/templates/gnu/trove/set

Modified Files:
      Tag: TROVE_3_WORKING
	_E_Set.template 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

Index: _E_Set.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/set/Attic/_E_Set.template,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** _E_Set.template	24 Aug 2009 21:44:55 -0000	1.1.2.1
--- _E_Set.template	2 Sep 2009 21:52:33 -0000	1.1.2.2
***************
*** 38,44 ****
   * Created: Sat Nov  3 10:38:17 2001
   *
!  * @author Eric D. Friedman,
!  * @author Rob Eden
!  * @author Jeff Randall
   * @version $Id$
   */
--- 38,42 ----
   * Created: Sat Nov  3 10:38:17 2001
   *
!  * @author Eric D. Friedman, Rob Eden, Jeff Randall
   * @version $Id$
   */
***************
*** 51,54 ****
--- 49,54 ----
       * value is generally zero, but can be changed during construction
       * of the collection.
+      *
+      * @return the value that represents null
       */
      public #e# getNoEntryValue();
***************
*** 74,83 ****
  
      /**
!      * Inserts a value into the set.
       *
!      * @param entry a <code>#e#</code> value
!      * @return true if the set was modified by the add operation
       */
!     public boolean add( #e# entry );
  
  
--- 74,92 ----
  
      /**
!      * Returns <tt>true</tt> if this set contains the specified element.
       *
!      * @param entry an <code>#e#</code> value
!      * @return true if the set contains the specified element.
       */
!     public boolean contains( #e# entry );
! 
! 
!     /**
!      * Creates an iterator over the values of the set.  The iterator
!      * supports element deletion.
!      *
!      * @return an <code>T#E#Iterator</code> value
!      */
!     public T#E#Iterator iterator();
  
  
***************
*** 102,110 ****
  
      /**
!      * Returns an array containing all of the elements in this set; the
!      * runtime type of the returned array is that of the specified array.
!      * If the set fits in the specified array, it is returned therein.
!      * Otherwise, a new array is allocated with the runtime type of the
!      * specified array and the size of this set.
       *
       * <p>If this set fits in the specified array with room to spare
--- 111,115 ----
  
      /**
!      * Returns an array containing elements in this set.
       *
       * <p>If this set fits in the specified array with room to spare
***************
*** 115,152 ****
       * set does not contain any elements representing null.)
       *
       * <p>If this set makes any guarantees as to what order its elements
       * are returned by its iterator, this method must return the elements
       * in the same order.
       *
!      * <p>Like the {@link #toArray()} method, this method acts as bridge between
!      * array-based and collection-based APIs.  Further, this method allows
!      * precise control over the runtime type of the output array, and may,
!      * under certain circumstances, be used to save allocation costs.
!      *
!      * <p>The following code can be used to dump the set into a newly
!      * allocated array of <tt>#e#</tt>:
!      *
!      * <pre>
!      *     #e#[] y = x.toArray(new #e#[0]);</pre>
!      *
!      * Note that <tt>toArray(new #e#[0])</tt> is identical in function to
!      * <tt>toArray()</tt>.
!      *
!      * @param a the array into which the elements of this set are to be
!      *        stored, if it is big enough; otherwise, a new array of the same
!      *        runtime type is allocated for this purpose.
!      * @return an array containing all the elements in this set
!      * @throws ArrayStoreException if the runtime type of the specified array
!      *         is not a supertype of the runtime type of every element in this
!      *         set
       * @throws NullPointerException if the specified array is null
       */
!     public #e#[] toArray( #e#[] a );
  
  
      /**
!      * Empties the set.
       */
!     public void clear();
  
  
--- 120,146 ----
       * set does not contain any elements representing null.)
       *
+      * <p>If the native array is smaller than the set size,
+      * the array will be filled with elements in Iterator order
+      * until it is full and exclude the remainder.
+      *
       * <p>If this set makes any guarantees as to what order its elements
       * are returned by its iterator, this method must return the elements
       * in the same order.
       *
!      * @param dest the array into which the elements of this set are to be
!      *        stored.
!      * @return an <tt>#e#[]</tt> containing all the elements in this set
       * @throws NullPointerException if the specified array is null
       */
!     public #e#[] toArray( #e#[] dest );
  
  
      /**
!      * Inserts a value into the set.
!      *
!      * @param entry a <code>#e#</code> value
!      * @return true if the set was modified by the add operation
       */
!     public boolean add( #e# entry );
  
  
***************
*** 161,173 ****
  
      /**
-      * Creates an iterator over the values of the set.  The iterator
-      * supports element deletion.
-      *
-      * @return an <code>T#E#Iterator</code> value
-      */
-     public T#E#Iterator iterator();
- 
- 
-     /**
       * Tests the set to determine if all of the elements in
       * <tt>collection</tt> are present.
--- 155,158 ----
***************
*** 190,193 ****
--- 175,188 ----
  
      /**
+      * Tests the set to determine if all of the elements in
+      * <tt>array</tt> are present.
+      *
+      * @param array as <code>array</code> of #e# primitives.
+      * @return true if all elements were present in the set.
+      */
+     public boolean containsAll( #e#[] array );
+ 
+ 
+     /**
       * Adds all of the elements in <tt>collection</tt> to the set.
       *
***************
*** 208,211 ****
--- 203,245 ----
  
      /**
+      * Adds all of the elements in the <tt>array</tt> to the set.
+      *
+      * @param array a <code>array</code> of #e# primitives.
+      * @return true if the set was modified by the add all operation.
+      */
+     public boolean addAll( #e#[] array );
+ 
+ 
+     /**
+      * Removes any values in the set which are not contained in
+      * <tt>collection</tt>.
+      *
+      * @param collection a <code>Collection</code> value
+      * @return true if the set was modified by the retain all operation
+      */
+     public boolean retainAll( Collection<?> collection );
+ 
+ 
+     /**
+      * Removes any values in the set which are not contained in
+      * <tt>T#E#Set</tt>.
+      *
+      * @param set a <code>T#E#Set</code> value
+      * @return true if the set was modified by the retain all operation
+      */
+     public boolean retainAll( T#E#Set set );
+ 
+ 
+     /**
+      * Removes any values in the set which are not contained in
+      * <tt>array</tt>.
+      *
+      * @param array an <code>array</code> of #e# primitives.
+      * @return true if the set was modified by the retain all operation
+      */
+     public boolean retainAll( #e#[] array );
+ 
+ 
+     /**
       * Removes all of the elements in <tt>collection</tt> from the set.
       *
***************
*** 226,246 ****
  
      /**
!      * Removes any values in the set which are not contained in
!      * <tt>collection</tt>.
       *
!      * @param collection a <code>Collection</code> value
!      * @return true if the set was modified by the retain all operation
       */
!     public boolean retainAll( Collection<?> collection );
  
  
      /**
!      * Removes any values in the set which are not contained in
!      * <tt>T#E#Set</tt>.
!      *
!      * @param set a <code>T#E#Set</code> value
!      * @return true if the set was modified by the retain all operation
       */
!     public boolean retainAll( T#E#Set set );
  
  
--- 260,275 ----
  
      /**
!      * Removes all of the elements in <tt>array</tt> from the set.
       *
!      * @param array an <code>array</code> of #e# primitives.
!      * @return true if the set was modified by the remove all operation.
       */
!     public boolean removeAll( #e#[] array );
  
  
      /**
!      * Empties the set.
       */
!     public void clear();
  
  
***************
*** 259,263 ****
       * @return <tt>true</tt> if the specified object is equal to this set
       */
!     boolean equals( T#E#Set o );
  
  
--- 288,292 ----
       * @return <tt>true</tt> if the specified object is equal to this set
       */
!     boolean equals( Object o );
  
  

[Trove4j-commit] CVS: trove/src/gnu/trove/impl Constants.java, 1.1.2.2, 1.1.2.3 HashFunctions.java, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/impl
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/src/gnu/trove/impl

Modified Files:
      Tag: TROVE_3_WORKING
	Constants.java HashFunctions.java 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

Index: Constants.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/impl/Attic/Constants.java,v
retrieving revision 1.1.2.2
retrieving revision 1.1.2.3
diff -C2 -d -r1.1.2.2 -r1.1.2.3
*** Constants.java	19 Aug 2009 05:00:46 -0000	1.1.2.2
--- Constants.java	2 Sep 2009 21:52:33 -0000	1.1.2.3
***************
*** 27,29 ****
--- 27,40 ----
      public static final int DEFAULT_CAPACITY = 10;
  
+     /** the load above which rehashing occurs. */
+     public static final float DEFAULT_LOAD_FACTOR = 0.5f;
+ 
+ //    /** flag indicating that a slot in the hashtable is available */
+ //    public static final byte SLOT_FREE = 0;
+ //
+ //    /** flag indicating that a slot in the hashtable is occupied */
+ //    public static final byte SLOT_FULL = 1;
+ //
+ //    /** flag indicating that the value of a slot in the hashtable was deleted */
+ //    public static final byte SLOT_REMOVED = 2;
  }

Index: HashFunctions.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/impl/Attic/HashFunctions.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** HashFunctions.java	18 Aug 2009 21:22:54 -0000	1.1.2.1
--- HashFunctions.java	2 Sep 2009 21:52:33 -0000	1.1.2.2
***************
*** 80,84 ****
       * of "ceil" rather than to call to {@link Math#ceil(double)}.
       */
!     static int fastCeil( float v ) {
          int possible_result = ( int ) v;
          if ( v - possible_result > 0 ) possible_result++;
--- 80,84 ----
       * of "ceil" rather than to call to {@link Math#ceil(double)}.
       */
!     public static int fastCeil( float v ) {
          int possible_result = ( int ) v;
          if ( v - possible_result > 0 ) possible_result++;

[Trove4j-commit] CVS: trove/templates/gnu/trove/list _E_List.template, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/list
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/templates/gnu/trove/list

Modified Files:
      Tag: TROVE_3_WORKING
	_E_List.template 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

Index: _E_List.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/list/Attic/_E_List.template,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** _E_List.template	14 Aug 2009 21:20:57 -0000	1.1.2.1
--- _E_List.template	2 Sep 2009 21:52:33 -0000	1.1.2.2
***************
*** 1,4 ****
--- 1,5 ----
  ///////////////////////////////////////////////////////////////////////////////
  // Copyright (c) 2009, Rob Eden All Rights Reserved.
+ // Copyright (c) 2009, Jeff Randall All Rights Reserved.
  //
  // This library is free software; you can redistribute it and/or
***************
*** 28,32 ****
  
  import java.io.Serializable;
- import java.util.Arrays;
  import java.util.Random;
  
--- 29,32 ----
***************
*** 37,45 ****
--- 37,59 ----
   */
  public interface T#E#List extends Serializable {
+ 
+     /**
+      * Returns the value that is used to represent null. The default
+      * value is generally zero, but can be changed during construction
+      * of the collection.
+      *
+      * @return the value that represents null
+      */
+     public #e# getNoEntryValue();
+ 
+ 
      /**
       * Returns the number of values in the list.
+      *
+      * @return the number of values in the list.
       */
      public int size();
  
+ 
      /**
       * Tests whether this list contains any values.
***************
*** 57,60 ****
--- 71,75 ----
      public void add(#e# val);
  
+ 
      /**
       * Adds the values in the array <tt>vals</tt> to the end of the
***************
*** 65,68 ****
--- 80,84 ----
      public void add( #e#[] vals );
  
+ 
      /**
       * Adds a subset of the values in the array <tt>vals</tt> to the
***************
*** 75,79 ****
      public void add( #e#[] vals, int offset, int length );
  
!     /**
       * Inserts <tt>value</tt> into the list at <tt>offset</tt>.  All
       * values including and to the right of <tt>offset</tt> are shifted
--- 91,96 ----
      public void add( #e#[] vals, int offset, int length );
  
! 
!    /**
       * Inserts <tt>value</tt> into the list at <tt>offset</tt>.  All
       * values including and to the right of <tt>offset</tt> are shifted
***************
*** 85,88 ****
--- 102,106 ----
      public void insert( int offset, #e# value );
  
+ 
      /**
       * Inserts the array of <tt>values</tt> into the list at
***************
*** 95,98 ****
--- 113,117 ----
      public void insert( int offset, #e#[] values );
  
+ 
      /**
       * Inserts a slice of the array of <tt>values</tt> into the list
***************
*** 108,111 ****
--- 127,131 ----
      public void insert( int offset, #e#[] values, int valOffset, int len );
  
+ 
      /**
       * Returns the value at the specified offset.
***************
*** 116,119 ****
--- 136,140 ----
      public #e# get( int offset );
  
+ 
      /**
       * Sets the value at the specified offset.
***************
*** 124,127 ****
--- 145,149 ----
      public void set( int offset, #e# val );
  
+ 
      /**
       * Replace the values in the list starting at <tt>offset</tt> with
***************
*** 133,136 ****
--- 155,159 ----
      public void set( int offset, #e#[] values );
  
+ 
      /**
       * Replace the values in the list starting at <tt>offset</tt> with
***************
*** 145,148 ****
--- 168,172 ----
      public void set( int offset, #e#[] values, int valOffset, int length );
  
+ 
      /**
       * Sets the value at the specified offset and returns the
***************
*** 155,158 ****
--- 179,183 ----
      public #e# replace( int offset, #e# val );
  
+ 
      /**
       * Flushes the internal state of the list, resetting the capacity
***************
*** 170,173 ****
--- 195,199 ----
      public #e# remove( int offset );
  
+ 
      /**
       * Removes <tt>length</tt> values from the list, starting at
***************
*** 179,182 ****
--- 205,209 ----
      public void remove( int offset, int length );
  
+ 
      /**
       * Transform each value in the list using the specified function.
***************
*** 186,189 ****
--- 213,217 ----
      public void transformValues( T#E#Function function );
  
+ 
      /**
       * Reverse the order of the elements in the list.
***************
*** 191,194 ****
--- 219,223 ----
      public void reverse();
  
+ 
      /**
       * Reverse the order of the elements in the range of the list.
***************
*** 199,202 ****
--- 228,232 ----
      public void reverse( int from, int to );
  
+ 
      /**
       * Shuffle the elements of the list using the specified random
***************
*** 225,229 ****
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toNativeArray();
  
      /**
--- 255,260 ----
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toArray();
! 
  
      /**
***************
*** 234,238 ****
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toNativeArray( int offset, int len );
  
      /**
--- 265,290 ----
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toArray( int offset, int len );
! 
! 
!     /**
!      * Copies a slice of the list into a native array.
!      *
!      * <p>If the list fits in the specified array with room to spare (i.e.,
!      * the array has more elements than the list), the element in the array
!      * immediately following the end of the list is set to
!      * <tt>{@link #getNoEntryValue()}</tt>.
!      * (This is useful in determining the length of the list <i>only</i> if
!      * the caller knows that the list does not contain any "null" elements.)
!      *
!      * <p>NOTE: Trove does not allocate a new array if the array passed in is
!      * not large enough to hold all of the data elements.  It will instead fill
!      * the array passed in.
!      *
!      * @param dest the array to copy into.
!      * @return the array passed in.
!      */
!     public #e#[] toArray( #e#[] dest );
! 
  
      /**
***************
*** 242,247 ****
       * @param offset the offset of the first value to copy
       * @param len the number of values to copy.
       */
!     public void toNativeArray( #e#[] dest, int offset, int len );
  
  
--- 294,300 ----
       * @param offset the offset of the first value to copy
       * @param len the number of values to copy.
+      * @return the array passed in.
       */
!     public #e#[] toArray( #e#[] dest, int offset, int len );
  
  
***************
*** 255,258 ****
--- 308,312 ----
      public boolean forEach( T#E#Procedure procedure );
  
+ 
      /**
       * Applies the procedure to each value in the list in descending
***************
*** 264,267 ****
--- 318,322 ----
      public boolean forEachDescending( T#E#Procedure procedure );
  
+ 
      /**
       * Sort the values in the list (ascending) using the Sun quicksort
***************
*** 272,275 ****
--- 327,331 ----
      public void sort();
  
+ 
      /**
       * Sort a slice of the list (ascending) using the Sun quicksort
***************
*** 290,293 ****
--- 346,350 ----
      public void fill( #e# val );
  
+ 
      /**
       * Fills a range in the list with the specified value.
***************
*** 299,302 ****
--- 356,360 ----
      public void fill( int fromIndex, int toIndex, #e# val );
  
+ 
      /**
       * Performs a binary search for <tt>value</tt> in the entire list.
***************
*** 310,313 ****
--- 368,372 ----
      public int binarySearch( #e# value );
  
+ 
      /**
       * Performs a binary search for <tt>value</tt> in the specified
***************
*** 323,326 ****
--- 382,386 ----
      public int binarySearch( #e# value, int fromIndex, int toIndex );
  
+ 
      /**
       * Searches the list front to back for the index of
***************
*** 334,337 ****
--- 394,398 ----
      public int indexOf( #e# value );
  
+ 
      /**
       * Searches the list front to back for the index of
***************
*** 347,350 ****
--- 408,412 ----
      public int indexOf( int offset, #e# value );
  
+ 
      /**
       * Searches the list back to front for the last index of
***************
*** 358,361 ****
--- 420,424 ----
      public int lastIndexOf( #e# value );
  
+ 
      /**
       * Searches the list back to front for the last index of
***************
*** 371,374 ****
--- 434,438 ----
      public int lastIndexOf( int offset, #e# value );
  
+ 
      /**
       * Searches the list for <tt>value</tt>
***************
*** 379,382 ****
--- 443,447 ----
      public boolean contains( #e# value );
  
+ 
      /**
       * Searches the list for values satisfying <tt>condition</tt> in
***************
*** 388,391 ****
--- 453,457 ----
      public T#E#List grep( T#E#Procedure condition );
  
+ 
      /**
       * Searches the list for values which do <b>not</b> satisfy
***************
*** 397,400 ****
--- 463,467 ----
      public T#E#List inverseGrep( T#E#Procedure condition );
  
+ 
      /**
       * Finds the maximum value in the list.
***************
*** 405,408 ****
--- 472,476 ----
      public #e# max();
  
+ 
      /**
       * Finds the minimum value in the list.

[Trove4j-commit] CVS: trove/templates/gnu/trove/stack _E_Stack.template, 1.1.2.1, 1.1.2.2

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/stack
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/templates/gnu/trove/stack

Modified Files:
      Tag: TROVE_3_WORKING
	_E_Stack.template 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

Index: _E_Stack.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/stack/Attic/_E_Stack.template,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** _E_Stack.template	14 Aug 2009 21:20:57 -0000	1.1.2.1
--- _E_Stack.template	2 Sep 2009 21:52:33 -0000	1.1.2.2
***************
*** 1,4 ****
--- 1,6 ----
  ///////////////////////////////////////////////////////////////////////////////
  // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
+ // Copyright (c) 2009, Rob Eden All Rights Reserved.
+ // Copyright (c) 2009, Jeff Randall All Rights Reserved.
  //
  // This library is free software; you can redistribute it and/or
***************
*** 31,34 ****
--- 33,47 ----
   */
  public interface T#E#Stack extends Serializable {
+ 
+     /**
+      * Returns the value that is used to represent null. The default
+      * value is generally zero, but can be changed during construction
+      * of the collection.
+      *
+      * @return the value that represents null
+      */
+     public #e# getNoEntryValue();
+ 
+ 
      /**
       * Pushes the value onto the top of the stack.
***************
*** 38,41 ****
--- 51,55 ----
      public void push( #e# val );
  
+ 
      /**
       * Removes and returns the value at the top of the stack.
***************
*** 45,48 ****
--- 59,63 ----
      public #e# pop();
  
+ 
      /**
       * Returns the value at the top of the stack.
***************
*** 52,55 ****
--- 67,71 ----
      public #e# peek();
  
+ 
      /**
       * Returns the current depth of the stack.
***************
*** 57,60 ****
--- 73,77 ----
      public int size();
  
+ 
      /**
       * Clears the stack.
***************
*** 62,65 ****
--- 79,83 ----
      public void clear();
  
+ 
      /**
       * Copies the contents of the stack into a native array. Note that this will NOT
***************
*** 68,72 ****
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toNativeArray();
  
      /**
--- 86,91 ----
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toArray();
! 
  
      /**
***************
*** 76,79 ****
       * @param dest the array to copy into.
       */
!     public void toNativeArray( #e#[] dest );
  }
\ No newline at end of file
--- 95,98 ----
       * @param dest the array to copy into.
       */
!     public void toArray( #e#[] dest );
  }
\ No newline at end of file

[Trove4j-commit] CVS: trove/src/gnu/trove/impl/hash TPrimitiveHash.java, NONE, 1.1.2.1 THash.java, NONE, 1.1.2.1 TObjectHash.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/impl/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/src/gnu/trove/impl/hash

Added Files:
      Tag: TROVE_3_WORKING
	TPrimitiveHash.java THash.java TObjectHash.java 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

--- NEW FILE: TPrimitiveHash.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.impl.hash;

import gnu.trove.impl.HashFunctions;



/**
 * The base class for hashtables of primitive values.  Since there is
 * no notion of object equality for primitives, it isn't possible to
 * use a `REMOVED' object to track deletions in an open-addressed table.
 * So, we have to resort to using a parallel `bookkeeping' array of bytes,
 * in which flags can be set to indicate that a particular slot in the
 * hash table is FREE, FULL, or REMOVED.
 *
 * @author Eric D. Friedman, Rob Eden, Jeff Randall
 * @version $Id: TPrimitiveHash.java,v 1.1.2.1 2009/09/02 21:52:32 upholderoftruth Exp $
 */
abstract public class TPrimitiveHash extends THash {

    /**
     * flags indicating whether each position in the hash is
     * FREE, FULL, or REMOVED
     */
    protected transient byte[] _states;

    /* constants used for state flags */

    /** flag indicating that a slot in the hashtable is available */
    protected static final byte FREE = 0;

    /** flag indicating that a slot in the hashtable is occupied */
    protected static final byte FULL = 1;

    /**
     * flag indicating that the value of a slot in the hashtable
     * was deleted
     */
    protected static final byte REMOVED = 2;


    /**
     * Creates a new <code>THash</code> instance with the default
     * capacity and load factor.
     */
    public TPrimitiveHash() {
        super();
    }


    /**
     * Creates a new <code>TPrimitiveHash</code> instance with a prime
     * capacity at or near the specified capacity and with the default
     * load factor.
     *
     * @param initialCapacity an <code>int</code> value
     */
    public TPrimitiveHash( int initialCapacity ) {
        this( initialCapacity, DEFAULT_LOAD_FACTOR );
    }


    /**
     * Creates a new <code>TPrimitiveHash</code> instance with a prime
     * capacity at or near the minimum needed to hold
     * <tt>initialCapacity<tt> elements with load factor
     * <tt>loadFactor</tt> without triggering a rehash.
     *
     * @param initialCapacity an <code>int</code> value
     * @param loadFactor      a <code>float</code> value
     */
    public TPrimitiveHash( int initialCapacity, float loadFactor ) {
        super();
        _loadFactor = loadFactor;
        setUp( HashFunctions.fastCeil( initialCapacity / loadFactor ) );
    }


    /**
     * Returns the capacity of the hash table.  This is the true
     * physical capacity, without adjusting for the load factor.
     *
     * @return the physical capacity of the hash table.
     */
    public int capacity() {
        return _states.length;
    }


    /**
     * Delete the record at <tt>index</tt>.
     *
     * @param index an <code>int</code> value
     */
    public void removeAt( int index ) {
        _states[index] = REMOVED;
        super.removeAt( index );
    }


    /**
     * initializes the hashtable to a prime capacity which is at least
     * <tt>initialCapacity + 1</tt>.
     *
     * @param initialCapacity an <code>int</code> value
     * @return the actual capacity chosen
     */
    protected int setUp( int initialCapacity ) {
        int capacity;

        capacity = super.setUp( initialCapacity );
        _states = new byte[capacity];
        return capacity;
    }
} // TPrimitiveHash
--- NEW FILE: THash.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.impl.hash;

import gnu.trove.impl.Constants;
import gnu.trove.impl.HashFunctions;
import gnu.trove.impl.PrimeFinder;

import java.io.Externalizable;
import java.io.ObjectOutput;
import java.io.IOException;
import java.io.ObjectInput;



/**
 * Base class for hashtables that use open addressing to resolve
 * collisions.
 *
 * Created: Wed Nov 28 21:11:16 2001
 *
 * @author Eric D. Friedman
 * @author Rob Eden (auto-compaction)
 * @author Jeff Randall
 *
 * @version $Id: THash.java,v 1.1.2.1 2009/09/02 21:52:32 upholderoftruth Exp $
 */
abstract public class THash implements Externalizable {

    static final long serialVersionUID = -1792948471915530295L;

    /** the load above which rehashing occurs. */
    protected static final float DEFAULT_LOAD_FACTOR = Constants.DEFAULT_LOAD_FACTOR;

    /**
     * the default initial capacity for the hash table.  This is one
     * less than a prime value because one is added to it when
     * searching for a prime capacity to account for the free slot
     * required by open addressing. Thus, the real default capacity is
     * 11.
     */
    protected static final int DEFAULT_CAPACITY = Constants.DEFAULT_CAPACITY;


    /** the current number of occupied slots in the hash. */
    protected transient int _size;

    /** the current number of free slots in the hash. */
    protected transient int _free;

    /**
     * Determines how full the internal table can become before
     * rehashing is required. This must be a value in the range: 0.0 <
     * loadFactor < 1.0.  The default value is 0.5, which is about as
     * large as you can get in open addressing without hurting
     * performance.  Cf. Knuth, Volume 3., Chapter 6.
     */
    protected float _loadFactor;

    /**
     * The maximum number of elements allowed without allocating more
     * space.
     */
    protected int _maxSize;


    /** The number of removes that should be performed before an auto-compaction occurs. */
    protected int _autoCompactRemovesRemaining;

    /**
     * The auto-compaction factor for the table.
     *
     * @see #setAutoCompactionFactor
     */
    protected float _autoCompactionFactor;

    /** @see #tempDisableAutoCompaction */
    protected transient boolean _autoCompactTemporaryDisable = false;


    /**
     * Creates a new <code>THash</code> instance with the default
     * capacity and load factor.
     */
    public THash() {
        this( DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR );
    }


    /**
     * Creates a new <code>THash</code> instance with a prime capacity
     * at or near the specified capacity and with the default load
     * factor.
     *
     * @param initialCapacity an <code>int</code> value
     */
    public THash( int initialCapacity ) {
        this( initialCapacity, DEFAULT_LOAD_FACTOR );
    }


    /**
     * Creates a new <code>THash</code> instance with a prime capacity
     * at or near the minimum needed to hold <tt>initialCapacity</tt>
     * elements with load factor <tt>loadFactor</tt> without triggering
     * a rehash.
     *
     * @param initialCapacity an <code>int</code> value
     * @param loadFactor      a <code>float</code> value
     */
    public THash( int initialCapacity, float loadFactor ) {
        super();
        _loadFactor = loadFactor;

        // Through testing, the load factor (especially the default load factor) has been
        // found to be a pretty good starting auto-compaction factor.
        _autoCompactionFactor = loadFactor;

        setUp( HashFunctions.fastCeil( initialCapacity / loadFactor ) );
    }


    /**
     * Tells whether this set is currently holding any elements.
     *
     * @return a <code>boolean</code> value
     */
    public boolean isEmpty() {
        return 0 == _size;
    }


    /**
     * Returns the number of distinct elements in this collection.
     *
     * @return an <code>int</code> value
     */
    public int size() {
        return _size;
    }


    /** @return the current physical capacity of the hash table. */
    abstract public int capacity();


    /**
     * Ensure that this hashtable has sufficient capacity to hold
     * <tt>desiredCapacity<tt> <b>additional</b> elements without
     * requiring a rehash.  This is a tuning method you can call
     * before doing a large insert.
     *
     * @param desiredCapacity an <code>int</code> value
     */
    public void ensureCapacity( int desiredCapacity ) {
        if ( desiredCapacity > ( _maxSize - size() ) ) {
            rehash( PrimeFinder.nextPrime( HashFunctions.fastCeil(
                    ( desiredCapacity + size() ) / _loadFactor ) + 1 ) );
            computeMaxSize( capacity() );
        }
    }


    /**
     * Compresses the hashtable to the minimum prime size (as defined
     * by PrimeFinder) that will hold all of the elements currently in
     * the table.  If you have done a lot of <tt>remove</tt>
     * operations and plan to do a lot of queries or insertions or
     * iteration, it is a good idea to invoke this method.  Doing so
     * will accomplish two things:
     * <p/>
     * <ol>
     * <li> You'll free memory allocated to the table but no
     * longer needed because of the remove()s.</li>
     * <p/>
     * <li> You'll get better query/insert/iterator performance
     * because there won't be any <tt>REMOVED</tt> slots to skip
     * over when probing for indices in the table.</li>
     * </ol>
     */
    public void compact() {
        // need at least one free spot for open addressing
        rehash( PrimeFinder.nextPrime( HashFunctions.fastCeil( size() / _loadFactor ) + 1 ) );
        computeMaxSize( capacity() );

        // If auto-compaction is enabled, re-determine the compaction interval
        if ( _autoCompactionFactor != 0 ) {
            computeNextAutoCompactionAmount( size() );
        }
    }


    /**
     * The auto-compaction factor controls whether and when a table performs a
     * {@link #compact} automatically after a certain number of remove operations.
     * If the value is non-zero, the number of removes that need to occur for
     * auto-compaction is the size of table at the time of the previous compaction
     * (or the initial capacity) multiplied by this factor.
     * <p/>
     * Setting this value to zero will disable auto-compaction.
     *
     * @param factor a <tt>float</tt> that indicates the auto-compaction factor
     */
    public void setAutoCompactionFactor( float factor ) {
        if ( factor < 0 ) {
            throw new IllegalArgumentException( "Factor must be >= 0: " + factor );
        }

        _autoCompactionFactor = factor;
    }


    /**
     * @see #setAutoCompactionFactor
     *
     * @return a <<tt>float</tt> that represents the auto-compaction factor.
     */
    public float getAutoCompactionFactor() {
        return _autoCompactionFactor;
    }


    /**
     * This simply calls {@link #compact compact}.  It is included for
     * symmetry with other collection classes.  Note that the name of this
     * method is somewhat misleading (which is why we prefer
     * <tt>compact</tt>) as the load factor may require capacity above
     * and beyond the size of this collection.
     *
     * @see #compact
     */
    public final void trimToSize() {
        compact();
    }


    /**
     * Delete the record at <tt>index</tt>.  Reduces the size of the
     * collection by one.
     *
     * @param index an <code>int</code> value
     */
    @SuppressWarnings({"UnusedDeclaration"})
    public void removeAt( int index ) {
        _size--;

        // If auto-compaction is enabled, see if we need to compact
        if ( _autoCompactionFactor != 0 ) {
            _autoCompactRemovesRemaining--;

            if ( !_autoCompactTemporaryDisable && _autoCompactRemovesRemaining <= 0 ) {
                // Do the compact
                // NOTE: this will cause the next compaction interval to be calculated
                compact();
            }
        }
    }


    /** Empties the collection. */
    public void clear() {
        _size = 0;
        _free = capacity();
    }


    /**
     * initializes the hashtable to a prime capacity which is at least
     * <tt>initialCapacity + 1</tt>.
     *
     * @param initialCapacity an <code>int</code> value
     * @return the actual capacity chosen
     */
    protected int setUp( int initialCapacity ) {
        int capacity;

        capacity = PrimeFinder.nextPrime( initialCapacity );
        computeMaxSize( capacity );
        computeNextAutoCompactionAmount( initialCapacity );

        return capacity;
    }


    /**
     * Rehashes the set.
     *
     * @param newCapacity an <code>int</code> value
     */
    protected abstract void rehash( int newCapacity );


    /**
     * Temporarily disables auto-compaction. MUST be followed by calling
     * {@link #reenableAutoCompaction}.
     */
    public void tempDisableAutoCompaction() {
        _autoCompactTemporaryDisable = true;
    }


    /**
     * Re-enable auto-compaction after it was disabled via
     * {@link #tempDisableAutoCompaction()}.
     *
     * @param check_for_compaction True if compaction should be performed if needed
     *                             before returning. If false, no compaction will be
     *                             performed.
     */
    public void reenableAutoCompaction( boolean check_for_compaction ) {
        _autoCompactTemporaryDisable = false;

        if ( check_for_compaction && _autoCompactRemovesRemaining <= 0 &&
             _autoCompactionFactor != 0 ) {

            // Do the compact
            // NOTE: this will cause the next compaction interval to be calculated
            compact();
        }
    }


    /**
     * Computes the values of maxSize. There will always be at least
     * one free slot required.
     *
     * @param capacity an <code>int</code> value
     */
    protected void computeMaxSize( int capacity ) {
        // need at least one free slot for open addressing
        _maxSize = Math.min( capacity - 1, (int) ( capacity * _loadFactor ) );
        _free = capacity - _size; // reset the free element count
    }


    /**
     * Computes the number of removes that need to happen before the next auto-compaction
     * will occur.
     *
     * @param size an <tt>int</tt> that sets the auto-compaction limit.
     */
    protected void computeNextAutoCompactionAmount( int size ) {
        if ( _autoCompactionFactor != 0 ) {
            // NOTE: doing the round ourselves has been found to be faster than using
            //       Math.round.
            _autoCompactRemovesRemaining =
                    (int) ( ( size * _autoCompactionFactor ) + 0.5f );
        }
    }


    /**
     * After an insert, this hook is called to adjust the size/free
     * values of the set and to perform rehashing if necessary.
     *
     * @param usedFreeSlot the slot
     */
    protected final void postInsertHook( boolean usedFreeSlot ) {
        if ( usedFreeSlot ) {
            _free--;
        }

        // rehash whenever we exhaust the available space in the table
        if ( ++_size > _maxSize || _free == 0 ) {
            // choose a new capacity suited to the new state of the table
            // if we've grown beyond our maximum size, double capacity;
            // if we've exhausted the free spots, rehash to the same capacity,
            // which will free up any stale removed slots for reuse.
            int newCapacity = _size > _maxSize ? PrimeFinder.nextPrime( capacity() << 1 ) : capacity();
            rehash( newCapacity );
            computeMaxSize( capacity() );
        }
    }


    protected int calculateGrownCapacity() {
        return capacity() << 1;
    }


    public void writeExternal( ObjectOutput out ) throws IOException {
        // VERSION
        out.writeByte( 0 );

        // LOAD FACTOR
        out.writeFloat( _loadFactor );

        // AUTO COMPACTION LOAD FACTOR
        out.writeFloat( _autoCompactionFactor );
    }


    public void readExternal( ObjectInput in )
            throws IOException, ClassNotFoundException {

        // VERSION
        in.readByte();

        // LOAD FACTOR
        float old_factor = _loadFactor;
        _loadFactor = in.readFloat();

        // AUTO COMPACTION LOAD FACTOR
        _autoCompactionFactor = in.readFloat();


        // If we change the laod factor from the default, re-setup
        if ( old_factor != _loadFactor ) {
            setUp( (int) Math.ceil( DEFAULT_CAPACITY / _loadFactor ) );
        }
    }
}// THash
--- NEW FILE: TObjectHash.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.impl.hash;

import gnu.trove.impl.HashFunctions;
import gnu.trove.procedure.TObjectProcedure;

import java.util.Arrays;
import java.io.ObjectOutput;
import java.io.IOException;
import java.io.ObjectInput;



/**
 * An open addressed hashing implementation for Object types.
 * <p/>
 * Created: Sun Nov  4 08:56:06 2001
 *
 * @author Eric D. Friedman
 * @version $Id: TObjectHash.java,v 1.1.2.1 2009/09/02 21:52:32 upholderoftruth Exp $
 */
abstract public class TObjectHash<T> extends THash {

    static final long serialVersionUID = -3461112548087185871L;


    /** the set of Objects */
    public transient Object[] _set;

    public static final Object REMOVED = new Object(), FREE = new Object();


    /**
     * Creates a new <code>TObjectHash</code> instance with the
     * default capacity and load factor.
     */
    public TObjectHash() {
        super();
    }


    /**
     * Creates a new <code>TObjectHash</code> instance whose capacity
     * is the next highest prime above <tt>initialCapacity + 1</tt>
     * unless that value is already prime.
     *
     * @param initialCapacity an <code>int</code> value
     */
    public TObjectHash( int initialCapacity ) {
        super( initialCapacity );
    }


    /**
     * Creates a new <code>TObjectHash</code> instance with a prime
     * value at or near the specified capacity and load factor.
     *
     * @param initialCapacity used to find a prime capacity for the table.
     * @param loadFactor      used to calculate the threshold over which
     *                        rehashing takes place.
     */
    public TObjectHash( int initialCapacity, float loadFactor ) {
        super( initialCapacity, loadFactor );
    }


    public int capacity() {
        return _set.length;
    }


    public void removeAt( int index ) {
        _set[index] = REMOVED;
        super.removeAt( index );
    }


    /**
     * initializes the Object set of this hash table.
     *
     * @param initialCapacity an <code>int</code> value
     * @return an <code>int</code> value
     */
    public int setUp( int initialCapacity ) {
        int capacity;

        capacity = super.setUp( initialCapacity );
        _set = new Object[capacity];
        Arrays.fill( _set, FREE );
        return capacity;
    }


    /**
     * Executes <tt>procedure</tt> for each element in the set.
     *
     * @param procedure a <code>TObjectProcedure</code> value
     * @return false if the loop over the set terminated because
     *         the procedure returned false for some value.
     */
    public boolean forEach( TObjectProcedure<T> procedure ) {
        Object[] set = _set;
        for ( int i = set.length; i-- > 0; ) {
            if ( set[i] != FREE
                 && set[i] != REMOVED
                 && !procedure.execute( (T) set[i] ) ) {
                return false;
            }
        }
        return true;
    }


    /**
     * Searches the set for <tt>obj</tt>
     *
     * @param obj an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    public boolean contains( Object obj ) {
        return index( (T) obj ) >= 0;
    }


    /**
     * Locates the index of <tt>obj</tt>.
     *
     * @param obj an <code>Object</code> value
     * @return the index of <tt>obj</tt> or -1 if it isn't in the set.
     */
    protected int index( T obj ) {

        final Object[] set = _set;
        final int length = set.length;
        final int hash = HashFunctions.hash( obj ) & 0x7fffffff;
        int index = hash % length;
        Object cur = set[index];

        if ( cur == FREE ) {
            return -1;
        }

        // NOTE: here it has to be REMOVED or FULL (some user-given value)
        if ( cur == REMOVED || !cur.equals( obj ) ) {
            // see Knuth, p. 529
            final int probe = 1 + ( hash % ( length - 2 ) );

            do {
                index -= probe;
                if ( index < 0 ) {
                    index += length;
                }
                cur = set[index];
            } while ( cur != FREE
                      && ( cur == REMOVED || !cur.equals( obj ) ) );
        }

        return cur == FREE ? -1 : index;
    }


    /**
     * Locates the index at which <tt>obj</tt> can be inserted.  if
     * there is already a value equal()ing <tt>obj</tt> in the set,
     * returns that value's index as <tt>-index - 1</tt>.
     *
     * @param obj an <code>Object</code> value
     * @return the index of a FREE slot at which obj can be inserted
     *         or, if obj is already stored in the hash, the negative value of
     *         that index, minus 1: -index -1.
     */
    protected int insertionIndex( T obj ) {

        final Object[] set = _set;
        final int length = set.length;
        final int hash = HashFunctions.hash( obj ) & 0x7fffffff;
        int index = hash % length;
        Object cur = set[index];

        if ( cur == FREE ) {
            return index;       // empty, all done
        } else if ( cur != REMOVED && cur.equals( obj ) ) {
            return -index - 1;   // already stored
        } else {                // already FULL or REMOVED, must probe
            // compute the double hash
            final int probe = 1 + ( hash % ( length - 2 ) );

            // if the slot we landed on is FULL (but not removed), probe
            // until we find an empty slot, a REMOVED slot, or an element
            // equal to the one we are trying to insert.
            // finding an empty slot means that the value is not present
            // and that we should use that slot as the insertion point;
            // finding a REMOVED slot means that we need to keep searching,
            // however we want to remember the offset of that REMOVED slot
            // so we can reuse it in case a "new" insertion (i.e. not an update)
            // is possible.
            // finding a matching value means that we've found that our desired
            // key is already in the table
            if ( cur != REMOVED ) {
                // starting at the natural offset, probe until we find an
                // offset that isn't full.
                do {
                    index -= probe;
                    if ( index < 0 ) {
                        index += length;
                    }
                    cur = set[index];
                } while ( cur != FREE
                          && cur != REMOVED
                          && !cur.equals( obj ) );
            }

            // if the index we found was removed: continue probing until we
            // locate a free location or an element which equal()s the
            // one we have.
            if ( cur == REMOVED ) {
                int firstRemoved = index;
                while ( cur != FREE
                        && ( cur == REMOVED || !cur.equals( obj ) ) ) {
                    index -= probe;
                    if ( index < 0 ) {
                        index += length;
                    }
                    cur = set[index];
                }
                // NOTE: cur cannot == REMOVED in this block
                return ( cur != FREE ) ? -index - 1 : firstRemoved;
            }
            // if it's full, the key is already stored
            // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
            return ( cur != FREE ) ? -index - 1 : index;
        }
    }


    /**
     * This is the default implementation of TObjectHashingStrategy:
     * it delegates hashing to the Object's hashCode method.
     *
     * @param o for which the hashcode is to be computed
     * @return the hashCode
     * @see Object#hashCode()
     */
    public final int computeHashCode( T o ) {
        return o == null ? 0 : o.hashCode();
    }


    /**
     * This is the default implementation of TObjectHashingStrategy:
     * it delegates equality comparisons to the first parameter's
     * equals() method.
     *
     * @param o1 an <code>Object</code> value
     * @param o2 an <code>Object</code> value
     * @return true if the objects are equal
     * @see Object#equals(Object)
     */
    public final boolean equals( T o1, T o2 ) {
        return o1 == null ? o2 == null : o1.equals( o2 );
    }


    /**
     * Convenience methods for subclasses to use in throwing exceptions about
     * badly behaved user objects employed as keys.  We have to throw an
     * IllegalArgumentException with a rather verbose message telling the
     * user that they need to fix their object implementation to conform
     * to the general contract for java.lang.Object.
     *
     * @param o1 the first of the equal elements with unequal hash codes.
     * @param o2 the second of the equal elements with unequal hash codes.
     * @throws IllegalArgumentException the whole point of this method.
     */
    protected final void throwObjectContractViolation( Object o1, Object o2 )
            throws IllegalArgumentException {
        throw new IllegalArgumentException( "Equal objects must have equal hashcodes. "
                                            + "During rehashing, Trove discovered that "
                                            + "the following two objects claim to be "
                                            + "equal (as in java.lang.Object.equals()) "
                                            + "but their hashCodes (or those calculated by "
                                            + "your TObjectHashingStrategy) are not equal."
                                            + "This violates the general contract of "
                                            + "java.lang.Object.hashCode().  See bullet point two "
                                            + "in that method's documentation. "
                                            + "object #1 =" + o1
                                            + "; object #2 =" + o2 );
    }


    @Override
    public void writeExternal( ObjectOutput out ) throws IOException {
        super.writeExternal( out );

        // VERSION
        out.writeByte( 0 );

        // TODO: implement
    }


    @Override
    public void readExternal( ObjectInput in )
            throws IOException, ClassNotFoundException {

        super.readExternal( in );

        // VERSION
        in.readByte();

        // TODO: implement
    }
} // TObjectHash

[Trove4j-commit] CVS: trove/src/gnu/trove/iterator/hash TObjectHashIterator.java, NONE, 1.1.2.1 THashIterator.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/iterator/hash
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/src/gnu/trove/iterator/hash

Added Files:
      Tag: TROVE_3_WORKING
	TObjectHashIterator.java THashIterator.java 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

--- NEW FILE: TObjectHashIterator.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////


package gnu.trove.iterator.hash;

import gnu.trove.impl.hash.TObjectHash;



/**
 * Created: Wed Nov 28 21:30:53 2001
 *
 * @author Eric D. Friedman, Rob Eden, Jeff Randall
 * @version $Id: TObjectHashIterator.java,v 1.1.2.1 2009/09/02 21:52:33 upholderoftruth Exp $
 */

public class TObjectHashIterator<E> extends THashIterator<E> {

    protected final TObjectHash<E> _objectHash;


    public TObjectHashIterator( TObjectHash<E> hash ) {
        super( hash );
        _objectHash = hash;
    }


    protected E objectAtIndex( int index ) {
        return (E) _objectHash._set[index];
    }

} // TObjectHashIterator

--- NEW FILE: THashIterator.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.iterator.hash;

import gnu.trove.iterator.TIterator;
import gnu.trove.impl.hash.TObjectHash;
import gnu.trove.impl.hash.THash;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;



/**
 * Implements all iterator functions for the hashed object set.
 * Subclasses may override objectAtIndex to vary the object
 * returned by calls to next() (e.g. for values, and Map.Entry
 * objects).
 * <p/>
 * <p> Note that iteration is fastest if you forego the calls to
 * <tt>hasNext</tt> in favor of checking the size of the structure
 * yourself and then call next() that many times:
 * <p/>
 * <pre>
 * Iterator i = collection.iterator();
 * for (int size = collection.size(); size-- > 0;) {
 *   Object o = i.next();
 * }
 * </pre>
 * <p/>
 * <p>You may, of course, use the hasNext(), next() idiom too if
 * you aren't in a performance critical spot.</p>
 */
abstract class THashIterator<V> implements TIterator, Iterator<V> {


    private final TObjectHash _object_hash;

    /** the data structure this iterator traverses */
    protected final THash _hash;

    /**
     * the number of elements this iterator believes are in the
     * data structure it accesses.
     */
    protected int _expectedSize;

    /** the index used for iteration. */
    protected int _index;


    /** Create an instance of THashIterator over the values of the TObjectHash */
    public THashIterator( TObjectHash hash ) {
        _hash = hash;
        _expectedSize = _hash.size();
        _index = _hash.capacity();
        _object_hash = hash;
    }


    /**
     * Moves the iterator to the next Object and returns it.
     *
     * @return an <code>Object</code> value
     * @throws ConcurrentModificationException
     *                                if the structure
     *                                was changed using a method that isn't on this iterator.
     * @throws NoSuchElementException if this is called on an
     *                                exhausted iterator.
     */
    public V next() {
        moveToNextIndex();
        return objectAtIndex( _index );
    }


    /**
     * Returns true if the iterator can be advanced past its current
     * location.
     *
     * @return a <code>boolean</code> value
     */
    public boolean hasNext() {
        return nextIndex() >= 0;
    }


    /**
     * Removes the last entry returned by the iterator.
     * Invoking this method more than once for a single entry
     * will leave the underlying data structure in a confused
     * state.
     */
    public void remove() {
        if ( _expectedSize != _hash.size() ) {
            throw new ConcurrentModificationException();
        }

        // Disable auto compaction during the remove. This is a workaround for bug 1642768.
        try {
            _hash.tempDisableAutoCompaction();
            _hash.removeAt( _index );
        }
        finally {
            _hash.reenableAutoCompaction( false );
        }

        _expectedSize--;
    }


    /**
     * Sets the internal <tt>index</tt> so that the `next' object
     * can be returned.
     */
    protected final void moveToNextIndex() {
        // doing the assignment && < 0 in one line shaves
        // 3 opcodes...
        if ( ( _index = nextIndex() ) < 0 ) {
            throw new NoSuchElementException();
        }
    }


    /**
     * Returns the index of the next value in the data structure
     * or a negative value if the iterator is exhausted.
     *
     * @return an <code>int</code> value
     * @throws ConcurrentModificationException
     *          if the underlying
     *          collection's size has been modified since the iterator was
     *          created.
     */
    protected final int nextIndex() {
        if ( _expectedSize != _hash.size() ) {
            throw new ConcurrentModificationException();
        }

        Object[] set = _object_hash._set;
        int i = _index;
        while ( i-- > 0 && ( set[i] == TObjectHash.FREE || set[i] == TObjectHash.REMOVED ) ) {
            ;
        }
        return i;
    }


    /**
     * Returns the object at the specified index.  Subclasses should
     * implement this to return the appropriate object for the given
     * index.
     *
     * @param index the index of the value to return.
     * @return an <code>Object</code> value
     */
    abstract protected V objectAtIndex( int index );
} // THashIterator

[Trove4j-commit] CVS: trove/src/gnu/trove/procedure TObjectProcedure.java, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/src/gnu/trove/procedure
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/src/gnu/trove/procedure

Added Files:
      Tag: TROVE_3_WORKING
	TObjectProcedure.java 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

--- NEW FILE: TObjectProcedure.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////


package gnu.trove.procedure;

/**
 * Interface for procedures with one Object parameter.
 *
 * Created: Mon Nov  5 21:45:49 2001
 *
 * @author Eric D. Friedman
 * @version $Id: TObjectProcedure.java,v 1.1.2.1 2009/09/02 21:52:33 upholderoftruth Exp $
 */

public interface TObjectProcedure<T> {
    /**
     * Executes this procedure. A false return value indicates that
     * the application executing this procedure should not invoke this
     * procedure again.
     *
     * @param object an <code>Object</code> value
     * @return true if additional invocations of the procedure are
     * allowed.
     */
    public boolean execute(T object);
}// TObjectProcedure

[Trove4j-commit] CVS: trove/templates/gnu/trove/list/array _E_ArrayList.template, 1.1.2.7, 1.1.2.8

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/list/array
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/templates/gnu/trove/list/array

Modified Files:
      Tag: TROVE_3_WORKING
	_E_ArrayList.template 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

Index: _E_ArrayList.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/list/array/Attic/_E_ArrayList.template,v
retrieving revision 1.1.2.7
retrieving revision 1.1.2.8
diff -C2 -d -r1.1.2.7 -r1.1.2.8
*** _E_ArrayList.template	19 Aug 2009 05:01:49 -0000	1.1.2.7
--- _E_ArrayList.template	2 Sep 2009 21:52:33 -0000	1.1.2.8
***************
*** 54,57 ****
--- 54,61 ----
      protected static final int DEFAULT_CAPACITY = Constants.DEFAULT_CAPACITY;
  
+     /** the #e# value that represents null */
+     protected #e# no_entry_value;
+ 
+ 
      /**
       * Creates a new <code>T#E#ArrayList</code> instance with the
***************
*** 59,65 ****
       */
      public T#E#ArrayList() {
!         this( DEFAULT_CAPACITY );
      }
  
      /**
       * Creates a new <code>T#E#ArrayList</code> instance with the
--- 63,70 ----
       */
      public T#E#ArrayList() {
!         this( DEFAULT_CAPACITY, ( #e# ) 0 );
      }
  
+ 
      /**
       * Creates a new <code>T#E#ArrayList</code> instance with the
***************
*** 69,74 ****
--- 74,92 ----
       */
      public T#E#ArrayList( int capacity ) {
+         this( capacity, ( #e# ) 0 );
+     }
+ 
+ 
+     /**
+      * Creates a new <code>T#E#ArrayList</code> instance with the
+      * specified capacity.
+      *
+      * @param capacity an <code>int</code> value
+      * @param no_entry_value an <code>#e#</code> value that represents null.
+      */
+     public T#E#ArrayList( int capacity, #e# no_entry_value ) {
          _data = new #e#[ capacity ];
          _pos = 0;
+         this.no_entry_value = no_entry_value;
      }
  
***************
*** 80,85 ****
       */
      public T#E#ArrayList ( T#E#ArrayList list ) {
!         this._data = list.toNativeArray();
          this._pos = list._pos;
      }
  
--- 98,104 ----
       */
      public T#E#ArrayList ( T#E#ArrayList list ) {
!         this._data = list.toArray();
          this._pos = list._pos;
+         this.no_entry_value = list.no_entry_value;
      }
  
***************
*** 94,101 ****
       */
      public T#E#ArrayList( #e#[] values ) {
!         this( Math.max( values.length, 1 ) );
          add( values );
      }
  
      // sizing
  
--- 113,131 ----
       */
      public T#E#ArrayList( #e#[] values ) {
!         this( Math.max( values.length, DEFAULT_CAPACITY ) );
          add( values );
      }
  
+ 
+     /**
+      * Returns the value that is used to represent null. The default
+      * value is generally zero, but can be changed during construction
+      * of the collection.
+      */
+     public #e# getNoEntryValue() {
+         return no_entry_value;
+     }
+ 
+ 
      // sizing
  
***************
*** 117,120 ****
--- 147,151 ----
      }
  
+ 
      /**
       * Returns the number of values in the list.
***************
*** 126,129 ****
--- 157,161 ----
      }
  
+ 
      /**
       * Tests whether this list contains any values.
***************
*** 135,138 ****
--- 167,171 ----
      }
  
+ 
      /**
       * Sheds any excess capacity above and beyond the current size of
***************
*** 142,150 ****
          if ( _data.length > size() ) {
              #e#[] tmp = new #e#[ size() ];
!             toNativeArray( tmp, 0, tmp.length );
              _data = tmp;
          }
      }
  
      // modifying
  
--- 175,184 ----
          if ( _data.length > size() ) {
              #e#[] tmp = new #e#[ size() ];
!             toArray( tmp, 0, tmp.length );
              _data = tmp;
          }
      }
  
+ 
      // modifying
  
***************
*** 159,162 ****
--- 193,197 ----
      }
  
+ 
      /**
       * Adds the values in the array <tt>vals</tt> to the end of the
***************
*** 169,173 ****
      }
  
!     /**
       * Adds a subset of the values in the array <tt>vals</tt> to the
       * end of the list, in order.
--- 204,209 ----
      }
  
! 
!    /**
       * Adds a subset of the values in the array <tt>vals</tt> to the
       * end of the list, in order.
***************
*** 183,186 ****
--- 219,223 ----
      }
  
+ 
      /**
       * Inserts <tt>value</tt> into the list at <tt>offset</tt>.  All
***************
*** 204,207 ****
--- 241,245 ----
      }
  
+ 
      /**
       * Inserts the array of <tt>values</tt> into the list at
***************
*** 216,219 ****
--- 254,258 ----
      }
  
+ 
      /**
       * Inserts a slice of the array of <tt>values</tt> into the list
***************
*** 241,244 ****
--- 280,284 ----
      }
  
+ 
      /**
       * Returns the value at the specified offset.
***************
*** 254,257 ****
--- 294,298 ----
      }
  
+ 
      /**
       * Returns the value at the specified offset without doing any
***************
*** 265,268 ****
--- 306,310 ----
      }
  
+ 
      /**
       * Sets the value at the specified offset.
***************
*** 278,281 ****
--- 320,324 ----
      }
  
+ 
      /**
       * Sets the value at the specified offset and returns the
***************
*** 295,298 ****
--- 338,342 ----
      }
  
+ 
      /**
       * Replace the values in the list starting at <tt>offset</tt> with
***************
*** 306,309 ****
--- 350,354 ----
      }
  
+ 
      /**
       * Replace the values in the list starting at <tt>offset</tt> with
***************
*** 323,326 ****
--- 368,372 ----
      }
  
+ 
      /**
       * Sets the value at the specified offset without doing any bounds
***************
*** 334,337 ****
--- 380,384 ----
      }
  
+ 
      /**
       * Flushes the internal state of the list, resetting the capacity
***************
*** 342,345 ****
--- 389,393 ----
      }
  
+ 
      /**
       * Flushes the internal state of the list, setting the capacity of
***************
*** 353,356 ****
--- 401,405 ----
      }
  
+ 
      /**
       * Sets the size of the list to 0, but does not change its
***************
*** 366,369 ****
--- 415,419 ----
      }
  
+ 
      /**
       * Sets the size of the list to 0, but does not change its
***************
*** 384,387 ****
--- 434,438 ----
      }
  
+ 
      /**
       * Removes the value at <tt>offset</tt> from the list.
***************
*** 396,399 ****
--- 447,451 ----
      }
  
+ 
      /**
       * Removes <tt>length</tt> values from the list, starting at
***************
*** 427,430 ****
--- 479,483 ----
      }
  
+ 
      /**
       * Transform each value in the list using the specified function.
***************
*** 438,441 ****
--- 491,495 ----
      }
  
+ 
      /**
       * Reverse the order of the elements in the list.
***************
*** 445,448 ****
--- 499,503 ----
      }
  
+ 
      /**
       * Reverse the order of the elements in the range of the list.
***************
*** 463,466 ****
--- 518,522 ----
      }
  
+ 
      /**
       * Shuffle the elements of the list using the specified random
***************
*** 475,478 ****
--- 531,535 ----
      }
  
+ 
      /**
       * Swap the values at offsets <tt>i</tt> and <tt>j</tt>.
***************
*** 487,490 ****
--- 544,548 ----
      }
  
+ 
      // copying
  
***************
*** 522,529 ****
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toNativeArray() {
!         return toNativeArray( 0, _pos );
      }
  
      /**
       * Copies a slice of the list into a native array.
--- 580,588 ----
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toArray() {
!         return toArray( 0, _pos );
      }
  
+ 
      /**
       * Copies a slice of the list into a native array.
***************
*** 533,542 ****
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toNativeArray( int offset, int len ) {
          #e#[] rv = new #e#[ len ];
!         toNativeArray( rv, offset, len );
          return rv;
      }
  
      /**
       * Copies a slice of the list into a native array.
--- 592,630 ----
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toArray( int offset, int len ) {
          #e#[] rv = new #e#[ len ];
!         toArray( rv, offset, len );
          return rv;
      }
  
+ 
+     /**
+      * Copies a slice of the list into a native array.
+      *
+      * <p>If the list fits in the specified array with room to spare (i.e.,
+      * the array has more elements than the list), the element in the array
+      * immediately following the end of the list is set to
+      * <tt>{@link #getNoEntryValue()}</tt>.
+      * (This is useful in determining the length of the list <i>only</i> if
+      * the caller knows that the list does not contain any "null" elements.)
+      *
+      * <p>NOTE: Trove does not allocate a new array if the array passed in is
+      * not large enough to hold all of the data elements.  It will instead fill
+      * the array passed in.
+      *
+      * @param dest the array to copy into.
+      * @return the array passed in.
+      */
+     public #e#[] toArray( #e#[] dest ) {
+         int len = dest.length;
+         if ( dest.length > _pos ) {
+             len = _pos;
+             dest[len] = no_entry_value;
+         }
+         toArray( dest, 0, len );
+         return dest;
+     }
+ 
+ 
      /**
       * Copies a slice of the list into a native array.
***************
*** 545,552 ****
       * @param offset the offset of the first value to copy
       * @param len the number of values to copy.
       */
!     public void toNativeArray( #e#[] dest, int offset, int len ) {
          if ( len == 0 ) {
!             return;             // nothing to copy
          }
          if ( offset < 0 || offset >= _pos ) {
--- 633,641 ----
       * @param offset the offset of the first value to copy
       * @param len the number of values to copy.
+      * @return the array passed in.
       */
!     public #e#[] toArray( #e#[] dest, int offset, int len ) {
          if ( len == 0 ) {
!             return dest;             // nothing to copy
          }
          if ( offset < 0 || offset >= _pos ) {
***************
*** 554,559 ****
--- 643,650 ----
          }
          System.arraycopy( _data, offset, dest, 0, len );
+         return dest;
      }
  
+ 
      // comparing
  
***************
*** 584,587 ****
--- 675,679 ----
      }
  
+ 
      public int hashCode() {
          int h = 0;
***************
*** 592,595 ****
--- 684,688 ----
      }
  
+ 
      // procedures
  
***************
*** 610,613 ****
--- 703,707 ----
      }
  
+ 
      /**
       * Applies the procedure to each value in the list in descending
***************
*** 626,629 ****
--- 720,724 ----
      }
  
+ 
      // sorting
  
***************
*** 638,641 ****
--- 733,737 ----
      }
  
+ 
      /**
       * Sort a slice of the list (ascending) using the Sun quicksort
***************
*** 650,653 ****
--- 746,750 ----
      }
  
+ 
      // filling
  
***************
*** 661,664 ****
--- 758,762 ----
      }
  
+ 
      /**
       * Fills a range in the list with the specified value.
***************
*** 676,679 ****
--- 774,778 ----
      }
  
+ 
      // searching
  
***************
*** 691,694 ****
--- 790,794 ----
      }
  
+ 
      /**
       * Performs a binary search for <tt>value</tt> in the specified
***************
*** 730,733 ****
--- 830,834 ----
      }
  
+ 
      /**
       * Searches the list front to back for the index of
***************
*** 743,746 ****
--- 844,848 ----
      }
  
+ 
      /**
       * Searches the list front to back for the index of
***************
*** 763,766 ****
--- 865,869 ----
      }
  
+ 
      /**
       * Searches the list back to front for the last index of
***************
*** 776,779 ****
--- 879,883 ----
      }
  
+ 
      /**
       * Searches the list back to front for the last index of
***************
*** 796,799 ****
--- 900,904 ----
      }
  
+ 
      /**
       * Searches the list for <tt>value</tt>
***************
*** 806,809 ****
--- 911,915 ----
      }
  
+ 
      /**
       * Searches the list for values satisfying <tt>condition</tt> in
***************
*** 823,826 ****
--- 929,933 ----
      }
  
+ 
      /**
       * Searches the list for values which do <b>not</b> satisfy
***************
*** 840,843 ****
--- 947,951 ----
      }
  
+ 
      /**
       * Finds the maximum value in the list.
***************
*** 859,862 ****
--- 967,971 ----
      }
  
+ 
      /**
       * Finds the minimum value in the list.
***************
*** 878,881 ****
--- 987,991 ----
      }
  
+ 
      // stringification
  
***************
*** 906,909 ****
--- 1016,1022 ----
      	out.writeInt( _pos );
  
+     	// NO_ENTRY_VALUE
+     	out.write#E#( no_entry_value );
+ 
      	// ENTRIES
      	int len = _data.length;
***************
*** 914,917 ****
--- 1027,1031 ----
      }
  
+ 
      public void readExternal( ObjectInput in )
      	throws IOException, ClassNotFoundException {
***************
*** 923,926 ****
--- 1037,1043 ----
      	_pos = in.readInt();
  
+     	// NO_ENTRY_VALUE
+     	no_entry_value = in.read#E#();
+ 
      	// ENTRIES
      	int len = in.readInt();

[Trove4j-commit] CVS: trove/templates/gnu/trove/iterator/array _E_ArrayIterator.template, NONE, 1.1.2.1

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/iterator/array
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/templates/gnu/trove/iterator/array

Added Files:
      Tag: TROVE_3_WORKING
	_E_ArrayIterator.template 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

--- NEW FILE: _E_ArrayIterator.template ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
// Copyright (c) 2009, Rob Eden All Rights Reserved.
// Copyright (c) 2009, Jeff Randall All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove.iterator.array;

import gnu.trove.iterator.T#E#Iterator;
import gnu.trove.set.hash.T#E#HashSet;

//////////////////////////////////////////////////
// THIS IS A GENERATED CLASS. DO NOT HAND EDIT! //
//////////////////////////////////////////////////


/**
 * Iterator for #e# collections.
 */
public class T#E#ArrayIterator implements T#E#Iterator {

    public T#E#ArrayIterator( T#E#HashSet set ) {
        // TODO: implement
    }


    /**
     * Returns true if the iterator can be advanced past its current location.
     *
     * @return a <code>boolean</code> value
     */
    public boolean hasNext() {
        return false;  // TODO: implement
    }


    /**
     * Removes the last entry returned by the iterator. The result
     * of invoking this method more than once for a single entry is
     * undefined and can leave the underlying data structure in a
     * confused state.
     */
    public void remove() {
        // TODO: implement
    }


    /**
     * Advances the iterator to the next element in the underlying collection
     * and returns it.
     *
     * @return the next #e# in the collection
     * @exception NoSuchElementException if the iterator is already exhausted
     */
    public #e# next() {
        // TODO: implement
        return ( #e# ) 0;
    }
}

[Trove4j-commit] CVS: trove/templates/gnu/trove/stack/array _E_ArrayStack.template, 1.1.2.6, 1.1.2.7

[Jeff R. <uph...@us...>]

Update of /cvsroot/trove4j/trove/templates/gnu/trove/stack/array
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv14856/templates/gnu/trove/stack/array

Modified Files:
      Tag: TROVE_3_WORKING
	_E_ArrayStack.template 
Log Message:
Implementation of HashSets, Add tests, changes as needed to allow those changes.

Index: _E_ArrayStack.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/stack/array/Attic/_E_ArrayStack.template,v
retrieving revision 1.1.2.6
retrieving revision 1.1.2.7
diff -C2 -d -r1.1.2.6 -r1.1.2.7
*** _E_ArrayStack.template	19 Aug 2009 05:44:53 -0000	1.1.2.6
--- _E_ArrayStack.template	2 Sep 2009 21:52:33 -0000	1.1.2.7
***************
*** 47,50 ****
--- 47,51 ----
      public static final int DEFAULT_CAPACITY = Constants.DEFAULT_CAPACITY;
  
+ 
      /**
       * Creates a new <code>T#E#ArrayStack</code> instance with the default
***************
*** 52,58 ****
       */
      public T#E#ArrayStack() {
!         this(DEFAULT_CAPACITY);
      }
  
      /**
       * Creates a new <code>T#E#ArrayStack</code> instance with the
--- 53,60 ----
       */
      public T#E#ArrayStack() {
!         this( DEFAULT_CAPACITY );
      }
  
+ 
      /**
       * Creates a new <code>T#E#ArrayStack</code> instance with the
***************
*** 65,68 ****
--- 67,83 ----
      }
  
+ 
+     /**
+      * Creates a new <code>T#E#ArrayStack</code> instance with the
+      * specified capacity.
+      *
+      * @param capacity the initial depth of the stack
+      * @param no_entry_value value that represents null
+      */
+     public T#E#ArrayStack( int capacity, #e# no_entry_value ) {
+         _list = new T#E#ArrayList( capacity, no_entry_value );
+     }
+ 
+ 
      /**
       * Creates a new <code>T#E#ArrayStack</code> instance that is
***************
*** 75,78 ****
--- 90,106 ----
      }
  
+ 
+     /**
+      * Returns the value that is used to represent null. The default
+      * value is generally zero, but can be changed during construction
+      * of the collection.
+      *
+      * @return the value that represents null
+      */
+     public #e# getNoEntryValue() {
+         return _list.getNoEntryValue();
+     }
+ 
+ 
      /**
       * Pushes the value onto the top of the stack.
***************
*** 84,87 ****
--- 112,116 ----
      }
  
+ 
      /**
       * Removes and returns the value at the top of the stack.
***************
*** 103,106 ****
--- 132,136 ----
      }
  
+ 
      /**
       * Returns the current depth of the stack.
***************
*** 110,113 ****
--- 140,144 ----
      }
  
+ 
      /**
       * Clears the stack.
***************
*** 117,120 ****
--- 148,152 ----
      }
  
+ 
      /**
       * Copies the contents of the stack into a native array. Note that this will NOT
***************
*** 123,136 ****
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toNativeArray() {
!         #e#[] retval = _list.toNativeArray();
          reverse( retval, 0, size() );
          return retval;
      }
  
      /**
       * Copies a slice of the list into a native array. Note that this will NOT
       * pop them out of the stack.  The front of the list will be the top
!      * of the stack.<p>
       * If the native array is smaller than the stack depth,
       * the native array will be filled with the elements from the top
--- 155,170 ----
       * @return an <code>#e#[]</code> value
       */
!     public #e#[] toArray() {
!         #e#[] retval = _list.toArray();
          reverse( retval, 0, size() );
          return retval;
      }
  
+ 
      /**
       * Copies a slice of the list into a native array. Note that this will NOT
       * pop them out of the stack.  The front of the list will be the top
!      * of the stack.
!      * <p>
       * If the native array is smaller than the stack depth,
       * the native array will be filled with the elements from the top
***************
*** 139,153 ****
       * @param dest the array to copy into.
       */
!     public void toNativeArray( #e#[] dest ) {
!         int start = size() - dest.length;
          if ( start < 0 ) {
              start = 0;
          }
  
!         _list.toNativeArray( dest, start, size() );
!         reverse( dest, 0, size() );
! 
      }
  
      /**
       * Reverse the order of the elements in the range of the list.
--- 173,189 ----
       * @param dest the array to copy into.
       */
!     public void toArray( #e#[] dest ) {
!         int size = size();
!         int start = size - dest.length;
          if ( start < 0 ) {
              start = 0;
          }
  
!         int length = Math.min( size, dest.length );
!         _list.toArray( dest, start, length );
!         reverse( dest, 0, length );
      }
  
+ 
      /**
       * Reverse the order of the elements in the range of the list.
***************
*** 169,172 ****
--- 205,209 ----
      }
  
+ 
      /**
       * Swap the values at offsets <tt>i</tt> and <tt>j</tt>.
***************
*** 215,218 ****
--- 252,256 ----
      }
  
+ 
      public int hashCode() {
          return _list.hashCode();
***************
*** 228,231 ****
--- 266,270 ----
      }
  
+ 
      public void readExternal( ObjectInput in )
      	throws IOException, ClassNotFoundException {