Merge "Remove unnecessary getComparableKey from HashMapBinding"
[simantics/platform.git] / bundles / org.simantics.databoard / src / org / simantics / databoard / binding / impl / HashMapBinding.java
1 /*******************************************************************************
2  *  Copyright (c) 2010 Association for Decentralized Information Management in
3  *  Industry THTH ry.
4  *  All rights reserved. This program and the accompanying materials
5  *  are made available under the terms of the Eclipse Public License v1.0
6  *  which accompanies this distribution, and is available at
7  *  http://www.eclipse.org/legal/epl-v10.html
8  *
9  *  Contributors:
10  *      VTT Technical Research Centre of Finland - initial API and implementation
11  *******************************************************************************/
12 package org.simantics.databoard.binding.impl;
13
14 import java.util.Arrays;
15 import java.util.Comparator;
16 import java.util.HashMap;
17 import java.util.IdentityHashMap;
18 import java.util.Iterator;
19 import java.util.List;
20 import java.util.Map;
21 import java.util.Map.Entry;
22 import java.util.Set;
23
24 import org.simantics.databoard.Bindings;
25 import org.simantics.databoard.adapter.AdaptException;
26 import org.simantics.databoard.adapter.Adapter;
27 import org.simantics.databoard.adapter.AdapterConstructionException;
28 import org.simantics.databoard.binding.ArrayBinding;
29 import org.simantics.databoard.binding.Binding;
30 import org.simantics.databoard.binding.MapBinding;
31 import org.simantics.databoard.binding.error.BindingException;
32 import org.simantics.databoard.type.MapType;
33
34 /**
35  * Binds Databoard's MapType to java.util.Map and instantiates java.util.HashMap.
36  * 
37  * HashMapBinding has a very poor performance. This operations cannot be performed
38  * with map operations because HashMap doesn't support exterior comparator
39  * which is required.
40  * 
41  * TODO This could be optimized by inquiring whether the Key is {@link Comparable} 
42  *
43  * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
44  */
45 public class HashMapBinding extends MapBinding {
46         
47         public HashMapBinding(Binding keyBinding, Binding valueBinding) {
48                 super(keyBinding, valueBinding);
49         }
50
51         public HashMapBinding(MapType mapType, Binding keyBinding,
52                         Binding valueBinding) {
53                 super(mapType, keyBinding, valueBinding);
54         }
55         
56     @Override
57     public Object create() {        
58         return new HashMap<Object, Object>();
59     }
60     
61         @Override
62         public Object create(Object[] keys, Object[] values) {
63                 if (keys.length!=values.length)
64                         throw new IllegalArgumentException("Equal length arrays expected");
65                 
66                 int len = keys.length;
67                 HashMap<Object, Object> result = new HashMap<Object, Object>(len);
68                 
69                 for (int i=0; i<len; i++) {
70                         Object key = keys[i];
71                         Object value = values[i];
72                         result.put(key, value);
73                 }
74                 
75                 return result;
76         }
77         
78         @Override
79         public Object create(List<Object> keys, List<Object> values) {
80                 if (keys.size()!=values.size())
81                         throw new IllegalArgumentException("Equal length arrays expected");
82                 
83                 int len = keys.size();
84                 HashMap<Object, Object> result = new HashMap<Object, Object>(len);
85                 
86                 for (int i=0; i<len; i++) {
87                         Object key = keys.get(i);
88                         Object value = values.get(i);
89                         result.put(key, value);
90                 }
91                 
92                 return result;
93         }
94         
95         @Override
96         public Object create(Map<?, ?> initialMap) throws BindingException {
97             if (initialMap instanceof HashMap)
98                 return initialMap;
99             
100                 // Replace with TreeMap. Create comparator from binding.
101                 HashMap<Object, Object> result = new HashMap<Object, Object>();
102                 putAll(result, initialMap);
103                 return result;
104         }
105         
106         @Override
107         public void clear(Object map) {
108                 ((Map<?, ?> )map).clear();
109         }
110
111         @Override
112         public boolean containsKey(Object map, Object key) {
113                 Map<?, ?>  m = ((Map<?, ?> )map);
114                 Binding kb = getKeyBinding();
115                 
116                 for (Object v : m.keySet())
117                 {
118                         if (kb.equals(v, key)) return true;
119                 }
120                 return false;
121         }
122
123         @Override
124         public boolean containsValue(Object map, Object value) {
125                 Map<?, ?>  m = ((Map<?, ?> )map);
126                 Binding vb = getValueBinding();
127                 for (Object v : m.values())
128                 {
129                         if (vb.equals(v, value)) return true;
130                 }
131                 return false;
132         }
133
134         @SuppressWarnings("unchecked")
135         @Override
136         public Object get(Object map, Object key) {
137                 Map<Object, Object> m = ((Map<Object, Object>)map);
138                 Binding kb = getKeyBinding();
139                 for (Entry<Object, Object> e : (Set<Entry<Object, Object>>) m.entrySet())
140                 {
141                         if (kb.equals(e.getKey(), key)) return e.getValue();
142                 }
143                 return null;
144         }
145
146         @Override
147         public Object[] getKeys(Object map) {
148                 Map<?, ?>  m = ((Map<?, ?> )map);
149                 Object[] result = m.keySet().toArray(new Object[m.size()]);
150                 Arrays.sort(result, getKeyBinding());
151                 return result;
152         }
153         
154         @Override
155         public void getKeys(Object map, Set<Object> keys) throws BindingException {
156                 Map<?, ?>  m = ((Map<?, ?> )map);
157                 keys.addAll(m.keySet());
158         }
159         
160         @SuppressWarnings("unchecked")
161         @Override
162         public int getEntries(Object src, Object from, boolean fromInclusive, Object end, boolean endInclusive, ArrayBinding dstKeyArrayBinding, Object dstKeyArray, ArrayBinding dstValueArrayBinding, Object dstValueArray, int limit) throws BindingException {
163                 // Assert end > from
164                 if (keyBinding.compare(from, end)>0) return 0;
165                 
166                 try {
167                         int dkc = dstKeyArrayBinding.size(dstKeyArray);
168                         int dvc = dstValueArrayBinding.size(dstValueArray);
169                         Adapter ka = Bindings.getTypeAdapter(keyBinding, dstKeyArrayBinding.getComponentBinding());
170                         Adapter va = Bindings.getTypeAdapter(valueBinding, dstValueArrayBinding.getComponentBinding());
171                         HashMap<Object, Object> m = ((HashMap<Object, Object>)src);
172                         int i = 0;
173                         for (Entry<Object, Object> e : m.entrySet()) {
174                                 if (limit>=0 && i>=limit) break;
175                                 Object k = e.getKey();
176                                 int fk = keyBinding.compare(from, k);
177                                 int ek = keyBinding.compare(k, end);
178                                 boolean fromMatches = fromInclusive ? fk<=0 : fk<0;
179                                 boolean endMatches = endInclusive ? ek<=0 : ek <0;                      
180                                 if ( fromMatches && endMatches ) {
181                                         Object dk = ka.adapt( e.getKey() );
182                                         Object dv = va.adapt( e.getValue() );
183                                         if (i<dkc) dstKeyArrayBinding.set(dstKeyArray, i, dk); else dstKeyArrayBinding.add(dstKeyArray, dk);
184                                         if (i<dvc) dstValueArrayBinding.set(dstValueArray, i, dv); else dstValueArrayBinding.add(dstValueArray, dv);
185                                         i++;
186                                 }
187                         }
188                         return i;
189                 } catch (AdapterConstructionException e) {
190                         throw new BindingException( e );
191                 } catch (AdaptException e) {
192                         throw new BindingException( e );
193                 }
194         }
195         
196         @SuppressWarnings("unchecked")
197         @Override
198         public int count(Object src, Object from, boolean fromInclusive,
199                         Object end, boolean endInclusive) throws BindingException {
200                 // Assert end > from
201                 if (keyBinding.compare(from, end)>0) return 0;
202                 
203                 int result = 0;
204                 HashMap<Object, Object> m = ((HashMap<Object, Object>)src);
205                 for (Object k : m.keySet()) {
206                         int fk = keyBinding.compare(from, k);
207                         int ek = keyBinding.compare(k, end);
208                         boolean fromMatches = fromInclusive ? fk<=0 : fk<0;
209                         boolean endMatches = endInclusive ? ek<=0 : ek <0;                      
210                         if ( fromMatches && endMatches ) result++;
211                 }               
212                 return result;
213         }
214                 
215         @Override
216         public Object[] getValues(Object map) {
217                 Map<?, ?>  m = ((Map<?, ?> )map);
218                 int len = m.size();
219                 Object[] keys = getKeys(map);
220                 Object[] values = new Object[len];
221                 for (int i=0; i<len; i++) {
222                         values[i] = m.get(keys[i]);
223                 }
224                 return values;
225         }
226         
227         @SuppressWarnings("unchecked")
228         @Override
229         public void put(Object map, Object key, Object value) {
230                 Map<Object, Object> m = ((Map<Object, Object>)map);
231                 m.put(key, value);
232         }
233
234         @SuppressWarnings("unchecked")
235         @Override
236         public <K, V> void putAll(Object map, Map<K, V>  src) throws BindingException {
237                 Map<K, V>  m = ((Map<K, V> )map);
238                 for (Entry<K, V>  e : (Set<Entry<K, V> >) src.entrySet()) {
239                         m.put(e.getKey(), e.getValue());
240                 }
241         }
242         
243         @SuppressWarnings("unchecked")
244     @Override
245         public <K, V> void getAll(Object mapFrom, Map<K, V> to) {
246                 Map<K, V> m = ((Map<K, V>)mapFrom);
247                 to.putAll(m);
248         }
249
250         @Override
251         public void getAll(Object mapFrom, Object[] keys, Object[] values) 
252         throws BindingException 
253         {
254                 Map<?, ?> m = ((Map<?, ?>)mapFrom);             
255                 int len = m.size();
256                 
257                 if (len!=keys.length) throw new BindingException("Keys array is wrong size");
258                 if (len!=values.length) throw new BindingException("Values array is wrong size");
259                 
260                 Iterator<?> iter = m.keySet().iterator();
261                 int i=0;
262                 while (iter.hasNext()) {
263                         keys[i++] = iter.next();
264                 }
265                 Arrays.sort(keys, getKeyBinding());
266                 for (i=0; i<len; i++) {
267                         values[i] = m.get(keys[i]);
268                 }
269         }
270         
271         @SuppressWarnings("unchecked")
272         @Override
273         public Object remove(Object map, Object key) {
274                 Map<Object, Object> m = ((Map<Object, Object>)map);
275                 Binding kb = getKeyBinding();
276                 for (Entry<Object, Object> e : (Set<Entry<Object, Object>>) m.entrySet())
277                 {
278                         if (kb.equals(e.getKey(), key)) return m.remove(e.getKey());
279                 }
280                 return null;
281         }
282
283         @Override
284         public int size(Object map) {
285                 Map<?, ?> m = ((Map<?, ?>)map);
286                 return m.size();
287         }
288         
289         @Override
290         public boolean isInstance(Object obj) {
291                 return obj instanceof HashMap;
292         }
293
294         @SuppressWarnings("unchecked")
295     @Override
296     public int deepHashValue(Object map, IdentityHashMap<Object, Object> hashedObjects) throws BindingException {
297                 int result = 0;
298                 Map<Object, Object> m = ((Map<Object, Object>)map);
299                 Set<Entry<Object, Object>> s = m.entrySet();
300                 for (Entry<Object, Object> e : s) {                                             
301                         int keyHash   = getKeyBinding().deepHashValue( e.getKey(), hashedObjects );
302                         int valueHash = getValueBinding().deepHashValue( e.getValue(), hashedObjects );                 
303                         result += (keyHash ^ valueHash);
304                 }
305                 return result;
306         }
307
308         @SuppressWarnings("unchecked")
309     @Override
310         public Object getCeilingKey(Object map, Object key) {
311                 Map<Object, Object> m = ((Map<Object, Object>)map);
312                 if (m.isEmpty()) return null;
313                 Comparator<Object> comparator = getKeyBinding();
314                 Object pivot = null;
315                 for (Object o : m.keySet()) {
316                         // We are trying to find key > o > pivot
317                         int c2 = comparator.compare(key, o);
318                         if (c2>0) continue;
319                         if (pivot==null) {pivot = o; continue;}
320                         int c1 = comparator.compare(o, pivot);
321                         if (c1<0) pivot = o;
322                 }
323                 return pivot;
324         }
325
326         @SuppressWarnings("unchecked")
327     @Override
328         public Object getFirstKey(Object map) {
329                 Map<Object, Object> m = (Map<Object, Object>) map;
330                 if (m.isEmpty()) return null;
331                 Comparator<Object> c = getKeyBinding();
332                 Object result = null;
333                 for (Object o : m.keySet()) {
334                         if (result==null) {
335                                 result = o;
336                                 continue;
337                         }
338                         if (c.compare(o, result)<0) result = o;
339                 }       
340                 
341                 return result;  
342         }
343
344         @SuppressWarnings("unchecked")
345     @Override
346         public Object getFloorKey(Object map, Object key) {
347                 Map<Object, Object> m = ((Map<Object, Object>)map);
348                 if (m.isEmpty()) return null;   
349 //              if (m.containsKey(key)) return key;
350                 
351                 Comparator<Object> comparator = getKeyBinding();
352                 Object pivot = null;
353                 for (Object o : m.keySet()) {
354                         // We are trying to find pivot <= o <= key
355                         int c2 = comparator.compare(o, key);
356                         if (c2==0) return o;
357                         if (c2>0) continue;
358                         if (pivot==null) {pivot = o; continue;}
359                         int c1 = comparator.compare(pivot, o);
360                         if (c1<0) pivot = o;
361                 }
362                 return pivot;
363         }
364
365         @SuppressWarnings("unchecked")
366     @Override
367         public Object getHigherKey(Object map, Object key) {
368                 Map<Object, Object> m = ((Map<Object, Object>)map);
369                 if (m.isEmpty()) return null;
370                 Comparator<Object> comparator = getKeyBinding();
371                 Object pivot = null;
372                 for (Object o : m.keySet()) {
373                         // We are trying to find key > o > pivot
374                         int c2 = comparator.compare(key, o);
375                         if (c2>=0) continue;
376                         if (pivot==null) {pivot = o; continue;}
377                         int c1 = comparator.compare(o, pivot);
378                         if (c1<0) pivot = o;
379                 }
380                 return pivot;
381         }
382
383         @SuppressWarnings("unchecked")
384     @Override
385         public Object getLastKey(Object map) {
386                 Map<Object, Object> m = (Map<Object, Object>) map;
387                 if (m.isEmpty()) return null;
388                 Comparator<Object> c = getKeyBinding();
389                 Object result = null;
390                 for (Object o : m.keySet()) {
391                         if (result==null) {
392                                 result = o;
393                                 continue;
394                         }
395                         if (c.compare(o, result)>0) result = o;
396                 }       
397                 
398                 return result;  
399         }
400
401         @SuppressWarnings("unchecked")
402     @Override
403         public Object getLowerKey(Object map, Object key) {
404                 Map<Object, Object> m = ((Map<Object, Object>)map);
405                 if (m.isEmpty()) return null;
406                 Comparator<Object> comparator = getKeyBinding();
407                 Object pivot = null;
408                 for (Object o : m.keySet()) {
409                         // We are trying to find pivot < o < key
410                         int c2 = comparator.compare(o, key);
411                         if (c2>=0) continue;
412                         if (pivot==null) {pivot = o; continue;}
413                         int c1 = comparator.compare(pivot, o);
414                         if (c1<0) pivot = o;
415                 }
416                 return pivot;
417         }
418         
419 }
420