CompactMap


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  package org.netbeans.lib.editor.util;
21  
22  import java.util.AbstractSet  ;
23  import java.util.Collection  ;
24  import java.util.ConcurrentModificationException  ;
25  import java.util.HashMap  ;
26  import java.util.Iterator  ;
27  import java.util.Map  ;
28  import java.util.NoSuchElementException  ;
29  import java.util.Set  ;
30  
31  /**
32   * Map implementation that allows to define the class that implements
33   * the <code>Map.Entry</code>.
34   * <br/>
35   * The present implementation does not allow <code>null</code> to be used
36   * as a key in the map. The client may use NULL_KEY masking on its own side
37   * if it wants to use null keys (see <code>java.util.HashMap</code> impl).
38   * <br/>
39   * The load factor is fixed to <code>1.0</code> but if the approximate map size
40   * is known there is a constructor that allows to pass the initial capacity.
41   * <br/>
42   * There are no additional attempts to generally improve hashing for poor hashing functions
43   * like those in <code>HashMap.hash()</code>.
44   * <br/>
45   * The iterators produced by this map are not fail-fast - they will continue iteration
46   * and their behavior is generally undefined after the modification.
47   * The caller should ensure that there will be no pending iterators during modification
48   * of this map.
49   * <br/>
50   * When iterating through entries in a bucket the <code>Object.equals()</code>
51   * is used for comparison.
52   * <br/>
53   *
54   * @author Miloslav Metelka
55   * @version 1.00
56   */
57  
58  public class CompactMap<K,V> implements Map  <K,V> {
59      
60      private static int EXPAND_THRESHOLD = 4;
61  
62      // Empty array would fail with present impl
63      private MapEntry<K,V>[] table;
64      
65      private int size;
66  
67      public CompactMap() {
68          table = allocateTableArray(1);
69      }
70  
71      public CompactMap(int initialCapacity) {
72          // Find a power of 2 >= initialCapacity
73          int capacity = 1;
74          while (capacity < initialCapacity) {
75              capacity <<= 1;
76          }
77          table = allocateTableArray(capacity);
78      }
79      
80      public V get(Object   key) {
81          MapEntry<K,V> e = findEntry(key);
82          return (e != null) ? e.getValue() : null;
83      }
84      
85      /**
86       * Get an entry from a bucket that corresponds to the given hash code.
87       * <br/>
88       * This may be useful if the hash code can be computed without creating
89       * an actual object being stored in the map. The target object should
90       * provide some method for comparing itself to the passed arguments that represent
91       * the contained data.
92       * 
93       * @param hashCode computed hash code.
94       * @return first entry in the particular bucket or null if there are no entries
95       *  for the given hash code. The caller may need to iterate through the linked
96       *  list of the entries to find the right entry.
97       */
98      public MapEntry<K,V> getFirstEntry(int hashCode) {
99          return table[hashCode & (table.length - 1)];
100     }
101 
102     public boolean containsKey(Object   key) {
103         MapEntry<K,V> e = findEntry(key);
104         return (e != null);
105     }
106     
107     public boolean containsValue(Object   value) {
108         for (int i = table.length - 1; i >= 0 ; i--) {
109             for (MapEntry<K,V> e = table[i]; e != null; e = e.nextMapEntry()) {
110                 if ((value == null && e.getValue() == null)
111                     || (value != null && value.equals(e.getValue()))
112                 ) {
113                     return true;
114                 }
115             }
116         }
117         return false;
118     }
119 
120     /**
121      * Put the given entry into the map.
122      * <br/>
123      * The given entry should only be added to one compact map instance.
124      * <br/>
125      * Adding a single entry into multiple compact maps will break
126      * internal consistency of all the intended maps!
127      * <br/>
128      * If there will be an existing entry with a key that equals to the key
129      * in the entry parameter then the original entry will be replaced
130      * by the given entry.
131      */
132     public MapEntry<K,V> putEntry(MapEntry<K,V> entry) {
133         Object   key = entry.getKey();
134         int hash = key.hashCode();
135         int tableIndex = hash & (table.length - 1);
136         entry.setKeyHashCode(hash);
137         MapEntry<K,V> e = table[tableIndex];
138         MapEntry<K,V> prevEntry = null;
139         while (e != null) {
140             if (e == entry) { // Entry already added => do nothing
141                 return entry;
142             }
143             if (hash == e.keyHashCode() && (key == e.getKey() || key.equals(e.getKey()))) {
144                 // Found the entry -> replace it
145                 if (prevEntry == null) {
146                     table[tableIndex] = entry;
147                 } else {
148                     prevEntry.setNextMapEntry(entry);
149                 }
150                 entry.setNextMapEntry(e.nextMapEntry());
151                 e.setNextMapEntry(null);
152                 return e;
153             }
154             prevEntry = e;
155             e = e.nextMapEntry();
156         }
157         
158         // Not found in present table => add the entry
159         addEntry(entry, tableIndex);
160         return null; // nothing replaced
161     }
162 
163     public V put(K key, V value) {
164         int hash = key.hashCode();
165         int tableIndex = hash & (table.length - 1);
166         MapEntry<K,V> e = table[tableIndex];
167         while (e != null) {
168             if (hash == e.keyHashCode() && (key == e.getKey() || key.equals(e.getKey()))) {
169                 // Found the entry
170                 V oldValue = e.getValue();
171                 e.setValue(value);
172                 return oldValue;
173             }
174             e = e.nextMapEntry();
175         }
176         
177         // Not found in present table => add the entry
178         e = new DefaultMapEntry<K,V>(key);
179         e.setValue(value);
180         e.setKeyHashCode(hash);
181         addEntry(e, tableIndex);
182         return null;
183     }
184 
185     public void putAll(Map  <? extends K,? extends V> map) {
186         for (Map.Entry  <? extends K, ? extends V> e : map.entrySet()) {
187             put(e.getKey(), e.getValue());
188         }
189     }
190 
191     public V remove(Object   key) {
192         MapEntry<K,V> e = removeEntryForKey(key);
193         return (e != null) ? e.getValue() : null;
194     }
195     
196     /**
197      * Remove the given entry from the map.
198      * <br/>
199      * This method will search for the entry instance (not its key)
200      * so the given entry must be physically used in the map
201      * otherwise this method will not do anything.
202      */
203     public MapEntry<K,V> removeEntry(MapEntry<K,V> entry) {
204         int hash = entry.keyHashCode();
205         int tableIndex = hash & (table.length - 1);
206         MapEntry<K,V> e = table[tableIndex];
207         MapEntry<K,V> prev = null;
208         while (e != null) {
209             if (e == entry) {
210                 if (prev == null) {
211                     table[tableIndex] = e.nextMapEntry();
212                 } else {
213                     prev.setNextMapEntry(e.nextMapEntry());
214                 }
215                 entry.setNextMapEntry(null);
216                 size--;
217                 return entry;
218             }
219             prev = entry;
220             entry = entry.nextMapEntry();
221         }
222         return null;
223     }
224 
225     public void clear() {
226         // Retain present table array
227         for (int i = table.length - 1; i >= 0; i--) {
228             MapEntry<K,V> e = table[i];
229             table[i] = null;
230             // Unbind entries
231             while (e != null) {
232                 MapEntry<K,V> next = e.nextMapEntry();
233                 e.setNextMapEntry(null);
234                 e = next;
235             }
236         }
237         size = 0;
238     }
239 
240     public final int size() {
241         return size;
242     }
243 
244     public boolean isEmpty() {
245         return (size() == 0);
246     }
247 
248     public Set  <Entry<K,V>> entrySet() {
249         return new EntrySet();
250     }
251     
252     public Collection  <V> values() {
253         throw new IllegalStateException  ("Not yet implemented");
254     }
255 
256     public Set  <K> keySet() {
257         throw new IllegalStateException  ("Not yet implemented");
258     }
259 
260     private MapEntry<K,V> findEntry(Object   key) {
261         int hash = key.hashCode();
262         int tableIndex = hash & (table.length - 1);
263         MapEntry<K,V> e = table[tableIndex];
264         while (e != null) {
265             if (hash == e.keyHashCode() && (key == e.getKey() || key.equals(e.getKey()))) {
266                 return e;
267             }
268             e = e.nextMapEntry();
269         }
270         return null;
271     }
272     
273     private void addEntry(MapEntry<K,V> entry, int tableIndex) {
274         entry.setNextMapEntry(table[tableIndex]);
275         table[tableIndex] = entry;
276         size++;
277         if (size > table.length) { // Fill factor is 1.0
278             MapEntry<K,V>[] newTable = allocateTableArray(Math.max(table.length << 1, 4));
279             for (int i = table.length - 1; i >= 0; i--) {
280                 entry = table[i];
281                 while (entry != null) {
282                     MapEntry<K,V> next = entry.nextMapEntry();
283                     int newIndex = entry.keyHashCode() & (newTable.length - 1);
284                     entry.setNextMapEntry(newTable[newIndex]);
285                     newTable[newIndex] = entry;
286                     entry = next;
287                 }
288             }
289             table = newTable;
290         }
291     }
292     
293     private MapEntry<K,V> removeEntryForKey(Object   key) {
294         int hash = key.hashCode();
295         int tableIndex = hash & (table.length - 1);
296         MapEntry<K,V> e = table[tableIndex];
297         MapEntry<K,V> prev = null;
298         while (e != null) {
299             if (hash == e.keyHashCode() && (key == e.getKey() || key.equals(e.getKey()))) {
300                 if (prev == null) {
301                     table[tableIndex] = e.nextMapEntry();
302                 } else {
303                     prev.setNextMapEntry(e.nextMapEntry());
304                 }
305                 e.setNextMapEntry(null);
306                 size--;
307                 return e;
308             }
309             prev = e;
310             e = e.nextMapEntry();
311         }
312         return null;
313     }
314     
315     @SuppressWarnings  ("unchecked")
316     private MapEntry<K,V>[] allocateTableArray(int capacity) {
317         return new MapEntry[capacity];
318     }
319     
320     public String   toString() {
321     StringBuffer   buf = new StringBuffer  ();
322     buf.append("{");
323 
324     Iterator   i = entrySet().iterator();
325         boolean hasNext = i.hasNext();
326         while (hasNext) {
327         Map.Entry   e = (Map.Entry  )i.next();
328         Object   key = e.getKey();
329             Object   value = e.getValue();
330         if (key == this)
331         buf.append("(this Map)");
332         else
333         buf.append(key);
334         buf.append("=");
335         if (value == this)
336         buf.append("(this Map)");
337         else
338         buf.append(value);
339             hasNext = i.hasNext();
340             if (hasNext)
341                 buf.append(", ");
342         }
343 
344     buf.append("}");
345     return buf.toString();
346     }
347 
348     /**
349      * Abstract implementation of the map entry.
350      * <br/>
351      * This is suitable for the cases when e.g. the value is a primitive
352      * data type.
353      */
354     public static abstract class MapEntry<K,V> implements Map.Entry  <K,V> {
355         
356         private MapEntry<K,V> nextMapEntry; // 12 bytes (8-Object + 4)
357         
358         private int keyHashCode; // 16 bytes
359         
360         public abstract K getKey();
361         
362         public abstract V getValue();
363         
364         public abstract V setValue(V value);
365         
366         /**
367          * Used by {@link #hashCode()} to return the real hashCode for the value
368          * held by this map entry.
369          * <br/>
370          * <code>getValue().hashCode</code> cannot be used in general because
371          * <code>getValue()</code> may return <code>this</code> e.g. in case
372          * the value is represented by primitive data type. The method should
373          * use that real value for the hash code computation.
374          */
375         protected abstract int valueHashCode();
376         
377         /**
378          * Used by {@link #equals(Object)} to check whether the value
379          * held by this map entry equals to the the given value.
380          * <br/>
381          * <code>getValue().equals()</code> cannot be used in general because
382          * <code>getValue()</code> may return <code>this</code> e.g. in case
383          * the value is represented by primitive data type. The method should
384          * use that real value for the operation of this method.
385          * 
386          * @param value2 value to be compared with value stored in this entry.
387          *  The argument may be null.
388          */
389         protected abstract boolean valueEquals(Object   value2);
390         
391         
392         /**
393          * Get next map entry linked to this one.
394          * <br/>
395          * This method may be useful after using {@link #getFirstEntry(int)}.
396          */
397         public final MapEntry<K,V> nextMapEntry() {
398             return nextMapEntry;
399         }
400         
401         final void setNextMapEntry(MapEntry<K,V> next) {
402             this.nextMapEntry = next;
403         }
404         
405         /**
406          * Get stored hash code of the key contained in this entry.
407          * <br/>
408          * This method may be useful after using {@link #getFirstEntry(int)}
409          * to quickly exclude entries which hash code differs from the requested one.
410          */
411         public final int keyHashCode() {
412             return keyHashCode;
413         }
414         
415         final void setKeyHashCode(int keyHashCode) {
416             this.keyHashCode = keyHashCode;
417         }
418     
419         /**
420          * Implementation that adheres to {@link java.util.Map.Entry#hashCode()} contract.
421          */
422         public final int hashCode() {
423             // keyHashCode() cannot be used always as the entry is possibly not yet contained in a map
424             int keyHash = (keyHashCode != 0) ? keyHashCode : getKey().hashCode();
425             return keyHash ^ valueHashCode();
426         }
427         
428         /**
429          * Implementation that adheres to {@link java.util.Map.Entry#equals(Object)} contract.
430          */
431         public final boolean equals(Object   o) {
432             if (o == this)
433                 return true;
434             if (o instanceof Map.Entry  ) {
435                 Map.Entry   e = (Map.Entry  )o;
436                 K key = getKey();
437                 Object   key2 = e.getKey();
438                 // Note: update needed if this map would allow for null keys
439                 if (key == key2 || key.equals(key2)) {
440                     return valueEquals(e.getValue());
441                 }
442             }
443             return false;
444         }
445         
446     }
447     
448     /**
449      * Default implementation of the map entry similar to e.g. the <code>HashMap</code>.
450      * <br/>
451      * It may be extended as well if the should be an additional information stored
452      * in the map entry.
453      */
454     public static class DefaultMapEntry<K,V> extends MapEntry<K,V> {
455         
456         private K key; // 20 bytes
457         
458         private V value; // 24 bytes
459         
460         public DefaultMapEntry(K key) {
461             this.key = key;
462         }
463         
464         public final K getKey() {
465             return key;
466         }
467         
468         public final V getValue() {
469             return value;
470         }
471         
472         public final V setValue(V value) {
473             Object   oldValue = this.value;
474             this.value = value;
475             return value;
476         }
477         
478         protected final int valueHashCode() {
479             return (value != null) ? value.hashCode() : 0;
480         }
481         
482         protected final boolean valueEquals(Object   value2) {
483             return (value == value2 || (value != null && value.equals(value2)));
484         }
485         
486         public String   toString() {
487             return "key=" + getKey() + ", value=" + getValue(); // NOI18N
488         }
489         
490     }
491 
492     private final class EntrySet extends AbstractSet  <Entry<K,V>> {
493 
494         public Iterator  <Entry<K,V>> iterator() {
495             return new EntryIterator();
496         }
497 
498         public boolean contains(Object   o) {
499             if (!(o instanceof Map.Entry  ))
500                 return false;
501             @SuppressWarnings  ("unchecked")
502             Map.Entry  <K,V> e = (Map.Entry  <K,V>)o;
503             MapEntry<K,V> candidate = findEntry(e.getKey());
504             return candidate != null && candidate.equals(e);
505         }
506 
507         public boolean remove(Object   o) {
508             @SuppressWarnings  ("unchecked")
509             MapEntry<K,V> e = (MapEntry<K,V>)o;
510             return removeEntry(e) != null;
511         }
512 
513         public int size() {
514             return CompactMap.this.size();
515         }
516 
517         public void clear() {
518             CompactMap.this.clear();
519         }
520 
521     }
522     
523     private abstract class HashIterator {
524 
525         MapEntry<K,V> next;       // next entry to return
526         int index;                   // current slot
527         MapEntry<K,V> current;    // current entry
528         
529         HashIterator() {
530             MapEntry<K,V>[] t = table;
531             int i = t.length;
532             MapEntry<K,V> n = null;
533             if (size != 0) { // advance to first entry
534                 while (i > 0 && (n = t[--i]) == null)
535                     ;
536             }
537             next = n;
538             index = i;
539         }
540         
541         public boolean hasNext() {
542             return next != null;
543         }
544         
545         MapEntry<K,V> nextEntry() {
546             MapEntry<K,V> e = next;
547             if (e == null)
548                 throw new NoSuchElementException  ();
549             
550             MapEntry<K,V> n = e.nextMapEntry();
551             MapEntry<K,V>[] t = table;
552             int i = index;
553             while (n == null && i > 0)
554                 n = t[--i];
555             index = i;
556             next = n;
557             return current = e;
558         }
559         
560         public void remove() {
561             if (current == null)
562                 throw new IllegalStateException  ();
563             Object   k = current.getKey();
564             current = null;
565             removeEntryForKey(k);
566         }
567         
568     }
569     
570     private final class ValueIterator extends HashIterator implements Iterator  <V> {
571 
572         public V next() {
573             return nextEntry().getValue();
574         }
575     }
576     
577     private final class KeyIterator extends HashIterator implements Iterator  <K> {
578 
579         public K next() {
580             return nextEntry().getKey();
581         }
582 
583     }
584     
585     private final class EntryIterator extends HashIterator implements Iterator  <Entry<K,V>> {
586 
587         public Entry<K,V> next() {
588             return nextEntry();
589         }
590 
591     }
592 
593 }
594
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags