trove4j-commit — commit logs for trove CVS projects

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

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

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

Added Files:
      Tag: TROVE_3_WORKING
	TObjectFunction.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

--- NEW FILE: TObjectFunction.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.function;

/**
 * Interface for functions that accept and return one Object reference.
 * <p/>
 * Created: Mon Nov  5 22:19:36 2001
 *
 * @author Eric D. Friedman
 * @version $Id: TObjectFunction.java,v 1.1.2.1 2009/09/06 17:02:19 upholderoftruth Exp $
 */

public interface TObjectFunction<T, R> {

    /**
     * Execute this function with <tt>value</tt>
     *
     * @param value an <code>Object</code> input
     * @return an <code>Object</code> result
     */
    public R execute( T value );
}// TObjectFunction

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

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

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

Modified Files:
      Tag: TROVE_3_WORKING
	THashTest.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

Index: THashTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/impl/hash/Attic/THashTest.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
*** THashTest.java	3 Sep 2009 16:17:45 -0000	1.1.2.2
--- THashTest.java	6 Sep 2009 17:02:20 -0000	1.1.2.3
***************
*** 3,6 ****
--- 3,7 ----
  import junit.framework.TestCase;
  import gnu.trove.set.hash.THashSet;
+ import gnu.trove.map.hash.THashMap;
  
  
***************
*** 75,77 ****
--- 76,122 ----
      }
  
+ 
+     public void testCompact() throws Exception {
+         THashMap<Integer,Integer> map = new THashMap<Integer,Integer>();
+         
+         Integer[] data = new Integer[1000];
+ 
+         for (int i = 0; i < 1000; i++) {
+             data[i] = new Integer(i);
+             map.put(data[i], data[i]);
+         }
+         assertTrue(map._maxSize > 1000);
+         for (int i = 0; i < 1000; i+=2) {
+ //            try {
+             map.remove(data[i]);
+ //            }
+ //            catch( RuntimeException ex ) {
+ //                System.err.println("Error on i: " + i);
+ //                System.out.println("Hash codes:");
+ //                for( int j = 0 ; j < data.length; j++ ) {
+ //                    if ( ( j % 8 ) == 0 ) {
+ //                        System.out.println(",");
+ //                    }
+ //                    else System.out.print(",");
+ //                    System.out.print(map._hashingStrategy.computeHashCode(data[j]));
+ //                }
+ //
+ //
+ //                System.out.println("Remove:");
+ //                for( int j = 0 ; j <= i; j+=2 ) {
+ //                    if ( ( j % 8 ) == 0 ) {
+ //                        System.out.println(",");
+ //                    }
+ //                    else System.out.print(",");
+ //                    System.out.print(map._hashingStrategy.computeHashCode(data[j]));
+ //                }
+ //                throw ex;
+ //            }
+         }
+         assertEquals(500, map.size());
+         map.compact();
+         assertEquals(500, map.size());
+         assertTrue(map._maxSize < 1000);
+     }
+ 
  }

[Trove4j-commit] CVS: trove/test/gnu/trove/map/hash THashMapTest.java, NONE, 1.1.2.1

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

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

Added Files:
      Tag: TROVE_3_WORKING
	THashMapTest.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

--- NEW FILE: THashMapTest.java ---
///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001-2006, 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.
///////////////////////////////////////////////////////////////////////////////
[...1052 lines suppressed...]
//        assertEquals(1, m.size());
//
//        m.remove( new Integer( 1 ) );
//        assertEquals(0, m.size());
//
//        m.put( new Integer( 1 ), "one" );
//        assertEquals(1, m.size());
//    }


    public void testToString() {
        ss_map.put( "One", "1" );
        ss_map.put( "Two", "2" );

        String to_string = ss_map.toString();
        assertTrue( to_string,
                to_string.equals( "{One=1,Two=2}" ) ||
                to_string.equals( "{Two=2,One=1}" ) );
    }
} // THashMapTests

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

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

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

Added Files:
      Tag: TROVE_3_WORKING
	THashMap.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

--- NEW FILE: THashMap.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.map.hash;

import gnu.trove.impl.hash.TObjectHash;
import gnu.trove.impl.HashFunctions;
import gnu.trove.procedure.TObjectProcedure;
import gnu.trove.procedure.TObjectObjectProcedure;
import gnu.trove.function.TObjectFunction;
import gnu.trove.iterator.hash.TObjectHashIterator;

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



/**
 * An implementation of the Map interface which uses an open addressed
 * hash table to store its contents.
 * <p/>
 * Created: Sun Nov  4 08:52:45 2001
 *
 * @author Eric D. Friedman
 * @author Rob Eden
 * @author Jeff Randall
 * @version $Id: THashMap.java,v 1.1.2.1 2009/09/06 17:02:20 upholderoftruth Exp $
 */

public class THashMap<K, V> extends TObjectHash<K> implements Map<K, V>, Externalizable {

    static final long serialVersionUID = 1L;

    /** the values of the  map */
    protected transient V[] _values;


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


    /**
     * Creates a new <code>THashMap</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 THashMap( int initialCapacity ) {
        super( initialCapacity );
    }


    /**
     * Creates a new <code>THashMap</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 THashMap( int initialCapacity, float loadFactor ) {
        super( initialCapacity, loadFactor );
    }


    /**
     * Creates a new <code>THashMap</code> instance which contains the
     * key/value pairs in <tt>map</tt>.
     *
     * @param map a <code>Map</code> value
     */
    public THashMap( Map<K, V> map ) {
        this( map.size() );
        putAll( map );
    }


    /**
     * Creates a new <code>THashMap</code> instance which contains the
     * key/value pairs in <tt>map</tt>.
     *
     * @param map a <code>Map</code> value
     */
    public THashMap( THashMap<K, V> map ) {
        this( map.size() );
        putAll( map );
    }


    /**
     * initialize the value array of the map.
     *
     * @param initialCapacity an <code>int</code> value
     * @return an <code>int</code> value
     */
    public int setUp( int initialCapacity ) {
        int capacity;

        capacity = super.setUp( initialCapacity );
        //noinspection unchecked
        _values = (V[]) new Object[capacity];
        return capacity;
    }


    /**
     * Inserts a key/value pair into the map.
     *
     * @param key   an <code>Object</code> value
     * @param value an <code>Object</code> value
     * @return the previous value associated with <tt>key</tt>,
     *         or {@code null} if none was found.
     */
    public V put( K key, V value ) {
        int index = insertionIndex( key );
        return doPut( key, value, index );
    }


    /**
     * Inserts a key/value pair into the map if the specified key is not already
     * associated with a value.
     *
     * @param key   an <code>Object</code> value
     * @param value an <code>Object</code> value
     * @return the previous value associated with <tt>key</tt>,
     *         or {@code null} if none was found.
     */
    public V putIfAbsent( K key, V value ) {
        int index = insertionIndex( key );
        if ( index < 0 ) {
            return _values[-index - 1];
        }
        return doPut( key, value, index );
    }


    private V doPut( K key, V value, int index ) {
        V previous = null;
        Object oldKey;
        boolean isNewMapping = true;
        if ( index < 0 ) {
            index = -index - 1;
            previous = _values[index];
            isNewMapping = false;
        }
        oldKey = _set[index];
        _set[index] = key;
        _values[index] = value;
        if ( isNewMapping ) {
            postInsertHook( oldKey == FREE );
        }

        return previous;
    }


    /**
     * Compares this map with another map for equality of their stored
     * entries.
     *
     * @param other an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    @SuppressWarnings({"unchecked", "SimplifiableIfStatement"})
    public boolean equals( Object other ) {
        if ( !( other instanceof Map ) ) {
            return false;
        }
        Map<K, V> that = (Map<K, V>) other;
        if ( that.size() != this.size() ) {
            return false;
        }
        return forEachEntry( new EqProcedure<K, V>( that ) );
    }


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


    public String toString() {
        final StringBuilder buf = new StringBuilder( "{" );
        forEachEntry( new TObjectObjectProcedure<K, V>() {
            private boolean first = true;


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

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


    private final class HashProcedure implements TObjectObjectProcedure<K, V> {

        private int h = 0;


        public int getHashCode() {
            return h;
        }


        public final boolean execute( K key, V value ) {
            h += HashFunctions.hash( key ) ^ ( value == null ? 0 : value.hashCode() );
            return true;
        }
    }

    private static final class EqProcedure<K, V> implements TObjectObjectProcedure<K, V> {

        private final Map<K, V> _otherMap;


        EqProcedure( Map<K, V> otherMap ) {
            _otherMap = otherMap;
        }


        public final boolean execute( K key, V value ) {
            // Check to make sure the key is there. This avoids problems that come up with
            // null values. Since it is only caused in that cause, only do this when the
            // value is null (to avoid extra work).
            if ( value == null && !_otherMap.containsKey( key ) ) {
                return false;
            }

            V oValue = _otherMap.get( key );
            return oValue == value || ( oValue != null && oValue.equals( value ) );
        }
    }


    /**
     * Executes <tt>procedure</tt> for each key in the map.
     *
     * @param procedure a <code>TObjectProcedure</code> value
     * @return false if the loop over the keys terminated because
     *         the procedure returned false for some key.
     */
    public boolean forEachKey( TObjectProcedure<K> procedure ) {
        return forEach( procedure );
    }


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


    /**
     * Executes <tt>procedure</tt> for each key/value entry in the
     * map.
     *
     * @param procedure a <code>TObjectObjectProcedure</code> value
     * @return false if the loop over the entries terminated because
     *         the procedure returned false for some entry.
     */
    @SuppressWarnings({"unchecked"})
    public boolean forEachEntry( TObjectObjectProcedure<K, V> procedure ) {
        Object[] keys = _set;
        V[] values = _values;
        for ( int i = keys.length; i-- > 0; ) {
            if ( keys[i] != FREE
                 && keys[i] != REMOVED
                 && !procedure.execute( (K) keys[i], values[i] ) ) {
                return false;
            }
        }
        return true;
    }


    /**
     * Retains only those entries in the map for which the procedure
     * returns a true value.
     *
     * @param procedure determines which entries to keep
     * @return true if the map was modified.
     */
    @SuppressWarnings({"unchecked"})
    public boolean retainEntries( TObjectObjectProcedure<K, V> procedure ) {
        boolean modified = false;
        Object[] keys = _set;
        V[] values = _values;

        // Temporarily disable compaction. This is a fix for bug #1738760
        tempDisableAutoCompaction();
        try {
            for ( int i = keys.length; i-- > 0; ) {
                if ( keys[i] != FREE
                     && keys[i] != REMOVED
                     && !procedure.execute( (K) keys[i], values[i] ) ) {
                    removeAt( i );
                    modified = true;
                }
            }
        }
        finally {
            reenableAutoCompaction( true );
        }

        return modified;
    }


    /**
     * Transform the values in this map using <tt>function</tt>.
     *
     * @param function a <code>TObjectFunction</code> value
     */
    public void transformValues( TObjectFunction<V, V> function ) {
        V[] values = _values;
        Object[] set = _set;
        for ( int i = values.length; i-- > 0; ) {
            if ( set[i] != FREE && set[i] != REMOVED ) {
                values[i] = function.execute( values[i] );
            }
        }
    }


    /**
     * rehashes the map to the new capacity.
     *
     * @param newCapacity an <code>int</code> value
     */
    @SuppressWarnings({"unchecked"})
    protected void rehash( int newCapacity ) {
        int oldCapacity = _set.length;
        Object oldKeys[] = _set;
        V oldVals[] = _values;

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

        for ( int i = oldCapacity; i-- > 0; ) {
            if ( oldKeys[i] != FREE && oldKeys[i] != REMOVED ) {
                Object o = oldKeys[i];
                int index = insertionIndex( (K) o );
                if ( index < 0 ) {
                    throwObjectContractViolation( _set[( -index - 1 )], o );
                }
                _set[index] = o;
                _values[index] = oldVals[i];
            }
        }
    }


    /**
     * retrieves the value for <tt>key</tt>
     *
     * @param key an <code>Object</code> value
     * @return the value of <tt>key</tt> or null if no such mapping exists.
     */
    @SuppressWarnings({"unchecked"})
    public V get( Object key ) {
        int index = index( (K) key );
        return index < 0 ? null : _values[index];
    }


    /** Empties the map. */
    public void clear() {
        if ( size() == 0 ) {
            return; // optimization
        }

        super.clear();

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


    /**
     * Deletes a key/value pair from the map.
     *
     * @param key an <code>Object</code> value
     * @return an <code>Object</code> value
     */
    @SuppressWarnings({"unchecked"})
    public V remove( Object key ) {
        V prev = null;
        int index = index( (K) key );
        if ( index >= 0 ) {
            prev = _values[index];
            removeAt( index );    // clear key,state; adjust size
        }
        return prev;
    }


    /**
     * removes the mapping at <tt>index</tt> from the map.
     *
     * @param index an <code>int</code> value
     */
    public void removeAt( int index ) {
        _values[index] = null;
        super.removeAt( index );  // clear key, state; adjust size
    }


    /**
     * Returns a view on the values of the map.
     *
     * @return a <code>Collection</code> value
     */
    public Collection<V> values() {
        return new ValueView();
    }


    /**
     * returns a Set view on the keys of the map.
     *
     * @return a <code>Set</code> value
     */
    public Set<K> keySet() {
        return new KeyView();
    }


    /**
     * Returns a Set view on the entries of the map.
     *
     * @return a <code>Set</code> value
     */
    public Set<Map.Entry<K, V>> entrySet() {
        return new EntryView();
    }


    /**
     * checks for the presence of <tt>val</tt> in the values of the map.
     *
     * @param val an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    public boolean containsValue( Object val ) {
        Object[] set = _set;
        V[] vals = _values;

        // special case null values so that we don't have to
        // perform null checks before every call to equals()
        if ( null == val ) {
            for ( int i = vals.length; i-- > 0; ) {
                if ( ( set[i] != FREE && set[i] != REMOVED ) &&
                     val == vals[i] ) {
                    return true;
                }
            }
        } else {
            for ( int i = vals.length; i-- > 0; ) {
                if ( ( set[i] != FREE && set[i] != REMOVED ) &&
                     ( val == vals[i] || val.equals( vals[i] ) ) ) {
                    return true;
                }
            }
        } // end of else
        return false;
    }


    /**
     * checks for the present of <tt>key</tt> in the keys of the map.
     *
     * @param key an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    public boolean containsKey( Object key ) {
        return contains( key );
    }


    /**
     * copies the key/value mappings in <tt>map</tt> into this map.
     *
     * @param map a <code>Map</code> value
     */
    public void putAll( Map<? extends K, ? extends V> map ) {
        ensureCapacity( map.size() );
        // could optimize this for cases when map instanceof THashMap
        for ( Map.Entry<? extends K, ? extends V> e : map.entrySet() ) {
            put( e.getKey(), e.getValue() );
        }
    }


    /** a view onto the values of the map. */
    protected class ValueView extends MapBackedView<V> {

        @SuppressWarnings({"unchecked"})
        public Iterator<V> iterator() {
            return new TObjectHashIterator( THashMap.this ) {
                protected V objectAtIndex( int index ) {
                    return _values[index];
                }
            };
        }


        public boolean containsElement( V value ) {
            return containsValue( value );
        }


        public boolean removeElement( V value ) {
            Object[] values = _values;
            Object[] set = _set;

            for ( int i = values.length; i-- > 0; ) {
                if ( ( set[i] != FREE && set[i] != REMOVED ) &&
                     value == values[i] ||
                     ( null != values[i] && values[i].equals( value ) ) ) {

                    removeAt( i );
                    return true;
                }
            }

            return false;
        }
    }

    /** a view onto the entries of the map. */
    protected class EntryView extends MapBackedView<Map.Entry<K, V>> {

        private final class EntryIterator extends TObjectHashIterator {

            EntryIterator( THashMap<K, V> map ) {
                super( map );
            }


            @SuppressWarnings({"unchecked"})
            public Entry objectAtIndex( final int index ) {
                return new Entry( (K) _set[index], _values[index], index );
            }
        }


        @SuppressWarnings({"unchecked"})
        public Iterator<Map.Entry<K, V>> iterator() {
            return new EntryIterator( THashMap.this );
        }


        public boolean removeElement( Map.Entry<K, V> entry ) {
            // have to effectively reimplement Map.remove here
            // because we need to return true/false depending on
            // whether the removal took place.  Since the Entry's
            // value can be null, this means that we can't rely
            // on the value of the object returned by Map.remove()
            // to determine whether a deletion actually happened.
            //
            // Note also that the deletion is only legal if
            // both the key and the value match.
            Object val;
            int index;

            K key = keyForEntry( entry );
            index = index( key );
            if ( index >= 0 ) {
                val = valueForEntry( entry );
                if ( val == _values[index] ||
                     ( null != val && val.equals( _values[index] ) ) ) {
                    removeAt( index );    // clear key,state; adjust size
                    return true;
                }
            }
            return false;
        }


        public boolean containsElement( Map.Entry<K, V> entry ) {
            Object val = get( keyForEntry( entry ) );
            Object entryValue = entry.getValue();
            return entryValue == val ||
                   ( null != val && val.equals( entryValue ) );
        }


        protected V valueForEntry( Map.Entry<K, V> entry ) {
            return entry.getValue();
        }


        protected K keyForEntry( Map.Entry<K, V> entry ) {
            return entry.getKey();
        }
    }

    private abstract class MapBackedView<E> extends AbstractSet<E>
            implements Set<E>, Iterable<E> {

        public abstract Iterator<E> iterator();


        public abstract boolean removeElement( E key );


        public abstract boolean containsElement( E key );


        @SuppressWarnings({"unchecked"})
        public boolean contains( Object key ) {
            return containsElement( (E) key );
        }


        @SuppressWarnings({"unchecked"})
        public boolean remove( Object o ) {
            return removeElement( (E) o );
        }


//        public boolean containsAll( Collection<?> collection ) {
//            for ( Object element : collection ) {
//                if ( !contains( element ) ) {
//                    return false;
//                }
//            }
//            return true;
//        }


        public void clear() {
            THashMap.this.clear();
        }


        public boolean add( E obj ) {
            throw new UnsupportedOperationException();
        }


        public int size() {
            return THashMap.this.size();
        }


        public Object[] toArray() {
            Object[] result = new Object[size()];
            Iterator<E> e = iterator();
            for ( int i = 0; e.hasNext(); i++ ) {
                result[i] = e.next();
            }
            return result;
        }


        @SuppressWarnings({"unchecked"})
        public <T> T[] toArray( T[] a ) {
            int size = size();
            if ( a.length < size ) {
                a = (T[]) java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size );
            }

            Iterator<E> it = iterator();
            Object[] result = a;
            for ( int i = 0; i < size; i++ ) {
                result[i] = it.next();
            }

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

            return a;
        }


        public boolean isEmpty() {
            return THashMap.this.isEmpty();
        }


        public boolean addAll( Collection<? extends E> collection ) {
            throw new UnsupportedOperationException();
        }


        @SuppressWarnings({"SuspiciousMethodCalls"})
        public boolean retainAll( Collection<?> collection ) {
            boolean changed = false;
            Iterator<E> i = iterator();
            while ( i.hasNext() ) {
                if ( !collection.contains( i.next() ) ) {
                    i.remove();
                    changed = true;
                }
            }
            return changed;
        }
    }

    /** a view onto the keys of the map. */
    protected class KeyView extends MapBackedView<K> {

        @SuppressWarnings({"unchecked"})
        public Iterator<K> iterator() {
            return new TObjectHashIterator( THashMap.this );
        }


        public boolean removeElement( K key ) {
            return null != THashMap.this.remove( key );
        }


        public boolean containsElement( K key ) {
            return THashMap.this.contains( key );
        }
    }

