bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java

   1 package org.simantics.scl.runtime;
   2
   3 import java.util.ArrayList;
   4 import java.util.Arrays;
   5 import java.util.Collections;
   6 import java.util.Comparator;
   7 import java.util.Iterator;
   8 import java.util.List;
   9
  10 import org.simantics.scl.runtime.function.Function;
  11 import org.simantics.scl.runtime.function.FunctionImpl1;
  12 import org.simantics.scl.runtime.function.FunctionImpl2;
  13 import org.simantics.scl.runtime.tuple.Tuple2;
  14
  15 import gnu.trove.map.hash.TCustomHashMap;
  16 import gnu.trove.map.hash.THashMap;
  17 import gnu.trove.set.hash.THashSet;
  18 import gnu.trove.strategy.HashingStrategy;
  19
  20
  21 @SuppressWarnings({"rawtypes", "unchecked"})
  22 public class Lists {
  23
  24     public static List map(Function f, List l) {
  25         ArrayList result = new ArrayList(l.size());
  26         for(Object a : l)
  27             result.add(f.apply(a));
  28         return result;
  29     }
  30
  31     public static void iter(Function f, List l) {
  32         for(Object a : l)
  33             f.apply(a);
  34     }
  35
  36     public static List filter(Function p, List l) {
  37         ArrayList result = new ArrayList(Math.min(10, l.size()));
  38         for(Object a : l)
  39             if((Boolean)p.apply(a))
  40                 result.add(a);
  41         return result;
  42     }
  43
  44     public static List filterJust(List l) {
  45         ArrayList result = new ArrayList(Math.min(10, l.size()));
  46         for(Object a : l)
  47             if(a != null)
  48                 result.add(a);
  49         return result;
  50     }
  51
  52     public static List reverse(List l) {
  53         ArrayList result = new ArrayList(l.size());
  54         for(int i=l.size()-1;i>=0;--i)
  55             result.add(l.get(i));
  56         return result;
  57     }
  58
  59     public static Object foldl(Function f, Object initial, List l) {
  60         for(Object a : l)
  61             initial = f.apply(initial, a);
  62         return initial;
  63     }
  64
  65     // (b -> Maybe (a, b)) -> b -> [a]
  66     public static List unfoldr(Function f, Object state) {
  67         ArrayList result = new ArrayList();
  68         while(true) {
  69             Object r = f.apply(state);
  70             if(r == null)
  71                 return result;
  72             Tuple2 t = (Tuple2)r;
  73             result.add(t.c0);
  74             state = t.c1;
  75         }
  76     }
  77
  78     public static Object foldr(Function f, Object initial, List l) {
  79         for(int i=l.size()-1;i>=0;--i)
  80             initial = f.apply(initial, l.get(i));
  81         return initial;
  82     }
  83
  84     public static Object foldl1(Function f, List l) {
  85         Iterator it = l.iterator();
  86         Object initial = it.next();
  87         while(it.hasNext())
  88             initial = f.apply(initial, it.next());
  89         return initial;
  90     }
  91
  92     public static Object foldr1(Function f, List l) {
  93         int i=l.size()-1;
  94         Object initial = l.get(i);
  95         for(--i;i>=0;--i)
  96             initial = f.apply(initial, l.get(i));
  97         return initial;
  98     }
  99
 100     public static List _pp(List a, List b) {
 101         ArrayList result = new ArrayList(a.size() + b.size());
 102         result.addAll(a);
 103         result.addAll(b);
 104         return result;
 105     }
 106
 107     public static List concat(List l) {
 108         int size = 0;
 109         for(Object e : l)
 110             size += ((List)e).size();
 111         ArrayList result = new ArrayList(size);
 112         for(Object e : l)
 113             result.addAll((List)e);
 114         return result;
 115     }
 116
 117     public static List append(List a, List b) {
 118         ArrayList result = new ArrayList(a.size() + b.size());
 119         result.addAll(a);
 120         result.addAll(b);
 121         return result;
 122     }
 123
 124     public static List concatMap(Function f, List l) {
 125         return concat(map(f, l));
 126     }
 127
 128     public static int length(List l) {
 129         return l.size();
 130     }
 131
 132     public static boolean forall(Function p, List l) {
 133         for(Object e : l)
 134             if(!(Boolean)p.apply(e))
 135                 return false;
 136         return true;
 137     }
 138
 139     public static boolean exists(Function p, List l) {
 140         for(Object e : l)
 141             if((Boolean)p.apply(e))
 142                 return true;
 143         return false;
 144     }
 145
 146     public static Object get(List l, double i) {
 147         return l.get((int)i);
 148     }
 149
 150     private static final FunctionImpl2 BUILD_FUNC = new FunctionImpl2() {
 151         @Override
 152         public Object apply(Object p0, Object p1) {
 153             ((ArrayList)p0).add(p1);
 154             return p0;
 155         }
 156     };
 157
 158     public static List build(Function f) {
 159         return (List)f.apply(new ArrayList(), BUILD_FUNC);
 160     }
 161
 162     public static List range(int from, int to) {
 163         ArrayList result = new ArrayList();
 164         while(from <= to) {
 165             result.add(from);
 166             ++from;
 167         }
 168         return result;
 169     }
 170
 171     public static List newList() {
 172         return new ArrayList(2);
 173     }
 174
 175     public static void add(List a, Object b) {
 176         a.add(b);
 177     }
 178
 179     public static List zip(List a, List b) {
 180         int len = Math.min(a.size(), b.size());
 181         ArrayList result = new ArrayList(len);
 182         for(int i=0;i<len;++i)
 183             result.add(new Tuple2(a.get(i), b.get(i)));
 184         return result;
 185     }
 186
 187     public static List zipWith(Function f, List a, List b) {
 188         int len = Math.min(a.size(), b.size());
 189         ArrayList result = new ArrayList(len);
 190         for(int i=0;i<len;++i)
 191             result.add(f.apply(a.get(i), b.get(i)));
 192         return result;
 193     }
 194
 195     public static Tuple2 unzip(List in) {
 196         int len = in.size();
 197         ArrayList a = new ArrayList(len);
 198         ArrayList b = new ArrayList(len);
 199         for(int i=0;i<len;++i) {
 200             Tuple2 tuple = (Tuple2)in.get(i);
 201             a.add(tuple.c0);
 202             b.add(tuple.c1);
 203         }
 204         return new Tuple2(a, b);
 205     }
 206
 207     public static Function indexWith(final Function hash, final Function eq, List<Tuple2> l) {
 208         final TCustomHashMap<Object,Object> map = new TCustomHashMap<Object,Object>(
 209                 new HashingStrategy<Object>() {
 210                     private static final long serialVersionUID = 3130052128660420673L;
 211
 212                     @Override
 213                     public int computeHashCode(Object object) {
 214                         return (Integer)hash.apply(object);
 215                     }
 216
 217                     @Override
 218                     public boolean equals(Object o1, Object o2) {
 219                         return (Boolean)eq.apply(o1, o2);
 220                     }
 221                 });
 222         for(Tuple2 t : l)
 223             map.put(t.c0, t.c1);
 224         return new FunctionImpl1<Object,Object>() {
 225             @Override
 226             public Object apply(Object p0) {
 227                 return map.get(p0);
 228             }
 229         };
 230     }
 231
 232     public static Function index(List<Tuple2> l) {
 233         THashMap map = new THashMap(l.size());
 234         for(Tuple2 t : l)
 235             map.put(t.c0, t.c1);
 236         return new FunctionImpl1<Object,Object>() {
 237             @Override
 238             public Object apply(Object p0) {
 239                 return map.get(p0);
 240             }
 241         };
 242     }
 243
 244     public static Function indexSet(List<Object> l) {
 245         THashSet set = new THashSet(l.size());
 246         for(Object obj : l)
 247             set.add(obj);
 248         return new FunctionImpl1<Object,Object>() {
 249             @Override
 250             public Object apply(Object p0) {
 251                 return set.contains(p0);
 252             }
 253         };
 254     }
 255
 256     public static Function indexBy(Function f, List l) {
 257         THashMap map = new THashMap(l.size());
 258         for(Object o : l)
 259             map.put(f.apply(o), o);
 260         return new FunctionImpl1<Object,Object>() {
 261             @Override
 262             public Object apply(Object p0) {
 263                 return map.get(p0);
 264             }
 265         };
 266     }
 267
 268     // groupWith :: (a -> Integer) -> (a -> a -> Boolean) -> (a -> b) -> [a] -> [(b, [a])]
 269     @SuppressWarnings("serial")
 270     public static List<Tuple2> groupWith(final Function hash, final Function eq, Function keyFunction, Function valueFunction, List<Object> input) {
 271         final TCustomHashMap<Object,ArrayList<Object>> map = new TCustomHashMap<Object,ArrayList<Object>>(
 272                 new HashingStrategy<Object>() {
 273                     @Override
 274                     public int computeHashCode(Object object) {
 275                         return (Integer)hash.apply(object);
 276                     }
 277
 278                     @Override
 279                     public boolean equals(Object o1, Object o2) {
 280                         return (Boolean)eq.apply(o1, o2);
 281                     }
 282                 });
 283         ArrayList<Tuple2> result = new ArrayList<Tuple2>();
 284         for(Object o : input) {
 285             Object key = keyFunction.apply(o);
 286             ArrayList<Object> l = map.get(key);
 287             if(l == null) {
 288                 l = new ArrayList<Object>();
 289                 map.put(key, l);
 290                 result.add(new Tuple2(key, l));
 291             }
 292             l.add(valueFunction.apply(o));
 293         }
 294         return result;
 295     }
 296
 297     public static List<Tuple2> group(List<Tuple2> input) {
 298         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
 299         ArrayList<Tuple2> result = new ArrayList<Tuple2>();
 300         for(Tuple2 t : input) {
 301             Object key = t.c0;
 302             ArrayList<Object> list = groupMap.get(key);
 303             if(list == null) {
 304                 list = new ArrayList<Object>();
 305                 groupMap.put(key, list);
 306                 result.add(new Tuple2(key, list));
 307             }
 308             list.add(t.c1);
 309         }
 310         return result;
 311     }
 312
 313     public static List<Tuple2> groupBy(Function f, List<Tuple2> input) {
 314         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
 315         ArrayList<Tuple2> result = new ArrayList<Tuple2>();
 316         for(Object value : input) {
 317             Object key = f.apply(value);
 318             ArrayList<Object> list = groupMap.get(key);
 319             if(list == null) {
 320                 list = new ArrayList<Object>();
 321                 groupMap.put(key, list);
 322                 result.add(new Tuple2(key, list));
 323             }
 324             list.add(value);
 325         }
 326         return result;
 327     }
 328
 329     private static class GroupMapFunction extends FunctionImpl1<Object, List<Object>> {
 330         THashMap<Object, ArrayList<Object>> groupMap;
 331         public GroupMapFunction(THashMap<Object, ArrayList<Object>> groupMap) {
 332             this.groupMap = groupMap;
 333         }
 334         @Override
 335         public List<Object> apply(Object p0) {
 336             List<Object> result = groupMap.get(p0);
 337             if(result == null)
 338                 return Collections.emptyList();
 339             else
 340                 return result;
 341         }
 342     }
 343
 344     public static Function indexGroup(List<Tuple2> input) {
 345         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
 346         for(Tuple2 t : input) {
 347             Object key = t.c0;
 348             ArrayList<Object> list = groupMap.get(key);
 349             if(list == null) {
 350                 list = new ArrayList<Object>();
 351                 groupMap.put(key, list);
 352             }
 353             list.add(t.c1);
 354         }
 355         return new GroupMapFunction(groupMap);
 356     }
 357
 358     public static Function indexGroupBy(Function f, List<Tuple2> input) {
 359         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
 360         for(Object value : input) {
 361             Object key = f.apply(value);
 362             ArrayList<Object> list = groupMap.get(key);
 363             if(list == null) {
 364                 list = new ArrayList<Object>();
 365                 groupMap.put(key, list);
 366             }
 367             list.add(value);
 368         }
 369         return new GroupMapFunction(groupMap);
 370     }
 371
 372     public static List sortWith(final Function compare, List l) {
 373         Object[] result = l.toArray(new Object[l.size()]);
 374         Arrays.sort(result, new Comparator() {
 375             @Override
 376             public int compare(Object o1, Object o2) {
 377                 return (Integer)compare.apply(o1, o2);
 378             }
 379         });
 380         return Arrays.asList(result);
 381     }
 382
 383     public static List uniqueWith(Function compare, List l) {
 384         ArrayList result = new ArrayList(Math.min(10, l.size()));
 385         outerLoop:
 386         for(int i=0;i<l.size();++i) {
 387             Object el = l.get(i);
 388             for(int j=0;j<result.size();++j)
 389                 if(compare.apply(el, result.get(j)).equals(Boolean.TRUE))
 390                     continue outerLoop;
 391             result.add(el);
 392         }
 393         return result;
 394     }
 395
 396     public static List deleteAllBy(Function compare, List a, List b) {
 397         ArrayList result = new ArrayList(Math.min(10, a.size()));
 398         outerLoop:
 399         for(Object el : a) {
 400             for(Object el2 : b)
 401                 if(compare.apply(el, el2).equals(Boolean.TRUE))
 402                     continue outerLoop;
 403             result.add(el);
 404         }
 405         return result;
 406     }
 407
 408     public static List listDifference(List a, List b) {
 409         if(a.isEmpty() || b.isEmpty())
 410             return a;
 411         THashSet setB = new THashSet(b);
 412         for(int i=0;i<a.size();++i) {
 413             Object el = a.get(i);
 414             if(setB.contains(el)) {
 415                 ArrayList result = new ArrayList(a.size()-1);
 416                 for(int j=0;j<i;++j)
 417                     result.add(a.get(j));
 418                 for(++i;i<a.size();++i) {
 419                     el = a.get(i);
 420                     if(!setB.contains(el))
 421                         result.add(el);
 422                 }
 423                 return result;
 424             }
 425         }
 426         return a;
 427     }
 428
 429     public static List<Object> unique(List<Object> l) {
 430         THashSet<Object> set = new THashSet<Object>(l.size());
 431         ArrayList<Object> result = new ArrayList<Object>(l.size());
 432         for(Object el : l)
 433             if(set.add(el))
 434                 result.add(el);
 435         return result;
 436     }
 437
 438     public static List<Object> uniqueBy(Function f, List<Object> l) {
 439         THashSet<Object> set = new THashSet<Object>(l.size());
 440         ArrayList<Object> result = new ArrayList<Object>(l.size());
 441         for(Object el : l)
 442             if(set.add(f.apply(el)))
 443                 result.add(el);
 444         return result;
 445     }
 446 }