KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sosnoski > util > hashset > IntHashSet


1 /*
2  * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20  * IN THE SOFTWARE.
21  */
22
23 package com.sosnoski.util.hashset;
24
25 /**
26  * Hash set using primitive <code>int</code> values. This implementation is
27  * unsynchronized in order to provide the best possible performance for typical
28  * usage scenarios, so explicit synchronization must be implemented by a wrapper
29  * class or directly by the application in cases where instances are modified
30  * in a multithreaded environment. See the base classes for other details of
31  * the hash set implementation.
32  *
33  * @author Dennis M. Sosnoski
34  * @version 1.0
35  */
36
37 public class IntHashSet extends PrimitiveSetBase
38 {
39     /** Array of key table slots. */
40     protected int[] m_keyTable;
41
42     /**
43      * Constructor with full specification.
44      *
45      * @param count number of values to assume in initial sizing of table
46      * @param fill fraction full allowed for table before growing
47      */
48     
49     public IntHashSet(int count, double fill) {
50         super(count, fill, int.class);
51     }
52
53     /**
54      * Constructor with only size supplied. Uses default value for fill
55      * fraction.
56      *
57      * @param count number of values to assume in initial sizing of table
58      */
59     
60     public IntHashSet(int count) {
61         this(count, DEFAULT_FILL);
62     }
63
64     /**
65      * Default constructor.
66      */
67     
68     public IntHashSet() {
69         this(0, DEFAULT_FILL);
70     }
71
72     /**
73      * Copy (clone) constructor.
74      *
75      * @param base instance being copied
76      */
77     
78     public IntHashSet(IntHashSet base) {
79         super(base);
80     }
81
82     /**
83      * Get the backing array of keys. This implementation of an abstract
84      * method is used by the type-agnostic base class code to access the
85      * array used for type-specific storage by the child class.
86      *
87      * @return backing key array object
88      */
89     
90     protected Object JavaDoc getKeyArray() {
91         return m_keyTable;
92     }
93
94     /**
95      * Set the backing array of keys. This implementation of an abstract
96      * method is used by the type-agnostic base class code to set the
97      * array used for type-specific storage by the child class.
98      *
99      * @param array backing key array object
100      */
101     
102     protected void setKeyArray(Object JavaDoc array) {
103         m_keyTable = (int[])array;
104     }
105
106     /**
107      * Reinsert a key into the hash map. This method is designed for
108      * internal use when the table is being modified, and does not adjust
109      * the count present or check the table capacity.
110      *
111      * @param slot position of key to be reinserted into hash map
112      * @return <code>true</code> if the slot number used by the key has
113      * has changed, <code>false</code> if not
114      */
115     
116     protected final boolean reinsert(int slot) {
117         m_flagTable[slot] = false;
118         return assignSlot(m_keyTable[slot]) != slot;
119     }
120
121     /**
122      * Restructure the table. This implementation of an abstract method is
123      * used when the table is increasing or decreasing in size,
124      * and works directly with the old table representation arrays. It
125      * inserts keys from the old array directly into the table without
126      * adjusting the count present or checking the table size.
127      *
128      * @param flags array of flags for array slots used
129      * @param karray array of keys
130      */
131     
132     protected void restructure(boolean[] flags, Object JavaDoc karray) {
133         int[] keys = (int[])karray;
134         for (int i = 0; i < flags.length; i++) {
135             if (flags[i]) {
136                 assignSlot(keys[i]);
137             }
138         }
139     }
140
141     /**
142      * Compute the base slot for a key.
143      *
144      * @param key key value to be computed
145      * @return base slot for key
146      */
147     
148     protected final int computeSlot(int key) {
149         return (key * KEY_MULTIPLIER & Integer.MAX_VALUE) % m_flagTable.length;
150     }
151
152     /**
153      * Assign slot for key. Starts at the slot found by the hashed key
154      * value. If this slot is already occupied, it steps the slot number and
155      * checks the resulting slot, repeating until an unused slot is found. This
156      * method does not check for duplicate keys, so it should only be used for
157      * internal reordering of the tables.
158      *
159      * @param key key to be added to table
160      * @return slot at which key was added
161      */
162     
163     protected int assignSlot(int key) {
164         int offset = freeSlot(computeSlot(key));
165         m_flagTable[offset] = true;
166         m_keyTable[offset] = key;
167         return offset;
168     }
169
170     /**
171      * Add a key to the set.
172      *
173      * @param key key to be added to set
174      * @return <code>true</code> if key added to set, <code>false</code> if
175      * already present in set
176      */
177     
178     public boolean add(int key) {
179         ensureCapacity(m_entryCount+1);
180         int offset = -internalFind(key) - 1;
181         if (offset >= 0) {
182             m_entryCount++;
183             m_flagTable[offset] = true;
184             m_keyTable[offset] = key;
185             return true;
186         } else {
187             return false;
188         }
189     }
190
191     /**
192      * Internal find key in table.
193      *
194      * @param key to be found in table
195      * @return index of matching key, or <code>-index-1</code> of slot to be
196      * used for inserting key in table if not already present (always negative)
197      */
198     
199     protected final int internalFind(int key) {
200         int slot = computeSlot(key);
201         while (m_flagTable[slot]) {
202             if (key == m_keyTable[slot]) {
203                 return slot;
204             }
205             slot = stepSlot(slot);
206         }
207         return -slot - 1;
208     }
209
210     /**
211      * Check if a key is present in the table.
212      *
213      * @param key key to be found
214      * @return <code>true</code> if key found in table, <code>false</code>
215      * if not
216      */
217     
218     public boolean contains(int key) {
219         return internalFind(key) >= 0;
220     }
221
222     /**
223      * Remove a key from the table.
224      *
225      * @param key key to be removed from table
226      * @return <code>true</code> if key successfully removed from set,
227      * <code>false</code> if key not found in set
228      */
229     
230     public boolean remove(int key) {
231         int slot = internalFind(key);
232         if (slot >= 0) {
233             m_flagTable[slot] = false;
234             m_entryCount--;
235             while (m_flagTable[(slot = stepSlot(slot))]) {
236                 reinsert(slot);
237             }
238             return true;
239         } else {
240             return false;
241         }
242     }
243
244     /**
245      * Construct a copy of the table.
246      *
247      * @return copy of table
248      */
249     
250     public Object JavaDoc clone() {
251         return new IntHashSet(this);
252     }
253 }
254
Popular Tags