    final class Entry implements Map.Entry<K, V> {

        private K key;
        private V val;
        private final int index;


        Entry( final K key, V value, final int index ) {
            this.key = key;
            this.val = value;
            this.index = index;
        }


        // TODO: remove?
//        void setKey( K aKey ) {
//            this.key = aKey;
//        }


        // TODO: remove?
        void setValue0( V aValue ) {
            this.val = aValue;
        }


        public K getKey() {
            return key;
        }


        public V getValue() {
            return val;
        }


        public V setValue( V o ) {
            if ( _values[index] != val ) {
                throw new ConcurrentModificationException();
            }
            // need to return previous value
            V retval = val;
            // update this entry's value, in case setValue is called again
            _values[index] = o;
            val = o;
            return retval;
        }


        public boolean equals( Object o ) {
            if ( o instanceof Map.Entry ) {
                Map.Entry<K, V> e1 = this;
                Map.Entry e2 = (Map.Entry) o;
                return ( e1.getKey() == null ? e2.getKey() == null : e1.getKey().equals( e2.getKey() ) )
                       && ( e1.getValue() == null ? e2.getValue() == null : e1.getValue().equals( e2.getValue() ) );
            }
            return false;
        }


        public int hashCode() {
            return ( getKey() == null ? 0 : getKey().hashCode() ) ^ ( getValue() == null ? 0 : getValue().hashCode() );
        }


        @Override
        public String toString() {
            return key + "=" + val;
        }
    }


    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
        for ( int i = _set.length; i-- > 0; ) {
            if ( _set[i] != REMOVED && _set[i] != FREE ) {
                out.writeObject( _set[i] );
                out.writeObject( _values[i] );
            }
        }
    }


    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
        while ( size-- > 0 ) {
            //noinspection unchecked
            K key = (K) in.readObject();
            //noinspection unchecked
            V val = (V) in.readObject();
            put( key, val );
        }
    }
} // THashMap

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

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

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

Modified Files:
      Tag: TROVE_3_WORKING
	THashSet.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

Index: THashSet.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/set/hash/Attic/THashSet.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
*** THashSet.java	4 Sep 2009 12:32:34 -0000	1.1.2.2
--- THashSet.java	6 Sep 2009 17:02:20 -0000	1.1.2.3
***************
*** 257,262 ****
       * @return an <code>Iterator</code> value
       */
!     public Iterator<E> iterator() {
!         return new TObjectHashIterator<E>( this );
      }
  
--- 257,263 ----
       * @return an <code>Iterator</code> value
       */
!     @SuppressWarnings({"unchecked"})
!     public TObjectHashIterator iterator() {
!         return new TObjectHashIterator( this );
      }
  

[Trove4j-commit] CVS: trove/src/gnu/trove/procedure TObjectObjectProcedure.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-serv18189/src/gnu/trove/procedure

Added Files:
      Tag: TROVE_3_WORKING
	TObjectObjectProcedure.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

--- NEW FILE: TObjectObjectProcedure.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 that take two Object parameters.
 * <p/>
 * Created: Mon Nov  5 22:03:30 2001
 *
 * @author Eric D. Friedman
 * @version $Id: TObjectObjectProcedure.java,v 1.1.2.1 2009/09/06 17:02:20 upholderoftruth Exp $
 */

public interface TObjectObjectProcedure<K, V> {

    /**
     * Executes this procedure. A false return value indicates that
     * the application executing this procedure should not invoke this
     * procedure again.
     *
     * @param a an <code>Object</code> value
     * @param b an <code>Object</code> value
     * @return true if additional invocations of the procedure are
     *         allowed.
     */
    public boolean execute( K a, V b );
}// TObjectObjectProcedure

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

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

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

Modified Files:
      Tag: TROVE_3_WORKING
	TObjectHashIterator.java THashIterator.java 
Log Message:
THashMap implementation and tests, changes required to implement it.

Index: TObjectHashIterator.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/iterator/hash/Attic/TObjectHashIterator.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
*** TObjectHashIterator.java	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- TObjectHashIterator.java	6 Sep 2009 17:02:20 -0000	1.1.2.2
***************
*** 27,42 ****
  
  /**
   * Created: Wed Nov 28 21:30:53 2001
   *
!  * @author Eric D. Friedman, Rob Eden, Jeff Randall
   * @version $Id$
   */
  
! public class TObjectHashIterator<E> extends THashIterator<E> {
  
!     protected final TObjectHash<E> _objectHash;
  
  
!     public TObjectHashIterator( TObjectHash<E> hash ) {
          super( hash );
          _objectHash = hash;
--- 27,50 ----
  
  /**
+  * Iterator for hashtables that use open addressing to resolve collisions.
+  * <p/>
+  * NOTE: This class cannot currently use Generics without causing issues
+  *       when used with THashMap, but that is hidden behind the scenes as
+  *       the Interface returned to the user does use Generics.
+  * <p/>
   * Created: Wed Nov 28 21:30:53 2001
   *
!  * @author Eric D. Friedman
!  * @author Rob Eden
!  * @author Jeff Randall
   * @version $Id$
   */
  
! public class TObjectHashIterator extends THashIterator {
  
!     protected final TObjectHash _objectHash;
  
  
!     public TObjectHashIterator( TObjectHash hash ) {
          super( hash );
          _objectHash = hash;
***************
*** 44,49 ****
  
  
!     protected E objectAtIndex( int index ) {
!         return (E) _objectHash._set[index];
      }
  
--- 52,57 ----
  
  
!     protected Object objectAtIndex( int index ) {
!         return _objectHash._set[index];
      }
  

Index: THashIterator.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/iterator/hash/Attic/THashIterator.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
*** THashIterator.java	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- THashIterator.java	6 Sep 2009 17:02:20 -0000	1.1.2.2
***************
*** 52,56 ****
  
  
!     private final TObjectHash _object_hash;
  
      /** the data structure this iterator traverses */
--- 52,56 ----
  
  
!     private final TObjectHash<V> _object_hash;
  
      /** the data structure this iterator traverses */
***************
*** 67,72 ****
  
  
!     /** Create an instance of THashIterator over the values of the TObjectHash */
!     public THashIterator( TObjectHash hash ) {
          _hash = hash;
          _expectedSize = _hash.size();
--- 67,76 ----
  
  
!     /**
!      * Create an instance of THashIterator over the values of the TObjectHash
!      *
!      * @param hash the object 
!      */
!     public THashIterator( TObjectHash<V> hash ) {
          _hash = hash;
          _expectedSize = _hash.size();

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

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

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

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

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

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

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

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

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

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

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

Modified Files:
      Tag: TROVE_3_WORKING
	TLinkedListTest.java 
Log Message:
Full test coverage of TLinkedList.

Index: TLinkedListTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/list/linked/Attic/TLinkedListTest.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
*** TLinkedListTest.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
--- TLinkedListTest.java	5 Sep 2009 00:10:06 -0000	1.1.2.3
***************
*** 544,548 ****
          }
  
!         ListIterator i;
  
          i = list.listIterator( 5 );
--- 544,548 ----
          }
  
!         ListIterator<Data> i;
  
          i = list.listIterator( 5 );
***************
*** 554,557 ****
--- 554,657 ----
  
  
+     public void testIteratorPastEnds() {
+         int size = 10;
+         Data[] data = new Data[size];
+         for ( int i = 0; i < data.length; i++ ) {
+             data[i] = new Data( i );
+             list.add( data[i] );
+         }
+ 
+         ListIterator<Data> iter = list.listIterator();
+         Data current = list.getFirst();
+         while( iter.hasNext() ) {
+             assertEquals( current, list.get( iter.nextIndex() ) );
+             assertEquals( current, iter.next() );
+             Data test = list.getNext( current );
+             if ( test != null  ) {
+                 current = test;
+             }
+         }
+ 
+         // Now at end of the list;
+         assertEquals( current, list.getLast() );
+         assertFalse( iter.hasNext() );
+         assertNull( list.getNext( current ) );
+ 
+         try {
+             iter.next();
+             fail( "Expected NoSuchElementException" );
+         }
+         catch ( NoSuchElementException ex ) {
+             // Expected
+         }
+ 
+         /// Start end and work to the front.
+         current = list.getLast();
+         iter = list.listIterator( list.size() );
+         while ( iter.hasPrevious() ) {
+             assertEquals( current, list.get( iter.previousIndex() ) );
+             assertEquals( current, iter.previous() );
+             Data test = list.getPrevious( current );
+             if ( test != null  ) {
+                 current = test;
+             }
+         }
+ 
+         // Now at front of the list;
+         assertEquals( current, list.getFirst() );
+         assertFalse( iter.hasPrevious() );
+         assertNull( list.getPrevious( current ) );
+ 
+         try {
+             iter.previous();
+             fail( "Expected NoSuchElementException" );
+         }
+         catch ( NoSuchElementException ex ) {
+             // Expected
+         }
+     }
+ 
+ 
+     public void testInvalidIterators() {
+         int size = 10;
+         Data[] data = new Data[size];
+         for ( int i = 0; i < data.length; i++ ) {
+             data[i] = new Data( i );
+             list.add( data[i] );
+         }
+ 
+         // Creating an iterator pointing before the start of the list should fail
+         try {
+             ListIterator<Data> iter = list.listIterator( -1 );
+             fail( "Expected IndexOutOfBoundsException" );
+             iter.next(); // prevent unused inspection, never reached
+         }
+         catch ( IndexOutOfBoundsException ex ) {
+             // Expected
+         }
+ 
+         // Creating an iterator pointing past the end of the list should fail
+         try {
+             ListIterator<Data> iter = list.listIterator( list.size() + 1 );
+             fail( "Expected IndexOutOfBoundsException" );
+             iter.next(); // prevent unused inspection, never reached
+         }
+         catch ( IndexOutOfBoundsException ex ) {
+             // Expected
+         }
+ 
+         // Set on a fresh iterator should fail.
+         try {
+             ListIterator<Data> iter = list.listIterator();
+             iter.set( new Data( 1138 ) );
+             fail( "Expected IllegalStateException" );
+         }
+         catch ( IllegalStateException ex ) {
+             // Expected
+         }
+ 
+     }
+ 
+ 
      public void testSerialize() throws Exception {
          TLinkedList<Data> list1 = new TLinkedList<Data>();

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Index: TLinkedListTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/list/linked/Attic/TLinkedListTest.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
*** TLinkedListTest.java	3 Sep 2009 16:16:36 -0000	1.1.2.1
--- TLinkedListTest.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 37,41 ****
   * @author Rob Eden
   * @author Jeff Randall
-  * 
   * @version $Id$
   */
--- 37,40 ----
***************
*** 71,74 ****
--- 70,143 ----
  
  
+     public void testAddAtIndex() throws Exception {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         Data to_insert = new Data( 1138 );
+         list.add( 1, to_insert );
+ 
+         assertEquals( to_insert, list.get( 1 ) );
+         assertEquals( data[0], list.get( 0 ) );
+         for ( int i = 2; i < data.length; i++ ) {
+             assertEquals( data[i - 1], list.get( i ) );
+         }
+     }
+ 
+ 
+     public void testAddIllegalArgs() {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         try {
+             list.add( -1, new Data( 1138 ) );
+             fail( "Expected IndexOutOfBoundsException" );
+         }
+         catch ( IndexOutOfBoundsException ex ) {
+             // Expected
+         }
+ 
+         try {
+             list.add( list.size() + 1, new Data( 1138 ) );
+             fail( "Expected IndexOutOfBoundsException" );
+         }
+         catch ( IndexOutOfBoundsException ex ) {
+             // Expected
+         }
+     }
+ 
+ 
+     public void testClear() {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         list.clear();
+         assertTrue( "list should be empty", list.isEmpty() );
+     }
+ 
+ 
      public void testInsert() throws Exception {
          Data[] data = {new Data( 2 ), new Data( 4 ), new Data( 6 )};
***************
*** 89,92 ****
--- 158,249 ----
  
  
+     public void testToArray() {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         Data[] data_array = list.toArray( new Data[0] );
+         assertEquals( list.size(), data_array.length );
+         for ( int i = 0; i < list.size(); i++ ) {
+             assertEquals( data_array[i], list.get( i ) );
+         }
+ 
+         Object[] obj_array = list.toArray();
+         assertEquals( list.size(), obj_array.length );
+         for ( int i = 0; i < list.size(); i++ ) {
+             assertEquals( obj_array[i], list.get( i ) );
+         }
+     }
+ 
+ 
+     public void testToUnlinkedArray() {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         Object[] data_array = list.toUnlinkedArray();
+         assertEquals( data.length, data_array.length );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], data_array[i] );
+         }
+     }
+ 
+ 
+     public void testToUnlinkedArrayTyped() {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         Data[] data_array = list.toUnlinkedArray( new Data[0] );
+         assertEquals( data.length, data_array.length );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], data_array[i] );
+         }
+     }
+ 
+ 
+     public void testContains() {
+         Data[] data = {new Data( 1 ), new Data( 2 ), new Data( 3 ),
+                        new Data( 4 ), new Data( 5 ), new Data( 6 ),
+                        new Data( 7 ), new Data( 8 ), new Data( 9 )};
+         for ( int i = 0; i < data.length; i++ ) {
+             list.add( data[i] );
+         }
+         assertEquals( data.length, list.size() );
+         for ( int i = 0; i < data.length; i++ ) {
+             assertEquals( data[i], list.get( i ) );
+         }
+ 
+         Data item = new Data( 5 );
+         assertTrue( "list contains item: " + item + ", " + list,
+                 list.contains( item ) );
+ 
+         item = new Data( 1138 );
+         assertFalse( "list doesn't contain item: "+ item + ", " + list,
+                 list.contains( item ) );
+     }
+ 
+ 
      public void testNextIterator() throws Exception {
          Data[] data = new Data[100];
***************
*** 281,284 ****
--- 438,452 ----
  
  
+     public void testRemoveInvalidObject() {
+         Object obj = new Object();
+         Data d = new Data( 1 );
+         list.add( d );
+         assertEquals( 1, list.size() );
+ 
+         assertFalse( "cannot remove elements that don't implement TLinkable",
+                 list.remove( obj ) );
+     }
+ 
+ 
      public void testIteratorAddFront() throws Exception {
          Data[] d = {new Data( 0 ), new Data( 1 ), new Data( 2 )};
***************
*** 465,469 ****
          list.addBefore( null, new Data( 6 ) );
  
!         System.out.println( "List: " + list );
  
          // Iterate forward
--- 633,637 ----
          list.addBefore( null, new Data( 6 ) );
  
! //        System.out.println( "List: " + list );
  
          // Iterate forward
***************
*** 507,511 ****
          list.addAfter( null, new Data( 0 ) );
  
!         System.out.println( "List: " + list );
  
          // Iterate forward
--- 675,679 ----
          list.addAfter( null, new Data( 0 ) );
  
! //        System.out.println( "List: " + list );
  
          // Iterate forward
***************
*** 525,529 ****
          cur = list.getLast();
          while ( cur != null ) {
!             System.out.println( "Itr back: " + cur._val );
              assertEquals( value - 1, cur._val );
              value = cur._val;
--- 693,697 ----
          cur = list.getLast();
          while ( cur != null ) {
! //            System.out.println( "Itr back: " + cur._val );
              assertEquals( value - 1, cur._val );
              value = cur._val;
***************
*** 668,677 ****
           * @param next value to assign to next.
           */
!         public void setNext( TLinkable<Data> next ) {
              this._next = next;
          }
  
  
!         protected TLinkable<Data> _previous;
  
  
--- 836,845 ----
           * @param next value to assign to next.
           */
!         public void setNext( Data next ) {
              this._next = next;
          }
  
  
!         protected Data _previous;
  
  
***************
*** 683,687 ****
           */
          public Data getPrevious() {
!             return (Data) _previous;
          }
  
--- 851,855 ----
           */
          public Data getPrevious() {
!             return _previous;
          }
  
***************
*** 692,696 ****
           * @param previous value to assign to previous.
           */
!         public void setPrevious( TLinkable<Data> previous ) {
              this._previous = previous;
          }
--- 860,864 ----
           * @param previous value to assign to previous.
           */
!         public void setPrevious( Data previous ) {
              this._previous = previous;
          }
***************
*** 703,709 ****
  
          public boolean equals( Object o ) {
!             if ( ! ( o instanceof Data ) )
                  return false;
!             
              Data that = (Data) o;
              return this._val == that._val;
--- 871,878 ----
  
          public boolean equals( Object o ) {
!             if ( !( o instanceof Data ) ) {
                  return false;
!             }
! 
              Data that = (Data) o;
              return this._val == that._val;

[Trove4j-commit] CVS: trove/templates/gnu/trove/impl/hash _E_Hash.template, 1.1.2.1, 1.1.2.2

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

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

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

Index: _E_Hash.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/impl/hash/Attic/_E_Hash.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_Hash.template	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- _E_Hash.template	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 40,44 ****
  
      /** the set of #e#s */
!     protected transient #e#[] _set;
  
      /**
--- 40,44 ----
  
      /** the set of #e#s */
!     public transient #e#[] _set;
  
      /**
***************
*** 167,172 ****
       * @param index an <code>int</code> value
       */
!     public void removeAt(int index) {
!         _set[index] = (#e#)0;
          super.removeAt( index );
      }
--- 167,172 ----
       * @param index an <code>int</code> value
       */
!     public void removeAt( int index ) {
!         _set[index] = no_entry_value;
          super.removeAt( index );
      }
***************
*** 272,286 ****
          }
      }
- 
- 
-     /**
-      * Default implementation of T#E#HashingStrategy:
-      * delegates hashing to HashFunctions.hash(#e#).
-      *
-      * @param val the value to hash
-      * @return the hashcode.
-      */
-     public final int computeHashCode( #e# val ) {
-         return HashFunctions.hash( val );
-     }
  } // T#E#Hash
--- 272,274 ----

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

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

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

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

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

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

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

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

Index: _E_ArrayStack.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/stack/array/Attic/_E_ArrayStack.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_ArrayStack.template	2 Sep 2009 21:52:33 -0000	1.1.2.7
--- _E_ArrayStack.template	4 Sep 2009 12:32:33 -0000	1.1.2.8
***************
*** 86,91 ****
       * @param stack the instance to copy
       */
!     public T#E#ArrayStack( T#E#ArrayStack stack ) {
!         this._list = new T#E#ArrayList( stack._list );
      }
  
--- 86,96 ----
       * @param stack the instance to copy
       */
!     public T#E#ArrayStack( T#E#Stack stack ) {
!         if ( stack instanceof T#E#ArrayStack ) {
!             T#E#ArrayStack array_stack = ( T#E#ArrayStack ) stack;
!             this._list = new T#E#ArrayList( array_stack._list );
!         } else {
!             throw new UnsupportedOperationException( "Only support T#E#ArrayStack" );
!         }
      }
  
***************
*** 145,149 ****
       */
      public void clear() {
!         _list.clear( DEFAULT_CAPACITY );
      }
  
--- 150,154 ----
       */
      public void clear() {
!         _list.clear();
      }
  
***************
*** 183,186 ****
--- 188,194 ----
          _list.toArray( dest, start, length );
          reverse( dest, 0, length );
+         if ( dest.length > size ) {
+             dest[size] = _list.getNoEntryValue();
+         }
      }
  

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

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

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

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

Index: TLinkedList.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/list/linked/Attic/TLinkedList.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
*** TLinkedList.java	3 Sep 2009 16:16:36 -0000	1.1.2.1
--- TLinkedList.java	4 Sep 2009 12:32:34 -0000	1.1.2.2
***************
*** 29,32 ****
--- 29,33 ----
  import java.util.ListIterator;
  import java.util.NoSuchElementException;
+ import java.lang.reflect.Array;
  
  
***************
*** 223,226 ****
--- 224,254 ----
  
      /**
+      * Returns a typed array of the objects in the set.
+      *
+      * @param a an <code>Object[]</code> value
+      * @return an <code>Object[]</code> value
+      */
+     @SuppressWarnings({"unchecked"})
+     public T[] toUnlinkedArray( T[] a ) {
+         int size = size();
+         if ( a.length < size ) {
+             a = (T[]) Array.newInstance( a.getClass().getComponentType(), size );
+         }
+ 
+         int i = 0;
+         for ( T link = _head, tmp; link != null; i++ ) {
+             a[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 a;
+     }
+ 
+ 
+     /**
       * A linear search for <tt>o</tt> in the list.
       *
***************
*** 253,257 ****
  
              while ( position > index ) {
!                 node = (T) node.getPrevious();
                  position--;
              }
--- 281,285 ----
  
              while ( position > index ) {
!                 node = node.getPrevious();
                  position--;
              }
***************
*** 263,267 ****
  
              while ( position < index ) {
!                 node = (T) node.getNext();
                  position++;
              }
--- 291,295 ----
  
              while ( position < index ) {
!                 node = node.getNext();
                  position++;
              }
***************
*** 309,313 ****
      @SuppressWarnings({"unchecked"})
      public T getNext( T current ) {
!         return (T) current.getNext();
      }
  
--- 337,341 ----
      @SuppressWarnings({"unchecked"})
      public T getNext( T current ) {
!         return current.getNext();
      }
  
***************
*** 330,334 ****
      @SuppressWarnings({"unchecked"})
      public T getPrevious( T current ) {
!         return (T) current.getPrevious();
      }
  
--- 358,362 ----
      @SuppressWarnings({"unchecked"})
      public T getPrevious( T current ) {
!         return current.getPrevious();
      }
  
***************
*** 347,351 ****
          }
  
!         T n = (T) o.getNext();
          o.setNext( null );
  
--- 375,379 ----
          }
  
!         T n = o.getNext();
          o.setNext( null );
  
***************
*** 375,379 ****
          }
  
!         T prev = (T) o.getPrevious();
          o.setPrevious( null );
  
--- 403,407 ----
          }
  
!         T prev = o.getPrevious();
          o.setPrevious( null );
  
***************
*** 411,415 ****
              T node = get( index );
  
!             T before = (T) node.getPrevious();
              if ( before != null ) {
                  before.setNext( linkable );
--- 439,443 ----
              T node = get( index );
  
!             T before = node.getPrevious();
              if ( before != null ) {
                  before.setNext( linkable );
***************
*** 439,444 ****
              TLinkable<T> link = (TLinkable<T>) o;
  
!             p = (T) link.getPrevious();
!             n = (T) link.getNext();
  
              if ( n == null && p == null ) { // emptying the list
--- 467,472 ----
              TLinkable<T> link = (TLinkable<T>) o;
  
!             p = link.getPrevious();
!             n = link.getNext();
  
              if ( n == null && p == null ) { // emptying the list
***************
*** 491,495 ****
              addLast( newElement );
          } else {
!             TLinkable<T> p = current.getPrevious();
              newElement.setNext( current );
              p.setNext( newElement );
--- 519,523 ----
              addLast( newElement );
          } else {
!             T p = current.getPrevious();
              newElement.setNext( current );
              p.setNext( newElement );
***************
*** 516,520 ****
              addFirst( newElement );
          } else {
!             TLinkable<T> n = current.getNext();
              newElement.setPrevious( current );
              newElement.setNext( n );
--- 544,548 ----
              addFirst( newElement );
          } else {
!             T n = current.getNext();
              newElement.setPrevious( current );
              newElement.setNext( n );
***************
*** 542,546 ****
              }
  
!             node = (T) node.getNext();
          }
  
--- 570,574 ----
              }
  
!             node = node.getNext();
          }
  
***************
*** 610,619 ****
                  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();
                  }
              }
--- 638,647 ----
                  int pos = 0;
                  for ( _next = _head; pos < position; pos++ ) {
!                     _next = _next.getNext();
                  }
              } else {
                  int pos = _size - 1;
                  for ( _next = _tail; pos > position; pos-- ) {
!                     _next = _next.getPrevious();
                  }
              }
***************
*** 673,677 ****
  
              _lastReturned = _next;
!             _next = (T) _next.getNext();
              _nextIndex++;
              return _lastReturned;
--- 701,705 ----
  
              _lastReturned = _next;
!             _next = _next.getNext();
              _nextIndex++;
              return _lastReturned;
***************
*** 706,710 ****
                  _lastReturned = _next = _tail;
              } else {
!                 _lastReturned = _next = (T) _next.getPrevious();
              }
  
--- 734,738 ----
                  _lastReturned = _next = _tail;
              } else {
!                 _lastReturned = _next = _next.getPrevious();
              }
  
***************
*** 741,745 ****
                  _nextIndex--;
              }
!             _next = (T) _lastReturned.getNext();
              TLinkedList.this.remove( _lastReturned );
              _lastReturned = null;
--- 769,773 ----
                  _nextIndex--;
              }
!             _next = _lastReturned.getNext();
              TLinkedList.this.remove( _lastReturned );
              _lastReturned = null;
***************
*** 780,785 ****
           */
          private void swap( T from, T to ) {
!             TLinkable<T> p = from.getPrevious();
!             TLinkable<T> n = from.getNext();
  
              if ( null != p ) {
--- 808,813 ----
           */
          private void swap( T from, T to ) {
!             T p = from.getPrevious();
!             T n = from.getNext();
  
              if ( null != p ) {

[Trove4j-commit] CVS: trove/test/gnu/trove TStackTest.java, 1.1.4.2, 1.1.4.3

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

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

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

Index: TStackTest.java
===================================================================
RCS file: /cvsroot/trove4j/trove/test/gnu/trove/TStackTest.java,v
retrieving revision 1.1.4.2
retrieving revision 1.1.4.3
diff -C2 -d -r1.1.4.2 -r1.1.4.3
*** TStackTest.java	2 Sep 2009 21:52:33 -0000	1.1.4.2
--- TStackTest.java	4 Sep 2009 12:32:33 -0000	1.1.4.3
***************
*** 24,27 ****
--- 24,33 ----
  import gnu.trove.stack.TIntStack;
  import gnu.trove.stack.array.TIntArrayStack;
+ import gnu.trove.list.array.TIntArrayList;
+ 
+ import java.io.ByteArrayOutputStream;
+ import java.io.ObjectOutputStream;
+ import java.io.ByteArrayInputStream;
+ import java.io.ObjectInputStream;
  
  
***************
*** 43,46 ****
--- 49,74 ----
  
  
+     public void testConstructors() {
+         TIntStack stack = new TIntArrayStack();
+         assertEquals( 0, stack.size() );
+ 
+         stack.push( 10 );
+         stack.push( 20 );
+         assertEquals( 2, stack.size() );
+ 
+         TIntStack other = new TIntArrayStack( 20 );
+         other.push( 10 );
+         other.push( 20 );
+         assertEquals( 2, other.size() );
+ 
+         assertTrue( "stacks should be equal: " + stack + ", " + other,
+                 stack.equals( other ) );
+ 
+         TIntStack copy = new TIntArrayStack( stack );
+         assertTrue( "stacks should be equal: " + stack + ", " + copy,
+                 stack.equals( copy ) );
+     }
+ 
+ 
      public void testBasic() {
          TIntStack stack = new TIntArrayStack();
***************
*** 72,76 ****
  
      public void testArrays() {
!         TIntStack stack = new TIntArrayStack();
  
          int[] array;
--- 100,106 ----
  
      public void testArrays() {
!         int no_entry_value = Integer.MIN_VALUE;
!         TIntStack stack = new TIntArrayStack(10, no_entry_value);
!         assertEquals( no_entry_value, stack.getNoEntryValue() );
  
          int[] array;
***************
*** 114,118 ****
--- 144,240 ----
          assertEquals( 40, array_too_short[0] );
          assertEquals( 30, array_too_short[1] );
+     }
+ 
+ 
+     public void testClear() {
+         TIntStack stack = new TIntArrayStack();
+ 
+         assertEquals( 0, stack.size() );
+ 
+         stack.push( 10 );
+ 
+         assertEquals( 1, stack.size() );
+         assertEquals( 10, stack.pop() );
+         assertEquals( 0, stack.size() );
+ 
+         stack.push( 10 );
+         stack.push( 20 );
+         stack.push( 30 );
+ 
+         assertEquals( 3, stack.size() );
+         stack.clear();
+ 
+         assertEquals( 0, stack.size() );
+     }
+ 
+ 
+     public void testEquals() {
+         TIntStack stack = new TIntArrayStack();
+         assertEquals( 0, stack.size() );
+ 
+         stack.push( 10 );
+         stack.push( 20 );
+         assertEquals( 2, stack.size() );
+ 
+         TIntStack other = new TIntArrayStack( 20 );
+         other.push( 10 );
+         other.push( 20 );
+         assertEquals( 2, other.size() );
+ 
+         assertTrue( "stacks should equal itself: " + stack,
+                 stack.equals( stack ) );
+ 
+         assertTrue( "stacks should be equal: " + stack + ", " + other,
+                 stack.equals( other ) );
+ 
+         TIntArrayList list = new TIntArrayList( stack.toArray() );
+         assertFalse( "stack should not equal list: " + stack + ", " + list,
+                 stack.equals( list ) );
+     }
+ 
+ 
+     public void testHashCode() {
+         TIntStack stack = new TIntArrayStack();
+         assertEquals( 0, stack.size() );
+ 
+         stack.push( 10 );
+         stack.push( 20 );
+         assertEquals( 2, stack.size() );
+ 
+         TIntStack other = new TIntArrayStack( 20 );
+         other.push( 10 );
+         other.push( 20 );
+         assertEquals( 2, other.size() );
+ 
+         assertTrue( "stack hashcode should equal itself: " + stack,
+                 stack.hashCode() == stack.hashCode() );
+ 
+         assertTrue( "stacks should be equal: " + stack + ", " + other,
+                 stack.hashCode() == other.hashCode() );
+ 
+         other.push( 30 );
+         assertFalse( "stack should not equal list: " + stack + ", " + other,
+                 stack.hashCode() == other.hashCode() );
+     }
  
+ 
+     public void testSerialize() throws Exception {
+         TIntStack stack = new TIntArrayStack();
+         stack.push( 10 );
+         stack.push( 20 );
+         stack.push( 30 );
+         stack.push( 40 );
+         stack.push( 50 );
+ 
+         ByteArrayOutputStream baos = new ByteArrayOutputStream();
+         ObjectOutputStream oos = new ObjectOutputStream( baos );
+         oos.writeObject( stack );
+ 
+         ByteArrayInputStream bais = new ByteArrayInputStream( baos.toByteArray() );
+         ObjectInputStream ois = new ObjectInputStream( bais );
+ 
+         TIntStack serialized = (TIntStack) ois.readObject();
+ 
+         assertEquals( stack, serialized );
      }
  }

[Trove4j-commit] CVS: trove/src/gnu/trove/iterator/hash TPrimitiveIterator.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-serv14944/src/gnu/trove/iterator/hash

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

--- NEW FILE: TPrimitiveIterator.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.iterator.TIterator;
import gnu.trove.impl.hash.TPrimitiveHash;

import java.util.ConcurrentModificationException;
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 TPrimitiveIterator implements TIterator {

    /** the data structure this iterator traverses */
    protected final TPrimitiveHash _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;



    /**
     * Creates a <tt>TPrimitiveIterator</tt> for the specified collection.
     *
     * @param hash the <tt>TPrimitiveHash</tt> we want to iterate over.
     */
    public TPrimitiveIterator( TPrimitiveHash hash ) {
        _hash = hash;
        _expectedSize = _hash.size();
        _index = _hash.capacity();
    }


    /**
     * 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();
        }

        byte[] states = _hash._states;
        int i = _index;
        while ( i-- > 0 && ( states[i] != TPrimitiveHash.FULL ) ) {
            ;
        }
        return i;
    }


    /**
     * 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();
        }
    }



} // TPrimitiveIterator

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

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

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

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

Index: _E_HashSet.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/set/hash/Attic/_E_HashSet.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_HashSet.template	2 Sep 2009 21:52:33 -0000	1.1.2.1
--- _E_HashSet.template	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 23,27 ****
  import gnu.trove.set.T#E#Set;
  import gnu.trove.iterator.T#E#Iterator;
! import gnu.trove.iterator.array.T#E#ArrayIterator;
  import gnu.trove.procedure.T#E#Procedure;
  import gnu.trove.impl.*;
--- 23,27 ----
  import gnu.trove.set.T#E#Set;
  import gnu.trove.iterator.T#E#Iterator;
! import gnu.trove.iterator.hash.T#E#HashIterator;
  import gnu.trove.procedure.T#E#Procedure;
  import gnu.trove.impl.*;
***************
*** 75,78 ****
--- 75,91 ----
  
      /**
+      * Creates a new <code>TIntHash</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 load_factor used to calculate the threshold over which
+      * rehashing takes place.
+      */
+     public T#E#HashSet( int initialCapacity, float load_factor ) {
+         super( initialCapacity, load_factor );
+     }
+ 
+ 
+     /**
       * Creates a new <code>T#E#HashSet</code> instance with a prime
       * capacity equal to or greater than <tt>initial_capacity</tt> and
***************
*** 83,86 ****
--- 96,100 ----
       * @param no_entry_value a <code>#e#</code> value that represents null.
       */
+     @SuppressWarnings({"RedundantCast"})
      public T#E#HashSet( int initial_capacity, float load_factor,
              #e# no_entry_value ) {
***************
*** 105,116 ****
  
      /**
!      * Creates a new <code>T#E#HashSet</code> instance with the default
!      * capacity and load factor.
       *
!      * @param set a <tt>T#E#HashSet</tt> that will be duplicated.
       */
!     public T#E#HashSet( T#E#HashSet set ) {
!         this( Math.max( set.size(), DEFAULT_CAPACITY ),
!                 set._loadFactor, set.no_entry_value );
          addAll( set );
      }
--- 119,135 ----
  
      /**
!      * Creates a new <code>T#E#HashSet</code> instance that is a copy
!      * of the existing set.
       *
!      * @param set a <tt>T#E#Set</tt> that will be duplicated.
       */
!     public T#E#HashSet( T#E#Set set ) {
!         this( Math.max( set.size(), DEFAULT_CAPACITY ) );
!         if ( set instanceof T#E#HashSet ) {
!             T#E#HashSet hashset = ( T#E#HashSet ) set;
!             this._loadFactor = hashset._loadFactor;
!             this.no_entry_value = hashset.no_entry_value;
!             setUp( (int) Math.ceil( DEFAULT_CAPACITY / _loadFactor ) );
!         }
          addAll( set );
      }
***************
*** 121,125 ****
       */
      public T#E#Iterator iterator() {
!         return new T#E#ArrayIterator(this);
      }
  
--- 140,144 ----
       */
      public T#E#Iterator iterator() {
!         return new T#E#HashIterator( this );
      }
  
***************
*** 365,368 ****
--- 384,390 ----
       */
      public boolean retainAll( T#E#Set set ) {
+         if ( this == set ) {
+             return false;
+         }
          boolean modified = false;
  	    T#E#Iterator iter = iterator();
***************
*** 471,498 ****
  
      /**
-      * Delete the record at <tt>index</tt>.
-      *
-      * @param index an <code>int</code> value
-      */
-     public void removeAt( int index ) {
-         _set[index] = no_entry_value;
-         _states[index] = REMOVED;
- 
-         _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();
-             }
-         }
-     }
- 
- 
-     /**
       * Expands the set to accommodate new values.
       *
--- 493,496 ----
***************
*** 519,570 ****
  
      /**
-      * 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:
-      *
-      * <ol>
-      * <li> You'll free memory allocated to the table but no
-      * longer needed because of the remove()s.</li>
-      *
-      * <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());
-         }
-     }
- 
- 
-     /**
-      * 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 ) {
-         byte[] states = _states;
-         #e#[] set = _set;
-         for ( int i = set.length; i-- > 0; ) {
-             if ( states[i] == FULL && ! procedure.execute( set[i] ) ) {
-                 return false;
-             }
-         }
-         return true;
-     }
- 
- 
-     /**
       * Compares this set with another set for equality of their stored
       * entries.
--- 517,520 ----
***************
*** 610,614 ****
  
  
!    public void writeExternal( ObjectOutput out ) throws IOException {
  
      	// VERSION
--- 560,580 ----
  
  
!     public String toString() {
!         StringBuilder buffy = new StringBuilder( _size * 2 + 2 );
!         buffy.append("{");
!         for ( int i = _states.length, j = 1; i-- > 0; ) {
!             if ( _states[i] == FULL ) {
!                 buffy.append( _set[i] );
!                 if ( j++ < _size ) {
!                     buffy.append( "," );
!                 }
!             }
!         }
!         buffy.append("}");
!         return buffy.toString();
!     }
! 
! 
!     public void writeExternal( ObjectOutput out ) throws IOException {
  
      	// VERSION
***************
*** 633,636 ****
--- 599,603 ----
  
  
+     @SuppressWarnings({"RedundantCast"})
      public void readExternal( ObjectInput in )
      	throws IOException, ClassNotFoundException {

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

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

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

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

--- NEW FILE: _E_HashIterator.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.hash;

import gnu.trove.impl.hash.T#E#Hash;
import gnu.trove.iterator.T#E#Iterator;

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


/**
 * Iterator for byte collections.
 *
 * @author Eric D. Friedman
 * @author Rob Eden
 * @author Jeff Randall
 * @version $Id: _E_HashIterator.template,v 1.1.2.1 2009/09/04 12:32:33 upholderoftruth Exp $
 */

public class T#E#HashIterator extends TPrimitiveIterator implements T#E#Iterator {

    /** the collection on which the iterator operates */
    private final T#E#Hash _hash;


    /**
     * Creates a T#E#Iterator for the elements in the specified collection.
     *
     * @param hash the <tt>T#E#Hash</tt> collection to iterate over.
     */
    public T#E#HashIterator( T#E#Hash hash ) {
	    super( hash );
	    this._hash = hash;
    }


    /**
     * Advances the iterator to the next element in the underlying collection
     * and returns it.
     *
     * @return the next <tt>#e#</tt> in the collection
     * @exception NoSuchElementException if the iterator is already exhausted
     */
    public #e# next() {
	    moveToNextIndex();
	    return _hash._set[_index];
    }
}// T#E#Iterator

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

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

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

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

Index: TLinkable.java
===================================================================
RCS file: /cvsroot/trove4j/trove/src/gnu/trove/list/Attic/TLinkable.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
*** TLinkable.java	3 Sep 2009 16:16:35 -0000	1.1.2.1
--- TLinkable.java	4 Sep 2009 12:32:33 -0000	1.1.2.2
***************
*** 38,42 ****
       * @return a <code>TLinkable</code> value
       */
!     public TLinkable<T> getNext();
  
  
--- 38,42 ----
       * @return a <code>TLinkable</code> value
       */
!     public T getNext();
  
  
***************
*** 46,50 ****
       * @return a <code>TLinkable</code> value
       */
!     public TLinkable<T> getPrevious();
  
  
--- 46,50 ----
       * @return a <code>TLinkable</code> value
       */
!     public T getPrevious();
  
  
***************
*** 54,58 ****
       * @param linkable a <code>TLinkable</code> value
       */
!     public void setNext( TLinkable<T> linkable );
  
  
--- 54,58 ----
       * @param linkable a <code>TLinkable</code> value
       */
!     public void setNext( T linkable );
  
  
***************
*** 62,65 ****
       * @param linkable a <code>TLinkable</code> value
       */
!     public void setPrevious( TLinkable<T> linkable );
  }// TLinkable
--- 62,65 ----
       * @param linkable a <code>TLinkable</code> value
       */
!     public void setPrevious( T linkable );
  }// TLinkable

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

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

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

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

Index: _E_ArrayList.template
===================================================================
RCS file: /cvsroot/trove4j/trove/templates/gnu/trove/list/array/Attic/_E_ArrayList.template,v
retrieving revision 1.1.2.8
retrieving revision 1.1.2.9
diff -C2 -d -r1.1.2.8 -r1.1.2.9
*** _E_ArrayList.template	2 Sep 2009 21:52:33 -0000	1.1.2.8
--- _E_ArrayList.template	4 Sep 2009 12:32:34 -0000	1.1.2.9
***************
*** 62,65 ****
--- 62,66 ----
       * default capacity.
       */
+     @SuppressWarnings({"RedundantCast"})
      public T#E#ArrayList() {
          this( DEFAULT_CAPACITY, ( #e# ) 0 );
***************
*** 73,76 ****
--- 74,78 ----
       * @param capacity an <code>int</code> value
       */
+     @SuppressWarnings({"RedundantCast"})
      public T#E#ArrayList( int capacity ) {
          this( capacity, ( #e# ) 0 );
***************
*** 97,104 ****
       * @param list the instance to copy
       */
!     public T#E#ArrayList ( T#E#ArrayList list ) {
!         this._data = list.toArray();
!         this._pos = list._pos;
!         this.no_entry_value = list.no_entry_value;
      }
  
--- 99,111 ----
       * @param list the instance to copy
       */
!     public T#E#ArrayList ( T#E#List list ) {
!          if ( list instanceof T#E#ArrayList ) {
!             T#E#ArrayList array_list = ( T#E#ArrayList ) list;
!             this._data = array_list.toArray();
!             this._pos = array_list._pos;
!             this.no_entry_value = array_list.no_entry_value;
!         } else {
!             throw new UnsupportedOperationException( "only supports T#E#ArrayList" );
!         }
      }
  
***************
*** 412,416 ****
      public void reset() {
          _pos = 0;
!         fill( ( #e# ) 0 );
      }
  
--- 419,423 ----
      public void reset() {
          _pos = 0;
!         Arrays.fill( _data, no_entry_value );
      }
  

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

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

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

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

--- NEW FILE: TPrimitiveArrayListTest.java ---
package gnu.trove.list.array;

import junit.framework.TestCase;

import java.util.Arrays;
import java.io.ByteArrayOutputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectInputStream;
import java.io.ByteArrayInputStream;

import gnu.trove.list.TIntList;
import gnu.trove.impl.Constants;
import gnu.trove.procedure.TIntProcedure;
import gnu.trove.function.TIntFunction;



public class TPrimitiveArrayListTest extends TestCase {

    private TIntList list;


    public void setUp() throws Exception {
        super.setUp();

        list = new TIntArrayList();
        list.add( 1 );
        list.add( 2 );
        list.add( 3 );
        list.add( 4 );
        list.add( 5 );
    }


    public void tearDown() throws Exception {
        super.tearDown();
    }


    public void testGet() {

        assertEquals( 4, list.get( 3 ) );

        try {
            list.get( 10 );
            fail( "Expected IndexOutOfBoundsException" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // Expected
        }

        int element_count = 10;
        TIntArrayList array_list = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            array_list.add( i );
        }

        for ( int i = 0; i < array_list.size(); i++ ) {
            int expected = i + 1;
            assertEquals( expected, array_list.getQuick( i ) );
        }

        try {
            array_list.getQuick( 100 );
            fail( "Expected IndexOutOfBoundsException" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // Expected
        }

    }


    public void testContains() {
        int element_count = 10;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        for ( int i = 1; i <= element_count; i++ ) {
            assertTrue( "element " + i + " not found in " + a, a.contains( i ) );
        }

        assertFalse( "list doesn't hold MAX_VALUE: " + a,
                a.contains( Integer.MAX_VALUE ) );
    }


    public void testInsert() {
        int element_count = 10;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        int testval = 1138;
        a.insert( 5, testval );

        for ( int i = 0; i < 5; i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        assertEquals( testval, a.get( 5 ) );

        for ( int i = 6; i < a.size(); i++ ) {
            int result = a.get( i );
            assertTrue( "element " + result + " should be " + i,
                    result == i );
        }
    }


    public void testInsertArray() {
        int element_count = 10;
        int[] ints = {1138, 42, 86, 99, 101};

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.insert( 0, ints );
        assertEquals( ints.length + element_count, a.size() );

        for ( int i = 0; i < ints.length; i++ ) {
            assertEquals( ints[i], a.get( i ) );
        }
        for ( int i = ints.length, j = 1;
              i < ints.length + element_count;
              i++, j++ ) {
            assertEquals( j, a.get( i ) );
        }
    }


    public void testInsertAtEnd() {
        int element_count = 10;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.insert( a.size(), 11 );

        for ( int i = 0; i < element_count; i++ ) {
            assertEquals( i + 1, a.get( i ) );
        }
        for ( int i = element_count;
              i < a.size();
              i++ ) {
            int expected = i + 1;
            assertEquals( expected, a.get( i ) );
        }
    }


    public void testInsertArrayAtEnd() {
        int element_count = 10;
        int[] ints = {1138, 42, 86, 99, 101};

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.insert( a.size(), ints );

        for ( int i = 0; i < element_count; i++ ) {
            assertEquals( i + 1, a.get( i ) );
        }
        for ( int i = element_count, j = 0;
              i < ints.length + element_count;
              i++, j++ ) {
            assertEquals( ints[j], a.get( i ) );
        }
    }


    public void testSetArray() {
        int element_count = 10;
        int[] ints = {1138, 42, 86, 99, 101};

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.set( a.size() - ints.length, ints );

        for ( int i = 0; i < element_count - ints.length; i++ ) {
            assertEquals( i + 1, a.get( i ) );
        }
        for ( int i = element_count - ints.length, j = 0;
              i < a.size();
              i++, j++ ) {
            assertEquals( ints[j], a.get( i ) );
        }

        try {
            a.set( a.size(), ints );
            fail( "Expected IndexOutOfBoundsException" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // Expected
        }
    }


    public void testSet() {
        int element_count = 10;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        int testval = 1138;
        a.set( 5, testval );

        for ( int i = 0; i < 5; i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        assertEquals( testval, a.get( 5 ) );

        for ( int i = 6; i < a.size(); i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        try {
            a.set( 100, 20 );
            fail( "Expected IndexOutOfBoundsException" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // Expected
        }
    }


    public void testSetQuick() {
        int element_count = 10;

        TIntArrayList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        int testval = 1138;
        a.setQuick( 5, testval );

        for ( int i = 0; i < 5; i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        assertEquals( testval, a.get( 5 ) );

        for ( int i = 6; i < a.size(); i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        try {
            a.setQuick( 100, 20 );
            fail( "Expected IndexOutOfBoundsException" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // Expected
        }
    }


    public void testReplace() {
        int element_count = 10;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        int testval = 1138;
        assertEquals( 6, a.replace( 5, testval ) );

        for ( int i = 0; i < 5; i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        assertEquals( testval, a.get( 5 ) );

        for ( int i = 6; i < a.size(); i++ ) {
            int result = a.get( i );
            int expected = i + 1;
            assertTrue( "element " + result + " should be " + expected,
                    result == expected );
        }

        try {
            a.replace( 100, 20 );
            fail( "Expected IndexOutOfBoundsException" );
        }
        catch ( IndexOutOfBoundsException ex ) {
            // Expected
        }
    }


    public void testRemove() {
        int element_count = 10;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.remove( 5 );
        for ( int i = 0; i < 4; i++ ) {
            int expected = i + 1;
            assertTrue( "index " + i + " expected " + expected, a.get( i ) == expected );
        }
        for ( int i = 5; i < a.size(); i++ ) {
            int expected = i + 2;
            assertTrue( "index " + i + " expected " + expected, a.get( i ) == expected );
        }
    }


    public void testRemoveMultiple() {
        int element_count = 20;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        // Remove odd offsets, which are even numbers.
        for ( int i = element_count; i >= 0; i-- ) {
            if ( i % 2 == 1 ) {
                a.remove( i );
            }
        }

        for ( int i = 0; i < a.size(); i++ ) {
            int expected = i * 2 + 1;
            assertTrue( "index " + i + " expected " + expected, a.get( i ) == expected );
        }
    }


    public void testRemoveChunk() {
        int element_count = 20;

        TIntList a = new TIntArrayList();
        assertTrue( a.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.remove( 5, 10 );

        for ( int i = 0; i < 4; i++ ) {
            int expected = i + 1;
            assertTrue( "index " + i + " expected " + expected, a.get( i ) == expected );
        }
        for ( int i = 5; i < a.size(); i++ ) {
            int expected = i + 11;
            assertTrue( "index " + i + " expected " + expected +
                        " but got " + a.get( i ), a.get( i ) == expected );
        }

        try {
            a.remove( -1, 10 );
            fail( "Expected ArrayIndexOutOfBoundsException" );
        }
        catch ( ArrayIndexOutOfBoundsException ex ) {
            // Expected
        }

        try {
            a.remove( a.size(), 1 );
            fail( "Expected ArrayIndexOutOfBoundsException" );
        }
        catch ( ArrayIndexOutOfBoundsException ex ) {
            // Expected
        }
    }


    public void testEnsureCapacity() {
        int size = 1000;
        TIntArrayList array_list = new TIntArrayList();
        int initial_length = array_list._data.length;
        assertEquals( Constants.DEFAULT_CAPACITY, initial_length );

        array_list.ensureCapacity( size );
        int max_length = array_list._data.length;
        assertTrue( "not large enough: " + max_length + " should be >= " + size,
                max_length >= size );
    }


    public void testTrimToSize() {
        int initial_size = 1000;
        int element_count = 100;

        TIntArrayList array_list = new TIntArrayList( initial_size );
        int initial_length = array_list._data.length;
        assertEquals( initial_size, initial_length );
        assertTrue( array_list.isEmpty() );

        for ( int i = 1; i <= element_count; i++ ) {
            array_list.add( i );
        }
        array_list.trimToSize();

        int trimmed_length = array_list._data.length;
        assertTrue( "not trimmed: " + trimmed_length + " should be == " + element_count,
                trimmed_length == element_count );
    }


    public void testToArray() {
        assertTrue( Arrays.equals( new int[]{1, 2, 3, 4, 5}, list.toArray() ) );
        assertTrue( Arrays.equals( new int[]{1, 2, 3, 4}, list.toArray( 0, 4 ) ) );
        assertTrue( Arrays.equals( new int[]{2, 3, 4, 5}, list.toArray( 1, 4 ) ) );
        assertTrue( Arrays.equals( new int[]{2, 3, 4}, list.toArray( 1, 3 ) ) );

        try {
            list.toArray( -1, 5 );
            fail( "Expected ArrayIndexOutOfBoundsException when begin < 0" );
        }
        catch ( ArrayIndexOutOfBoundsException expected ) {
            // Expected
        }
    }


    public void testSubList() throws Exception {
        TIntList subList = list.subList( 1, 4 );
        assertEquals( 3, subList.size() );
        assertEquals( 2, subList.get( 0 ) );
        assertEquals( 4, subList.get( 2 ) );
    }


    public void testSublist_Exceptions() {
        try {
            list.subList( 1, 0 );
            fail( "expected IllegalArgumentException when end < begin" );
        }
        catch ( IllegalArgumentException expected ) {
        }

        try {
            list.subList( -1, 3 );
            fail( "expected IndexOutOfBoundsException when begin < 0" );
        }
        catch ( IndexOutOfBoundsException expected ) {
        }

        try {
            list.subList( 1, 42 );
            fail( "expected IndexOutOfBoundsException when end > length" );
        }
        catch ( IndexOutOfBoundsException expected ) {
        }
    }


    public void testIndexOf() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        int index = a.indexOf( 10 );
        assertEquals( 9, index );

        // Add more elements, but duplicates
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }
        index = a.indexOf( 10 );
        assertEquals( 9, index );

        index = a.indexOf( 5 );
        assertEquals( 4, index );

        index = a.lastIndexOf( 5 );
        assertEquals( 24, index );

        // Non-existant entry
        index = a.indexOf( 100 );
        assertEquals( -1, index );
    }


    public void testBinarySearch() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.sort();

        int index = a.binarySearch( 5 );
        assertEquals( 4, index );

        index = a.binarySearch( 8 );
        assertEquals( 7, index );

        // Add more elements, but duplicates
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.sort();

        index = a.indexOf( 5 );
        assertTrue( "index: " + index, index >= 8 && index <= 9 );

        // Not in this range.
        index = a.binarySearch( 5, 15, 30 );
        assertTrue( "index: " + index, index < 0 );

        try {
            a.binarySearch( 5, 10, 55 );
            fail( "Expected ArrayIndexOutOfBoundsException" );
        }
        catch ( ArrayIndexOutOfBoundsException ex ) {
            // Expected
        }

        try {
            a.binarySearch( 5, -1, 15 );
            fail( "Expected ArrayIndexOutOfBoundsException" );
        }
        catch ( ArrayIndexOutOfBoundsException ex ) {
            // Expected
        }
    }


    public void testFill() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.fill( 0xdeadbeef );
        for ( int i = 0; i < element_count; i++ ) {
            assertEquals( 0xdeadbeef, a.get( i ) );
        }
    }


    public void testFillOffsets() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.fill( 10, 15, 0xdeadbeef );
        for ( int i = 0; i < 10; i++ ) {
            assertEquals( i + 1, a.get( i ) );
        }
        for ( int i = 10; i < 15; i++ ) {
            assertEquals( 0xdeadbeef, a.get( i ) );
        }
        for ( int i = 15; i < a.size(); i++ ) {
            assertEquals( i + 1, a.get( i ) );
        }

        a.fill( 15, 25, 0xcafebabe );
        assertEquals( 25, a.size() );
        for ( int i = 0; i < 10; i++ ) {
            assertEquals( i + 1, a.get( i ) );
        }
        for ( int i = 10; i < 15; i++ ) {
            assertEquals( 0xdeadbeef, a.get( i ) );
        }
        for ( int i = 15; i < a.size(); i++ ) {
            assertEquals( 0xcafebabe, a.get( i ) );
        }
    }


    public void testReset() {
        int element_count = 20;
        TIntArrayList a = new TIntArrayList( 20, Integer.MIN_VALUE );
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        assertEquals( element_count, a.size() );
        a.reset();
        assertEquals( 0, a.size() );

        for ( int i = 0; i < element_count; i++ ) {
            int expected = a.getQuick( i );
            assertTrue( "index " + i + " is " + expected,
                    a.getNoEntryValue() == expected );
        }
    }


    public void testGrep() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i < element_count; i++ ) {
            a.add( i );
        }

        TIntList grepped = a.grep( new TIntProcedure() {
            public boolean execute( int value ) {
                return value > 10;
            }
        } );

        for ( int i = 0; i < grepped.size(); i++ ) {
            int expected = i + 11;
            assertEquals( expected, grepped.get( i ) );
        }
    }


    public void testInverseGrep() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i < element_count; i++ ) {
            a.add( i );
        }

        TIntList grepped = a.inverseGrep( new TIntProcedure() {
            public boolean execute( int value ) {
                return value <= 10;
            }
        } );

        for ( int i = 0; i < grepped.size(); i++ ) {
            int expected = i + 11;
            assertEquals( expected, grepped.get( i ) );
        }
    }


    public void testMax() {
        assertEquals( 5, list.max() );
        assertEquals( 1, list.min() );

        TIntList list2 = new TIntArrayList();
        assertTrue( list2.isEmpty() );
        list2.add( 3 );
        list2.add( 1 );
        list2.add( 2 );
        list2.add( 5 );
        list2.add( 4 );
        assertEquals( 5, list2.max() );
        assertEquals( 1, list2.min() );

        try {
            TIntList list3 = new TIntArrayList();
            list3.min();
            fail( "Expected IllegalStateException" );
        }
        catch ( IllegalStateException ex ) {
            // Expected
        }

        try {
            TIntList list3 = new TIntArrayList();
            list3.max();
            fail( "Expected IllegalStateException" );
        }
        catch ( IllegalStateException ex ) {
            // Expected
        }
    }


    public void testForEach() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i < element_count; i++ ) {
            a.add( i );
        }

        class ForEach implements TIntProcedure {
            TIntList built = new TIntArrayList();


            public boolean execute( int value ) {
                built.add( value );
                return true;
            }

            TIntList getBuilt() {
                return built;
            }
        }

        ForEach foreach = new ForEach();
        a.forEach( foreach );
        TIntList built = foreach.getBuilt();
        assertEquals( a, built );
    }


    public void testForEachDescending() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i < element_count; i++ ) {
            a.add( i );
        }

        class ForEach implements TIntProcedure {
            TIntList built = new TIntArrayList();


            public boolean execute( int value ) {
                built.add( value );
                return true;
            }

            TIntList getBuilt() {
                return built;
            }
        }

        ForEach foreach = new ForEach();
        a.forEachDescending( foreach );
        TIntList built = foreach.getBuilt();
        built.reverse();
        assertEquals( a, built );
    }


    public void testTransform() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i < element_count; i++ ) {
            a.add( i );
        }

        a.transformValues( new TIntFunction() {
            public int execute( int value ) {
                return value * value;
            }
        } );

        for ( int i = 0; i < a.size(); i++ ) {
            int result = a.get( i );
            int expected = ( i + 1 ) * ( i + 1 );
            assertEquals( expected, result );
        }
    }


    public void testReverse() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.reverse();

        for ( int i = 0, j = a.size(); i < a.size(); i++, j-- ) {
            assertEquals( j, a.get( i ) );
        }
    }


    public void testReversePartial() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.reverse( 1, 19 );

        int[] expected = {1, 19, 18, 17, 16, 15, 14, 13, 12, 11,
                          10, 9, 8, 7, 6, 5, 4, 3, 2, 20};
        for ( int i = 0; i < a.size(); i++ ) {
            assertEquals( expected[i], a.get( i ) );
        }

        try {
            a.reverse( 20, 10 );
            fail( "Expected IllegalArgumentException" );
        }
        catch ( IllegalArgumentException ex ) {
            // Expected
        }
    }


    public void testSortPartial() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        a.reverse();
        a.sort( 5, 15 );

        int[] expected = {20, 19, 18, 17, 16, 6, 7, 8, 9, 10,
                          11, 12, 13, 14, 15, 5, 4, 3, 2, 1};
        for ( int i = 0; i < a.size(); i++ ) {
            assertEquals( expected[i], a.get( i ) );
        }

        try {
            a.sort( 20, 10 );
            fail( "Expected IllegalArgumentException" );
        }
        catch ( IllegalArgumentException ex ) {
            // Expected
        }
    }


    public void testEquals() {
        int element_count = 20;
        TIntList a = new TIntArrayList();
        for ( int i = 1; i <= element_count; i++ ) {
            a.add( i );
        }

        assertEquals( a, a );
        assertEquals( a, new TIntArrayList( a ) );
    }


    public void testSerialization() throws Exception {
        ByteArrayOutputStream bout = new ByteArrayOutputStream();
        ObjectOutputStream oout = new ObjectOutputStream( bout );
        oout.writeObject( list );
        oout.close();

        ObjectInputStream oin = new ObjectInputStream(
                new ByteArrayInputStream( bout.toByteArray() ) );

        TIntArrayList new_list = (TIntArrayList) oin.readObject();

        assertEquals( list, new_list );
    }
}