]> gerrit.simantics Code Review - simantics/platform.git/commitdiff
Improvement of index and group implementations and indexGroup(By) 50/1050/1
authorHannu Niemistö <hannu.niemisto@semantum.fi>
Thu, 28 Sep 2017 10:21:29 +0000 (13:21 +0300)
committerHannu Niemistö <hannu.niemisto@semantum.fi>
Thu, 28 Sep 2017 10:21:29 +0000 (13:21 +0300)
(refs #7514)

Change-Id: I0c3d6a08f17ba7f9028d0a7df515fec8abd04734

bundles/org.simantics.scl.runtime/scl/Prelude.scl
bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java
tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java
tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ListFunctions.scl [new file with mode: 0644]

index 907d6e00d74084dfc12dddedd205448624ecc2a8..f06acb29fce55e74e98c111364ede07908947df9 100644 (file)
@@ -1930,14 +1930,51 @@ importJava "org.simantics.scl.runtime.Lists" where
     
     "Sorts the list using the given comparator."
     sortWith :: (a -> a -> <e> Integer) -> [a] -> <e> [a]
+    
+    """
+    Given a list of key-value pairs, the function produces a function that finds a value
+    efficiently for the given key.
+    """
+    index :: [(a,b)] -> a -> Maybe b
+    
+    """
+    Given a list of values and a function computing a key for each value, the function produces a function that finds a value
+    effeciently for the given key.
+    """
+    indexBy ::  (a -> b) -> [a] -> b -> Maybe a
+    
     "Works like `index` but uses the given functions as hash codes and equality."
     indexWith :: (a -> Integer) -> (a -> a -> Boolean) -> [(a,b)] -> a -> Maybe b
+    
+    "Groups a list values by a key computed by the given function."
+    groupBy :: (a -> <e> b) -> [a] -> <e> [(b, [a])]
+    
+    "Groups a list of key-value pairs by the keys."
+    group :: [(a,b)] -> [(a, [b])]
+
+    "Composition of index and groupBy."
+    indexGroupBy :: (a -> <e> b) -> [a] -> <e> (b -> [a])
+    
+    "Composition of index and group."
+    indexGroup :: [(a,b)] -> a -> [b]
+    
     groupWith :: (b -> Integer) -> (b -> b -> Boolean) -> (a -> <e> b) -> (a -> <e> c) -> [a] -> <e> [(b, [c])]
+    
+    "Removes duplicates (all but the first occurrence) from the list but otherwise preserves the order of the elements."
+    unique :: [a] -> [a]
+    
+    "Like `unique`, but uses the given function for finding the key values used for uniqueness testing."
+    uniqueBy :: (a -> b) -> [a] -> [a]
+
     "Works like `unique` but uses the given function for equality tests."
     uniqueWith :: (a -> a -> Boolean) -> [a] -> [a]
+    
     "Works like `\\\\` but uses the given function for equality tests."
     deleteAllBy :: (a -> a -> Boolean) -> [a] -> [a] -> [a]
     
+    @private
+    listDifference :: [a] -> [a] -> [a]
+    
     //range :: Integer -> Integer -> [Integer]
     
     //build :: (forall a. a -> (a -> b -> <e> a) -> <e> a) -> <e> [b]
@@ -2062,42 +2099,9 @@ sortBy f l = sortWith (\x y -> compare (f x) (f y)) l
 // This is faster if f is slow, but will generate more auxiliary structures
 //sortBy f l = map snd (sortWith (\(x,_) (y,_) -> compare x y) [(f x, x) | x <- l])
 
-"""
-Given a list of key-value pairs, the function produces a function that finds a value
-efficiently for the given key.
-"""
-index :: [(a,b)] -> a -> Maybe b
-index = indexWith hashCode (==)
-
-"""
-Given a list of values and a function computing a key for each value, the function produces a function that finds a value
-effeciently for the given key.
-"""
-indexBy ::  (a -> b) -> [a] -> b -> Maybe a
-indexBy f l = index [(f x, x) | x <- l]
-
-"Groups a list values by a key computed by the given function."
-groupBy :: (a -> <e> b) -> [a] -> <e> [(b, [a])]
-groupBy f l = groupWith hashCode (==) f id l
-
-"Groups a list of key-value pairs by the keys."
-group :: [(a,b)] -> [(a, [b])]
-group = groupWith hashCode (==) fst snd
-
-"Removes duplicates (all but the first occurrence) from the list but otherwise preserves the order of the elements."
-unique ::  [a] -> [a]
-unique = uniqueWith (==)
-
-"Like `unique`, but uses the given function for finding the key values used for uniqueness testing."
-uniqueBy :: (a -> b) -> [a] -> [a]
-uniqueBy f = uniqueWith (\a b -> f a == f b)
-
-//sortAndUniqueBy :: Ord b => (a -> b) -> [a] -> [a]
-//sortAndUniqueBy f = map snd . uniqueWith (\a b -> fst a == fst b) . sortBy fst . map (\x -> (f x, x))
-
 "`a \\\\ b` removes all elements of `b` from the list `a`."
 (\\) :: [a] -> [a] -> [a]
-(\\) = deleteAllBy (==)
+(\\) = listDifference
 
 /// Dynamic ///
 
index a5722763551855d4d60525066732ba9943420d8c..5259ce6315a38b5b9b1ab64f94ce452cb82930ca 100644 (file)
@@ -2,6 +2,7 @@ package org.simantics.scl.runtime;
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
@@ -12,6 +13,7 @@ import org.simantics.scl.runtime.function.FunctionImpl2;
 import org.simantics.scl.runtime.tuple.Tuple2;
 
 import gnu.trove.map.hash.TCustomHashMap;
+import gnu.trove.map.hash.THashMap;
 import gnu.trove.set.hash.THashSet;
 import gnu.trove.strategy.HashingStrategy;
 
@@ -227,9 +229,33 @@ public class Lists {
         };
     }
     
