From 8c1a41b09c7fbc5760f048ff9d3e5f9b468f8fbd Mon Sep 17 00:00:00 2001 From: =?utf8?q?Hannu=20Niemist=C3=B6?= Date: Thu, 28 Sep 2017 13:21:29 +0300 Subject: [PATCH] Improvement of index and group implementations and indexGroup(By) (refs #7514) Change-Id: I0c3d6a08f17ba7f9028d0a7df515fec8abd04734 --- .../org.simantics.scl.runtime/scl/Prelude.scl | 72 ++++----- .../src/org/simantics/scl/runtime/Lists.java | 141 +++++++++++++++++- .../compiler/tests/ModuleRegressionTests.java | 1 + .../scl/compiler/tests/scl/ListFunctions.scl | 40 +++++ 4 files changed, 216 insertions(+), 38 deletions(-) create mode 100644 tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ListFunctions.scl diff --git a/bundles/org.simantics.scl.runtime/scl/Prelude.scl b/bundles/org.simantics.scl.runtime/scl/Prelude.scl index 907d6e00d..f06acb29f 100644 --- a/bundles/org.simantics.scl.runtime/scl/Prelude.scl +++ b/bundles/org.simantics.scl.runtime/scl/Prelude.scl @@ -1930,14 +1930,51 @@ importJava "org.simantics.scl.runtime.Lists" where "Sorts the list using the given comparator." sortWith :: (a -> a -> Integer) -> [a] -> [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 -> b) -> [a] -> [(b, [a])] + + "Groups a list of key-value pairs by the keys." + group :: [(a,b)] -> [(a, [b])] + + "Composition of index and groupBy." + indexGroupBy :: (a -> b) -> [a] -> (b -> [a]) + + "Composition of index and group." + indexGroup :: [(a,b)] -> a -> [b] + groupWith :: (b -> Integer) -> (b -> b -> Boolean) -> (a -> b) -> (a -> c) -> [a] -> [(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 -> a) -> a) -> [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 -> b) -> [a] -> [(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 /// diff --git a/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java b/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java index a57227635..5259ce631 100644 --- a/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java +++ b/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/Lists.java @@ -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 l) { + THashMap map = new THashMap(l.size()); + for(Tuple2 t : l) + map.put(t.c0, t.c1); + return new FunctionImpl1() { + @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() { + @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 groupWith(final Function hash, final Function eq, Function keyFunction, Function valueFunction, List input) { + public static List groupWith(final Function hash, final Function eq, Function keyFunction, Function valueFunction, List input) { final TCustomHashMap> map = new TCustomHashMap>( new HashingStrategy() { @Override @@ -256,6 +282,81 @@ public class Lists { return result; } + public static List group(List input) { + THashMap> groupMap = new THashMap>(); + ArrayList result = new ArrayList(); + for(Tuple2 t : input) { + Object key = t.c0; + ArrayList list = groupMap.get(key); + if(list == null) { + list = new ArrayList(); + groupMap.put(key, list); + result.add(new Tuple2(key, list)); + } + list.add(t.c1); + } + return result; + } + + public static List groupBy(Function f, List input) { + THashMap> groupMap = new THashMap>(); + ArrayList result = new ArrayList(); + for(Object value : input) { + Object key = f.apply(value); + ArrayList list = groupMap.get(key); + if(list == null) { + list = new ArrayList(); + groupMap.put(key, list); + result.add(new Tuple2(key, list)); + } + list.add(value); + } + return result; + } + + private static class GroupMapFunction extends FunctionImpl1> { + THashMap> groupMap; + public GroupMapFunction(THashMap> groupMap) { + this.groupMap = groupMap; + } + @Override + public List apply(Object p0) { + List result = groupMap.get(p0); + if(result == null) + return Collections.emptyList(); + else + return result; + } + } + + public static Function indexGroup(List input) { + THashMap> groupMap = new THashMap>(); + for(Tuple2 t : input) { + Object key = t.c0; + ArrayList list = groupMap.get(key); + if(list == null) { + list = new ArrayList(); + groupMap.put(key, list); + } + list.add(t.c1); + } + return new GroupMapFunction(groupMap); + } + + public static Function indexGroupBy(Function f, List input) { + THashMap> groupMap = new THashMap>(); + for(Object value : input) { + Object key = f.apply(value); + ArrayList list = groupMap.get(key); + if(list == null) { + list = new ArrayList(); + 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 unique(List l) { - THashSet set = new THashSet(); + THashSet set = new THashSet(l.size()); + ArrayList result = new ArrayList(l.size()); + for(Object el : l) + if(set.add(el)) + result.add(el); + return result; + } + + public static List uniqueBy(Function f, List l) { + THashSet set = new THashSet(l.size()); + ArrayList result = new ArrayList(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; } } diff --git a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java index 95cbcd2e3..7e419f6ab 100644 --- a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java +++ b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java @@ -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 index 000000000..e8423819c --- /dev/null +++ b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ListFunctions.scl @@ -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 -> () +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 -- 2.43.2