StringHashSet


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