ObjectSetBase


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  import java.lang.reflect.Array  ;
26  import java.util.Iterator  ;
27  
28  import com.sosnoski.util.ObjectHashBase;
29  import com.sosnoski.util.SparseArrayIterator;
30  
31  /**
32   * Base class for type-specific hash set classes with object keys. This
33   * class builds on the basic structure provided by <code>ObjectHashBase</code>,
34   * specializing it for the case of a hash set where the keys are the only data.
35   * See the base class description for details of the implementation.<p>
36   *
37   * Hash sets based on this class are unsynchronized in order to provide the
38   * best possible performance for typical usage scenarios, so explicit
39   * synchronization must be implemented by the subclass or the application in
40   * cases where they are to be modified in a multithreaded environment.<p>
41   *
42   * Subclasses need to implement the abstract methods defined by the base class
43   * for working with the key array, and the abstract restructuring method
44   * defined by this class, as well as the actual data access methods (at least
45   * the basic <code>add</code>, <code>contains</code>, and <code>remove</code>
46   * methods).
47   *
48   * @author Dennis M. Sosnoski
49   * @version 1.1
50   */
51  
52  public abstract class ObjectSetBase extends ObjectHashBase
53  {
54      /**
55       * Constructor with full specification.
56       *
57       * @param count number of values to assume in initial sizing of table
58       * @param fill fraction full allowed for table before growing
59       * @param type type of objects contained in table
60       * @param tech hash technique specifier (one of STANDARD_HASH,
61       * IDENTITY_COMP, or IDENTITY_HASH, inherited from
62       * {@link com.sosnoski.util.hashset.ObjectSetBase})
63       */
64  
65      public ObjectSetBase(int count, double fill, Class   type, Object   tech) {
66          super(count, fill, type, tech);
67      }
68  
69      /**
70       * Copy (clone) constructor.
71       *
72       * @param base instance being copied
73       */
74  
75      public ObjectSetBase(ObjectSetBase base) {
76          super(base);
77      }
78  
79      /**
80       * Reinsert an entry into the table. This method is used when the table is
81       * being directly modified by the base class, and should not adjust the
82       * count present or check the table capacity.
83       *
84       * @param slot position of entry to be reinserted into table
85       * @return <code>true</code> if the slot number used by the entry has
86       * has changed, <code>false</code> if not
87       */
88  
89      protected abstract boolean reinsert(int slot);
90  
91      /**
92       * Restructure the table. This abstract method is used when the table
93       * is increasing or decreasing in size, and works directly with the old
94       * table representation array. It should insert keys from the old array
95       * directly into the table without adjusting the count present or checking
96       * the table size.
97       *
98       * @param karray array of keys
99       */
100 
101     protected abstract void restructure(Object   karray);
102 
103     /**
104      * Resize the base array after a size change. This implementation of the
105      * abstract base class method allocates the new array and then calls
106      * another method for handling the actual transfer of the key set from the
107      * old array to the new one.
108      *
109      * @param size new size for base arrays
110      */
111 
112     protected void reallocate(int size) {
113 
114         // allocate the larger array
115         Object   keys = getKeyArray();
116         Class   type = keys.getClass().getComponentType();
117         setKeyArray(Array.newInstance(type, size));
118 
119         // reinsert all entries into new arrays
120         restructure(keys);
121     }
122 
123     /**
124      * Internal remove item from the table. Removes the item from the table
125      * by setting the key entry to <code>null</code> and adjusting the count
126      * present, then chains through the table to reinsert any other items
127      * which may have collided with the removed item.
128      *
129      * @param slot index number of item to be removed
130      */
131 
132     protected void internalRemove(int slot) {
133         Object  [] items = getKeyArray();
134         items[slot] = null;
135         m_entryCount--;
136         while (items[(slot = stepSlot(slot))] != null) {
137             reinsert(slot);
138         }
139     }
140 
141     /**
142      * Return an iterator for the <code>Object</code>s in this set. The
143      * iterator returns all items in arbitrary order, but is not "live". Any
144      * changes to the set while the iteration is in progress will give
145      * indeterminant results.
146      *
147      * @return iterator for values in set
148      */
149 
150     public final Iterator   iterator() {
151         return SparseArrayIterator.buildIterator(getKeyArray());
152     }
153 }
154
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags