Added addFirst/After/Before + remove SCL functions for Ordered Sets
[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                         key = getComparableKey(result, key);                    
72                         Object value = values[i];
73                         result.put(key, value);
74                 }
75                 
76                 return result;
77         }
78         
79         @Override
80         public Object create(List<Object> keys, List<Object> values) {
81                 if (keys.size()!=values.size())
82                         throw new IllegalArgumentException("Equal length arrays expected");
83                 
84                 int len = keys.size();
85                 HashMap<Object, Object> result = new HashMap<Object, Object>(len);
86                 
87                 for (int i=0; i<len; i++) {
88                         Object key = keys.get(i);
89                         key = getComparableKey(result, key);
90                         Object value = values.get(i);
91                         result.put(key, value);
92                 }
93                 
94                 return result;
95         }
96         
97         @Override
98         public Object create(Map<?, ?> initialMap) throws BindingException {
99             if (initialMap instanceof HashMap)
100                 return initialMap;
101             
102                 // Replace with TreeMap. Create comparator from binding.
103                 HashMap<Object, Object> result = new HashMap<Object, Object>();
104                 putAll(result, initialMap);
105                 return result;
106         }
107         
108         @Override
109         public void clear(Object map) {
110                 ((Map<?, ?> )map).clear();
111         }
112
113         @Override
114         public boolean containsKey(Object map, Object key) {
115                 Map<?, ?>  m = ((Map<?, ?> )map);
116                 Binding kb = getKeyBinding();
117                 
118                 for (Object v : m.keySet())
119                 {
120                         if (kb.equals(v, key)) return true;
121                 }
122                 return false;
123         }
124
125         @Override
126         public boolean containsValue(Object map, Object value) {
127                 Map<?, ?>  m = ((Map<?, ?> )map);
128                 Binding vb = getValueBinding();
129                 for (Object v : m.values())
130                 {
131                         if (vb.equals(v, value)) return true;
132                 }
133                 return false;
134         }
135
136         @SuppressWarnings("unchecked")
137         @Override
138         public Object get(Object map, Object key) {
139                 Map<Object, Object> m = ((Map<Object, Object>)map);
140                 Binding kb = getKeyBinding();
141                 for (Entry<Object, Object> e : (Set<Entry<Object, Object>>) m.entrySet())
142                 {
143                         if (kb.equals(e.getKey(), key)) return e.getValue();
144                 }
145                 return null;
146         }
147
148         @Override
149         public Object[] getKeys(Object map) {
150                 Map<?, ?>  m = ((Map<?, ?> )map);
151                 Object[] result = m.keySet().toArray(new Object[m.size()]);
152                 Arrays.sort(result, getKeyBinding());
153                 return result;
154         }
155         
156         @Override
157         public void getKeys(Object map, Set<Object> keys) throws BindingException {
158                 Map<?, ?>  m = ((Map<?, ?> )map);
159                 keys.addAll(m.keySet());
160         }
161         
162         @SuppressWarnings("unchecked")
163         @Override
164         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 {
165                 // Assert end > from
166                 if (keyBinding.compare(from, end)>0) return 0;
167                 
168                 try {
169                         int dkc = dstKeyArrayBinding.size(dstKeyArray);
170                         int dvc = dstValueArrayBinding.size(dstValueArray);
171                         Adapter ka = Bindings.getTypeAdapter(keyBinding, dstKeyArrayBinding.getComponentBinding());
172                         Adapter va = Bindings.getTypeAdapter(valueBinding, dstValueArrayBinding.getComponentBinding());
173                         HashMap<Object, Object> m = ((HashMap<Object, Object>)src);
174                         int i = 0;
175                         for (Entry<Object, Object> e : m.entrySet()) {
176                                 if (limit>=0 && i>=limit) break;
177                                 Object k = e.getKey();
178                                 int fk = keyBinding.compare(from, k);
179                                 int ek = keyBinding.compare(k, end);
180                                 boolean fromMatches = fromInclusive ? fk<=0 : fk<0;
181                                 boolean endMatches = endInclusive ? ek<=0 : ek <0;                      
182                                 if ( fromMatches && endMatches ) {
183                                         Object dk = ka.adapt( e.getKey() );
184                                         Object dv = va.adapt( e.getValue() );
185                                         if (i<dkc) dstKeyArrayBinding.set(dstKeyArray, i, dk); else dstKeyArrayBinding.add(dstKeyArray, dk);
186                                         if (i<dvc) dstValueArrayBinding.set(dstValueArray, i, dv); else dstValueArrayBinding.add(dstValueArray, dv);
187                                         i++;
188                                 }
189                         }
190                         return i;
191                 } catch (AdapterConstructionException e) {
192                         throw new BindingException( e );
193                 } catch (AdaptException e) {
194                         throw new BindingException( e );
195                 }
196         }
197         
198         @SuppressWarnings("unchecked")
199         @Override
200         public int count(Object src, Object from, boolean fromInclusive,
201                         Object end, boolean endInclusive) throws BindingException {
202                 // Assert end > from
203                 if (keyBinding.compare(from, end)>0) return 0;
204                 
205                 int result = 0;
206                 HashMap<Object, Object> m = ((HashMap<Object, Object>)src);
207                 for (Object k : m.keySet()) {
208                         int fk = keyBinding.compare(from, k);
209                         int ek = keyBinding.compare(k, end);
210                         boolean fromMatches = fromInclusive ? fk<=0 : fk<0;
211                         boolean endMatches = endInclusive ? ek<=0 : ek <0;                      
212                         if ( fromMatches && endMatches ) result++;
213                 }               
214                 return result;
215         }
216                 
217         @Override
218         public Object[] getValues(Object map) {
219                 Map<?, ?>  m = ((Map<?, ?> )map);
220                 int len = m.size();
221                 Object[] keys = getKeys(map);
222                 Object[] values = new Object[len];
223                 for (int i=0; i<len; i++) {
224                         values[i] = m.get(keys[i]);
225                 }
226                 return values;
227         }
228
229         @SuppressWarnings("unchecked")
230         protected Object getComparableKey(Object map, Object key) {
231                 // if (keyIsComparable) return key;
232                 
233                 Map<Object, Object> m = ((Map<Object, Object>)map);
234                 Binding kb = getKeyBinding();
235                 for (Object k : m.keySet())
236                 {
237                         if (kb.equals(k, key))
238                                 return k;
239                 }
240                 return key;
241         }
242         
243         @SuppressWarnings("unchecked")
244         @Override
245         public void put(Object map, Object key, Object value) {
246                 Map<Object, Object> m = ((Map<Object, Object>)map);
247                 Object ck = getComparableKey(m, key);
248                 m.remove(ck);
249                 m.put(key, value);
250         }
251
252         @SuppressWarnings("unchecked")
253         @Override
254         public <K, V> void putAll(Object map, Map<K, V>  src) throws BindingException {
255                 Map<K, V>  m = ((Map<K, V> )map);
256                 for (Entry<K, V>  e : (Set<Entry<K, V> >) src.entrySet()) {
257                         Object ck = getComparableKey(map, e.getKey());
258                         m.remove(ck);
259                         m.put(e.getKey(), e.getValue());
260                 }
261         }
262         
263         @SuppressWarnings("unchecked")
264     @Override
265         public <K, V> void getAll(Object mapFrom, Map<K, V> to) {
266                 Map<K, V> m = ((Map<K, V>)mapFrom);
267                 to.putAll(m);
268         }
269
270         @Override
271         public void getAll(Object mapFrom, Object[] keys, Object[] values) 
272         throws BindingException 
273         {
274                 Map<?, ?> m = ((Map<?, ?>)mapFrom);             
275                 int len = m.size();
276                 
277                 if (len!=keys.length) throw new BindingException("Keys array is wrong size");
278                 if (len!=values.length) throw new BindingException("Values array is wrong size");
279                 
280                 Iterator<?> iter = m.keySet().iterator();
281                 int i=0;
282                 while (iter.hasNext()) {
283                         keys[i++] = iter.next();
284                 }
285                 Arrays.sort(keys, getKeyBinding());
286                 for (i=0; i<len; i++) {
287                         values[i] = m.get(keys[i]);
288                 }
289         }
290         
291         @SuppressWarnings("unchecked")
292         @Override
293         public Object remove(Object map, Object key) {
294                 Map<Object, Object> m = ((Map<Object, Object>)map);
295                 Binding kb = getKeyBinding();
296                 for (Entry<Object, Object> e : (Set<Entry<Object, Object>>) m.entrySet())
297                 {
298                         if (kb.equals(e.getKey(), key)) return m.remove(e.getKey());
299                 }
300                 return null;
301         }
302
303         @Override
304         public int size(Object map) {
305                 Map<?, ?> m = ((Map<?, ?>)map);
306                 return m.size();
307         }
308         
309         @Override
310         public boolean isInstance(Object obj) {
311                 return obj instanceof HashMap;
312         }
313
314         @SuppressWarnings("unchecked")
315     @Override
316     public int deepHashValue(Object map, IdentityHashMap<Object, Object> hashedObjects) throws BindingException {
317                 int result = 0;
318                 Map<Object, Object> m = ((Map<Object, Object>)map);
319                 Set<Entry<Object, Object>> s = m.entrySet();
320                 for (Entry<Object, Object> e : s) {                                             
321                         int keyHash   = getKeyBinding().deepHashValue( e.getKey(), hashedObjects );
322                         int valueHash = getValueBinding().deepHashValue( e.getValue(), hashedObjects );                 
323                         result += (keyHash ^ valueHash);
324                 }
325                 return result;
326         }
327
328         @SuppressWarnings("unchecked")
329     @Override
330         public Object getCeilingKey(Object map, Object key) {
331                 Map<Object, Object> m = ((Map<Object, Object>)map);
332                 if (m.isEmpty()) return null;
333                 Comparator<Object> comparator = getKeyBinding();
334                 Object pivot = null;
335                 for (Object o : m.keySet()) {
336                         // We are trying to find key > o > pivot
337                         int c2 = comparator.compare(key, o);
338                         if (c2>0) continue;
339                         if (pivot==null) {pivot = o; continue;}
340                         int c1 = comparator.compare(o, pivot);
341                         if (c1<0) pivot = o;
342                 }
343                 return pivot;
344         }
345
346         @SuppressWarnings("unchecked")
347     @Override
348         public Object getFirstKey(Object map) {
349                 Map<Object, Object> m = (Map<Object, Object>) map;
350                 if (m.isEmpty()) return null;
351                 Comparator<Object> c = getKeyBinding();
352                 Object result = null;
353                 for (Object o : m.keySet()) {
354                         if (result==null) {
355                                 result = o;
356                                 continue;
357                         }
358                         if (c.compare(o, result)<0) result = o;
359                 }       
360                 
361                 return result;  
362         }
363
364         @SuppressWarnings("unchecked")
365     @Override
366         public Object getFloorKey(Object map, Object key) {
367                 Map<Object, Object> m = ((Map<Object, Object>)map);
368                 if (m.isEmpty()) return null;   
369 //              if (m.containsKey(key)) return key;
370                 
371                 Comparator<Object> comparator = getKeyBinding();
372                 Object pivot = null;
373                 for (Object o : m.keySet()) {
374                         // We are trying to find pivot <= o <= key
375                         int c2 = comparator.compare(o, key);
376                         if (c2==0) return o;
377                         if (c2>0) continue;
378                         if (pivot==null) {pivot = o; continue;}
379                         int c1 = comparator.compare(pivot, o);
380                         if (c1<0) pivot = o;
381                 }
382                 return pivot;
383         }
384
385         @SuppressWarnings("unchecked")
386     @Override
387         public Object getHigherKey(Object map, Object key) {
388                 Map<Object, Object> m = ((Map<Object, Object>)map);
389                 if (m.isEmpty()) return null;
390                 Comparator<Object> comparator = getKeyBinding();
391                 Object pivot = null;
392                 for (Object o : m.keySet()) {
393                         // We are trying to find key > o > pivot
394                         int c2 = comparator.compare(key, o);
395                         if (c2>=0) continue;
396                         if (pivot==null) {pivot = o; continue;}
397                         int c1 = comparator.compare(o, pivot);
398                         if (c1<0) pivot = o;
399                 }
400                 return pivot;
401         }
402
403         @SuppressWarnings("unchecked")
404     @Override
405         public Object getLastKey(Object map) {
406                 Map<Object, Object> m = (Map<Object, Object>) map;
407                 if (m.isEmpty()) return null;
408                 Comparator<Object> c = getKeyBinding();
409                 Object result = null;
410                 for (Object o : m.keySet()) {
411                         if (result==null) {
412                                 result = o;
413                                 continue;
414                         }
415                         if (c.compare(o, result)>0) result = o;
416                 }       
417                 
418                 return result;  
419         }
420
421         @SuppressWarnings("unchecked")
422     @Override
423         public Object getLowerKey(Object map, Object key) {
424                 Map<Object, Object> m = ((Map<Object, Object>)map);
425                 if (m.isEmpty()) return null;
426                 Comparator<Object> comparator = getKeyBinding();
427                 Object pivot = null;
428                 for (Object o : m.keySet()) {
429                         // We are trying to find pivot < o < key
430                         int c2 = comparator.compare(o, key);
431                         if (c2>=0) continue;
432                         if (pivot==null) {pivot = o; continue;}
433                         int c1 = comparator.compare(pivot, o);
434                         if (c1<0) pivot = o;
435                 }
436                 return pivot;
437         }
438         
439 }
440