bundles/org.simantics.databoard/src/org/simantics/databoard/binding/impl/HashMapBinding.java

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