1   /*
2    *  SimpleMapImpl.java
3    *
4    *  Copyright (c) 2001, The University of Sheffield.
5    *
6    *  This file is part of GATE (see http://gate.ac.uk/), and is free
7    *  software, licenced under the GNU Library General Public License,
8    *  Version 2, June 1991 (in the distribution as file licence.html,
9    *  and also available at http://gate.ac.uk/gate/licence.html).
10   *
11   *  D.Ognyanoff, 5/Nov/2001
12   *
13   *  $Id: SimpleMapImpl.java,v 1.9 2004/03/25 13:00:53 valyt Exp $
14   */
15  
16  package gate.util;
17  
18  import java.io.IOException;
19  import java.io.ObjectInputStream;
20  import java.util.*;
21  
22  /**
23   * Implements Map interface in using less memory. Very simple but usefull
24   * for small number of items on it.
25   */
26  
27  class SimpleMapImpl implements Map, java.lang.Cloneable, java.io.Serializable {
28  
29    /**
30     * The capacity of the map
31     */
32    int capacity = 3;
33  
34    /**
35     * The current number of elements of the map
36     */
37    int count = 0;
38  
39    /**
40     * Array keeping the keys of the entries in the map. It is "synchrnized"
41     * with the values array - the Nth position in both arrays correspond
42     * to one and the same entry
43     */
44    Object theKeys[];
45  
46    /**
47     * Array keeping the values of the entries in the map. It is "synchrnized"
48     * with the keys array - the Nth position in both arrays correspond
49     * to one and the same entry
50     */
51    Object theValues[];
52  
53    /** Freeze the serialization UID. */
54    static final long serialVersionUID = -6747241616127229116L;
55  
56    /** the Object instance that will represent the NULL keys in the map */
57    transient static Object nullKey = new Object();
58  
59    /** the static 'all keys' collection */
60    transient public static HashMap theKeysHere = new HashMap();
61  
62    /** additional static members initialization */
63    static {
64      theKeysHere.put(nullKey, nullKey);
65    } // static code
66  
67    /**
68     * Constructor
69     */
70    public SimpleMapImpl() {
71      theKeys = new Object[capacity];
72      theValues = new Object[capacity];
73    } // SimpleMapImpl()
74  
75    /**
76     * return the number of elements in the map
77     */
78    public int size() {
79      return count;
80    } // size()
81  
82    /**
83     * return true if there are no elements in the map
84     */
85    public boolean isEmpty() {
86      return (count == 0);
87    } // isEmpty()
88  
89    /**
90     * Not supported. This method is here only to conform the Map interface
91     */
92    public Collection values() {
93      throw new UnsupportedOperationException(
94        "SimpleMapImpl.values() not implemented!");
95    } // values()
96  
97    /**
98     * return the set of the keys in the map. The changes in the set DO NOT
99     * affect the map.
100    */
101   public Set keySet()
102   {
103     HashSet s = new HashSet(size());
104     Object k;
105     for (int i = 0; i < count; i++) {
106       k = theKeys[i];
107       if (k == nullKey)
108            s.add(null);
109         else
110            s.add(k);
111     } //for
112     return s;
113   } // keySet()
114 
115   /**
116    * clear the map
117    */
118   public void clear()
119   {
120     for (int i = 0; i < count; i++) {
121       theKeys[i] = null;
122       theValues[i] = null;
123     } // for
124     count = 0;
125   } // clear
126 
127   /**
128    * return true if the key is in the map
129    */
130   public boolean containsKey(Object key) {
131     return (getPostionByKey(key) != -1);
132   }// containsKey
133 
134   /**
135    * return true if the map contains that value
136    */
137   public boolean containsValue(Object value) {
138     return (getPostionByValue(value) != -1);
139   }// containsValue
140 
141   /**
142    * return the value associated with the key. If the key is
143    * not in the map returns null.
144    */
145   public Object get(Object key) {
146     int pos = getPostionByKey(key);
147     return (pos == -1) ? null : theValues[pos];
148   } // get
149 
150   /**
151    * put a value in the map using the given key. If the key exist in the map
152    * the value is replaced and the old one is returned.
153    */
154   public Object put(Object key, Object value) {
155     Object gKey;
156     if (key == null) {
157       key = nullKey;
158       gKey = nullKey;
159     } else
160       gKey = theKeysHere.get(key);
161     // if the key is already in the 'all keys' map - try to find it in that instance
162     // comparing by reference
163     if (gKey != null) {
164       for (int i = 0; i < count; i++) {
165         if (gKey == theKeys[i]) {
166           // we found the reference - return the value
167           Object oldVal = theValues[i];
168           theValues[i] = value;
169           return oldVal;
170         }
171       } // for
172     } else {// if(gKey != null)
173       // no, the key is not in the 'all keys' map - put it there
174       theKeysHere.put(key, key);
175       gKey = key;
176     }
177     // enlarge the containers if necessary
178     if (count == capacity)
179       increaseCapacity();
180 
181     // put the key and value to the map
182     theKeys[count] = gKey;
183     theValues[count] = value;
184     count++;
185     return null;
186   } // put
187 
188   /**
189    * remove value from the map using it's key.
190    */
191   public Object remove(Object key) {
192     int pos = getPostionByKey(key);
193     if (pos == -1)
194         return null;
195 
196     // save the value to return it at the end
197     Object oldVal = theValues[pos];
198     count--;
199     // move the last element key and value removing the element
200     if (count != 0) {
201         theKeys[pos] = theKeys[count];
202         theValues[pos] = theValues[count];
203     }
204     // clear the last position
205     theKeys[count] = null;
206     theValues[count] = null;
207 
208     // return the value
209     return oldVal;
210   } // remove
211 
212   /**
213    * put all the elements from a map
214    */
215   public void putAll(Map t)
216   {
217     if (t == null) {
218       throw new UnsupportedOperationException(
219       "SimpleMapImpl.putAll argument is null");
220     } // if (t == null)
221 
222     if (t instanceof SimpleMapImpl) {
223       SimpleMapImpl sfm = (SimpleMapImpl)t;
224       Object key;
225       for (int i = 0; i < sfm.count; i++) {
226         key = sfm.theKeys[i];
227         put(key, sfm.theValues[i]);
228       } //for
229     } else { // if (t instanceof SimpleMapImpl)
230       Iterator entries = t.entrySet().iterator();
231       Map.Entry e;
232       while (entries.hasNext()) {
233         e = (Map.Entry)entries.next();
234         put(e.getKey(), e.getValue());
235       } // while
236     } // if(t instanceof SimpleMapImpl)
237   } // putAll
238 
239   /**
240    * return positive value as index of the key in the map.
241    * Negative value means that the key is not present in the map
242    */
243   private int getPostionByKey(Object key) {
244     if (key == null)
245       key = nullKey;
246     // check the 'all keys' map for the very first key occurence
247     key = theKeysHere.get(key);
248     if (key == null)
249       return -1;
250 
251     for (int i = 0; i < count; i++) {
252       if (key == theKeys[i])
253         return i;
254     } // for
255     return -1;
256   } // getPostionByKey
257 
258   /**
259    * return the index of the key in the map comparing them by reference only.
260    * This method is used in subsume check to speed it up.
261    */
262   protected int getSubsumeKey(Object key) {
263     for (int i = 0; i < count; i++) {
264       if (key == theKeys[i])
265         return i;
266     } // for
267     return -1;
268   } // getPostionByKey
269 
270   /**
271    * return positive value as index of the value in the map.
272    */
273   private int getPostionByValue(Object value) {
274     Object av;
275     for (int i = 0; i < count; i++) {
276       av = theValues[i];
277       if (value == null) {
278         if (av == null)
279           return i;
280       } else {//if (value == null)
281         if (value.equals(av))
282           return i;
283       } //if (value == null)
284     } // for
285 
286     return -1;
287   } // getPostionByValue
288 
289   // Modification Operations
290   private void increaseCapacity() {
291     int oldCapacity = capacity;
292     capacity *= 2;
293     Object oldKeys[] = theKeys;
294     theKeys = new Object[capacity];
295 
296     Object oldValues[] = theValues;
297     theValues = new Object[capacity];
298 
299     System.arraycopy(oldKeys, 0, theKeys, 0, oldCapacity);
300     System.arraycopy(oldValues, 0, theValues, 0, oldCapacity);
301   } // increaseCapacity
302 
303   /**
304    * Auxiliary classes needed for the support of entrySet() method
305    */
306   private static class Entry implements Map.Entry {
307     int hash;
308     Object key;
309     Object value;
310 
311     Entry(int hash, Object key, Object value) {
312       this.hash = hash;
313       this.key = key;
314       this.value = value;
315     }
316 
317     protected Object clone() {
318       return new Entry(hash, key, value);
319     }
320 
321     public Object getKey() {
322       return key;
323     }
324 
325     public Object getValue() {
326       return value;
327     }
328 
329     public Object setValue(Object value) {
330       Object oldValue = this.value;
331       this.value = value;
332       return oldValue;
333     }
334 
335     public boolean equals(Object o) {
336       if (!(o instanceof Map.Entry))
337         return false;
338       Map.Entry e = (Map.Entry)o;
339 
340       return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
341         (value==null ? e.getValue()==null : value.equals(e.getValue()));
342     }
343 
344     public int hashCode() {
345       return hash ^ (key==null ? 0 : key.hashCode());
346     }
347 
348     public String toString() {
349       return key+"="+value;
350     }
351   } // Entry
352 
353 
354   public Set entrySet() {
355     HashSet s = new HashSet(size());
356     Object v, k;
357     for (int i = 0; i < count; i++) {
358       k = theKeys[i];
359       s.add(new Entry(k.hashCode(), ((k==nullKey)?null:k), theValues[i]));
360     } //for
361     return s;
362   } // entrySet
363 
364   // Comparison and hashing
365   public boolean equals(Object o) {
366     if (!(o instanceof Map)) {
367       return false;
368     }
369 
370     Map m = (Map)o;
371     if (m.size() != count) {
372       return false;
373     }
374 
375     Object v, k;
376     for (int i = 0; i < count; i++) {
377       k = theKeys[i];
378       v = m.get(k);
379       if (v==null) {
380         if (theValues[i]!=null)
381           return false;
382       }
383       else if (!v.equals(theValues[i])){
384         return false;
385       }
386     } // for
387 
388     return true;
389   } // equals
390 
391   /**
392    * return the hashCode for the map
393    */
394   public int hashCode() {
395     int h = 0;
396     Iterator i = entrySet().iterator();
397     while (i.hasNext())
398       h += i.next().hashCode();
399     return h;
400   } // hashCode
401 
402   /**
403    * Create a copy of the map including the data.
404    */
405   public Object clone() {
406     SimpleMapImpl newMap;
407     try {
408       newMap = (SimpleMapImpl)super.clone();
409     } catch (CloneNotSupportedException e) {
410       throw(new InternalError(e.toString()));
411     }
412 
413     newMap.count = count;
414     newMap.theKeys = new Object[capacity];
415     System.arraycopy(theKeys, 0, newMap.theKeys, 0, capacity);
416 
417     newMap.theValues = new Object[capacity];
418     System.arraycopy(theValues, 0, newMap.theValues, 0, capacity);
419 
420     return newMap;
421   } // clone
422 
423   public String toString() {
424     int max = size() - 1;
425     StringBuffer buf = new StringBuffer();
426     Iterator i = entrySet().iterator();
427 
428     buf.append("{");
429     for (int j = 0; j <= max; j++) {
430       Entry e = (Entry) (i.next());
431       buf.append(e.getKey() + "=" + e.getValue());
432       if (j < max)
433         buf.append(", ");
434     }
435     buf.append("}");
436     return buf.toString();
437   } // toString
438 
439   /**
440    * readObject - calls the default readObject() and then initialises the
441    * transient data
442    *
443    * @serialData Read serializable fields. No optional data read.
444    */
445   private void readObject(ObjectInputStream s)
446       throws IOException, ClassNotFoundException {
447     s.defaultReadObject();
448     if (theKeysHere == null) {
449       theKeysHere = new HashMap();
450       theKeysHere.put(nullKey, nullKey);
451     }
452     for (int i = 0; i < theKeys.length; i++) {
453       // if the key is in the 'all keys' map
454       Object o = theKeysHere.get(theKeys[i]);
455       if (o != null) // yes - so reuse the reference
456         theKeys[i] = o;
457       else // no - put it in the 'all keys' map
458         theKeysHere.put(theKeys[i], theKeys[i]);
459     }//for
460   }//readObject
461 } //SimpleMapImpl
462