ObjectHashSet


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