svn commit: r900247 - in /lucene/mahout/trunk/math/src: main/java-templates/org/apache/mahout/math/map/ main/java/org/apache/mahout/math/function/ main/java/org/apache/mahout/math/map/ main/java/org/apache/mahout/math/set/ test/java-templates/org/apach...

[bi...@apache.org]

Author: bimargulies
Date: Mon Jan 18 00:13:13 2010
New Revision: 900247

URL: http://svn.apache.org/viewvc?rev=900247&view=rev
Log:
MAHOUT-255 open hash set and map on ordinary objects, fix complete misimplementation of maps from object to x

Added:
    lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/ObjectObjectProcedure.java   (with props)
    lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenHashMap.java   (with props)
    lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/OpenHashSet.java   (with props)
    lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/map/OpenHashMapTest.java   (with props)
    lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/
    lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/OpenHashSetTest.java   (with props)
Modified:
    lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMap.java.t
    lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/AbstractSet.java
    lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMapTest.java.t

Modified: lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMap.java.t
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMap.java.t?rev=900247&r1=900246&r2=900247&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMap.java.t (original)
+++ lucene/mahout/trunk/math/src/main/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMap.java.t Mon Jan 18 00:13:13 2010
@@ -230,7 +230,7 @@
 
     // stop if we find a removed or free slot, or if we find the key itself
     // do NOT skip over removed slots (yes, open addressing is like that...)
