ObjectMap


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    * 
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.core.internal.utils;
12  
13  import java.util.*;
14  
15  /**
16   * A specialized map implementation that is optimized for a 
17   * small set of object keys. 
18   * 
19   * Implemented as a single array that alternates keys and values.
20   */
21  public class ObjectMap implements Map, IStringPoolParticipant {
22  
23      // 8 attribute keys, 8 attribute values
24      protected static final int DEFAULT_SIZE = 16;
25      protected static final int GROW_SIZE = 10;
26      protected int count = 0;
27      protected Object  [] elements = null;
28  
29      /**
30       * Creates a new object map of default size
31       */
32      public ObjectMap() {
33          this(DEFAULT_SIZE);
34      }
35  
36      /**
37       * Creates a new object map.
38       * @param initialCapacity The initial number of elements that will fit in the map.
39       */
40      public ObjectMap(int initialCapacity) {
41          if (initialCapacity > 0)
42              elements = new Object  [Math.max(initialCapacity * 2, 0)];
43      }
44  
45      /**
46       * Creates a new object map of the same size as the given map and 
47       * populate it with the key/attribute pairs found in the map.
48       * @param map The entries in the given map will be added to the new map.
49       */
50      public ObjectMap(Map map) {
51          this(map.size());
52          putAll(map);
53      }
54  
55      /**
56       * @see Map#clear()
57       */
58      public void clear() {
59          elements = null;
60          count = 0;
61      }
62  
63      /**
64       * @see java.lang.Object#clone()
65       */
66      public Object   clone() {
67          return new ObjectMap(this);
68      }
69  
70      /**
71       * @see Map#containsKey(java.lang.Object)
72       */
73      public boolean containsKey(Object   key) {
74          if (elements == null || count == 0)
75              return false;
76          for (int i = 0; i < elements.length; i = i + 2)
77              if (elements[i] != null && elements[i].equals(key))
78                  return true;
79          return false;
80      }
81  
82      /**
83       * @see Map#containsValue(java.lang.Object)
84       */
85      public boolean containsValue(Object   value) {
86          if (elements == null || count == 0)
87              return false;
88          for (int i = 1; i < elements.length; i = i + 2)
89              if (elements[i] != null && elements[i].equals(value))
90                  return true;
91          return false;
92      }
93  
94      /**
95       * @see Map#entrySet()
96       * This implementation does not conform properly to the specification
97       * in the Map interface.  The returned collection will not be bound to
98       * this map and will not remain in sync with this map.
99       */
100     public Set entrySet() {
101         return toHashMap().entrySet();
102     }
103 
104     /**
105      * See Object#equals
106      */
107     public boolean equals(Object   o) {
108         if (!(o instanceof Map))
109             return false;
110         Map other = (Map) o;
111         //must be same size
112         if (count != other.size())
113             return false;
114 
115         //keysets must be equal
116         if (!keySet().equals(other.keySet()))
117             return false;
118 
119         //values for each key must be equal
120         for (int i = 0; i < elements.length; i = i + 2) {
121             if (elements[i] != null && (!elements[i + 1].equals(other.get(elements[i]))))
122                 return false;
123         }
124         return true;
125     }
126 
127     /**
128      * @see Map#get(java.lang.Object)
129      */
130     public Object   get(Object   key) {
131         if (elements == null || count == 0)
132             return null;
133         for (int i = 0; i < elements.length; i = i + 2)
134             if (elements[i] != null && elements[i].equals(key))
135                 return elements[i + 1];
136         return null;
137     }
138 
139     /**
140      * The capacity of the map has been exceeded, grow the array by
141      * GROW_SIZE to accommodate more entries.
142      */
143     protected void grow() {
144         Object  [] expanded = new Object  [elements.length + GROW_SIZE];
145         System.arraycopy(elements, 0, expanded, 0, elements.length);
146         elements = expanded;
147     }
148 
149     /**
150      * See Object#hashCode
151      */
152     public int hashCode() {
153         int hash = 0;
154         for (int i = 0; i < elements.length; i = i + 2) {
155             if (elements[i] != null) {
156                 hash += elements[i].hashCode();
157             }
158         }
159         return hash;
160     }
161 
162     /**
163      * @see Map#isEmpty()
164      */
165     public boolean isEmpty() {
166         return count == 0;
167     }
168 
169     /**
170      * @see Map#keySet()
171      * This implementation does not conform properly to the specification
172      * in the Map interface.  The returned collection will not be bound to
173      * this map and will not remain in sync with this map.
174      */
175     public Set keySet() {
176         Set result = new HashSet(size());
177         for (int i = 0; i < elements.length; i = i + 2) {
178             if (elements[i] != null) {
179                 result.add(elements[i]);
180             }
181         }
182         return result;
183     }
184 
185     /**
186      * @see Map#put(java.lang.Object, java.lang.Object)
187      */
188     public Object   put(Object   key, Object   value) {
189         if (key == null)
190             throw new NullPointerException  ();
191         if (value == null)
192             return remove(key);
193 
194         // handle the case where we don't have any attributes yet
195         if (elements == null)
196             elements = new Object  [DEFAULT_SIZE];
197         if (count == 0) {
198             elements[0] = key;
199             elements[1] = value;
200             count++;
201             return null;
202         }
203 
204         int emptyIndex = -1;
205         // replace existing value if it exists
206         for (int i = 0; i < elements.length; i += 2) {
207             if (elements[i] != null) {
208                 if (elements[i].equals(key)) {
209                     Object   oldValue = elements[i + 1];
210                     elements[i + 1] = value;
211                     return oldValue;
212                 }
213             } else if (emptyIndex == -1) {
214                 // keep track of the first empty index
215                 emptyIndex = i;
216             }
217         }
218         // this will put the emptyIndex greater than the size but
219         // that's ok because we will grow first.
220         if (emptyIndex == -1)
221             emptyIndex = count * 2;
222 
223         // otherwise add it to the list of elements.
224         // grow if necessary
225         if (elements.length <= (count * 2))
226             grow();
227         elements[emptyIndex] = key;
228         elements[emptyIndex + 1] = value;
229         count++;
230         return null;
231     }
232 
233     /**
234      * @see Map#putAll(java.util.Map)
235      */
236     public void putAll(Map map) {
237         for (Iterator i = map.keySet().iterator(); i.hasNext();) {
238             Object   key = i.next();
239             Object   value = map.get(key);
240             put(key, value);
241         }
242     }
243 
244     /**
245      * @see Map#remove(java.lang.Object)
246      */
247     public Object   remove(Object   key) {
248         if (elements == null || count == 0)
249             return null;
250         for (int i = 0; i < elements.length; i = i + 2) {
251             if (elements[i] != null && elements[i].equals(key)) {
252                 elements[i] = null;
253                 Object   result = elements[i + 1];
254                 elements[i + 1] = null;
255                 count--;
256                 return result;
257             }
258         }
259         return null;
260     }
261 
262     /**
263      * @see Map#size()
264      */
265     public int size() {
266         return count;
267     }
268 
269     /* (non-Javadoc
270      * Method declared on IStringPoolParticipant
271      */
272     public void shareStrings(StringPool set) {
273         //copy elements for thread safety
274         Object  [] array = elements;
275         if (array == null)
276             return;
277         for (int i = 0; i < array.length; i++) {
278             Object   o = array[i];
279             if (o instanceof String  )
280                 array[i] = set.add((String  ) o);
281             if (o instanceof IStringPoolParticipant)
282                 ((IStringPoolParticipant) o).shareStrings(set);
283         }
284     }
285 
286     /**
287      * Creates a new hash map with the same contents as this map.
288      */
289     private HashMap toHashMap() {
290         HashMap result = new HashMap(size());
291         for (int i = 0; i < elements.length; i = i + 2) {
292             if (elements[i] != null) {
293                 result.put(elements[i], elements[i + 1]);
294             }
295         }
296         return result;
297     }
298 
299     /**
300      * @see Map#values()
301      * This implementation does not conform properly to the specification
302      * in the Map interface.  The returned collection will not be bound to
303      * this map and will not remain in sync with this map.
304      */
305     public Collection values() {
306         Set result = new HashSet(size());
307         for (int i = 1; i < elements.length; i = i + 2) {
308             if (elements[i] != null) {
309                 result.add(elements[i]);
310             }
311         }
312         return result;
313     }
314 }
315
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags