SimpleMapImpl.java
001 /*
002  *  SimpleMapImpl.java
003  *
004  *  Copyright (c) 2001, The University of Sheffield.
005  *
006  *  This file is part of GATE (see http://gate.ac.uk/), and is free
007  *  software, licenced under the GNU Library General Public License,
008  *  Version 2, June 1991 (in the distribution as file licence.html,
009  *  and also available at http://gate.ac.uk/gate/licence.html).
010  *
011  *  D.Ognyanoff, 5/Nov/2001
012  *
013  *  $Id: SimpleMapImpl.java 17600 2014-03-08 18:47:11Z markagreenwood $
014  */
015 
016 package gate.util;
017 
018 import java.io.IOException;
019 import java.io.ObjectInputStream;
020 import java.io.Serializable;
021 import java.util.*;
022 import java.util.concurrent.ConcurrentHashMap;
023 
024 /**
025  * Implements Map interface in using less memory. Very simple but usefull
026  * for small number of items on it.
027  */
028 
029 class SimpleMapImpl implements Map<Object, Object>,
030       java.lang.Cloneable, java.io.Serializable {
031   
032   /**
033    * Special marker class used to represent null in the keys array.
034    */
035   private static class NullKey implements Serializable {
036     private static final long serialVersionUID = 6391916290867211345L;
037 
038     private NullKey() {
039     }
040   }
041 
042   /**
043    * The capacity of the map
044    */
045   int capacity = 3;
046 
047   /**
048    * The current number of elements of the map
049    */
050   int count = 0;
051 
052   /**
053    * Array keeping the keys of the entries in the map. It is "synchrnized"
054    * with the values array - the Nth position in both arrays correspond
055    * to one and the same entry
056    */
057   Object theKeys[];
058 
059   /**
060    * Array keeping the values of the entries in the map. It is "synchrnized"
061    * with the keys array - the Nth position in both arrays correspond
062    * to one and the same entry
063    */
064   Object theValues[];
065   
066   /** Freeze the serialization UID. */
067   static final long serialVersionUID = -6747241616127229116L;
068 
069   /** the Object instance that will represent the NULL keys in the map */
070   transient static Object nullKey = new NullKey();
071 
072   /** the static 'all keys' collection */
073   transient public static ConcurrentHashMap<Object,Object> theKeysHere;
074 
075   /** additional static members initialization */
076   static {
077     theKeysHere = new ConcurrentHashMap<Object,Object>();
078     theKeysHere.put(nullKey, nullKey);
079   // static code
080 
081   /**
082    * Constructor
083    */
084   public SimpleMapImpl() {
085     theKeys = new Object[capacity];
086     theValues = new Object[capacity];
087   // SimpleMapImpl()
088 
089   /**
090    * return the number of elements in the map
091    */
092   @Override
093   public int size() {
094     return count;
095   // size()
096 
097   /**
098    * return true if there are no elements in the map
099    */
100   @Override
101   public boolean isEmpty() {
102     return (count == 0);
103   // isEmpty()
104 
105   /**
106    * Not supported. This method is here only to conform the Map interface
107    */
108   @Override
109   public Collection<Object> values() {
110     throw new UnsupportedOperationException(
111       "SimpleMapImpl.values() not implemented!");
112   // values()
113 
114   /**
115    * return the set of the keys in the map. The changes in the set DO NOT
116    * affect the map.
117    */
118   @Override
119   public Set<Object> keySet()
120   {
121     Set<Object> s = new HashSet<Object>(size());
122     Object k;
123     for (int i = 0; i < count; i++) {
124       k = theKeys[i];
125       if (k == nullKey)
126            s.add(null);
127         else
128            s.add(k);
129     //for
130     return s;
131   // keySet()
132 
133   /**
134    * clear the map
135    */
136   @Override
137   public void clear()
138   {
139     for (int i = 0; i < count; i++) {
140       theKeys[inull;
141       theValues[inull;
142     // for
143     count = 0;
144   // clear
145 
146   /**
147    * return true if the key is in the map
148    */
149   @Override
150   public boolean containsKey(Object key) {
151     return (getPostionByKey(key!= -1);
152   }// containsKey
153 
154   /**
155    * return true if the map contains that value
156    */
157   @Override
158   public boolean containsValue(Object value) {
159     return (getPostionByValue(value!= -1);
160   }// containsValue
161 
162   /**
163    * return the value associated with the key. If the key is
164    * not in the map returns null.
165    */
166   @Override
167   public Object get(Object key) {
168     int pos = getPostionByKey(key);
169     return (pos == -1null : theValues[pos];
170   // get
171 
172   /**
173    * put a value in the map using the given key. If the key exist in the map
174    * the value is replaced and the old one is returned.
175    */
176   @Override
177   public Object put(Object key, Object value) {
178     Object gKey;
179     if (key == null) {
180       key = nullKey;
181       gKey = nullKey;
182     else
183       gKey = theKeysHere.putIfAbsent(key, key);
184     // if the key is already in the 'all keys' map - try to find it in that instance
185     // comparing by reference
186     if (gKey != null) {
187       for (int i = 0; i < count; i++) {
188         if (gKey == theKeys[i]) {
189           // we found the reference - return the value
190           Object oldVal = theValues[i];
191           theValues[i= value;
192           return oldVal;
193         }
194       // for
195     else {// if(gKey != null)
196       // no, the key is not in the 'all keys' map - put it there
197       gKey = key;
198     }
199     // enlarge the containers if necessary
200     if (count == capacity)
201       increaseCapacity();
202 
203     // put the key and value to the map
204     theKeys[count= gKey;
205     theValues[count= value;
206     count++;
207     return null;
208   // put
209 
210   /**
211    * remove value from the map using it's key.
212    */
213   @Override
214   public Object remove(Object key) {
215     int pos = getPostionByKey(key);
216     if (pos == -1)
217         return null;
218 
219     // save the value to return it at the end
220     Object oldVal = theValues[pos];
221     count--;
222     // move the last element key and value removing the element
223     if (count != 0) {
224         theKeys[pos= theKeys[count];
225         theValues[pos= theValues[count];
226     }
227     // clear the last position
228     theKeys[countnull;
229     theValues[countnull;
230 
231     // return the value
232     return oldVal;
233   // remove
234 
235   /**
236    * put all the elements from a map
237    */
238   @SuppressWarnings("unchecked")
239   @Override
240   public void putAll(Map<? extends Object, ? extends Object> t)
241   {
242     if (t == null) {
243       throw new UnsupportedOperationException(
244       "SimpleMapImpl.putAll argument is null");
245     // if (t == null)
246 
247     if (instanceof SimpleMapImpl) {
248       SimpleMapImpl sfm = (SimpleMapImpl)t;
249       Object key;
250       for (int i = 0; i < sfm.count; i++) {
251         key = sfm.theKeys[i];
252         put(key, sfm.theValues[i]);
253       //for
254     else // if (t instanceof SimpleMapImpl)
255       Iterator<?> entries = t.entrySet().iterator();
256       Map.Entry<Object,Object> e;
257       while (entries.hasNext()) {
258         e = (Map.Entry<Object,Object>)entries.next();
259         put(e.getKey(), e.getValue());
260       // while
261     // if(t instanceof SimpleMapImpl)
262   // putAll
263 
264   /**
265    * return positive value as index of the key in the map.
266    * Negative value means that the key is not present in the map
267    */
268   private int getPostionByKey(Object key) {
269     if (key == null)
270       key = nullKey;
271     // check the 'all keys' map for the very first key occurence
272     key = theKeysHere.get(key);
273     if (key == null)
274       return -1;
275 
276     for (int i = 0; i < count; i++) {
277       if (key == theKeys[i])
278         return i;
279     // for
280     return -1;
281   // getPostionByKey
282 
283   /**
284    * return the index of the key in the map comparing them by reference only.
285    * This method is used in subsume check to speed it up.
286    */
287   protected int getSubsumeKey(Object key) {
288     for (int i = 0; i < count; i++) {
289       if (key == theKeys[i])
290         return i;
291     // for
292     return -1;
293   // getPostionByKey
294 
295   /**
296    * return positive value as index of the value in the map.
297    */
298   private int getPostionByValue(Object value) {
299     Object av;
300     for (int i = 0; i < count; i++) {
301       av = theValues[i];
302       if (value == null) {
303         if (av == null)
304           return i;
305       else {//if (value == null)
306         if (value.equals(av))
307           return i;
308       //if (value == null)
309     // for
310 
311     return -1;
312   // getPostionByValue
313 
314   // Modification Operations
315   private void increaseCapacity() {
316     int oldCapacity = capacity;
317     capacity *= 2;
318     Object oldKeys[] = theKeys;
319     theKeys = new Object[capacity];
320 
321     Object oldValues[] = theValues;
322     theValues = new Object[capacity];
323 
324     System.arraycopy(oldKeys, 0, theKeys, 0, oldCapacity);
325     System.arraycopy(oldValues, 0, theValues, 0, oldCapacity);
326   // increaseCapacity
327 
328   /**
329    * Auxiliary classes needed for the support of entrySet() method
330    */
331   private static class Entry implements Map.Entry<Object,Object> {
332     int hash;
333     Object key;
334     Object value;
335 
336     Entry(int hash, Object key, Object value) {
337       this.hash = hash;
338       this.key = key;
339       this.value = value;
340     }
341 
342     @Override
343     protected Object clone() {
344       return new Entry(hash, key, value);
345     }
346 
347     @Override
348     public Object getKey() {
349       return key;
350     }
351 
352     @Override
353     public Object getValue() {
354       return value;
355     }
356 
357     @Override
358     public Object setValue(Object value) {
359       Object oldValue = this.value;
360       this.value = value;
361       return oldValue;
362     }
363 
364     @Override
365     public boolean equals(Object o) {
366       if (!(instanceof Map.Entry))
367         return false;
368       Map.Entry<?,?> e = (Map.Entry<?,?>)o;
369 
370       return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
371         (value==null ? e.getValue()==null : value.equals(e.getValue()));
372     }
373 
374     @Override
375     public int hashCode() {
376       return hash ^ (key==null : key.hashCode());
377     }
378 
379     @Override
380     public String toString() {
381       return key+"="+value;
382     }
383   // Entry
384 
385 
386   @Override
387   public Set<Map.Entry<Object, Object>> entrySet() {
388     Set<Map.Entry<Object, Object>> s = new HashSet<Map.Entry<Object,Object>>(size());
389     Object k;
390     for (int i = 0; i < count; i++) {
391       k = theKeys[i];
392       s.add(new Entry(k.hashCode()((k==nullKey)?null:k), theValues[i]));
393     //for
394     return s;
395   // entrySet
396 
397   // Comparison and hashing
398   @Override
399   public boolean equals(Object o) {
400     if (!(instanceof Map)) {
401       return false;
402     }
403 
404     @SuppressWarnings("unchecked")
405     Map<Object,Object> m = (Map<Object,Object>)o;
406     if (m.size() != count) {
407       return false;
408     }
409 
410     Object v, k;
411     for (int i = 0; i < count; i++) {
412       k = theKeys[i];
413       v = m.get(k);
414       if (v==null) {
415         if (theValues[i]!=null)
416           return false;
417       }
418       else if (!v.equals(theValues[i])){
419         return false;
420       }
421     // for
422 
423     return true;
424   // equals
425 
426   /**
427    * return the hashCode for the map
428    */
429   @Override
430   public int hashCode() {
431     int h = 0;
432     Iterator<Map.Entry<Object,Object>> i = entrySet().iterator();
433     while (i.hasNext())
434       h += i.next().hashCode();
435     return h;
436   // hashCode
437 
438   /**
439    * Create a copy of the map including the data.
440    */
441   @Override
442   public Object clone() {
443     SimpleMapImpl newMap;
444     try {
445       newMap = (SimpleMapImpl)super.clone();
446     catch (CloneNotSupportedException e) {
447       throw(new InternalError(e.toString()));
448     }
449 
450     newMap.count = count;
451     newMap.theKeys = new Object[capacity];
452     System.arraycopy(theKeys, 0, newMap.theKeys, 0, capacity);
453 
454     newMap.theValues = new Object[capacity];
455     System.arraycopy(theValues, 0, newMap.theValues, 0, capacity);
456 
457     return newMap;
458   // clone
459 
460   @Override
461   public String toString() {
462     int max = size() 1;
463     StringBuffer buf = new StringBuffer();
464     Iterator<Map.Entry<Object, Object>> i = entrySet().iterator();
465 
466     buf.append("{");
467     for (int j = 0; j <= max; j++) {
468       Map.Entry<Object, Object> e = (i.next());
469       buf.append(e.getKey() "=" + e.getValue());
470       if (j < max)
471         buf.append(", ");
472     }
473     buf.append("}");
474     return buf.toString();
475   // toString
476 
477   /**
478    * readObject - calls the default readObject() and then initialises the
479    * transient data
480    *
481    @serialData Read serializable fields. No optional data read.
482    */
483   private void readObject(ObjectInputStream s)
484       throws IOException, ClassNotFoundException {
485     s.defaultReadObject();
486         
487     for (int i = 0; i < theKeys.length; i++) {
488       if(theKeys[iinstanceof NullKey) {
489         theKeys[i= nullKey;
490       }
491       else if(theKeys[i!= null) {
492         // check if the key is in the 'all keys' map, adding it if not
493         Object o = theKeysHere.putIfAbsent(theKeys[i], theKeys[i]);
494         if (o != null// yes - so reuse the reference
495           theKeys[i= o;
496       }
497     }//for
498   }//readObject
499 //SimpleMapImpl