-    while (stat[i] == FULL && tab[i] != key) {
+    while (stat[i] == FULL && equalsMindTheNull(tab[i], key)) {
       i -= decrement;
       //hashCollisions++;
       if (i < 0) {
@@ -243,7 +243,7 @@
       // do skip over removed slots (yes, open addressing is like that...)
       // assertion: there is at least one FREE slot.
       int j = i;
-      while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
+      while (stat[i] != FREE && (stat[i] == REMOVED || !equalsMindTheNull(tab[i], key))) {
         i -= decrement;
         //hashCollisions++;
         if (i < 0) {
@@ -285,7 +285,7 @@
 
     // stop if we find a free slot, or if we find the key itself.
     // do skip over removed slots (yes, open addressing is like that...)
-    while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
+    while (stat[i] != FREE && (stat[i] == REMOVED || !equalsMindTheNull(tab[i], key))) {
       i -= decrement;
       //hashCollisions++;
       if (i < 0) {

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/ObjectObjectProcedure.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/ObjectObjectProcedure.java?rev=900247&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/ObjectObjectProcedure.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/ObjectObjectProcedure.java Mon Jan 18 00:13:13 2010
@@ -0,0 +1,40 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.mahout.math.function;
+
+/**
+ * Interface that represents a procedure object: 
+ * a procedure that takes two arguments and returns a 'continue' flag.
+ */
+public interface ObjectObjectProcedure<K,V> {
+
+  /**
+   * Applies a procedure to an argument. Optionally can return a boolean flag to inform the object calling the
+   * procedure.
+   *
+   * <p>Example: forEach() methods often use procedure objects. To signal to a forEach() method whether iteration should
+   * continue normally or terminate (because for example a matching element has been found), a procedure can return
+   * <tt>false</tt> to indicate termination and <tt>true</tt> to indicate continuation.
+   *
+   * @param key key value passed to the procedure
+   * @param value value value passed to the procedure.
+   * @return a flag  to inform the object calling the procedure.
+   */
+  boolean apply(K key, V value);
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/ObjectObjectProcedure.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenHashMap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenHashMap.java?rev=900247&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenHashMap.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenHashMap.java Mon Jan 18 00:13:13 2010
@@ -0,0 +1,668 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*
+Copyright � 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
+is hereby granted without fee, provided that the above copyright notice appear in all copies and 
+that both that copyright notice and this permission notice appear in supporting documentation. 
+CERN makes no representations about the suitability of this software for any purpose. 
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math.map;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.mahout.math.function.ObjectObjectProcedure;
+import org.apache.mahout.math.function.ObjectProcedure;
+import org.apache.mahout.math.set.AbstractSet;
+import org.apache.mahout.math.set.OpenHashSet;
+
+/**
+  * Open hash map. This implements Map, but it does not respect several aspects of the Map contract
+  * that impose the very sorts of performance penalities that this class exists to avoid.
+  * {@link #entrySet}, {@link #values}, and {@link #keySet()} do <strong>not</strong> return
+  * collections that share storage with the main map, and changes to those returned objects
+  * are <strong>not</strong> reflected in the container.
+ **/
+public class OpenHashMap<K,V> extends AbstractSet implements Map<K,V> {
+  protected static final byte FREE = 0;
+  protected static final byte FULL = 1;
+  protected static final byte REMOVED = 2;
+  protected static final Object NO_KEY_VALUE = null;
+
+  /** The hash table keys. */
+  protected Object[] table;
+
+  /** The hash table values. */
+  protected Object[] values;
+
+  /** The state of each hash table entry (FREE, FULL, REMOVED). */
+  protected byte[] state;
+
+  /** The number of table entries in state==FREE. */
+  protected int freeEntries;
+
+
+  /** Constructs an empty map with default capacity and default load factors. */
+  public OpenHashMap() {
+    this(defaultCapacity);
+  }
+
+  /**
+   * Constructs an empty map with the specified initial capacity and default load factors.
+   *
+   * @param initialCapacity the initial capacity of the map.
+   * @throws IllegalArgumentException if the initial capacity is less than zero.
+   */
+  public OpenHashMap(int initialCapacity) {
+    this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor);
+  }
+
+  /**
+   * Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.
+   *
+   * @param initialCapacity the initial capacity.
+   * @param minLoadFactor   the minimum load factor.
+   * @param maxLoadFactor   the maximum load factor.
+   * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+   *                                  (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+   *                                  maxLoadFactor)</tt>.
+   */
+  public OpenHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+    setUp(initialCapacity, minLoadFactor, maxLoadFactor);
+  }
+
+  /** Removes all (key,value) associations from the receiver. Implicitly calls <tt>trimToSize()</tt>. */
+  @Override
+  public void clear() {
+    Arrays.fill(this.state, 0, state.length - 1, FREE);
+    distinct = 0;
+    freeEntries = table.length; // delta
+    trimToSize();
+  }
+
+  /**
+   * Returns a deep copy of the receiver.
+   *
+   * @return a deep copy of the receiver.
+   */
+  @Override
+  @SuppressWarnings("unchecked")
+  public Object clone() {
+    OpenHashMap copy = (OpenHashMap) super.clone();
+    copy.table = copy.table.clone();
+    copy.values = copy.values.clone();
+    copy.state = copy.state.clone();
+    return copy;
+  }
+
+  /**
+   * Returns <tt>true</tt> if the receiver contains the specified key.
+   *
+   * @return <tt>true</tt> if the receiver contains the specified key.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public boolean containsKey(Object key) {
+    return indexOfKey((K)key) >= 0;
+  }
+
+  /**
+   * Returns <tt>true</tt> if the receiver contains the specified value.
+   *
+   * @return <tt>true</tt> if the receiver contains the specified value.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public boolean containsValue(Object value) {
+    return indexOfValue((V)value) >= 0;
+  }
+
+  /**
+   * Ensures that the receiver can hold at least the specified number of associations without needing to allocate new
+   * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. <p> This
+   * method never need be called; it is for performance tuning only. Calling this method before <tt>put()</tt>ing a
+   * large number of associations boosts performance, because the receiver will grow only once instead of potentially
+   * many times and hash collisions get less probable.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  @Override
+  public void ensureCapacity(int minCapacity) {
+    if (table.length < minCapacity) {
+      int newCapacity = nextPrime(minCapacity);
+      rehash(newCapacity);
+    }
+  }
+
+  /**
+   * Applies a procedure to each key of the receiver, if any. Note: Iterates over the keys in no particular order.
+   * Subclasses can define a particular order, for example, "sorted by key". All methods which <i>can</i> be expressed
+   * in terms of this method (most methods can) <i>must guarantee</i> to use the <i>same</i> order defined by this
+   * method, even if it is no particular order. This is necessary so that, for example, methods <tt>keys</tt> and
+   * <tt>values</tt> will yield association pairs, not two uncorrelated lists.
+   *
+   * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+   *                  continues.
+   * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+   */
+  @SuppressWarnings("unchecked")
+  public boolean forEachKey(ObjectProcedure<K> procedure) {
+    for (int i = table.length; i-- > 0;) {
+      if (state[i] == FULL) {
+        if (!procedure.apply((K)table[i])) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Applies a procedure to each (key,value) pair of the receiver, if any. Iteration order is guaranteed to be
+   * <i>identical</i> to the order used by method {@link #forEachKey(ObjectProcedure)}.
+   *
+   * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+   *                  continues.
+   * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+   */
+    @SuppressWarnings("unchecked")
+  public boolean forEachPair(ObjectObjectProcedure<K,V> procedure) {
+    for (int i = table.length; i-- > 0;) {
+      if (state[i] == FULL) {
+        if (!procedure.apply((K)table[i], (V)values[i])) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Returns the value associated with the specified key. It is often a good idea to first check with {@link
+   * #containsKey(double)} whether the given key has a value associated or not, i.e. whether there exists an association
+   * for the given key or not.
+   *
+   * @param key the key to be searched for.
+   * @return the value associated with the specified key; <tt>0</tt> if no such key is present.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public V get(Object key) {
+    int i = indexOfKey((K)key);
+    if (i < 0) {
+      return null;
+    } //not contained
+    return (V)values[i];
+  }
+
+  /**
+   * @param key the key to be added to the receiver.
+   * @return the index where the key would need to be inserted, if it is not already contained. Returns -index-1 if the
+   *         key is already contained at slot index. Therefore, if the returned index < 0, then it is already contained
+   *         at slot -index-1. If the returned index >= 0, then it is NOT already contained and should be inserted at
+   *         slot index.
+   */
+  protected int indexOfInsertion(K key) {
+    Object[] tab = table;
+    byte[] stat = state;
+    int length = tab.length;
+
+    int hash = key.hashCode() & 0x7FFFFFFF;
+    int i = hash % length;
+    int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+    //int decrement = (hash / length) % length;
+    if (decrement == 0) {
+      decrement = 1;
+    }
+
+    // stop if we find a removed or free slot, or if we find the key itself
+    // do NOT skip over removed slots (yes, open addressing is like that...)
+    while (stat[i] == FULL && !equalsMindTheNull(key, tab[i])) {
+      i -= decrement;
+      //hashCollisions++;
+      if (i < 0) {
+        i += length;
+      }
+    }
+
+    if (stat[i] == REMOVED) {
+      // stop if we find a free slot, or if we find the key itself.
+      // do skip over removed slots (yes, open addressing is like that...)
+      // assertion: there is at least one FREE slot.
+      int j = i;
+      while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
+        i -= decrement;
+        //hashCollisions++;
+        if (i < 0) {
+          i += length;
+        }
+      }
+      if (stat[i] == FREE) {
+        i = j;
+      }
+    }
+
+
+    if (stat[i] == FULL) {
+      // key already contained at slot i.
+      // return a negative number identifying the slot.
+      return -i - 1;
+    }
+    // not already contained, should be inserted at slot i.
+    // return a number >= 0 identifying the slot.
+    return i;
+  }
+
+  /**
+   * @param key the key to be searched in the receiver.
+   * @return the index where the key is contained in the receiver, returns -1 if the key was not found.
+   */
+  protected int indexOfKey(K key) {
+    Object[] tab = table;
+    byte[] stat = state;
+    int length = tab.length;
+
+    int hash = key.hashCode() & 0x7FFFFFFF;
+    int i = hash % length;
+    int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+    //int decrement = (hash / length) % length;
+    if (decrement == 0) {
+      decrement = 1;
+    }
+
+    // stop if we find a free slot, or if we find the key itself.
+    // do skip over removed slots (yes, open addressing is like that...)
+    while (stat[i] != FREE && (stat[i] == REMOVED || !equalsMindTheNull(key, tab[i]))) {
+      i -= decrement;
+      //hashCollisions++;
+      if (i < 0) {
+        i += length;
+      }
+    }
+
+    if (stat[i] == FREE) {
+      return -1;
+    } // not found
+    return i; //found, return index where key is contained
+  }
+
+  /**
+   * @param value the value to be searched in the receiver.
+   * @return the index where the value is contained in the receiver, returns -1 if the value was not found.
+   */
+  protected int indexOfValue(V value) {
+    Object[] val = values;
+    byte[] stat = state;
+
+    for (int i = stat.length; --i >= 0;) {
+      if (stat[i] == FULL && equalsMindTheNull(val[i], value)) {
+        return i;
+      }
+    }
+
+    return -1; // not found
+  }
+
+  /**
+   * Fills all keys contained in the receiver into the specified list. Fills the list, starting at index 0. After this
+   * call returns the specified list has a new size that equals <tt>this.size()</tt>. 
+   * This method can be used
+   * to iterate over the keys of the receiver.
+   *
+   * @param list the list to be filled, can have any size.
+   */
+  @SuppressWarnings("unchecked")
+  public void keys(List<K> list) {
+    list.clear();
+  
+
+    Object [] tab = table;
+    byte[] stat = state;
+
+    for (int i = tab.length; i-- > 0;) {
+      if (stat[i] == FULL) {
+        list.add((K)tab[i]);
+      }
+    }
+  }
+
+  /**
+   * Associates the given key with the given value. Replaces any old <tt>(key,someOtherValue)</tt> association, if
+   * existing.
+   *
+   * @param key   the key the value shall be associated with.
+   * @param value the value to be associated.
+   * @return <tt>true</tt> if the receiver did not already contain such a key; <tt>false</tt> if the receiver did
+   *         already contain such a key - the new value has now replaced the formerly associated value.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public V put(K key, V value) {
+    int i = indexOfInsertion(key);
+    V previous = null;
+    if (i < 0) { //already contained
+      i = -i - 1;
+      previous = (V) this.values[i];
+      this.values[i] = value;
+      return previous;
+    }
+
+    if (this.distinct > this.highWaterMark) {
+      int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+      /*
+      log.info("grow rehashing ");
+      log.info("at distinct="+distinct+", capacity="+table.length+" to newCapacity="+newCapacity+" ...");
+      */
+      rehash(newCapacity);
+      return put(key, value);
+    }
+
+    this.table[i] = key;
+    this.values[i] = value;
+    if (this.state[i] == FREE) {
+      this.freeEntries--;
+    }
+    this.state[i] = FULL;
+    this.distinct++;
+
+    if (this.freeEntries < 1) { //delta
+      int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+      rehash(newCapacity);
+    }
+
+    return null;
+  }
+
+  /**
+   * Rehashes the contents of the receiver into a new table with a smaller or larger capacity. This method is called
+   * automatically when the number of keys in the receiver exceeds the high water mark or falls below the low water
+   * mark.
+   */
+  @SuppressWarnings("unchecked")
+  protected void rehash(int newCapacity) {
+    int oldCapacity = table.length;
+    //if (oldCapacity == newCapacity) return;
+
+    Object[] oldTable = table;
+    Object[] oldValues = values;
+    byte[] oldState = state;
+
+    Object[] newTable = new Object[newCapacity];
+    Object[] newValues = new Object[newCapacity];
+    byte[] newState = new byte[newCapacity];
+
+    this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
+    this.highWaterMark = chooseHighWaterMark(newCapacity, this.maxLoadFactor);
+
+    this.table = newTable;
+    this.values = newValues;
+    this.state = newState;
+    this.freeEntries = newCapacity - this.distinct; // delta
+
+    for (int i = oldCapacity; i-- > 0;) {
+      if (oldState[i] == FULL) {
+        Object element = oldTable[i];
+        int index = indexOfInsertion((K)element);
+        newTable[index] = element;
+        newValues[index] = oldValues[i];
+        newState[index] = FULL;
+      }
+    }
+  }
+
+  /**
+   * Removes the given key with its associated element from the receiver, if present.
+   *
+   * @param key the key to be removed from the receiver.
+   * @return <tt>true</tt> if the receiver contained the specified key, <tt>false</tt> otherwise.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public V remove(Object key) {
+    V removed = null;
+    int i = indexOfKey((K)key);
+    if (i < 0) {
+      return null;
+    } else {// key not contained
+      removed = (V)values[i];
+    }
+
+    this.state[i] = REMOVED;
+    //this.values[i]=0; // delta
+    this.distinct--;
+
+    if (this.distinct < this.lowWaterMark) {
+      int newCapacity = chooseShrinkCapacity(this.distinct, this.minLoadFactor, this.maxLoadFactor);
+      /*
+      if (table.length != newCapacity) {
+        log.info("shrink rehashing ");
+        log.info("at distinct="+distinct+", capacity="+table.length+" to newCapacity="+newCapacity+" ...");
+      }
+      */
+      rehash(newCapacity);
+    }
+
+    return removed;
+  }
+
+  /**
+   * Initializes the receiver.
+   *
+   * @param initialCapacity the initial capacity of the receiver.
+   * @param minLoadFactor   the minLoadFactor of the receiver.
+   * @param maxLoadFactor   the maxLoadFactor of the receiver.
+   * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+   *                                  (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+   *                                  maxLoadFactor)</tt>.
+   */
+  @Override
+  protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+    int capacity = initialCapacity;
+    super.setUp(capacity, minLoadFactor, maxLoadFactor);
+    capacity = nextPrime(capacity);
+    if (capacity == 0) {
+      capacity = 1;
+    } // open addressing needs at least one FREE slot at any time.
+
+    this.table = new Object[capacity];
+    this.values = new Object[capacity];
+    this.state = new byte[capacity];
+
+    // memory will be exhausted long before this pathological case happens, anyway.
+    this.minLoadFactor = minLoadFactor;
+    if (capacity == PrimeFinder.largestPrime) {
+      this.maxLoadFactor = 1.0;
+    } else {
+      this.maxLoadFactor = maxLoadFactor;
+    }
+
+    this.distinct = 0;
+    this.freeEntries = capacity; // delta
+
+    // lowWaterMark will be established upon first expansion.
+    // establishing it now (upon instance construction) would immediately make the table shrink upon first put(...).
+    // After all the idea of an "initialCapacity" implies violating lowWaterMarks when an object is young.
+    // See ensureCapacity(...)
+    this.lowWaterMark = 0;
+    this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
+  }
+
+  /**
+   * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An
+   * application can use this operation to minimize the storage of the receiver.
+   */
+  @Override
+  public void trimToSize() {
+    // * 1.2 because open addressing's performance exponentially degrades beyond that point
+    // so that even rehashing the table can take very long
+    int newCapacity = nextPrime((int) (1 + 1.2 * size()));
+    if (table.length > newCapacity) {
+      rehash(newCapacity);
+    }
+  }
+
+  /**
+   * Access for unit tests.
+   * @param capacity
+   * @param minLoadFactor
+   * @param maxLoadFactor
+   */
+  void getInternalFactors(int[] capacity, 
+      double[] minLoadFactor, 
+      double[] maxLoadFactor) {
+    capacity[0] = table.length;
+    minLoadFactor[0] = this.minLoadFactor;
+    maxLoadFactor[0] = this.maxLoadFactor;
+  }
+
+  private class MapEntry implements Map.Entry<K,V> {
+    private K key;
+    private V value;
+    
+    MapEntry(K key, V value) {
+      this.key = key;
+      this.value = value;
+    }
+
+    @Override
+    public K getKey() {
+      return key;
+    }
+
+    @Override
+    public V getValue() {
+      return value;
+    }
+
+    @Override
+    public V setValue(V value) {
+      throw new UnsupportedOperationException("Map.Entry.setValue not supported for OpenHashMap");
+    }
+    
+  }
+
+  /**
+   * Allocate a set to contain Map.Entry objects for the pairs and return it.
+   */
+  @Override
+  public Set<java.util.Map.Entry<K,V>> entrySet() {
+    final OpenHashSet<Map.Entry<K,V>> entries = new OpenHashSet<Map.Entry<K,V>>();
+    forEachPair(new ObjectObjectProcedure<K,V>() {
+
+      @Override
+      public boolean apply(K key, V value) {
+        entries.add(new MapEntry(key, value));
+        return true;
+      }});
+    return entries;
+  }
+
+  /**
+   * Allocate a set to contain keys and return it.
+   * This violates the 'backing' provisions of the map interface.
+   */
+  @Override
+  public Set<K> keySet() {
+    final OpenHashSet<K> keys = new OpenHashSet<K>();
+    forEachKey(new ObjectProcedure<K>() {
+
+      @Override
+      public boolean apply(K element) {
+        keys.add(element);
+        return true;
+      }});
+    return keys;
+  }
+
+  @Override
+  public void putAll(Map<? extends K,? extends V> m) {
+    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
+      put(e.getKey(), e.getValue());
+    }
+  }
+
+  /**
+   * Allocate a list to contain the values and return it.
+   * This violates the 'backing' provision of the Map interface.
+   */
+  @Override
+  public Collection<V> values() {
+    final List<V> valueList = new ArrayList<V>();
+    forEachPair(new ObjectObjectProcedure<K,V>() {
+
+      @Override
+      public boolean apply(K key, V value) {
+        valueList.add(value);
+        return true;
+      }});
+    return valueList;
+  }
+
+  @SuppressWarnings("unchecked")
+  @Override
+  public boolean equals(Object obj) {
+    if (! (obj instanceof OpenHashMap)) {
+      return false;
+    }
+    final OpenHashMap o = (OpenHashMap) obj;
+    if (o.size() != size()) {
+      return false;
+    }
+    final boolean[] equal = new boolean[1];
+    equal[0] = true;
+    forEachPair(new ObjectObjectProcedure<K,V>() {
+
+      @Override
+      public boolean apply(K key, V value) {
+        Object ov = o.get(key);
+        if (!value.equals(ov)) {
+          equal[0] = false;
+          return false;
+        }
+        return true;
+      }});
+    return equal[0];
+  }
+
+  @Override
+  public String toString() {
+    final StringBuilder sb = new StringBuilder();
+    sb.append("{");
+    forEachPair(new ObjectObjectProcedure<K,V>() {
+
+      @Override
+      public boolean apply(K key, V value) {
+        sb.append("[");
+        sb.append(key);
+        sb.append(" -> ");
+        sb.append(value);
+        sb.append("] ");
+        return true;
+      }});
+    sb.append("}");
+    return sb.toString();
+  }
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/map/OpenHashMap.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/AbstractSet.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/AbstractSet.java?rev=900247&r1=900246&r2=900247&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/AbstractSet.java (original)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/AbstractSet.java Mon Jan 18 00:13:13 2010
@@ -175,4 +175,14 @@
    */
   public void trimToSize() {
   }
+  
+  protected static boolean equalsMindTheNull(Object a, Object b) {
+    if (a == null && b == null) {
+      return true;
+    }
+    if (a == null || b == null) {
+      return false;
+    }
+    return a.equals(b);
+  }
 }

Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/OpenHashSet.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/OpenHashSet.java?rev=900247&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/OpenHashSet.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/OpenHashSet.java Mon Jan 18 00:13:13 2010
@@ -0,0 +1,557 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.mahout.math.set;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.mahout.math.function.ObjectProcedure;
+import org.apache.mahout.math.map.PrimeFinder;
+
+/**
+  * Open hashing alternative to java.util.HashSet.
+ **/
+public class OpenHashSet<T> extends AbstractSet implements Set<T>  {
+  protected static final byte FREE = 0;
+  protected static final byte FULL = 1;
+  protected static final byte REMOVED = 2;
+  protected static final char NO_KEY_VALUE = 0;
+
+  /** The hash table keys. */
+  protected Object[] table;
+
+  /** The state of each hash table entry (FREE, FULL, REMOVED). */
+  protected byte[] state;
+
+  /** The number of table entries in state==FREE. */
+  protected int freeEntries;
+
+
+  /** Constructs an empty map with default capacity and default load factors. */
+  public OpenHashSet() {
+    this(defaultCapacity);
+  }
+
+  /**
+   * Constructs an empty map with the specified initial capacity and default load factors.
+   *
+   * @param initialCapacity the initial capacity of the map.
+   * @throws IllegalArgumentException if the initial capacity is less than zero.
+   */
+  public OpenHashSet(int initialCapacity) {
+    this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor);
+  }
+
+  /**
+   * Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.
+   *
+   * @param initialCapacity the initial capacity.
+   * @param minLoadFactor   the minimum load factor.
+   * @param maxLoadFactor   the maximum load factor.
+   * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+   *                                  (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+   *                                  maxLoadFactor)</tt>.
+   */
+  public OpenHashSet(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+    setUp(initialCapacity, minLoadFactor, maxLoadFactor);
+  }
+
+  /** Removes all values associations from the receiver. Implicitly calls <tt>trimToSize()</tt>. */
+  @Override
+  public void clear() {
+    Arrays.fill(this.state, 0, state.length - 1, FREE);
+    distinct = 0;
+    freeEntries = table.length; // delta
+    trimToSize();
+  }
+
+  /**
+   * Returns a deep copy of the receiver.
+   *
+   * @return a deep copy of the receiver.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public Object clone() {
+    OpenHashSet copy = (OpenHashSet) super.clone();
+    copy.table = copy.table.clone();
+    copy.state = copy.state.clone();
+    return copy;
+  }
+
+  /**
+   * Returns <tt>true</tt> if the receiver contains the specified key.
+   *
+   * @return <tt>true</tt> if the receiver contains the specified key.
+   */
+  @SuppressWarnings("unchecked")
+  public boolean contains(Object key) {
+    return indexOfKey((T)key) >= 0;
+  }
+
+  /**
+   * Ensures that the receiver can hold at least the specified number of associations without needing to allocate new
+   * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. <p> This
+   * method never need be called; it is for performance tuning only. Calling this method before <tt>add()</tt>ing a
+   * large number of associations boosts performance, because the receiver will grow only once instead of potentially
+   * many times and hash collisions get less probable.
+   *
+   * @param minCapacity the desired minimum capacity.
+   */
+  @Override
+  public void ensureCapacity(int minCapacity) {
+    if (table.length < minCapacity) {
+      int newCapacity = nextPrime(minCapacity);
+      rehash(newCapacity);
+    }
+  }
+
+  /**
+   * Applies a procedure to each key of the receiver, if any. Note: Iterates over the keys in no particular order.
+   * Subclasses can define a particular order, for example, "sorted by key". All methods which <i>can</i> be expressed
+   * in terms of this method (most methods can) <i>must guarantee</i> to use the <i>same</i> order defined by this
+   * method, even if it is no particular order. This is necessary so that, for example, methods <tt>keys</tt> and
+   * <tt>values</tt> will yield association pairs, not two uncorrelated lists.
+   *
+   * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+   *                  continues.
+   * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+   */
+  @SuppressWarnings("unchecked")
+  public boolean forEachKey(ObjectProcedure<T> procedure) {
+    for (int i = table.length; i-- > 0;) {
+      if (state[i] == FULL) {
+        if (!procedure.apply((T)table[i])) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  /**
+   * @param key the key to be added to the receiver.
+   * @return the index where the key would need to be inserted, if it is not already contained. Returns -index-1 if the
+   *         key is already contained at slot index. Therefore, if the returned index < 0, then it is already contained
+   *         at slot -index-1. If the returned index >= 0, then it is NOT already contained and should be inserted at
+   *         slot index.
+   */
+  protected int indexOfInsertion(T key) {
+    Object[] tab = table;
+    byte[] stat = state;
+    int length = tab.length;
+
+    int hash = key.hashCode() & 0x7FFFFFFF;
+    int i = hash % length;
+    int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+    //int decrement = (hash / length) % length;
+    if (decrement == 0) {
+      decrement = 1;
+    }
+
+    // stop if we find a removed or free slot, or if we find the key itself
+    // do NOT skip over removed slots (yes, open addressing is like that...)
+    while (stat[i] == FULL && tab[i] != key) {
+      i -= decrement;
+      //hashCollisions++;
+      if (i < 0) {
+        i += length;
+      }
+    }
+
+    if (stat[i] == REMOVED) {
+      // stop if we find a free slot, or if we find the key itself.
+      // do skip over removed slots (yes, open addressing is like that...)
+      // assertion: there is at least one FREE slot.
+      int j = i;
+      while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
+        i -= decrement;
+        //hashCollisions++;
+        if (i < 0) {
+          i += length;
+        }
+      }
+      if (stat[i] == FREE) {
+        i = j;
+      }
+    }
+
+
+    if (stat[i] == FULL) {
+      // key already contained at slot i.
+      // return a negative number identifying the slot.
+      return -i - 1;
+    }
+    // not already contained, should be inserted at slot i.
+    // return a number >= 0 identifying the slot.
+    return i;
+  }
+
+  /**
+   * @param key the key to be searched in the receiver.
+   * @return the index where the key is contained in the receiver, returns -1 if the key was not found.
+   */
+  protected int indexOfKey(T key) {
+    Object[] tab = table;
+    byte[] stat = state;
+    int length = tab.length;
+
+    int hash = key.hashCode() & 0x7FFFFFFF;
+    int i = hash % length;
+    int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+    //int decrement = (hash / length) % length;
+    if (decrement == 0) {
+      decrement = 1;
+    }
+
+    // stop if we find a free slot, or if we find the key itself.
+    // do skip over removed slots (yes, open addressing is like that...)
+    while (stat[i] != FREE && (stat[i] == REMOVED || (!key.equals(tab[i])))) {
+      i -= decrement;
+      //hashCollisions++;
+      if (i < 0) {
+        i += length;
+      }
+    }
+
+    if (stat[i] == FREE) {
+      return -1;
+    } // not found
+    return i; //found, return index where key is contained
+  }
+
+  /**
+   * Fills all keys contained in the receiver into the specified list. Fills the list, starting at index 0. After this
+   * call returns the specified list has a new size that equals <tt>this.size()</tt>. 
+   * This method can be used
+   * to iterate over the keys of the receiver.
+   *
+   * @param list the list to be filled, can have any size.
+   */
+  @SuppressWarnings("unchecked")
+  public void keys(List<T> list) {
+    list.clear();
+  
+
+    Object [] tab = table;
+    byte[] stat = state;
+
+    for (int i = tab.length; i-- > 0;) {
+      if (stat[i] == FULL) {
+        list.add((T)tab[i]);
+      }
+    }
+  }
+
+
+  /**
+   * Associates the given key with the given value. Replaces any old <tt>(key,someOtherValue)</tt> association, if
+   * existing.
+   *
+   * @param key   the key the value shall be associated with.
+   * @param value the value to be associated.
+   * @return <tt>true</tt> if the receiver did not already contain such a key; <tt>false</tt> if the receiver did
+   *         already contain such a key - the new value has now replaced the formerly associated value.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public boolean add(Object key) {
+    int i = indexOfInsertion((T)key);
+    if (i < 0) { //already contained
+      return false;
+    }
+
+    if (this.distinct > this.highWaterMark) {
+      int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+      /*
+      log.info("grow rehashing ");
+      log.info("at distinct="+distinct+", capacity="+table.length+" to newCapacity="+newCapacity+" ...");
+      */
+      rehash(newCapacity);
+      return add(key);
+    }
+
+    this.table[i] = key;
+    if (this.state[i] == FREE) {
+      this.freeEntries--;
+    }
+    this.state[i] = FULL;
+    this.distinct++;
+
+    if (this.freeEntries < 1) { //delta
+      int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+      rehash(newCapacity);
+      return add(key);
+    }
+    
+    return true;
+  }
+
+  /**
+   * Rehashes the contents of the receiver into a new table with a smaller or larger capacity. This method is called
+   * automatically when the number of keys in the receiver exceeds the high water mark or falls below the low water
+   * mark.
+   */
+  @SuppressWarnings("unchecked")
+  protected void rehash(int newCapacity) {
+    int oldCapacity = table.length;
+    //if (oldCapacity == newCapacity) return;
+
+    Object[] oldTable = table;
+    byte[] oldState = state;
+
+    Object[] newTable = new Object[newCapacity];
+    byte[] newState = new byte[newCapacity];
+
+    this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
+    this.highWaterMark = chooseHighWaterMark(newCapacity, this.maxLoadFactor);
+
+    this.table = newTable;
+    this.state = newState;
+    this.freeEntries = newCapacity - this.distinct; // delta
+
+    for (int i = oldCapacity; i-- > 0;) {
+      if (oldState[i] == FULL) {
+        Object element = oldTable[i];
+        int index = indexOfInsertion((T)element);
+        newTable[index] = element;
+        newState[index] = FULL;
+      }
+    }
+  }
+
+  /**
+   * Removes the given key with its associated element from the receiver, if present.
+   *
+   * @param key the key to be removed from the receiver.
+   * @return <tt>true</tt> if the receiver contained the specified key, <tt>false</tt> otherwise.
+   */
+  @SuppressWarnings("unchecked")
+  @Override
+  public boolean remove(Object key) {
+    int i = indexOfKey((T)key);
+    if (i < 0) {
+      return false;
+    } // key not contained
+
+    this.state[i] = REMOVED;
+    this.distinct--;
+
+    if (this.distinct < this.lowWaterMark) {
+      int newCapacity = chooseShrinkCapacity(this.distinct, this.minLoadFactor, this.maxLoadFactor);
+      /*
+      if (table.length != newCapacity) {
+        log.info("shrink rehashing ");
+        log.info("at distinct="+distinct+", capacity="+table.length+" to newCapacity="+newCapacity+" ...");
+      }
+      */
+      rehash(newCapacity);
+    }
+
+    return true;
+  }
+
+  /**
+   * Initializes the receiver.
+   *
+   * @param initialCapacity the initial capacity of the receiver.
+   * @param minLoadFactor   the minLoadFactor of the receiver.
+   * @param maxLoadFactor   the maxLoadFactor of the receiver.
+   * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+   *                                  (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+   *                                  maxLoadFactor)</tt>.
+   */
+  @Override
+  protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+    int capacity = initialCapacity;
+    super.setUp(capacity, minLoadFactor, maxLoadFactor);
+    capacity = nextPrime(capacity);
+    if (capacity == 0) {
+      capacity = 1;
+    } // open addressing needs at least one FREE slot at any time.
+
+    this.table = new Object[capacity];
+    this.state = new byte[capacity];
+
+    // memory will be exhausted long before this pathological case happens, anyway.
+    this.minLoadFactor = minLoadFactor;
+    if (capacity == PrimeFinder.largestPrime) {
+      this.maxLoadFactor = 1.0;
+    } else {
+      this.maxLoadFactor = maxLoadFactor;
+    }
+
+    this.distinct = 0;
+    this.freeEntries = capacity; // delta
+
+    // lowWaterMark will be established upon first expansion.
+    // establishing it now (upon instance construction) would immediately make the table shrink upon first put(...).
+    // After all the idea of an "initialCapacity" implies violating lowWaterMarks when an object is young.
+    // See ensureCapacity(...)
+    this.lowWaterMark = 0;
+    this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
+  }
+
+  /**
+   * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An
+   * application can use this operation to minimize the storage of the receiver.
+   */
+  @Override
+  public void trimToSize() {
+    // * 1.2 because open addressing's performance exponentially degrades beyond that point
+    // so that even rehashing the table can take very long
+    int newCapacity = nextPrime((int) (1 + 1.2 * size()));
+    if (table.length > newCapacity) {
+      rehash(newCapacity);
+    }
+  }
+
+  /**
+   * Access for unit tests.
+   * @param capacity
+   * @param minLoadFactor
+   * @param maxLoadFactor
+   */
+  void getInternalFactors(int[] capacity, 
+      double[] minLoadFactor, 
+      double[] maxLoadFactor) {
+    capacity[0] = table.length;
+    minLoadFactor[0] = this.minLoadFactor;
+    maxLoadFactor[0] = this.maxLoadFactor;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return size() == 0;
+  }
+  
+  /**
+   * OpenHashSet instances are only equal to other OpenHashSet instances, not to 
+   * any other collection. Hypothetically, we should check for and permit
+   * equals on other Sets.
+   */
+  @SuppressWarnings("unchecked")
+  public boolean equals(Object obj) {
+    if (obj == this) {
+      return true;
+    }
+
+    if (!(obj instanceof OpenHashSet)) {
+      return false;
+    }
+    final OpenHashSet other = (OpenHashSet) obj;
+    if (other.size() != size()) {
+      return false;
+    }
+
+    return
+        forEachKey(
+            new ObjectProcedure<T>() {
+              @Override
+              public boolean apply(T key) {
+                return other.contains(key);
+              }
+            }
+        );
+  }
+  
+  /**
+   * Implement the standard Java Collections iterator. Note that 'remove' is silently
+   * ineffectual here. This method is provided for convenience, only.
+   */
+  @Override
+  public Iterator<T> iterator() {
+    List<T> keyList = new ArrayList<T>();
+    keys(keyList);
+    return keyList.iterator();
+  }
+
+  @Override
+  public Object[] toArray() {
+    List<T> keyList = new ArrayList<T>();
+    keys(keyList);
+    return keyList.toArray();
+  }
+
+  @Override
+  public boolean addAll(Collection<? extends T> c) {
+    boolean anyAdded = false;
+    for(T o : c) {
+      boolean added = add(o);
+      anyAdded |= added;
+    }
+    return anyAdded;
+  }
+
+  @Override
+  public boolean containsAll(Collection<?> c) {
+    for (Object o : c) {
+      if (!contains(o)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  @Override
+  public boolean removeAll(Collection<?> c) {
+    boolean anyRemoved = false;
+    for(Object o : c) {
+      boolean removed = remove(o);
+      anyRemoved |= removed;
+    }
+    return anyRemoved;
+  }
+
+  @Override
+  public boolean retainAll(Collection<?> c) {
+    final Collection<?> finalCollection = c;
+    final boolean[] modified = new boolean[1];
+    modified[0] = false;
+    forEachKey(new ObjectProcedure<T>() {
+
+      @Override
+      public boolean apply(T element) {
+        if (!finalCollection.contains(element)) {
+          remove(element);
+          modified[0] = true;
+        }
+        return true;
+      }});
+    return modified[0];
+  }
+
+  @Override
+  public <T2> T2[] toArray(T2[] a) {
+    List<T> keys = new ArrayList<T>();
+    keys(keys);
+    return keys.toArray(a);
+  }
+
+  public List<T> keys() {
+    List<T> keys = new ArrayList<T>();
+    keys(keys);
+    return keys;
+  }
+}

Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/set/OpenHashSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMapTest.java.t
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMapTest.java.t?rev=900247&r1=900246&r2=900247&view=diff
==============================================================================
--- lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMapTest.java.t (original)
+++ lucene/mahout/trunk/math/src/test/java-templates/org/apache/mahout/math/map/OpenObjectValueTypeHashMapTest.java.t Mon Jan 18 00:13:13 2010
@@ -68,24 +68,6 @@
     }
   }
   
-   private static class ComparableKey extends NotComparableKey
-      implements Comparable<ComparableKey> {
-    public ComparableKey(int x) {
-      super(x);
-    }
-      
-    @Override
-    public String toString() {
-      return "[ck " + x + " ]";
-    }
-
-    @Override
-    public int compareTo(ComparableKey o) {
-
-      return (int)(x - o.x);
-    }
-  }
-  
   private NotComparableKey[] ncKeys = {
     new NotComparableKey(101),
     new NotComparableKey(99),
@@ -95,19 +77,9 @@
     new NotComparableKey(5)
     };
   
-  private ComparableKey[] cKeys = {
-    new ComparableKey(101),
-    new ComparableKey(99),
-    new ComparableKey(2),
-    new ComparableKey(3),
-    new ComparableKey(4),
-    new ComparableKey(5)
-    };
-  
-
   @Test
   public void testConstructors() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
     int[] capacity = new int[1];
     double[] minLoadFactor = new double[1];
     double[] maxLoadFactor = new double[1];
@@ -117,14 +89,14 @@
     assertEquals(AbstractSet.defaultMaxLoadFactor, maxLoadFactor[0], 0.001);
     assertEquals(AbstractSet.defaultMinLoadFactor, minLoadFactor[0], 0.001);
     int prime = PrimeFinder.nextPrime(907);
-    map = new OpenObject${valueTypeCap}HashMap<ComparableKey>(prime);
+    map = new OpenObject${valueTypeCap}HashMap<String>(prime);
     
     map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
     assertEquals(prime, capacity[0]);
     assertEquals(AbstractSet.defaultMaxLoadFactor, maxLoadFactor[0], 0.001);
     assertEquals(AbstractSet.defaultMinLoadFactor, minLoadFactor[0], 0.001);
     
-    map = new OpenObject${valueTypeCap}HashMap<ComparableKey>(prime, 0.4, 0.8);
+    map = new OpenObject${valueTypeCap}HashMap<String>(prime, 0.4, 0.8);
     map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
     assertEquals(prime, capacity[0]);
     assertEquals(0.4, minLoadFactor[0], 0.001);
@@ -133,7 +105,7 @@
   
   @Test
   public void testEnsureCapacity() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
     int prime = PrimeFinder.nextPrime(907);
     
     map.ensureCapacity(prime);
@@ -147,8 +119,8 @@
   
   @Test
   public void testClear() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType})11); 
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType})11); 
     assertEquals(1, map.size());
     map.clear();
     assertEquals(0, map.size());
