001: /*
002: Copyright (c) 2004-2005, Dennis M. Sosnoski.
003: All rights reserved.
004:
005: Redistribution and use in source and binary forms, with or without modification,
006: are permitted provided that the following conditions are met:
007:
008: * Redistributions of source code must retain the above copyright notice, this
009: list of conditions and the following disclaimer.
010: * Redistributions in binary form must reproduce the above copyright notice,
011: this list of conditions and the following disclaimer in the documentation
012: and/or other materials provided with the distribution.
013: * Neither the name of JiBX nor the names of its contributors may be used
014: to endorse or promote products derived from this software without specific
015: prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
018: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
019: WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
020: DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
021: ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
022: (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
023: LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
024: ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
026: SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028:
029: package org.jibx.util;
030:
031: /**
032: * Fixed size hash map using <code>String</code> values as keys mapped to
033: * primitive <code>int</code> values.
034: *
035: * @author Dennis M. Sosnoski
036: */
037: public class StringIntSizedMap {
038: /** Default fill fraction for sizing of tables. */
039: public static final double DEFAULT_FILL_FRACTION = 0.4;
040:
041: /** Default value returned when key not found in table. */
042: public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;
043:
044: /** Size of array used for keys. */
045: protected final int m_arraySize;
046:
047: /** Array of key table slots. */
048: protected final String[] m_keyTable;
049:
050: /** Array of value table slots. */
051: protected final int[] m_valueTable;
052:
053: /** Value returned when key not found in table. */
054: protected final int m_notFoundValue;
055:
056: /** Offset added (modulo table size) to slot number on collision. */
057: protected final int m_hitOffset;
058:
059: /**
060: * Constructor with full specification.
061: *
062: * @param count number of values to assume in sizing of table
063: * @param fill fraction fill for table (maximum of <code>0.7</code>, to
064: * prevent excessive collisions)
065: * @param miss value returned when key not found in table
066: */
067: public StringIntSizedMap(int count, double fill, int miss) {
068:
069: // make sure the fill fraction is in a reasonable range
070: if (fill <= 0.0 || fill > 0.7) {
071: throw new IllegalArgumentException("Fill fraction of "
072: + fill + " is out of allowed range");
073: }
074:
075: // compute initial table size (ensuring odd)
076: int size = Math.max((int) (count / fill), 11);
077: size += (size + 1) % 2;
078: m_arraySize = size;
079:
080: // initialize the table information
081: m_keyTable = new String[size];
082: m_valueTable = new int[size];
083: for (int i = 0; i < size; i++) {
084: m_valueTable[i] = -1;
085: }
086: m_hitOffset = m_arraySize / 2;
087: m_notFoundValue = miss;
088: }
089:
090: /**
091: * Constructor with value count and miss value specified. Uses default fill
092: * fraction.
093: *
094: * @param count number of values to assume in initial sizing of table
095: * @param miss value returned when key not found in table
096: */
097: public StringIntSizedMap(int count, int miss) {
098: this (count, DEFAULT_FILL_FRACTION, miss);
099: }
100:
101: /**
102: * Constructor with only value count specified. Uses default fill fraction
103: * and miss value.
104: *
105: * @param count number of values to assume in initial sizing of table
106: */
107: public StringIntSizedMap(int count) {
108: this (count, DEFAULT_FILL_FRACTION, DEFAULT_NOT_FOUND);
109: }
110:
111: /**
112: * Step the slot number for an entry. Adds the collision offset (modulo
113: * the table size) to the slot number.
114: *
115: * @param slot slot number to be stepped
116: * @return stepped slot number
117: */
118: private final int stepSlot(int slot) {
119: return (slot + m_hitOffset) % m_arraySize;
120: }
121:
122: /**
123: * Find free slot number for entry. Starts at the slot based directly
124: * on the hashed key value. If this slot is already occupied, it adds
125: * the collision offset (modulo the table size) to the slot number and
126: * checks that slot, repeating until an unused slot is found.
127: *
128: * @param slot initial slot computed from key
129: * @return slot at which entry was added
130: */
131: private final int freeSlot(int slot) {
132: while (m_keyTable[slot] != null) {
133: slot = stepSlot(slot);
134: }
135: return slot;
136: }
137:
138: /**
139: * Standard base slot computation for a key. This method may be used
140: * directly for key lookup using either the <code>hashCode()</code> method
141: * defined for the key objects or the <code>System.identityHashCode()</code>
142: * method, as selected by the hash technique constructor parameter. To
143: * implement a hash class based on some other methods of hashing and/or
144: * equality testing, define a separate method in the subclass with a
145: * different name and use that method instead. This avoids the overhead
146: * caused by overrides of a very heavily used method.
147: *
148: * @param key key value to be computed
149: * @return base slot for key
150: */
151: private final int standardSlot(String key) {
152: return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
153: }
154:
155: /**
156: * Standard find key in table. This uses identity comparisons for the key
157: * values.
158: *
159: * @param key to be found in table
160: * @return index of matching key, or <code>-index-1</code> of slot to be
161: * used for inserting key in table if not already present (always negative)
162: */
163: private int standardFind(String key) {
164:
165: // find the starting point for searching table
166: int slot = standardSlot(key);
167:
168: // scan through table to find target key
169: while (m_keyTable[slot] != null) {
170:
171: // check if we have a match on target key
172: if (m_keyTable[slot].equals(key)) {
173: return slot;
174: } else {
175: slot = stepSlot(slot);
176: }
177:
178: }
179: return -slot - 1;
180: }
181:
182: /**
183: * Add an entry to the table. If the key is already present in the table,
184: * this replaces the existing value associated with the key.
185: *
186: * @param key key to be added to table (non-<code>null</code>)
187: * @param value associated value for key
188: * @return value previously associated with key, or reserved not found
189: * value if key not previously present in table
190: */
191: public int add(String key, int value) {
192:
193: // first validate the parameters
194: if (key == null) {
195: throw new IllegalArgumentException("null key not supported");
196: } else if (value == -1) {
197: throw new IllegalArgumentException(
198: "value matching not found return not supported");
199: } else {
200:
201: // check space and duplicate key
202: int offset = standardFind(key);
203: if (offset >= 0) {
204:
205: // replace existing value for key
206: int prior = m_valueTable[offset];
207: m_valueTable[offset] = value;
208: return prior;
209:
210: } else {
211:
212: // add new pair to table
213: offset = -offset - 1;
214: m_keyTable[offset] = key;
215: m_valueTable[offset] = value;
216: return m_notFoundValue;
217:
218: }
219: }
220: }
221:
222: /**
223: * Check if an entry is present in the table. This method is supplied to
224: * support the use of values matching the reserved not found value.
225: *
226: * @param key key for entry to be found
227: * @return <code>true</code> if key found in table, <code>false</code>
228: * if not
229: */
230: public final boolean containsKey(String key) {
231: return standardFind(key) >= 0;
232: }
233:
234: /**
235: * Find an entry in the table.
236: *
237: * @param key key for entry to be returned
238: * @return value for key, or reserved not found value if key not found
239: */
240: public final int get(String key) {
241: int slot = standardFind(key);
242: if (slot >= 0) {
243: return m_valueTable[slot];
244: } else {
245: return m_notFoundValue;
246: }
247: }
248:
249: /**
250: * Set the table to the empty state.
251: */
252: public void clear() {
253: for (int i = 0; i < m_keyTable.length; i++) {
254: m_keyTable[i] = null;
255: m_valueTable[i] = m_notFoundValue;
256: }
257: }
258: }
|