KickJava   Java API By Example, From Geeks To Geeks.

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


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>double</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.<p>
32  *
33  * Note that the hashing function implemented in this class has not been tested
34  * extensively and may be unsuitable for use with some patterns of data values.
35  * To change the hashing function, modify the <code>computeSlot()</code>
36  * method.
37  *
38  * @author Dennis M. Sosnoski
39  * @version 1.0
40  */
41
42 public class DoubleHashSet extends PrimitiveSetBase
43 {
44     /** Array of key table slots. */
45     protected double[] m_keyTable;
46
47     /**
48      * Constructor with full specification.
49      *
50      * @param count number of values to assume in initial sizing of table
51      * @param fill fraction full allowed for table before growing
52      */
53     
54     public DoubleHashSet(int count, double fill) {
55         super(count, fill, double.class);
56     }
57
58     /**
59      * Constructor with only size supplied. Uses default value for fill
60      * fraction.
61      *
62      * @param count number of values to assume in initial sizing of table
63      */
64     
65     public DoubleHashSet(int count) {
66         this(count, DEFAULT_FILL);
67     }
68
69     /**
70      * Default constructor.
71      */
72     
73     public DoubleHashSet() {
74         this(0, DEFAULT_FILL);
75     }
76
77     /**
78      * Copy (clone) constructor.
79      *
80      * @param base instance being copied
81      */
82     
83     public DoubleHashSet(DoubleHashSet base) {
84         super(base);
85     }
86
87     /**
88      * Get the backing array of keys. This implementation of an abstract
89      * method is used by the type-agnostic base class code to access the
90      * array used for type-specific storage by the child class.
91      *
92      * @return backing key array object
93      */
94     
95     protected Object JavaDoc getKeyArray() {
96         return m_keyTable;
97     }
98
99     /**
100      * Set the backing array of keys. This implementation of an abstract
101      * method is used by the type-agnostic base class code to set the
102      * array used for type-specific storage by the child class.
103      *
104      * @param array backing key array object
105      */
106     
107     protected void setKeyArray(Object JavaDoc array) {
108         m_keyTable = (double[])array;
109     }
110
111     /**
112      * Reinsert a key into the hash set. This method is designed for
113      * internal use when the table is being modified, and does not adjust
114      * the count present or check the table capacity.
115      *
116      * @param slot position of key to be reinserted into hash set
117      * @return <code>true</code> if the slot number used by the key has
118      * has changed, <code>false</code> if not
119      */
120     
121     protected final boolean reinsert(int slot) {
122         m_flagTable[slot] = false;
123         return assignSlot(m_keyTable[slot]) != slot;
124     }
125
126     /**
127      * Restructure the table. This implementation of an abstract method is
128      * used when the table is increasing or decreasing in size,
129      * and works directly with the old table representation arrays. It
130      * inserts keys from the old array directly into the table without
131      * adjusting the count present or checking the table size.
132      *
133      * @param flags array of flags for array slots used
134      * @param karray array of keys
135      */
136     
137     protected void restructure(boolean[] flags, Object JavaDoc karray) {
138         double[] keys = (double[])karray;
139         for (int i = 0; i < flags.length; i++) {
140             if (flags[i]) {
141                 assignSlot(keys[i]);
142             }
143         }
144     }
145
146     /**
147      * Compute the base slot for a key.
148      *
149      * @param key key value to be computed
150      * @return base slot for key
151      */
152     
153     protected final int computeSlot(double key) {
154         long bits = Double.doubleToRawLongBits(key);
155         int reduced = ((int)(bits >> 48)) + ((int)(bits >> 24)) + (int)bits;
156         return (reduced * KEY_MULTIPLIER & Integer.MAX_VALUE) %
157             m_flagTable.length;
158     }
159
160     /**
161      * Assign slot for key. Starts at the slot found by the hashed key
162      * value. If this slot is already occupied, it steps the slot number and
163      * checks the resulting slot, repeating until an unused slot is found. This
164      * method does not check for duplicate keys, so it should only be used for
165      * internal reordering of the tables.
166      *
167      * @param key key to be added to table
168      * @return slot at which key was added
169      */
170     
171     protected int assignSlot(double key) {
172         int offset = freeSlot(computeSlot(key));
173         m_flagTable[offset] = true;
174         m_keyTable[offset] = key;
175         return offset;
176     }
177
178     /**
179      * Add a key to the table.
180      *
181      * @param key key to be added to table
182      * @return <code>true</code> if key added to set, <code>false</code> if
183      * already present in set
184      */
185     
186     public boolean add(double key) {
187         ensureCapacity(m_entryCount+1);
188         int offset = -internalFind(key) - 1;
189         if (offset >= 0) {
190             m_entryCount++;
191             m_flagTable[offset] = true;
192             m_keyTable[offset] = key;
193             return true;
194         } else {
195             return false;
196         }
197     }
198
199     /**
200      * Internal find key in table.
201      *
202      * @param key to be found in table
203      * @return index of matching key, or <code>-index-1</code> of slot to be
204      * used for inserting key in table if not already present (always negative)
205      */
206     
207     protected final int internalFind(double key) {
208         int slot = computeSlot(key);
209         while (m_flagTable[slot]) {
210             if (key == m_keyTable[slot]) {
211                 return slot;
212             }
213             slot = stepSlot(slot);
214         }
215         return -slot - 1;
216     }
217
218     /**
219      * Check if a key is present in the set.
220      *
221      * @param key key to be found
222      * @return <code>true</code> if key found in table, <code>false</code>
223      * if not
224      */
225     
226     public boolean contains(double key) {
227         return internalFind(key) >= 0;
228     }
229
230     /**
231      * Remove a key from the table.
232      *
233      * @param key key to be removed from table
234      * @return <code>true</code> if key successfully removed from set,
235      * <code>false</code> if key not found in set
236      */
237     
238     public boolean remove(double key) {
239         int slot = internalFind(key);
240         if (slot >= 0) {
241             m_flagTable[slot] = false;
242             m_entryCount--;
243             while (m_flagTable[(slot = stepSlot(slot))]) {
244                 reinsert(slot);
245             }
246             return true;
247         } else {
248             return false;
249         }
250     }
251
252     /**
253      * Construct a copy of the table.
254      *
255      * @return copy of table
256      */
257     
258     public Object JavaDoc clone() {
259         return new DoubleHashSet(this);
260     }
261 }
262
Popular Tags