source: src/main/java/weka/classifiers/lazy/kstar/KStarCache.java @ 10

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program 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 General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/**
 *    KStarCache.java
 *    Copyright (C) 1995 University of Waikato
 *    Java port to Weka by Abdelaziz Mahoui (am14@cs.waikato.ac.nz).
 *
 */


package weka.classifiers.lazy.kstar;

import weka.core.RevisionHandler;
import weka.core.RevisionUtils;

import java.io.Serializable;

/**
 * A class representing the caching system used to keep track of each attribute
 * value and its corresponding scale factor or stop parameter.
 *
 * @author Len Trigg (len@reeltwo.com)
 * @author Abdelaziz Mahoui (am14@cs.waikato.ac.nz)
 * @version $Revision: 1.11 $
 */
public class KStarCache
  implements Serializable, RevisionHandler {

  /** for serialization */
  private static final long serialVersionUID = -7693632394267140678L;
  
  /**
   * cache table
   */
  CacheTable m_Cache = new CacheTable();
  
  /**
   * Stores the specified values in the cahce table for easy retrieval.
   *
   * @param key attribute value used key to lookup the cache table.
   * @param value cache parameter: attribute scale/stop parameter.
   * @param pmiss cache parameter: transformation probability to 
   * attribute with missing value.
   */
  public void store(double key, double value, double pmiss) {
    if ( !m_Cache.containsKey(key) ) {
      m_Cache.insert(key, value, pmiss);
    }
  }
  
  /**
   * Checks if the specified key maps with an entry in the cache table
   *
   * @param key the key to map with an entry in the hashtable.
   */
  public boolean containsKey(double key) {
    if ( m_Cache.containsKey(key) ) {
      return true;
    }
    return false;
  }
  
  /**
   * Returns the values in the cache mapped by the specified key
   *
   * @param key the key used to retrieve the table entry.
   */
  public TableEntry getCacheValues( double key ) {
    if ( m_Cache.containsKey(key) ) {
      return m_Cache.getEntry(key);
    }
    return null;
  }

  /**
   * A custom hashtable class to support the caching system.
   *
   */
  public class CacheTable
    implements Serializable, RevisionHandler {

    /** for serialization */
    private static final long serialVersionUID = -8086106452588253423L;

    /** The hash table data. */
    private TableEntry [] m_Table;

    /** The total number of entries in the hash table. */
    private int m_Count;

    /** Rehashes the table when count exceeds this threshold. */
    private int m_Threshold;

    /** The load factor for the hashtable. */
    private float m_LoadFactor;

    /** The default size of the hashtable */
    private final int DEFAULT_TABLE_SIZE = 101;

    /** The default load factor for the hashtable */
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    //    private final float DEFAULT_LOAD_FACTOR = 0.5f;
    /** Accuracy value for equality */
    private final double EPSILON = 1.0E-5;
    
    /**
     * Constructs a new hashtable with a default capacity and load factor.
     */
    public CacheTable(int size, float loadFactor) {
      m_Table = new TableEntry[size];
      m_LoadFactor = loadFactor;
      m_Threshold = (int)(size * loadFactor);
      m_Count = 0;
    }
    
    /**
     * Constructs a new hashtable with a default capacity and load factor.
     */
    public CacheTable() {
      this(101, 0.75f);
    }
    
    /**
     * Tests if the specified double is a key in this hashtable.
     */
    public boolean containsKey(double key) {
      TableEntry [] table = m_Table;
      int hash = hashCode(key);
      int index = (hash & 0x7FFFFFFF) % table.length;
      for (TableEntry e = table[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && (Math.abs(e.key - key) < EPSILON)) {
          return true;
        }
      }
      return false;
    }
    
    /**
     * Inserts a new entry in the hashtable using the specified key. 
     * If the key already exist in the hashtable, do nothing.
     */
    public void insert(double key, double value, double pmiss) {
      // Makes sure the key is not already in the hashtable.
      TableEntry e, ne;
      TableEntry [] table = m_Table;
      int hash = hashCode(key);
      int index = (hash & 0x7FFFFFFF) % table.length;
      // start looking along the chain
      for (e = table[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && (Math.abs(e.key - key) < EPSILON)) {
          return;
        }
      }
      // At this point, key is not in table.
      // Creates a new entry.
      ne = new TableEntry( hash, key, value, pmiss, table[index] );
      // Put entry at the head of the chain.
      table[index] = ne;
      m_Count++;
      // Rehash the table if the threshold is exceeded
      if (m_Count >= m_Threshold) {
        rehash();
      }
    }
    
    /**
     * Returns the table entry to which the specified key is mapped in 
     * this hashtable.
     * @return a table entry.
     */
    public TableEntry getEntry(double key) {
      TableEntry [] table = m_Table;
      int hash = hashCode(key);
      int index = (hash & 0x7FFFFFFF) % table.length;
      for (TableEntry e = table[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && (Math.abs(e.key - key) < EPSILON)) {
          return e;
        }
      }
      return null;
    }
    
    /**
     * Returns the number of keys in this hashtable.
     * @return the number of keys in this hashtable.
     */
    public int size() {
      return m_Count;
    }
    
    /**
     * Tests if this hashtable maps no keys to values.
     * @return true if this hastable maps no keys to values.
     */
    public boolean isEmpty() {
      return m_Count == 0;
    }
    
    /**
     * Clears this hashtable so that it contains no keys.
     */
    public void clear() {
      TableEntry table[] = m_Table;
      for (int index = table.length; --index >= 0; ) {
        table[index] = null;
      }
      m_Count = 0;
    }
    
    /**
     * Rehashes the contents of the hashtable into a hashtable with a 
     * larger capacity. This method is called automatically when the 
     * number of keys in the hashtable exceeds this hashtable's capacity 
     * and load factor. 
     */
    private void rehash() {
      int oldCapacity = m_Table.length;
      TableEntry [] oldTable = m_Table;    
      int newCapacity = oldCapacity * 2 + 1;
      TableEntry [] newTable = new TableEntry[newCapacity];
      m_Threshold = (int)(newCapacity * m_LoadFactor);
      m_Table = newTable;
      TableEntry e, old;
      for (int i = oldCapacity ; i-- > 0 ;) {
        for (old = oldTable[i] ; old != null ; ) {
          e = old;
          old = old.next;
          int index = (e.hash & 0x7FFFFFFF) % newCapacity;
          e.next = newTable[index];
          newTable[index] = e;
        }
      }
    }
    
    /**
     * Returns the hash code of the specified double.
     * @return the hash code of the specified double.
     */
    private int hashCode(double key) {
      long bits = Double.doubleToLongBits(key);
      return (int)(bits ^ (bits >> 32));
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 1.11 $");
    }
  } // CacheTable
  
  /**
   * Hashtable collision list.
   */
  public class TableEntry
    implements Serializable, RevisionHandler {

    /** for serialization */
    private static final long serialVersionUID = 4057602386766259138L;

    /** attribute value hash code */
    public int hash;

    /** attribute value */
    public double key;

    /** scale factor or stop parameter */
    public double value;

    /** transformation probability to missing value */
    public double pmiss;

    /** next table entry (separate chaining) */
    public TableEntry next = null;

    /** Constructor */
    public TableEntry(int hash, double key, double value, 
                      double pmiss, TableEntry next) {
      this.hash  = hash;
      this.key   = key;
      this.value = value;
      this.pmiss = pmiss;
      this.next  = next;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 1.11 $");
    }
  }  // TableEntry
  
  /**
   * Returns the revision string.
   * 
   * @return            the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 1.11 $");
  }
  
} // Cache