IntSet


1   /* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
2    * 
3    * This program and the accompanying materials are made available under
4    * the terms of the Common Public License v1.0 which accompanies this distribution,
5    * and is available at http://www.eclipse.org/legal/cpl-v10.html
6    * 
7    * $Id: IntSet.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $
8    */
9   package com.vladium.util;
10  
11  // ----------------------------------------------------------------------------
12  /**
13   *
14   * MT-safety: an instance of this class is <I>not</I> safe for access from
15   * multiple concurrent threads [even if access is done by a single thread at a
16   * time]. The caller is expected to synchronize externally on an instance [the
17   * implementation does not do internal synchronization for the sake of efficiency].
18   * java.util.ConcurrentModificationException is not supported either.
19   *
20   * @author Vlad Roubtsov, (C) 2001
21   */
22  public
23  final class IntSet
24  {
25      // public: ................................................................
26  
27      /**
28       * Equivalent to <CODE>IntSet(11, 0.75F)</CODE>.
29       */
30      public IntSet ()
31      {
32          this (11, 0.75F);
33      }
34      
35      /**
36       * Equivalent to <CODE>IntSet(capacity, 0.75F)</CODE>.
37       */
38      public IntSet (final int initialCapacity)
39      {
40          this (initialCapacity, 0.75F);
41      }
42      
43      /**
44       * Constructs an IntSet with specified initial capacity and load factor.
45       *
46       * @param initialCapacity initial number of hash buckets in the table [may not be negative, 0 is equivalent to 1].
47       * @param loadFactor the load factor to use to determine rehashing points [must be in (0.0, 1.0] range].
48       */
49      public IntSet (int initialCapacity, final float loadFactor)
50      {
51          if (initialCapacity < 0) throw new IllegalArgumentException   ("negative input: initialCapacity [" + initialCapacity + "]");
52          if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6))
53              throw new IllegalArgumentException   ("loadFactor not in (0.0, 1.0] range: " + loadFactor);
54          
55          if (initialCapacity == 0) initialCapacity = 1;
56          
57          m_loadFactor = loadFactor > 1.0 ? 1.0F : loadFactor;        
58          m_sizeThreshold = (int) (initialCapacity * loadFactor);
59          m_buckets = new Entry [initialCapacity];
60      }
61      
62      
63      /**
64       * Overrides Object.toString() for debug purposes.
65       */
66      public String   toString ()
67      {
68          final StringBuffer   s = new StringBuffer   ();
69          debugDump (s);
70          
71          return s.toString ();
72      }
73      
74      /**
75       * Returns the number of key-value mappings in this map.
76       */
77      public int size ()
78      {
79          return m_size;
80      }
81      
82      public boolean contains (final int key)
83      {
84          // index into the corresponding hash bucket:
85          final Entry [] buckets = m_buckets;
86          final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
87          
88          // traverse the singly-linked list of entries in the bucket:
89          for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
90          {
91              if (key == entry.m_key)
92                  return true;
93          }
94          
95          return false;
96      }
97      
98      public int [] values ()
99      {
100         if (m_size == 0)
101             return IConstants.EMPTY_INT_ARRAY;
102         else
103         {
104             final int [] result = new int [m_size];
105             int scan = 0;
106             
107             for (int b = 0; b < m_buckets.length; ++ b)
108             {
109                 for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
110                 {
111                     result [scan ++] = entry.m_key;
112                 }
113             }
114             
115             return result;
116         }
117     }
118     
119     public void values (final int [] target, final int offset)
120     {
121         if (m_size != 0)
122         {
123             int scan = offset;
124             
125             for (int b = 0; b < m_buckets.length; ++ b)
126             {
127                 for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
128                 {
129                     target [scan ++] = entry.m_key;
130                 }
131             }
132         }
133     }
134     
135     public boolean add (final int key)
136     {
137         Entry currentKeyEntry = null;
138         
139         // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
140         
141         // index into the corresponding hash bucket:
142         int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length;
143         
144         // traverse the singly-linked list of entries in the bucket:
145         Entry [] buckets = m_buckets;
146         for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
147         {
148             if (key == entry.m_key)
149             {
150                 currentKeyEntry = entry;
151                 break;
152             }
153         }
154         
155         if (currentKeyEntry == null)
156         {
157             // add a new entry:
158             
159             if (m_size >= m_sizeThreshold) rehash ();
160             
161             buckets = m_buckets;
162             bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
163             final Entry bucketListHead = buckets [bucketIndex];
164             final Entry newEntry = new Entry (key, bucketListHead);
165             buckets [bucketIndex] = newEntry;
166             
167             ++ m_size;
168             
169             return true;
170         }
171         else
172             return false;
173     }
174     
175     // protected: .............................................................
176 
177     // package: ...............................................................
178     
179     
180     void debugDump (final StringBuffer   out)
181     {
182         if (out != null)
183         {
184             out.append (super.toString ()); out.append (EOL);
185             out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
186             out.append ("size threshold = " + m_sizeThreshold + EOL);
187         }
188     }
189 
190     // private: ...............................................................
191 
192     
193     /**
194      * The structure used for chaining colliding keys.
195      */
196     private static final class Entry
197     {
198         Entry (final int key, final Entry next)
199         {
200             m_key = key; 
201             m_next = next;
202         }
203         
204         final int m_key;
205         
206         Entry m_next; // singly-linked list link
207         
208     } // end of nested class
209     
210 
211     /**
212      * Re-hashes the table into a new array of buckets.
213      */
214     private void rehash ()
215     {
216         // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
217         // and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
218         // only grow in size
219         
220         final Entry [] buckets = m_buckets;
221         
222         final int newBucketCount = (m_buckets.length << 1) + 1;
223         final Entry [] newBuckets = new Entry [newBucketCount];
224 
225         // rehash all entry chains in every bucket:
226         for (int b = 0; b < buckets.length; ++ b)
227         {
228             for (Entry entry = buckets [b]; entry != null; )
229             {
230                 final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
231                 final int entryKey = entry.m_key;
232             
233                 // index into the corresponding new hash bucket:
234                 final int newBucketIndex = (entryKey & 0x7FFFFFFF) % newBucketCount;
235                 
236                 final Entry bucketListHead = newBuckets [newBucketIndex];
237                 entry.m_next = bucketListHead;
238                 newBuckets [newBucketIndex] = entry;                                
239                 
240                 entry = next;
241             }
242         }
243         
244 
245         m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
246         m_buckets = newBuckets;
247     }
248     
249     
250     private final float m_loadFactor; // determines the setting of m_sizeThreshold
251     
252     private Entry [] m_buckets; // table of buckets
253     private int m_size; // number of keys in the table, not cleared as of last check
254     private int m_sizeThreshold; // size threshold for rehashing
255         
256     private static final String   EOL = System.getProperty ("line.separator", "\n");
257     
258 } // end of class
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