@@ -157,60 +129,60 @@
   @Test
   @SuppressWarnings("unchecked")
   public void testClone() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType})11);
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map2 = (OpenObject${valueTypeCap}HashMap<ComparableKey>) map.clone();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType})11);
+    OpenObject${valueTypeCap}HashMap<String> map2 = (OpenObject${valueTypeCap}HashMap<String>) map.clone();
     map.clear();
     assertEquals(1, map2.size());
   }
   
   @Test
   public void testContainsKey() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType})11);
-    assertTrue(map.containsKey(cKeys[0]));
-    assertFalse(map.containsKey(cKeys[1]));
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType})11);
+    assertTrue(map.containsKey("Eleven"));
+    assertTrue(map.containsKey(new String("Eleven")));
+    assertFalse(map.containsKey("Twelve"));
   }
   
   @Test
   public void testContainValue() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType})11);
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType})11);
     assertTrue(map.containsValue((${valueType})11));
     assertFalse(map.containsValue((${valueType})12));
   }
   
   @Test
   public void testForEachKey() {
-    final List<ComparableKey> keys = new ArrayList<ComparableKey>();
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
-    map.removeKey(cKeys[2]);
-    map.forEachKey(new ObjectProcedure<ComparableKey>() {
+    final List<String> keys = new ArrayList<String>();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
+    map.removeKey("Thirteen");
+    map.forEachKey(new ObjectProcedure<String>() {
       
       @Override
-      public boolean apply(ComparableKey element) {
+      public boolean apply(String element) {
         keys.add(element);
         return true;
       }
     });
     
-    //2, 3, 1, 0
     assertEquals(3, keys.size());
     Collections.sort(keys);
-    assertSame(cKeys[3], keys.get(0));
-    assertSame(cKeys[1], keys.get(1));
-    assertSame(cKeys[0], keys.get(2));
+    assertSame("Fourteen", keys.get(1));
+    assertSame("Twelve", keys.get(2));
+    assertSame("Eleven", keys.get(0));
   }
   
   private static class Pair implements Comparable<Pair> {
     ${valueType} v;
-    ComparableKey k;
+    String k;
     
-    Pair(ComparableKey k, ${valueType} v) {
+    Pair(String k, ${valueType} v) {
       this.k = k;
       this.v = v;
     }
@@ -224,16 +196,16 @@
   @Test
   public void testForEachPair() {
     final List<Pair> pairs = new ArrayList<Pair>();
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
-    map.removeKey(cKeys[2]);
-    map.forEachPair(new Object${valueTypeCap}Procedure<ComparableKey>() {
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
+    map.removeKey("Thirteen");
+    map.forEachPair(new Object${valueTypeCap}Procedure<String>() {
       
       @Override
-      public boolean apply(ComparableKey first, ${valueType} second) {
+      public boolean apply(String first, ${valueType} second) {
         pairs.add(new Pair(first, second));
         return true;
       }
@@ -241,19 +213,19 @@
     
     Collections.sort(pairs);
     assertEquals(3, pairs.size());
-    assertEquals((${valueType})14, pairs.get(0).v ${valueEpsilon});
-    assertSame(cKeys[3], pairs.get(0).k);
-    assertEquals((${valueType}) 12, pairs.get(1).v ${valueEpsilon});
-    assertSame(cKeys[1], pairs.get(1).k);
-    assertEquals((${valueType}) 11, pairs.get(2).v ${valueEpsilon});
-    assertSame(cKeys[0], pairs.get(2).k);
+    assertEquals((${valueType})14, pairs.get(1).v ${valueEpsilon});
+    assertSame("Fourteen", pairs.get(1).k);
+    assertEquals((${valueType}) 12, pairs.get(2).v ${valueEpsilon});
+    assertSame("Twelve", pairs.get(2).k);
+    assertEquals((${valueType}) 11, pairs.get(0).v ${valueEpsilon});
+    assertSame("Eleven", pairs.get(0).k);
     
     pairs.clear();
-    map.forEachPair(new Object${valueTypeCap}Procedure<ComparableKey>() {
+    map.forEachPair(new Object${valueTypeCap}Procedure<String>() {
       int count = 0;
       
       @Override
-      public boolean apply(ComparableKey first, ${valueType} second) {
+      public boolean apply(String first, ${valueType} second) {
         pairs.add(new Pair(first, second));
         count++;
         return count < 2;
@@ -265,41 +237,41 @@
   
   @Test
   public void testGet() {
-    OpenObject${valueTypeCap}HashMap<NotComparableKey> map = new OpenObject${valueTypeCap}HashMap<NotComparableKey>();
-    map.put(ncKeys[0], (${valueType}) 11);
-    map.put(ncKeys[1], (${valueType}) 12);
-    assertEquals((${valueType})11, map.get(ncKeys[0]) ${valueEpsilon});
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    assertEquals((${valueType})11, map.get("Eleven") ${valueEpsilon});
   }
 
   @Test
   public void testKeys() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    List<ComparableKey> keys = new ArrayList<ComparableKey>();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    List<String> keys = new ArrayList<String>();
     map.keys(keys);
     Collections.sort(keys);
-    assertSame(cKeys[1], keys.get(0));
-    assertSame(cKeys[0], keys.get(1));
-    List<ComparableKey> k2 = map.keys();
+    assertSame("Twelve", keys.get(1));
+    assertSame("Eleven", keys.get(0));
+    List<String> k2 = map.keys();
     Collections.sort(k2);
     assertEquals(keys, k2);
   }
   
   @Test
   public void testPairsMatching() {
-    List<ComparableKey> keyList = new ArrayList<ComparableKey>();
+    List<String> keyList = new ArrayList<String>();
     ${valueTypeCap}ArrayList valueList = new ${valueTypeCap}ArrayList();
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
-    map.removeKey(cKeys[2]);
-    map.pairsMatching(new Object${valueTypeCap}Procedure<ComparableKey>() {
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
+    map.removeKey("Thirteen");
+    map.pairsMatching(new Object${valueTypeCap}Procedure<String>() {
 
       @Override
-      public boolean apply(ComparableKey first, ${valueType} second) {
+      public boolean apply(String first, ${valueType} second) {
         return (second % 2) == 0;
       }},
         keyList, valueList);
@@ -307,20 +279,20 @@
     valueList.sort();
     assertEquals(2, keyList.size());
     assertEquals(2, valueList.size());
-    assertSame(cKeys[3], keyList.get(0));
-    assertSame(cKeys[1], keyList.get(1));
+    assertSame("Fourteen", keyList.get(0));
+    assertSame("Twelve", keyList.get(1));
     assertEquals((${valueType})14, valueList.get(1) ${valueEpsilon});
     assertEquals((${valueType})12, valueList.get(0) ${valueEpsilon});
   }
   
   @Test
   public void testValues() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
-    map.removeKey(cKeys[2]);
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
+    map.removeKey("Thirteen");
     ${valueTypeCap}ArrayList values = new ${valueTypeCap}ArrayList(100);
     map.values(values);
     assertEquals(3, values.size());
@@ -334,9 +306,9 @@
   
   @Test
   public void testCopy() {
-    OpenObject${valueTypeCap}HashMap<NotComparableKey> map = new OpenObject${valueTypeCap}HashMap<NotComparableKey>();
-    map.put(ncKeys[0], (${valueType})11);
-    OpenObject${valueTypeCap}HashMap<NotComparableKey> map2 = (OpenObject${valueTypeCap}HashMap<NotComparableKey>) map.copy();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType})11);
+    OpenObject${valueTypeCap}HashMap<String> map2 = (OpenObject${valueTypeCap}HashMap<String>) map.copy();
     map.clear();
     assertEquals(1, map2.size());
   }
@@ -346,18 +318,18 @@
     // since there are no other subclasses of 
     // Abstractxxx available, we have to just test the
     // obvious.
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
-    map.removeKey(cKeys[2]);
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map2 = (OpenObject${valueTypeCap}HashMap<ComparableKey>) map.copy();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
+    map.removeKey("Thirteen");
+    OpenObject${valueTypeCap}HashMap<String> map2 = (OpenObject${valueTypeCap}HashMap<String>) map.copy();
     assertTrue(map.equals(map2));
     assertTrue(map2.equals(map));
     assertFalse("Hello Sailor".equals(map));
     assertFalse(map.equals("hello sailor"));
-    map2.removeKey(cKeys[0]);
+    map2.removeKey("Eleven");
     assertFalse(map.equals(map2));
     assertFalse(map2.equals(map));
   }
@@ -366,62 +338,74 @@
   
   @Test
   public void testKeysSortedByValue() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
-    map.removeKey(cKeys[2]);
-    List<ComparableKey> keys = new ArrayList<ComparableKey>();
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
+    map.removeKey("Thirteen");
+    List<String> keys = new ArrayList<String>();
     map.keysSortedByValue(keys);
-    ComparableKey[] keysArray = keys.toArray(new ComparableKey[keys.size()]);
-    assertArrayEquals(new ComparableKey[] {cKeys[0], cKeys[1], cKeys[3]},
+    String[] keysArray = keys.toArray(new String[keys.size()]);
+    assertArrayEquals(new String[] {"Eleven", "Twelve", "Fourteen"},
         keysArray);
   }
   
   @Test
   public void testPairsSortedByKey() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
     
     ${valueTypeCap}ArrayList values = new ${valueTypeCap}ArrayList();
-    List<ComparableKey> keys = new ArrayList<ComparableKey>();
+    List<String> keys = new ArrayList<String>();
     map.pairsSortedByKey(keys, values);
     
     assertEquals(4, keys.size());
     assertEquals(4, values.size());
-    assertEquals((${valueType}) 13, values.get(0) ${valueEpsilon});
-    assertSame(cKeys[2], keys.get(0));
+    assertEquals((${valueType}) 11, values.get(0) ${valueEpsilon});
+    assertSame("Eleven", keys.get(0));
     assertEquals((${valueType}) 14, values.get(1) ${valueEpsilon});
-    assertSame(cKeys[3], keys.get(1));
-    assertEquals((${valueType}) 12, values.get(2) ${valueEpsilon});
-    assertSame(cKeys[1], keys.get(2));
-    assertEquals((${valueType}) 11, values.get(3) ${valueEpsilon});
-    assertSame(cKeys[0], keys.get(3));
+    assertSame("Fourteen", keys.get(1));
+    assertEquals((${valueType}) 13, values.get(2) ${valueEpsilon});
+    assertSame("Thirteen", keys.get(2));
+    assertEquals((${valueType}) 12, values.get(3) ${valueEpsilon});
+    assertSame("Twelve", keys.get(3));
+  }
+  
+  @Test(expected=UnsupportedOperationException.class)
+  public void testPairsSortedByKeyNotComparable() {
+    OpenObject${valueTypeCap}HashMap<NotComparableKey> map = new OpenObject${valueTypeCap}HashMap<NotComparableKey>();
+    map.put(ncKeys[0], (${valueType}) 11);
+    map.put(ncKeys[1], (${valueType}) 12);
+    map.put(ncKeys[2], (${valueType}) 13);
+    map.put(ncKeys[3], (${valueType}) 14);
+    ${valueTypeCap}ArrayList values = new ${valueTypeCap}ArrayList();
+    List<NotComparableKey> keys = new ArrayList<NotComparableKey>();
+    map.pairsSortedByKey(keys, values);
   }
   
   @Test
   public void testPairsSortedByValue() {
-    OpenObject${valueTypeCap}HashMap<ComparableKey> map = new OpenObject${valueTypeCap}HashMap<ComparableKey>();
-    map.put(cKeys[0], (${valueType}) 11);
-    map.put(cKeys[1], (${valueType}) 12);
-    map.put(cKeys[2], (${valueType}) 13);
-    map.put(cKeys[3], (${valueType}) 14);
+    OpenObject${valueTypeCap}HashMap<String> map = new OpenObject${valueTypeCap}HashMap<String>();
+    map.put("Eleven", (${valueType}) 11);
+    map.put("Twelve", (${valueType}) 12);
+    map.put("Thirteen", (${valueType}) 13);
+    map.put("Fourteen", (${valueType}) 14);
     
-    List<ComparableKey> keys = new ArrayList<ComparableKey>();
+    List<String> keys = new ArrayList<String>();
     ${valueTypeCap}ArrayList values = new ${valueTypeCap}ArrayList();
     map.pairsSortedByValue(keys, values);
     assertEquals((${valueType}) 11, values.get(0) ${valueEpsilon});
-    assertEquals(cKeys[0], keys.get(0));
+    assertEquals("Eleven", keys.get(0));
     assertEquals((${valueType}) 12, values.get(1) ${valueEpsilon});
-    assertEquals(cKeys[1], keys.get(1));
+    assertEquals("Twelve", keys.get(1));
     assertEquals((${valueType}) 13, values.get(2) ${valueEpsilon});
-    assertEquals(cKeys[2], keys.get(2));
+    assertEquals("Thirteen", keys.get(2));
     assertEquals((${valueType}) 14, values.get(3) ${valueEpsilon});
-    assertEquals(cKeys[3], keys.get(3));
+    assertEquals("Fourteen", keys.get(3));
   }
  
  }

Added: lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/map/OpenHashMapTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/map/OpenHashMapTest.java?rev=900247&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/map/OpenHashMapTest.java (added)
+++ lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/map/OpenHashMapTest.java Mon Jan 18 00:13:13 2010
@@ -0,0 +1,265 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+  
+package org.apache.mahout.math.map;
+ 
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.mahout.math.function.ObjectObjectProcedure;
+import org.apache.mahout.math.function.ObjectProcedure;
+import org.apache.mahout.math.set.AbstractSet;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class OpenHashMapTest extends Assert {
+
+  @Test
+  public void testConstructors() {
+    OpenHashMap<String,String> map = new OpenHashMap<String, String>();
+    int[] capacity = new int[1];
+    double[] minLoadFactor = new double[1];
+    double[] maxLoadFactor = new double[1];
+    
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(AbstractSet.defaultCapacity, capacity[0]);
+    assertEquals(AbstractSet.defaultMaxLoadFactor, maxLoadFactor[0], 0.001);
+    assertEquals(AbstractSet.defaultMinLoadFactor, minLoadFactor[0], 0.001);
+    int prime = PrimeFinder.nextPrime(907);
+    map = new OpenHashMap<String, String>(prime);
+    
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(prime, capacity[0]);
+    assertEquals(AbstractSet.defaultMaxLoadFactor, maxLoadFactor[0], 0.001);
+    assertEquals(AbstractSet.defaultMinLoadFactor, minLoadFactor[0], 0.001);
+    
+    map = new OpenHashMap<String, String>(prime, 0.4, 0.8);
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(prime, capacity[0]);
+    assertEquals(0.4, minLoadFactor[0], 0.001);
+    assertEquals(0.8, maxLoadFactor[0], 0.001);
+  }
+  
+  @Test
+  public void testEnsureCapacity() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    int prime = PrimeFinder.nextPrime(907);
+    
+    map.ensureCapacity(prime);
+    int[] capacity = new int[1];
+    double[] minLoadFactor = new double[1];
+    double[] maxLoadFactor = new double[1];
+    
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(prime, capacity[0]);
+  }
+  
+  @Test
+  public void testClear() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11"); 
+    assertEquals(1, map.size());
+    map.clear();
+    assertEquals(0, map.size());
+  }
+  
+  @Test
+  @SuppressWarnings("unchecked")
+  public void testClone() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    OpenHashMap<String, String> map2 = (OpenHashMap<String, String>) map.clone();
+    map.clear();
+    assertEquals(1, map2.size());
+  }
+  
+  @Test
+  public void testContainsKey() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    assertTrue(map.containsKey("Eleven"));
+    assertFalse(map.containsKey("Twelve"));
+  }
+  
+  @Test
+  public void testContainValue() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    assertTrue(map.containsValue(new String("11")));
+    assertFalse(map.containsValue("Cowfeathers"));
+  }
+  
+  @Test
+  public void testForEachKey() {
+    final List<String> keys = new ArrayList<String>();
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    map.put("Twelve", "12");
+    map.put("Thirteen", "13");
+    map.put("Fourteen", "14");
+    map.remove(new String("Thirteen"));
+    map.forEachKey(new ObjectProcedure<String>() {
+      
+      @Override
+      public boolean apply(String element) {
+        keys.add(element);
+        return true;
+      }
+    });
+    
+    //2, 3, 1, 0
+    assertEquals(3, keys.size());
+    Collections.sort(keys);
+    assertSame("Eleven", keys.get(0));
+    assertSame("Fourteen", keys.get(1));
+    assertSame("Twelve", keys.get(2));
+  }
+  
+  private static class Pair implements Comparable<Pair> {
+    String k;
+    String v;
+    
+    Pair(String k, String v) {
+      this.k = k;
+      this.v = v;
+    }
+    
+    @Override
+    public int compareTo(Pair o) {
+      return k.compareTo(o.k);
+    }
+  }
+  
+  @Test
+  public void testForEachPair() {
+    final List<Pair> pairs = new ArrayList<Pair>();
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    map.put("Twelve", "12");
+    map.put("Thirteen", "13");
+    map.put("Fourteen", "14");
+    map.remove(new String("Thirteen"));
+    map.forEachPair(new ObjectObjectProcedure<String, String>() {
+      
+      @Override
+      public boolean apply(String first, String second) {
+        pairs.add(new Pair(first, second));
+        return true;
+      }
+    });
+    
+    Collections.sort(pairs);
+    assertEquals(3, pairs.size());
+    assertEquals("11", pairs.get(0).v );
+    assertEquals("Eleven", pairs.get(0).k);
+    assertEquals("14", pairs.get(1).v );
+    assertEquals("Fourteen", pairs.get(1).k);
+    assertEquals("12", pairs.get(2).v );
+    assertSame("Twelve", pairs.get(2).k);
+    
+    pairs.clear();
+    map.forEachPair(new ObjectObjectProcedure<String, String>() {
+      int count = 0;
+      
+      @Override
+      public boolean apply(String first, String second) {
+        pairs.add(new Pair(first, second));
+        count++;
+        return count < 2;
+      }
+    });
+    
+    assertEquals(2, pairs.size());
+  }
+  
+  @Test
+  public void testGet() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    map.put("Twelve", "12");
+    assertEquals("11", map.get(new String("Eleven")));
+  }
+
+  @Test
+  public void testKeys() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    map.put("Twelve", "12");
+    map.put("Thirteen", "13");
+    map.put("Fourteen", "14");
+    map.remove(new String("Thirteen"));
+    List<String> keys = new ArrayList<String>();
+    map.keys(keys);
+    Collections.sort(keys);
+    assertSame("Eleven", keys.get(0));
+    assertSame("Fourteen", keys.get(1));
+    Set<String> k2 = map.keySet();
+    List<String> k2l = new ArrayList<String>();
+    k2l.addAll(k2);
+    Collections.sort(k2l);
+    assertEquals(keys, k2l);
+  }
+  
+  @Test
+  public void testValues() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    map.put("Twelve", "12");
+    map.put("Thirteen", "13");
+    map.put("Fourteen", "14");
+    map.remove(new String("Thirteen"));
+    map.put("Extra", "11");
+    Collection<String> values = map.values();
+    assertEquals(4, values.size());
+  }
+  
+  // tests of the code in the abstract class
+  
+  @SuppressWarnings("unchecked")
+  @Test
+  public void testCopy() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    OpenHashMap<String, String> map2 = (OpenHashMap<String, String>) map.clone();
+    map.clear();
+    assertEquals(1, map2.size());
+  }
+  
+  @SuppressWarnings("unchecked")
+  @Test
+  public void testEquals() {
+    OpenHashMap<String, String> map = new OpenHashMap<String, String>();
+    map.put("Eleven", "11");
+    map.put("Twelve", "12");
+    map.put("Thirteen", "13");
+    map.put("Fourteen", "14");
+    map.remove(new String("Thirteen"));
+    OpenHashMap<String, String> map2 = (OpenHashMap<String, String>) map.clone();
+    assertTrue(map.equals(map2));
+    assertTrue(map2.equals(map));
+    assertFalse("Hello Sailor".equals(map));
+    assertFalse(map.equals("hello sailor"));
+    map2.remove("Eleven");
+    assertFalse(map.equals(map2));
+    assertFalse(map2.equals(map));
+  }
+ }

Propchange: lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/map/OpenHashMapTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/OpenHashSetTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/OpenHashSetTest.java?rev=900247&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/OpenHashSetTest.java (added)
+++ lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/OpenHashSetTest.java Mon Jan 18 00:13:13 2010
@@ -0,0 +1,164 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+ 
+  
+package org.apache.mahout.math.set;
+ 
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.mahout.math.function.ObjectProcedure;
+import org.apache.mahout.math.map.PrimeFinder;
+import org.apache.mahout.math.set.AbstractSet;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class OpenHashSetTest extends Assert {
+  
+  @Test
+  public void testConstructors() {
+    OpenCharHashSet map = new OpenCharHashSet();
+    int[] capacity = new int[1];
+    double[] minLoadFactor = new double[1];
+    double[] maxLoadFactor = new double[1];
+    
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(AbstractSet.defaultCapacity, capacity[0]);
+    assertEquals(AbstractSet.defaultMaxLoadFactor, maxLoadFactor[0], 0.001);
+    assertEquals(AbstractSet.defaultMinLoadFactor, minLoadFactor[0], 0.001);
+    int prime = PrimeFinder.nextPrime(907);
+    map = new OpenCharHashSet(prime);
+    
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(prime, capacity[0]);
+    assertEquals(AbstractSet.defaultMaxLoadFactor, maxLoadFactor[0], 0.001);
+    assertEquals(AbstractSet.defaultMinLoadFactor, minLoadFactor[0], 0.001);
+    
+    map = new OpenCharHashSet(prime, 0.4, 0.8);
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(prime, capacity[0]);
+    assertEquals(0.4, minLoadFactor[0], 0.001);
+    assertEquals(0.8, maxLoadFactor[0], 0.001);
+  }
+  
+  @Test
+  public void testEnsureCapacity() {
+    OpenCharHashSet map = new OpenCharHashSet();
+    int prime = PrimeFinder.nextPrime(907);
+    
+    map.ensureCapacity(prime);
+    int[] capacity = new int[1];
+    double[] minLoadFactor = new double[1];
+    double[] maxLoadFactor = new double[1];
+    
+    map.getInternalFactors(capacity, minLoadFactor, maxLoadFactor);
+    assertEquals(prime, capacity[0]);
+  }
+  
+  @Test
+  public void testClear() {
+    OpenHashSet<String> map = new OpenHashSet<String>();
+    map.add("Horsefeathers");
+    assertEquals(1, map.size());
+    map.clear();
+    assertEquals(0, map.size());
+  }
+  
+  @SuppressWarnings("unchecked")
+  @Test
+  public void testClone() {
+    OpenHashSet<String> map = new OpenHashSet<String>();
+    map.add((char) 11);
+    OpenHashSet<String> map2 = (OpenHashSet<String>) map.clone();
+    map.clear();
+    assertEquals(1, map2.size());
+  }
+  
+  @Test
+  public void testContains() {
+    OpenHashSet<String> map = new OpenHashSet<String>();
+    map.add("Horsefeathers");
+    assertTrue(map.contains(new String("Horsefeathers")));
+    assertFalse(map.contains("Cowfeathers"));
+  }
+  
+  @Test
+  public void testForEachKey() {
+    final List<String> keys = new ArrayList<String>();
+    OpenHashSet<String> map = new OpenHashSet<String>();
+    map.add("Eleven");
+    map.add("Twelve");
+    map.add("Thirteen");
+    map.add("Fourteen");
+    map.remove(new String("Thirteen"));
+    map.forEachKey(new ObjectProcedure<String>() {
+      
+      @Override
+      public boolean apply(String element) {
+        keys.add(element);
+        return true;
+      }
+    });
+    
+    String[] keysArray = keys.toArray(new String[keys.size()]);
+    Arrays.sort(keysArray);
+    
+    assertArrayEquals(new String[] { new String("Eleven"), 
+        new String("Fourteen"),
+        new String("Twelve")}, 
+        keysArray );
+  }
+  
+  @Test
+  public void testKeys() {
+    OpenHashSet<String> map = new OpenHashSet<String>();
+    map.add("Eleven");
+    map.add("Twelve");
+    List<String> keys = new ArrayList<String>();
+    map.keys(keys);
+    Collections.sort(keys);
+    assertEquals(new String("Eleven"), keys.get(0));
+    assertEquals(new String("Twelve"), keys.get(1));
+    List<String> k2 = map.keys();
+    Collections.sort(k2);
+    assertEquals(keys, k2);
+  }
+  
+  @SuppressWarnings("unchecked")
+  @Test
+  public void testEquals() {
+    OpenHashSet<String> map = new OpenHashSet<String>();
+    map.add("11");
+    map.add("12");
+    map.add("13");
+    map.add("14");
+    map.remove("13");
+    OpenHashSet<String> map2 = (OpenHashSet<String>) map.clone();
+    assertTrue(map.equals(map2));
+    assertTrue(map2.equals(map));
+    assertFalse("Hello Sailor".equals(map));
+    assertFalse(map.equals("hello sailor"));
+    map2.remove("11");
+    assertFalse(map.equals(map2));
+    assertFalse(map2.equals(map));
+  }
+ }

Propchange: lucene/mahout/trunk/math/src/test/java/org/apache/mahout/math/set/OpenHashSetTest.java
------------------------------------------------------------------------------
    svn:eol-style = native