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