001: ///////////////////////////////////////////////////////////////////////////////
002: // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
003: //
004: // This library is free software; you can redistribute it and/or
005: // modify it under the terms of the GNU Lesser General Public
006: // License as published by the Free Software Foundation; either
007: // version 2.1 of the License, or (at your option) any later version.
008: //
009: // This library is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU Lesser General Public
015: // License along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: ///////////////////////////////////////////////////////////////////////////////
018:
019: package gnu.trove;
020:
021: /**
022: * The base class for hashtables of primitive values. Since there is
023: * no notion of object equality for primitives, it isn't possible to
024: * use a `REMOVED' object to track deletions in an open-addressed table.
025: * So, we have to resort to using a parallel `bookkeeping' array of bytes,
026: * in which flags can be set to indicate that a particular slot in the
027: * hash table is FREE, FULL, or REMOVED.
028: *
029: * Created: Fri Jan 11 18:55:16 2002
030: *
031: * @author Eric D. Friedman
032: * @version $Id: TPrimitiveHash.java,v 1.4 2006/11/10 23:27:57 robeden Exp $
033: */
034:
035: abstract public class TPrimitiveHash extends THash {
036: /** flags indicating whether each position in the hash is
037: * FREE, FULL, or REMOVED */
038: protected transient byte[] _states;
039:
040: /* constants used for state flags */
041:
042: /** flag indicating that a slot in the hashtable is available */
043: protected static final byte FREE = 0;
044:
045: /** flag indicating that a slot in the hashtable is occupied */
046: protected static final byte FULL = 1;
047:
048: /** flag indicating that the value of a slot in the hashtable
049: * was deleted */
050: protected static final byte REMOVED = 2;
051:
052: /**
053: * Creates a new <code>THash</code> instance with the default
054: * capacity and load factor.
055: */
056: public TPrimitiveHash() {
057: super ();
058: }
059:
060: /**
061: * Creates a new <code>TPrimitiveHash</code> instance with a prime
062: * capacity at or near the specified capacity and with the default
063: * load factor.
064: *
065: * @param initialCapacity an <code>int</code> value
066: */
067: public TPrimitiveHash(int initialCapacity) {
068: this (initialCapacity, DEFAULT_LOAD_FACTOR);
069: }
070:
071: /**
072: * Creates a new <code>TPrimitiveHash</code> instance with a prime
073: * capacity at or near the minimum needed to hold
074: * <tt>initialCapacity<tt> elements with load factor
075: * <tt>loadFactor</tt> without triggering a rehash.
076: *
077: * @param initialCapacity an <code>int</code> value
078: * @param loadFactor a <code>float</code> value
079: */
080: public TPrimitiveHash(int initialCapacity, float loadFactor) {
081: super ();
082: _loadFactor = loadFactor;
083: setUp((int) Math.ceil(initialCapacity / loadFactor));
084: }
085:
086: public Object clone() {
087: TPrimitiveHash h = (TPrimitiveHash) super .clone();
088: h._states = (byte[]) this ._states.clone();
089: return h;
090: }
091:
092: /**
093: * Returns the capacity of the hash table. This is the true
094: * physical capacity, without adjusting for the load factor.
095: *
096: * @return the physical capacity of the hash table.
097: */
098: protected int capacity() {
099: return _states.length;
100: }
101:
102: /**
103: * Delete the record at <tt>index</tt>.
104: *
105: * @param index an <code>int</code> value
106: */
107: protected void removeAt(int index) {
108: _states[index] = REMOVED;
109: super .removeAt(index);
110: }
111:
112: /**
113: * initializes the hashtable to a prime capacity which is at least
114: * <tt>initialCapacity + 1</tt>.
115: *
116: * @param initialCapacity an <code>int</code> value
117: * @return the actual capacity chosen
118: */
119: protected int setUp(int initialCapacity) {
120: int capacity;
121:
122: capacity = super .setUp(initialCapacity);
123: _states = new byte[capacity];
124: return capacity;
125: }
126: } // TPrimitiveHash
|