+    public static Function index(List<Tuple2> l) {
+        THashMap map = new THashMap(l.size());
+        for(Tuple2 t : l)
+            map.put(t.c0, t.c1);
+        return new FunctionImpl1<Object,Object>() {
+            @Override
+            public Object apply(Object p0) {
+                return map.get(p0);
+            }
+        };
+    }
+    
+    public static Function indexBy(Function f, List l) {
+        THashMap map = new THashMap(l.size());
+        for(Object o : l)
+            map.put(f.apply(o), o);
+        return new FunctionImpl1<Object,Object>() {
+            @Override
+            public Object apply(Object p0) {
+                return map.get(p0);
+            }
+        };
+    }
+    
     // groupWith :: (a -> Integer) -> (a -> a -> Boolean) -> (a -> b) -> [a] -> [(b, [a])]
     @SuppressWarnings("serial")
-    public static ArrayList<Tuple2> groupWith(final Function hash, final Function eq, Function keyFunction, Function valueFunction, List<Object> input) {
+    public static List<Tuple2> groupWith(final Function hash, final Function eq, Function keyFunction, Function valueFunction, List<Object> input) {
         final TCustomHashMap<Object,ArrayList<Object>> map = new TCustomHashMap<Object,ArrayList<Object>>(
                 new HashingStrategy<Object>() {
                     @Override
@@ -256,6 +282,81 @@ public class Lists {
         return result;
     }
     
+    public static List<Tuple2> group(List<Tuple2> input) {
+        THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
+        ArrayList<Tuple2> result = new ArrayList<Tuple2>();
+        for(Tuple2 t : input) {
+            Object key = t.c0;
+            ArrayList<Object> list = groupMap.get(key);
+            if(list == null) {
+                list = new ArrayList<Object>();
+                groupMap.put(key, list);
+                result.add(new Tuple2(key, list));
+            }
+            list.add(t.c1);
+        }
+        return result;
+    }
+    
+    public static List<Tuple2> groupBy(Function f, List<Tuple2> input) {
+        THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
+        ArrayList<Tuple2> result = new ArrayList<Tuple2>();
+        for(Object value : input) {
+            Object key = f.apply(value);
+            ArrayList<Object> list = groupMap.get(key);
+            if(list == null) {
+                list = new ArrayList<Object>();
+                groupMap.put(key, list);
+                result.add(new Tuple2(key, list));
+            }
+            list.add(value);
+        }
+        return result;
+    }
+    
+    private static class GroupMapFunction extends FunctionImpl1<Object, List<Object>> {
+        THashMap<Object, ArrayList<Object>> groupMap;
+        public GroupMapFunction(THashMap<Object, ArrayList<Object>> groupMap) {
+            this.groupMap = groupMap;
+        }
+        @Override
+        public List<Object> apply(Object p0) {
+            List<Object> result = groupMap.get(p0);
+            if(result == null)
+                return Collections.emptyList();
+            else
+                return result;
+        }
+    }
+    
+    public static Function indexGroup(List<Tuple2> input) {
+        THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
+        for(Tuple2 t : input) {
+            Object key = t.c0;
+            ArrayList<Object> list = groupMap.get(key);
+            if(list == null) {
+                list = new ArrayList<Object>();
+                groupMap.put(key, list);
+            }
+            list.add(t.c1);
+        }
+        return new GroupMapFunction(groupMap);
+    }
+    
+    public static Function indexGroupBy(Function f, List<Tuple2> input) {
+        THashMap<Object, ArrayList<Object>> groupMap = new THashMap<Object, ArrayList<Object>>();
+        for(Object value : input) {
+            Object key = f.apply(value);
+            ArrayList<Object> list = groupMap.get(key);
+            if(list == null) {
+                list = new ArrayList<Object>();
+                groupMap.put(key, list);
+            }
+            list.add(value);
+        }
+        return new GroupMapFunction(groupMap);
+    }
+    
     public static List sortWith(final Function compare, List l) {
         Object[] result = l.toArray(new Object[l.size()]);
         Arrays.sort(result, new Comparator() {
@@ -292,10 +393,42 @@ public class Lists {
         return result;
     }
     
+    public static List listDifference(List a, List b) {
+        if(a.isEmpty() || b.isEmpty())
+            return a;
+        THashSet setB = new THashSet(b);
+        for(int i=0;i<a.size();++i) {
+            Object el = a.get(i);
+            if(setB.contains(el)) {
+                ArrayList result = new ArrayList(a.size()-1);
+                for(int j=0;j<i;++j)
+                    result.add(a.get(j));
+                for(++i;i<a.size();++i) {
+                    el = a.get(i);
+                    if(!setB.contains(el))
+                        result.add(el);
+                }
+                return result;
+            }
+        }
+        return a;
+    }
+    
     public static List<Object> unique(List<Object> l) {
-        THashSet<Object> set = new THashSet<Object>();
+        THashSet<Object> set = new THashSet<Object>(l.size());
+        ArrayList<Object> result = new ArrayList<Object>(l.size());
+        for(Object el : l)
+            if(set.add(el))
+                result.add(el);
+        return result;
+    }
+    
+    public static List<Object> uniqueBy(Function f, List<Object> l) {
+        THashSet<Object> set = new THashSet<Object>(l.size());
+        ArrayList<Object> result = new ArrayList<Object>(l.size());
         for(Object el : l)
-            set.add(el);
-        return Arrays.asList(set.toArray(new Object[set.size()]));
+            if(set.add(f.apply(el)))
+                result.add(el);
+        return result;
     }
 }
index 95cbcd2e37d073d1c3df2ded862493fad3fa8fd3..7e419f6abb2e4d25d526913a17a5b54f62b3d63a 100644 (file)
@@ -136,6 +136,7 @@ public class ModuleRegressionTests extends TestBase {
     @Test public void List() { test(); }
     @Test public void ListError1() { test(); }    
     @Test public void ListError2() { test(); }
+    @Test public void ListFunctions() { test(); }
     @Test public void ListSyntax() { test(); }
     @Test public void ListSyntax10() { test(); }
     @Test public void ListSyntax11() { test(); }
diff --git a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ListFunctions.scl b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ListFunctions.scl
new file mode 100644 (file)
index 0000000..e842381
--- /dev/null
@@ -0,0 +1,40 @@
+import "Prelude"
+main = do
+    print $ [1,2] \\ []
+    print $ [1,2,3] \\ [1]
+    print $ [1,2,3] \\ [2]
+    print $ [1,2,3] \\ [2,3]
+--
+[1, 2]
+[2, 3]
+[1, 3]
+[1]
+()    
+--
+import "Prelude"
+
+assertEquals :: Show a => a -> a -> <Proc> ()
+assertEquals a b = if a == b then () else fail "\(a) <> \(b)"
+
+testGrouping outVal f l = do
+    kl = map (\v -> (f v, v)) l
+    groups = group kl
+    print groups
+    
+    assertEquals groups (groupBy f l)
+    
+    i1 = fromMaybe [] . index groups
+    i2 = indexGroup kl
+    i3 = indexGroupBy f l
+    
+    keys = map fst groups + [outVal]
+    
+    for keys $ \k -> do 
+        assertEquals (i1 k) (i2 k)
+        assertEquals (i1 k) (i3 k)
+
+main = do
+    testGrouping 4 (`mod` 3) [2,4,6,8,10]
+--
+[(2, [2, 8]), (1, [4, 10]), (0, [6])]
+()
\ No newline at end of file