]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java
5259ce6315a38b5b9b1ab64f94ce452cb82930ca
[simantics/platform.git] / 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 indexBy(Function f, List l) {
245         THashMap map = new THashMap(l.size());
246         for(Object o : l)
247             map.put(f.apply(o), o);
248         return new FunctionImpl1<Object,Object>() {
249             @Override
250             public Object apply(Object p0) {
251                 return map.get(p0);
252             }
253         };
254     }
255     
256     // groupWith :: (a -> Integer) -> (a -> a -> Boolean) -> (a -> b) -> [a] -> [(b, [a])]
257     @SuppressWarnings("serial")
258     public static List<Tuple2> groupWith(final Function hash, final Function eq, Function keyFunction, Function valueFunction, List<Object> input) {
259         final TCustomHashMap<Object,ArrayList<Object>> map = new TCustomHashMap<Object,ArrayList<Object>>(
260                 new HashingStrategy<Object>() {
261                     @Override
262                     public int computeHashCode(Object object) {
263                         return (Integer)hash.apply(object);
264                     }
265
266                     @Override
267                     public boolean equals(Object o1, Object o2) {
268                         return (Boolean)eq.apply(o1, o2);
269                     }
270                 });
271         ArrayList<Tuple2> result = new ArrayList<Tuple2>();
272         for(Object o : input) {
273             Object key = keyFunction.apply(o);
274             ArrayList<Object> l = map.get(key);
275             if(l == null) {
276                 l = new ArrayList<Object>();
277                 map.put(key, l);
278                 result.add(new Tuple2(key, l));
279             }
280             l.add(valueFunction.apply(o));
281         }
282         return result;
283     }
284     
285     public static List<Tuple2> group(List<Tuple2> input) {
286         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
287         ArrayList<Tuple2> result = new ArrayList<Tuple2>();
288         for(Tuple2 t : input) {
289             Object key = t.c0;
290             ArrayList<Object> list = groupMap.get(key);
291             if(list == null) {
292                 list = new ArrayList<Object>();
293                 groupMap.put(key, list);
294                 result.add(new Tuple2(key, list));
295             }
296             list.add(t.c1);
297         }
298         return result;
299     }
300     
301     public static List<Tuple2> groupBy(Function f, List<Tuple2> input) {
302         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
303         ArrayList<Tuple2> result = new ArrayList<Tuple2>();
304         for(Object value : input) {
305             Object key = f.apply(value);
306             ArrayList<Object> list = groupMap.get(key);
307             if(list == null) {
308                 list = new ArrayList<Object>();
309                 groupMap.put(key, list);
310                 result.add(new Tuple2(key, list));
311             }
312             list.add(value);
313         }
314         return result;
315     }
316     
317     private static class GroupMapFunction extends FunctionImpl1<Object, List<Object>> {
318         THashMap<Object, ArrayList<Object>> groupMap;
319         public GroupMapFunction(THashMap<Object, ArrayList<Object>> groupMap) {
320             this.groupMap = groupMap;
321         }
322         @Override
323         public List<Object> apply(Object p0) {
324             List<Object> result = groupMap.get(p0);
325             if(result == null)
326                 return Collections.emptyList();
327             else
328                 return result;
329         }
330     }
331     
332     public static Function indexGroup(List<Tuple2> input) {
333         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
334         for(Tuple2 t : input) {
335             Object key = t.c0;
336             ArrayList<Object> list = groupMap.get(key);
337             if(list == null) {
338                 list = new ArrayList<Object>();
339                 groupMap.put(key, list);
340             }
341             list.add(t.c1);
342         }
343         return new GroupMapFunction(groupMap);
344     }
345     
346     public static Function indexGroupBy(Function f, List<Tuple2> input) {
347         THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
348         for(Object value : input) {
349             Object key = f.apply(value);
350             ArrayList<Object> list = groupMap.get(key);
351             if(list == null) {
352                 list = new ArrayList<Object>();
353                 groupMap.put(key, list);
354             }
355             list.add(value);
356         }
357         return new GroupMapFunction(groupMap);
358     }
359     
360     public static List sortWith(final Function compare, List l) {
361         Object[] result = l.toArray(new Object[l.size()]);
362         Arrays.sort(result, new Comparator() {
363             @Override
364             public int compare(Object o1, Object o2) {
365                 return (Integer)compare.apply(o1, o2);
366             }            
367         });
368         return Arrays.asList(result);
369     }
370     
371     public static List uniqueWith(Function compare, List l) {
372         ArrayList result = new ArrayList(Math.min(10, l.size()));
373         outerLoop:
374         for(int i=0;i<l.size();++i) {
375             Object el = l.get(i);
376             for(int j=0;j<result.size();++j)
377                 if(compare.apply(el, result.get(j)).equals(Boolean.TRUE))
378                     continue outerLoop;
379             result.add(el);
380         }
381         return result;
382     }
383     
384     public static List deleteAllBy(Function compare, List a, List b) {
385         ArrayList result = new ArrayList(Math.min(10, a.size()));
386         outerLoop:
387         for(Object el : a) {
388             for(Object el2 : b)
389                 if(compare.apply(el, el2).equals(Boolean.TRUE))
390                     continue outerLoop;
391             result.add(el);
392         }        
393         return result;
394     }
395     
396     public static List listDifference(List a, List b) {
397         if(a.isEmpty() || b.isEmpty())
398             return a;
399         THashSet setB = new THashSet(b);
400         for(int i=0;i<a.size();++i) {
401             Object el = a.get(i);
402             if(setB.contains(el)) {
403                 ArrayList result = new ArrayList(a.size()-1);
404                 for(int j=0;j<i;++j)
405                     result.add(a.get(j));
406                 for(++i;i<a.size();++i) {
407                     el = a.get(i);
408                     if(!setB.contains(el))
409                         result.add(el);
410                 }
411                 return result;
412             }
413         }
414         return a;
415     }
416     
417     public static List<Object> unique(List<Object> l) {
418         THashSet<Object> set = new THashSet<Object>(l.size());
419         ArrayList<Object> result = new ArrayList<Object>(l.size());
420         for(Object el : l)
421             if(set.add(el))
422                 result.add(el);
423         return result;
424     }
425     
426     public static List<Object> uniqueBy(Function f, List<Object> l) {
427         THashSet<Object> set = new THashSet<Object>(l.size());
428         ArrayList<Object> result = new ArrayList<Object>(l.size());
429         for(Object el : l)
430             if(set.add(f.apply(el)))
431                 result.add(el);
432         return result;
433     }
434 }