X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Felaboration%2Fconstraints%2FInstanceTree.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Felaboration%2Fconstraints%2FInstanceTree.java;h=3b0447394503f142c8c054b339a0480163d2047d;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java
new file mode 100644
index 000000000..3b0447394
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java
@@ -0,0 +1,124 @@
+package org.simantics.scl.compiler.internal.elaboration.constraints;
+
+import gnu.trove.map.hash.THashMap;
+import gnu.trove.procedure.TObjectObjectProcedure;
+
+import java.util.ArrayList;
+
+import org.simantics.scl.compiler.types.TApply;
+import org.simantics.scl.compiler.types.TCon;
+import org.simantics.scl.compiler.types.Type;
+import org.simantics.scl.compiler.types.Types;
+import org.simantics.scl.compiler.types.util.MultiApply;
+
+public class InstanceTree<T> {
+
+    Node<T> root;
+    
+    private static interface Node<T> {
+        T get(ArrayList<Type> types);        
+    }
+    
+    private static class SplitNode<T> implements Node<T> {
+        int pId;
+        THashMap<TCon, Node<T>> map;
+        Node<T> alternative;
+        
+        public SplitNode(int pId, THashMap<TCon, Node<T>> map, Node<T> alternative) {
+            this.pId = pId;
+            this.map = map;
+            this.alternative = alternative;
+        }
+
+        @Override
+        public T get(ArrayList<Type> types) {
+            MultiApply apply = Types.matchApply(types.get(pId));
+            Node<T> node = map.get(apply.constructor);
+            if(node == null)
+                return null;
+            for(Type parameter : apply.parameters)
+                types.add(parameter);
+            return node.get(types);
+        }
+    }
+    
+    private static class Entry<T> {
+        Type[] types;
+        T value;
+    }
+    
+    private static boolean isIndexable(Type type) {
+        type = Types.canonical(type);
+        while(true) {
+            if(type instanceof TCon)
+                return true;
+            else if(type instanceof TApply)
+                type = Types.canonical(((TApply)type).function);
+            else
+                return false;
+        }
+    }
+    
+    private static <T> int choosePId(ArrayList<Entry<T>> entries) {
+        int arity = entries.get(0).types.length;
+        if(arity == 1)
+            return 0;
+        int[] indexableCount = new int[arity];
+        for(Entry<T> entry : entries)
+            for(int i=0;i<arity;++i)
+                if(isIndexable(entry.types[i]))
+                    ++indexableCount[i];
+        int bestIndexableCount = indexableCount[0];
+        int bestPId = 0;
+        for(int i=1;i<arity;++i)
+            if(indexableCount[i] > bestIndexableCount) {
+                bestIndexableCount = indexableCount[i];
+                bestPId = i;
+            }
+        return bestPId;
+    }
+        
+    private static <T> Node<T> create(ArrayList<Entry<T>> entries) {
+        int pId = choosePId(entries);
+        THashMap<TCon, ArrayList<Entry<T>>> map1 = new THashMap<TCon, ArrayList<Entry<T>>>();
+        ArrayList<Entry<T>> otherEntries = new ArrayList<Entry<T>>(); 
+        for(Entry<T> entry : entries) {
+            Type[] types = entry.types;
+            Type type = types[pId];
+            MultiApply apply = Types.matchApply(type);
+            if(apply.constructor instanceof TCon) {
+                ArrayList<Entry<T>> l = map1.get((TCon)apply.constructor);
+                if(l == null) {
+                    l = new ArrayList<Entry<T>>();
+                    map1.put((TCon)apply.constructor, l);
+                }
+                Type[] newTypes = new Type[types.length-1+apply.parameters.length];
+                int j=0;
+                for(int i=0;i<pId;++i)
+                    newTypes[j++] = types[i];
+                for(int i=0;i<apply.parameters.length;++i)
+                    newTypes[j++] = apply.parameters[i];
+                for(int i=pId+1;i<types.length;++i)
+                    newTypes[j++] = types[i];
+                entry.types = newTypes;
+                l.add(entry);
+            }
+            else {
+                otherEntries.add(entry);
+            }
+        }
+        final THashMap<TCon, Node<T>> map = new THashMap<TCon, Node<T>>();
+        map1.forEachEntry(new TObjectObjectProcedure<TCon, ArrayList<Entry<T>>>() {
+            @Override
+            public boolean execute(TCon a, ArrayList<Entry<T>> b) {
+                map.put(a, create(b));
+                return true;
+            }
+        });
+        return new SplitNode<T>(pId, map, create(otherEntries));
+    }
+    
+    public T get(ArrayList<Type> types) {
+        return root.get(types);
+    }
+}