Merge commit '53059ca'
authorTuukka Lehtonen <tuukka.lehtonen@semantum.fi>
Thu, 3 Nov 2016 20:33:39 +0000 (22:33 +0200)
committerTuukka Lehtonen <tuukka.lehtonen@semantum.fi>
Thu, 3 Nov 2016 20:33:39 +0000 (22:33 +0200)
Conflicts:
bundles/org.simantics.scl.runtime/scl/Prelude.scl

refs #6726
refs #6788
refs #6791

bundles/org.simantics.scl.runtime/scl/Prelude.scl
bundles/org.simantics.tests.modelled/META-INF/MANIFEST.MF
bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSRunner.java [new file with mode: 0644]
bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSSuiteRunner.java [new file with mode: 0644]
bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSTestRunner.java [new file with mode: 0644]
bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeTestCollector.java [new file with mode: 0644]
bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMap.java
bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMapEntry.java [new file with mode: 0644]
bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/InterlacedArrayMap.java [new file with mode: 0644]

index 6966b4489d0652c61b8cde57fc7d185b75a2dd08..21658862db66f34262c1852603872ff5f25291ef 100644 (file)
@@ -1879,6 +1879,17 @@ maybeToList :: Maybe a -> [a]
 maybeToList (Just a) = [a]
 maybeToList _ = [] 
 
+"""
+`takeWhile p l`, returns the longest prefix (possibly empty) of list `l` of elements that satisfy `p`
+"""
+takeWhile :: (a -> <e> Boolean) -> [a] -> <e> [a]
+takeWhile f l = loop 0 
+  where
+    len = length l
+    loop i | i == len  = l
+           | f (l!i)   = loop (i+1)
+           | otherwise = take i l
+
 partition :: (a -> <e> Boolean) -> [a] -> <e> ([a], [a])
 partition p l = runProc do
     res1 = newArrayList
index 662bca7b714a8f7adc18b63c1bcd09aff19c4b56..bce9a42cfbe87b1921e65ff79f1f64117a309b46 100644 (file)
@@ -10,7 +10,11 @@ Require-Bundle: org.eclipse.core.runtime,
  org.simantics.tests.modelled.ontology,
  org.simantics.scl.osgi,
  org.simantics,
- org.simantics.scl.compiler
+ org.simantics.scl.compiler,
+ org.junit,
+ org.simantics.db.testing,
+ org.simantics.modeling;bundle-version="1.1.1"
 Bundle-RequiredExecutionEnvironment: JavaSE-1.8
 Bundle-ActivationPolicy: lazy
-Export-Package: org.simantics.tests.modelled
+Export-Package: org.simantics.tests.modelled,
+ org.simantics.tests.modelled.junit
diff --git a/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSRunner.java b/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSRunner.java
new file mode 100644 (file)
index 0000000..6f9bda0
--- /dev/null
@@ -0,0 +1,57 @@
+package org.simantics.tests.modelled.junit;\r
+\r
+import java.util.List;\r
+\r
+import org.junit.runner.Description;\r
+import org.junit.runner.Result;\r
+import org.junit.runner.Runner;\r
+import org.junit.runner.notification.Failure;\r
+import org.junit.runner.notification.RunListener;\r
+import org.junit.runner.notification.RunNotifier;\r
+import org.junit.runners.ParentRunner;\r
+\r
+public abstract class RuntimeSTSRunner extends ParentRunner<Runner> {\r
+\r
+    public RuntimeSTSRunner(Class<?> testClass) throws Exception {\r
+        super(testClass);\r
+    }\r
+\r
+    public abstract void initialize() throws Exception;\r
+\r
+    public abstract void deinitialize() throws Exception;\r
+\r
+    @Override\r
+    protected List<Runner> getChildren() {\r
+        System.out.println("getting children");\r
+        return RuntimeTestCollector.collectTests();\r
+    }\r
+\r
+    @Override\r
+    protected Description describeChild(Runner child) {\r
+        return child.getDescription();\r
+    }\r
+\r
+    @Override\r
+    public void run(RunNotifier notifier) {\r
+        notifier.addListener(new RunListener() {\r
+\r
+            @Override\r
+            public void testRunFinished(Result result) throws Exception {\r
+                deinitialize();\r
+            }\r
+        });\r
+        super.run(notifier);\r
+    }\r
+\r
+    @Override\r
+    protected void runChild(Runner child, RunNotifier notifier) {\r
+        Description desc = describeChild(child);\r
+        notifier.fireTestStarted(desc);\r
+        try {\r
+            child.run(notifier);\r
+            notifier.fireTestFinished(desc);\r
+        } catch (Throwable e) {\r
+            notifier.fireTestFailure(new Failure(desc, e));\r
+        }\r
+    }\r
+}\r
diff --git a/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSSuiteRunner.java b/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSSuiteRunner.java
new file mode 100644 (file)
index 0000000..7032531
--- /dev/null
@@ -0,0 +1,54 @@
+package org.simantics.tests.modelled.junit;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.List;\r
+\r
+import org.junit.runner.Description;\r
+import org.junit.runner.Runner;\r
+import org.simantics.scl.compiler.commands.CommandSession;\r
+import org.simantics.scl.osgi.SCLOsgi;\r
+\r
+public class RuntimeSTSSuiteRunner extends RuntimeSTSRunner {\r
+\r
+    private final List<RuntimeSTSTestRunner> children = new ArrayList<>();\r
+    private final String suiteName;\r
+\r
+    RuntimeSTSSuiteRunner(String suiteName) throws Exception {\r
+        super(RuntimeSTSSuiteRunner.class);\r
+        this.suiteName = suiteName;\r
+    }\r
+    \r
+    @Override\r
+    protected String getName() {\r
+        return suiteName;\r
+    }\r
+\r
+    @Override\r
+    public Description getDescription() {\r
+        Description description = Description.createSuiteDescription(getName(), getRunnerAnnotations());\r
+        getChildren().forEach(child -> description.addChild(describeChild(child)));\r
+        return description;\r
+    }\r
+\r
+    public void addChildren(Collection<RuntimeSTSTestRunner> testChildren) {\r
+        CommandSession session = new CommandSession(SCLOsgi.MODULE_REPOSITORY, null);\r
+        testChildren.forEach(c -> c.setCommandSession(session));\r
+        children.addAll(testChildren);\r
+    }\r
+    \r
+    @SuppressWarnings({ "unchecked", "rawtypes" })\r
+    @Override\r
+    protected List<Runner> getChildren() {\r
+        return (List) children;\r
+    }\r
+\r
+    @Override\r
+    public void initialize() {\r
+    }\r
+\r
+    @Override\r
+    public void deinitialize() {\r
+    }\r
+\r
+}\r
diff --git a/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSTestRunner.java b/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeSTSTestRunner.java
new file mode 100644 (file)
index 0000000..a80b84e
--- /dev/null
@@ -0,0 +1,69 @@
+package org.simantics.tests.modelled.junit;\r
+\r
+import java.io.BufferedReader;\r
+import java.io.IOException;\r
+import java.io.StringReader;\r
+\r
+import org.junit.runner.Description;\r
+import org.junit.runner.Runner;\r
+import org.junit.runner.notification.RunNotifier;\r
+import org.simantics.scl.compiler.commands.CommandSession;\r
+import org.simantics.scl.compiler.commands.TestScriptExecutor;\r
+import org.simantics.scl.osgi.SCLOsgi;\r
+import org.simantics.scl.runtime.SCLContext;\r
+import org.simantics.scl.runtime.reporting.SCLReportingHandler;\r
+\r
+public class RuntimeSTSTestRunner extends Runner {\r
+    \r
+    private final String name;\r
+    private final String code;\r
+    private final Integer priority;\r
+    private CommandSession session;\r
+\r
+    public RuntimeSTSTestRunner(String name, String code, Integer priority) {\r
+        this.name = name;\r
+        this.code = code;\r
+        this.priority = priority;\r
+    }\r
+    \r
+    public void setCommandSession(CommandSession session) {\r
+        this.session = session;\r
+    }\r
+\r
+    @Override\r
+    public Description getDescription() {\r
+        return Description.createTestDescription(RuntimeSTSTestRunner.class, name);\r
+    }\r
+\r
+    @Override\r
+    public void run(RunNotifier notifier) {\r
+        StringReader reade = new StringReader(code);\r
+        BufferedReader reader = new BufferedReader(reade);\r
+        \r
+        SCLContext context = SCLContext.getCurrent();\r
+        SCLReportingHandler printer = (SCLReportingHandler)context.get(SCLReportingHandler.REPORTING_HANDLER);\r
+        SCLReportingHandler handler;\r
+        if(printer instanceof SCLReportingHandler)\r
+            handler = (SCLReportingHandler)printer;\r
+        else\r
+            handler = SCLReportingHandler.DEFAULT;\r
+        \r
+        try {\r
+            if (session == null)\r
+                session = new CommandSession(SCLOsgi.MODULE_REPOSITORY, handler);\r
+            new TestScriptExecutor(session, reader, handler).execute();\r
+        } catch (IOException e) {\r
+            throw new RuntimeException(e);\r
+        } finally {\r
+            try {\r
+                reader.close();\r
+            } catch (IOException e) {\r
+                // Ignore\r
+            }\r
+        }\r
+    }\r
+\r
+    public Integer getPriority() {\r
+        return priority;\r
+    }\r
+}\r
diff --git a/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeTestCollector.java b/bundles/org.simantics.tests.modelled/src/org/simantics/tests/modelled/junit/RuntimeTestCollector.java
new file mode 100644 (file)
index 0000000..81d1ef7
--- /dev/null
@@ -0,0 +1,89 @@
+package org.simantics.tests.modelled.junit;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.Collections;\r
+import java.util.HashSet;\r
+import java.util.List;\r
+import java.util.Set;\r
+\r
+import org.junit.runner.Runner;\r
+import org.simantics.Simantics;\r
+import org.simantics.databoard.Bindings;\r
+import org.simantics.db.ReadGraph;\r
+import org.simantics.db.Resource;\r
+import org.simantics.db.common.request.ObjectsWithType;\r
+import org.simantics.db.common.request.UniqueRead;\r
+import org.simantics.db.exception.DatabaseException;\r
+import org.simantics.layer0.Layer0;\r
+import org.simantics.modeling.ModelingUtils;\r
+import org.simantics.scl.runtime.tuple.Tuple0;\r
+import org.simantics.tests.modelled.ontology.TestsResource;\r
+\r
+public class RuntimeTestCollector {\r
+\r
+    \r
+    /**\r
+     * TODO: The idea of this class was to collect all the tests from shared libraries and construct\r
+     * JUnit tests out of them programmatically and then run them with JUnit to get results\r
+     * \r
+     */\r
+    private static Collection<RuntimeSTSSuiteRunner> collectTestsFromGraph() {\r
+        try {\r
+            Collection<RuntimeSTSSuiteRunner> suitess = Simantics.getSession().syncRequest(new UniqueRead<Collection<RuntimeSTSSuiteRunner>>() {\r
+\r
+                @Override\r
+                public Collection<RuntimeSTSSuiteRunner> perform(ReadGraph graph) throws DatabaseException {\r
+                    \r
+                    List<Resource> sharedOntologies = Simantics.applySCL("Simantics/SharedOntologies", "getSharedOntologies", graph, Tuple0.INSTANCE);\r
+\r
+                    Set<RuntimeSTSSuiteRunner> suites = new HashSet<>();\r
+                    TestsResource TESTS = TestsResource.getInstance(graph);\r
+                    Layer0 L0 = Layer0.getInstance(graph);\r
+                    for (Resource sharedOntology : sharedOntologies) {\r
+                        List<Resource> stsSuites = ModelingUtils.searchByType(graph, sharedOntology, TESTS.STSSuite);\r
+                        for (Resource stsSuite : stsSuites) {\r
+                            try {\r
+                                String suiteName = graph.getURI(stsSuite);\r
+    \r
+                                Collection<Resource> tests = graph.syncRequest(new ObjectsWithType(stsSuite, L0.ConsistsOf, TESTS.STSTest));\r
+                                if (tests.isEmpty())\r
+                                    continue;\r
+    \r
+                                RuntimeSTSSuiteRunner suite = new RuntimeSTSSuiteRunner(suiteName);\r
+                                List<RuntimeSTSTestRunner> testRunners = new ArrayList<>();\r
+                                for (Resource test : tests) {\r
+                                    String testName = graph.getRelatedValue(test, L0.HasName, Bindings.STRING);\r
+                                    String code = graph.getRelatedValue(test, TESTS.STSTest_definition, Bindings.STRING);\r
+                                    Integer priority = graph.getPossibleRelatedValue(test, TESTS.STSTest_executionPriority, Bindings.INTEGER);\r
+                                    RuntimeSTSTestRunner testCase = new RuntimeSTSTestRunner(testName, code, priority);\r
+                                    testRunners.add(testCase);\r
+                                }\r
+                                \r
+                                testRunners.sort((test1, test2) -> {\r
+                                    if (test1.getPriority() <= test2.getPriority())\r
+                                        return -1;\r
+                                    else\r
+                                        return 1;\r
+                                });\r
+                                suite.addChildren(testRunners);\r
+                                suites.add(suite);\r
+                            } catch (Exception e) {\r
+                                e.printStackTrace();\r
+                            }\r
+                        }\r
+                    }\r
+                    return suites;\r
+                }\r
+            });\r
+            return suitess;\r
+        } catch (DatabaseException e) {\r
+            e.printStackTrace();\r
+            return Collections.emptyList();\r
+        }\r
+    }\r
+\r
+    public static List<Runner> collectTests() {\r
+        return new ArrayList<>(collectTestsFromGraph());\r
+    }\r
+}\r
index 7115f29d51bb82db3883a5108d2a7eb973626433..b9b5415d85ba3b1a779189151ad9b51cf5470fae 100644 (file)
@@ -39,8 +39,8 @@ import java.util.Set;
  */\r
 public class ArrayMap<K, V> implements Map<K, V> {\r
 \r
-    K[] keys;\r
-    V[] values;\r
+    final K[] keys;\r
+    final V[] values;\r
     Set<Map.Entry<K, V>> entrySet;\r
     Set<K> keySet;\r
     Collection<V> valueSet;\r
@@ -292,7 +292,7 @@ public class ArrayMap<K, V> implements Map<K, V> {
                 public Map.Entry<K, V> next() {\r
                     if (i >= keys.length)\r
                         throw new NoSuchElementException("no more elements (" + keys.length + " walked)");\r
-                    Map.Entry<K, V> entry = new Entry<K, V>(i, keys[i], values[i]);\r
+                    Map.Entry<K, V> entry = new ArrayMapEntry<K, V>(i, keys[i], values[i]);\r
                     ++i;\r
                     return entry;\r
                 }\r
@@ -306,63 +306,6 @@ public class ArrayMap<K, V> implements Map<K, V> {
 \r
     }\r
 \r
-    static class Entry<K, V> implements Map.Entry<K, V> {\r
-        final K key;\r
-        V value;\r
-\r
-        /**\r
-         * Creates new entry.\r
-         */\r
-        Entry(int h, K k, V v) {\r
-            value = v;\r
-            key = k;\r
-        }\r
-\r
-        @Override\r
-        public final K getKey() {\r
-            return key;\r
-        }\r
-\r
-        @Override\r
-        public final V getValue() {\r
-            return value;\r
-        }\r
-\r
-        @Override\r
-        public final V setValue(V newValue) {\r
-            V oldValue = value;\r
-            value = newValue;\r
-            return oldValue;\r
-        }\r
-\r
-        @Override\r
-        public final boolean equals(Object o) {\r
-            if (!(o instanceof Map.Entry<?, ?>))\r
-                return false;\r
-            Map.Entry<?, ?> e = (Map.Entry<?, ?>)o;\r
-            Object k1 = getKey();\r
-            Object k2 = e.getKey();\r
-            if (k1 == k2 || (k1 != null && k1.equals(k2))) {\r
-                Object v1 = getValue();\r
-                Object v2 = e.getValue();\r
-                if (v1 == v2 || (v1 != null && v1.equals(v2)))\r
-                    return true;\r
-            }\r
-            return false;\r
-        }\r
-\r
-        @Override\r
-        public final int hashCode() {\r
-            return (key==null   ? 0 : key.hashCode()) ^\r
-            (value==null ? 0 : value.hashCode());\r
-        }\r
-\r
-        @Override\r
-        public final String toString() {\r
-            return getKey() + "=" + getValue();\r
-        }\r
-    }\r
-\r
     /**\r
      * Returns the hash code value for this map.  The hash code of a map is\r
      * defined to be the sum of the hash codes of each entry in the map's\r
diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMapEntry.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMapEntry.java
new file mode 100644 (file)
index 0000000..4a7fd2e
--- /dev/null
@@ -0,0 +1,80 @@
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2016 Association for Decentralized Information Management\r
+ * in Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ *     Semantum Oy - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.utils.datastructures;\r
+\r
+import java.util.Map;\r
+\r
+/**\r
+ * A common {@link Entry} implementation for both {@link ArrayMap}\r
+ * and {@link InterlacedArrayMap}.\r
+ * \r
+ * @author Tuukka Lehtonen\r
+ *\r
+ * @param <K> key class\r
+ * @param <V> value class\r
+ */\r
+class ArrayMapEntry<K, V> implements Map.Entry<K, V> {\r
+    final K key;\r
+    V value;\r
+\r
+    /**\r
+     * Creates new entry.\r
+     */\r
+    ArrayMapEntry(int h, K k, V v) {\r
+        value = v;\r
+        key = k;\r
+    }\r
+\r
+    @Override\r
+    public final K getKey() {\r
+        return key;\r
+    }\r
+\r
+    @Override\r
+    public final V getValue() {\r
+        return value;\r
+    }\r
+\r
+    @Override\r
+    public final V setValue(V newValue) {\r
+        V oldValue = value;\r
+        value = newValue;\r
+        return oldValue;\r
+    }\r
+\r
+    @Override\r
+    public final boolean equals(Object o) {\r
+        if (!(o instanceof Map.Entry<?, ?>))\r
+            return false;\r
+        Map.Entry<?, ?> e = (Map.Entry<?, ?>)o;\r
+        Object k1 = getKey();\r
+        Object k2 = e.getKey();\r
+        if (k1 == k2 || (k1 != null && k1.equals(k2))) {\r
+            Object v1 = getValue();\r
+            Object v2 = e.getValue();\r
+            if (v1 == v2 || (v1 != null && v1.equals(v2)))\r
+                return true;\r
+        }\r
+        return false;\r
+    }\r
+\r
+    @Override\r
+    public final int hashCode() {\r
+        return (key==null   ? 0 : key.hashCode()) ^\r
+        (value==null ? 0 : value.hashCode());\r
+    }\r
+\r
+    @Override\r
+    public final String toString() {\r
+        return getKey() + "=" + getValue();\r
+    }\r
+}
\ No newline at end of file
diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/InterlacedArrayMap.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/InterlacedArrayMap.java
new file mode 100644 (file)
index 0000000..6ea16dd
--- /dev/null
@@ -0,0 +1,538 @@
+/*******************************************************************************\r
+ * Copyright (c) 2016 Association for Decentralized Information Management\r
+ * in Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ *     Semantum Oy - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.utils.datastructures;\r
+\r
+import java.lang.reflect.Array;\r
+import java.util.Arrays;\r
+import java.util.Collection;\r
+import java.util.Iterator;\r
+import java.util.List;\r
+import java.util.Map;\r
+import java.util.NoSuchElementException;\r
+import java.util.Set;\r
+\r
+/**\r
+ * A space-optimized immutable Map implementation where keys and values are\r
+ * interlaced in one Object array.\r
+ * \r
+ * <p>\r
+ * Both map keys and values are specified as separate typed arrays that must be\r
+ * equally sized. This provides for space-optimization by allowing reusable key\r
+ * array instances since the keys cannot be modified.\r
+ * \r
+ * <p>\r
+ * The map should be considered immutable, but it does allow modification of a\r
+ * value for an existing key as this only changes the value, the key will remain\r
+ * untouched.\r
+ * \r
+ * The nested class {@link InterlacedArrayMapBuilder} allows easy and\r
+ * minimal-allocation construction of an {@link InterlacedArrayMap}. Use\r
+ * {@link InterlacedArrayMap#builder()} or\r
+ * {@link InterlacedArrayMap#builder(int)} to create the builder. The idea is to\r
+ * minimize the space allocated for the {@link #data} field in the built map\r
+ * instance. If the builder is completely filled up, i.e. its capacity matches\r
+ * added key, value pair count, the array it contains is directly transferred to\r
+ * the built map instance without creating any extra copies. So if possible, set\r
+ * the correct initial capacity for the builder.\r
+ * \r
+ * @author Tuukka Lehtonen\r
+ * \r
+ * @param <K>\r
+ *            key class\r
+ * @param <V>\r
+ *            value class\r
+ */\r
+public class InterlacedArrayMap<K, V> implements Map<K, V> {\r
+\r
+    final Object[] data;\r
+    Set<Map.Entry<K, V>> entrySet;\r
+    Set<K> keySet;\r
+    Collection<V> valueSet;\r
+\r
+    public static class InterlacedArrayMapBuilder<K, V> {\r
+\r
+        private Object[] elementData;\r
+        private int count = 0;\r
+\r
+        private InterlacedArrayMapBuilder(int initialCapacity) {\r
+            this.elementData = new Object[initialCapacity*2];\r
+        }\r
+\r
+        public void add(K key, V v) {\r
+            ensureCapacityInternal(count + 2);\r
+            elementData[count] = key;\r
+            elementData[count+1] = v;\r
+            count += 2;\r
+        }\r
+\r
+        private void ensureCapacityInternal(int minCapacity) {\r
+            // overflow-conscious code\r
+            if (minCapacity - elementData.length > 0)\r
+                grow(minCapacity);\r
+        }\r
+\r
+        /**\r
+         * The maximum size of array to allocate.\r
+         * Some VMs reserve some header words in an array.\r
+         * Attempts to allocate larger arrays may result in\r
+         * OutOfMemoryError: Requested array size exceeds VM limit\r
+         */\r
+        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;\r
+\r
+        /**\r
+         * Increases the capacity to ensure that it can hold at least the\r
+         * number of elements specified by the minimum capacity argument.\r
+         *\r
+         * @param minCapacity the desired minimum capacity\r
+         */\r
+        private void grow(int minCapacity) {\r
+            // overflow-conscious code\r
+            int oldCapacity = elementData.length;\r
+            int newCapacity = oldCapacity + (oldCapacity >> 1);\r
+            if (newCapacity - minCapacity < 0)\r
+                newCapacity = minCapacity;\r
+            if (newCapacity - MAX_ARRAY_SIZE > 0)\r
+                newCapacity = hugeCapacity(minCapacity);\r
+            // minCapacity is usually close to size, so this is a win:\r
+            elementData = Arrays.copyOf(elementData, newCapacity);\r
+        }\r
+\r
+        private static int hugeCapacity(int minCapacity) {\r
+            if (minCapacity < 0) // overflow\r
+                throw new OutOfMemoryError();\r
+            return (minCapacity > MAX_ARRAY_SIZE) ?\r
+                Integer.MAX_VALUE :\r
+                MAX_ARRAY_SIZE;\r
+        }\r
+\r
+        public InterlacedArrayMap<K, V> build() {\r
+            return count == elementData.length\r
+                    ? new InterlacedArrayMap<>(elementData)\r
+                    : new InterlacedArrayMap<>(Arrays.copyOf(elementData, count));\r
+        }\r
+\r
+    }\r
+\r
+    /**\r
+     * Default initial capacity.\r
+     */\r
+    private static final int DEFAULT_CAPACITY = 10;\r
+\r
+    /**\r
+     * @return a map builder with the default initial capacity of\r
+     *         {@value #DEFAULT_CAPACITY} key,value pairs.\r
+     */\r
+    public static <K, V> InterlacedArrayMapBuilder<K, V> builder() {\r
+        return new InterlacedArrayMapBuilder<K, V>(DEFAULT_CAPACITY);\r
+    }\r
+\r
+    /**\r
+     * @param initialCapacity\r
+     *            the amount of key,value pairs to fit into the builder\r
+     *            initially without having to reallocate anything\r
+     * @return a map builder with the specified initial key,value pair capacity\r
+     */\r
+    public static <K, V> InterlacedArrayMapBuilder<K, V> builder(int initialCapacity) {\r
+        return new InterlacedArrayMapBuilder<K, V>(initialCapacity);\r
+    }\r
+\r
+    /**\r
+     * Just like {@link #InterlacedArrayMap(Object[])} but takes the array of\r
+     * objects as a collection.\r
+     * \r
+     * @param keysAndValues\r
+     *            an interlaced array where where (key, value) pairs are\r
+     *            repeated in consecutive indexes of the array\r
+     * @throws IllegalArgumentException\r
+     *             if the array size is not divisible by two\r
+     * @throws NullPointerException\r
+     *             if either parameter is <code>null</code>\r
+     */\r
+    public InterlacedArrayMap(List<?> keysAndValues) {\r
+        this(keysAndValues.toArray());\r
+    }\r
+\r
+    /**\r
+     * Constructs new ArrayMap based on an interlaced array of keys and values.\r
+     * The array size must be divisible by two.\r
+     * \r
+     * @param keysAndValues\r
+     *            an interlaced array where where (key, value) pairs are\r
+     *            repeated in consecutive indexes of the array\r
+     * @throws IllegalArgumentException\r
+     *             if the array size is not divisible by two\r
+     * @throws NullPointerException\r
+     *             if either parameter is <code>null</code>\r
+     */\r
+    public InterlacedArrayMap(Object[] keysAndValues) {\r
+        // NPE is caught by this.\r
+        if ((keysAndValues.length & 1) != 0)\r
+            throw new IllegalArgumentException("key and value array size (" + keysAndValues.length + ") is not divisible by 2");\r
+        this.data = keysAndValues;\r
+    }\r
+\r
+    @Override\r
+    public Set<Map.Entry<K, V>> entrySet() {\r
+        return (entrySet != null) ? entrySet : (entrySet = new EntrySet());\r
+    }\r
+\r
+    @Override\r
+    public void clear() {\r
+        throw new UnsupportedOperationException();\r
+    }\r
+\r
+    @Override\r
+    public boolean containsKey(Object key) {\r
+        return contains(0, key);\r
+    }\r
+\r
+    @Override\r
+    public boolean containsValue(Object value) {\r
+        return contains(1, value);\r
+    }\r
+\r
+    @SuppressWarnings("unchecked")\r
+    @Override\r
+    public V get(Object key) {\r
+        if (key == null) {\r
+            for (int i = 0; i < data.length; i += 2) {\r
+                if (data[i] == null) {\r
+                    return (V) data[i+1];\r
+                }\r
+            }\r
+            return null;\r
+        }\r
+        int hash = key.hashCode();\r
+        for (int i = 0; i < data.length; i += 2) {\r
+            Object k = data[i];\r
+            if (k == key || (hash == k.hashCode() && key.equals(k))) {\r
+                return (V) data[i+1];\r
+            }\r
+        }\r
+        return null;\r
+    }\r
+\r
+    @Override\r
+    public boolean isEmpty() {\r
+        return data.length == 0;\r
+    }\r
+\r
+    @Override\r
+    public Set<K> keySet() {\r
+        return (keySet != null) ? keySet : (keySet =  new OffsetSet<K>(0));\r
+    }\r
+\r
+    @SuppressWarnings("unchecked")\r
+    @Override\r
+    public V put(K key, V value) {\r
+        if (key == null) {\r
+            for (int i = 0; i < data.length; i += 2) {\r
+                if (data[i] == null) {\r
+                    V old = (V) data[i+1];\r
+                    data[i+1] = value;\r
+                    return old;\r
+                }\r
+            }\r
+            throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");\r
+        }\r
+        int hash = key.hashCode();\r
+        for (int i = 0; i < data.length; i += 2) {\r
+            K k = (K) data[i];\r
+            if (k == key || (hash == k.hashCode() && key.equals(k))) {\r
+                V old = (V) data[i+1];\r
+                data[i+1] = value;\r
+                return old;\r
+            }\r
+        }\r
+        throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");\r
+    }\r
+\r
+    @Override\r
+    public void putAll(Map<? extends K, ? extends V> m) {\r
+        for (K k : m.keySet()) {\r
+            if (!containsKey(k))\r
+                throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");\r
+        }\r
+        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {\r
+            put(entry.getKey(), entry.getValue());\r
+        }\r
+    }\r
+\r
+    @Override\r
+    public V remove(Object key) {\r
+        throw new UnsupportedOperationException();\r
+    }\r
+\r
+    @Override\r
+    public int size() {\r
+        return data.length >> 1;\r
+    }\r
+\r
+    @Override\r
+    public Collection<V> values() {\r
+        return valueSet != null ? valueSet : (valueSet = new OffsetSet<V>(1));\r
+    }\r
+\r
+    private boolean contains(int offset, Object o) {\r
+        int len = data.length;\r
+        if (o == null) {\r
+            for (int i = offset; i < len; i += 2)\r
+                if (data[i] == null)\r
+                    return true;\r
+            return false;\r
+        }\r
+        int hash = o.hashCode();\r
+        for (int i = offset; i < len; i += 2) {\r
+            Object k = data[i];\r
+            if (o == k || (hash == k.hashCode() && o.equals(k)))\r
+                return true;\r
+        }\r
+        return false;\r
+    }\r
+\r
+    class OffsetSet<T> extends ImmutableSet<T> implements Set<T> {\r
+\r
+        private final int offset;\r
+\r
+        public OffsetSet(int offset) {\r
+            this.offset = offset;\r
+        }\r
+\r
+        @Override\r
+        public boolean contains(Object o) {\r
+            return InterlacedArrayMap.this.contains(offset, o);\r
+        }\r
+\r
+        @Override\r
+        public boolean containsAll(Collection<?> c) {\r
+            for (Object o : c)\r
+                if (!contains(o))\r
+                    return false;\r
+            return true;\r
+        }\r
+\r
+        @Override\r
+        public boolean isEmpty() {\r
+            return data.length == 0;\r
+        }\r
+\r
+        @Override\r
+        public Iterator<T> iterator() {\r
+            return new ImmutableIterator<T>() {\r
+                int i = offset;\r
+\r
+                @Override\r
+                public boolean hasNext() {\r
+                    return i < data.length;\r
+                }\r
+\r
+                @Override\r
+                public T next() {\r
+                    if (i >= data.length)\r
+                        throw new NoSuchElementException("no more elements (" + data.length + " walked)");\r
+                    @SuppressWarnings("unchecked")\r
+                    T t = (T) data[i];\r
+                    ++i;\r
+                    return t;\r
+                }\r
+            };\r
+        }\r
+\r
+        @Override\r
+        public int size() {\r
+            return data.length >> 1;\r
+        }\r
+\r
+        @Override\r
+        public Object[] toArray() {\r
+            int len = data.length >> 1;\r
+            Object[] a = new Object[len];\r
+            for (int i = 0; i < len; ++i)\r
+                a[i] = data[i*2+offset];\r
+            return a;\r
+        }\r
+\r
+        @SuppressWarnings("unchecked")\r
+        @Override\r
+        public <TT> TT[] toArray(TT[] a) {\r
+            int len = data.length >> 1;\r
+            if (a.length < len) {\r
+                Class<?> clazz = a.getClass();\r
+                // Make a new array of a's runtime type, but my contents:\r
+                a = ((Object)clazz == (Object)Object[].class)\r
+                ? (TT[]) new Object[len]\r
+                : (TT[]) Array.newInstance(clazz.getComponentType(), len);\r
+            }\r
+            for (int i = 0; i < len; ++i)\r
+                a[i] = (TT) data[i*2+offset];\r
+            if (a.length > len)\r
+                a[len] = null;\r
+            return a;\r
+        }\r
+    }\r
+\r
+    class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {\r
+\r
+        @Override\r
+        public boolean contains(Object o) {\r
+            throw new UnsupportedOperationException("TODO");\r
+        }\r
+\r
+        @Override\r
+        public boolean containsAll(Collection<?> c) {\r
+            for (Object o : c)\r
+                if (!contains(o))\r
+                    return false;\r
+            return true;\r
+        }\r
+\r
+        @Override\r
+        public boolean isEmpty() {\r
+            return data.length == 0;\r
+        }\r
+\r
+        @Override\r
+        public Iterator<Map.Entry<K, V>> iterator() {\r
+            return new ImmutableIterator<Map.Entry<K, V>>() {\r
+                int i = 0;\r
+\r
+                @Override\r
+                public boolean hasNext() {\r
+                    return i < data.length;\r
+                }\r
+\r
+                @Override\r
+                public Map.Entry<K, V> next() {\r
+                    if (i >= data.length)\r
+                        throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)");\r
+                    @SuppressWarnings("unchecked")\r
+                    Map.Entry<K, V> entry = new ArrayMapEntry<K, V>(i, (K) data[i], (V) data[i+1]);\r
+                    i += 2;\r
+                    return entry;\r
+                }\r
+            };\r
+        }\r
+\r
+        @Override\r
+        public int size() {\r
+            return data.length >> 1;\r
+        }\r
+\r
+    }\r
+\r
+    /**\r
+     * Returns the hash code value for this map.  The hash code of a map is\r
+     * defined to be the sum of the hash codes of each entry in the map's\r
+     * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>\r
+     * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps\r
+     * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of\r
+     * {@link Object#hashCode}.\r
+     *\r
+     * <p>This implementation iterates over <tt>entrySet()</tt>, calling\r
+     * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the\r
+     * set, and adding up the results.\r
+     *\r
+     * @return the hash code value for this map\r
+     * @see Map.Entry#hashCode()\r
+     * @see Object#equals(Object)\r
+     * @see Set#equals(Object)\r
+     */\r
+    @Override\r
+    @SuppressWarnings("unchecked")\r
+    public int hashCode() {\r
+        int h = 0;\r
+        int l = data.length;\r
+        for (int i = 0; i < l; i += 2) {\r
+            K key = (K) data[i];\r
+            V value = (V) data[i+1];\r
+            int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());\r
+            h += hash;\r
+        }\r
+        return h;\r
+    }\r
+\r
+    /**\r
+     * Compares the specified object with this map for equality.  Returns\r
+     * <tt>true</tt> if the given object is also a map and the two maps\r
+     * represent the same mappings.  More formally, two maps <tt>m1</tt> and\r
+     * <tt>m2</tt> represent the same mappings if\r
+     * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the\r
+     * <tt>equals</tt> method works properly across different implementations\r
+     * of the <tt>Map</tt> interface.\r
+     *\r
+     * <p>This implementation first checks if the specified object is this map;\r
+     * if so it returns <tt>true</tt>.  Then, it checks if the specified\r
+     * object is a map whose size is identical to the size of this map; if\r
+     * not, it returns <tt>false</tt>.  If so, it iterates over this map's\r
+     * <tt>entrySet</tt> collection, and checks that the specified map\r
+     * contains each mapping that this map contains.  If the specified map\r
+     * fails to contain such a mapping, <tt>false</tt> is returned.  If the\r
+     * iteration completes, <tt>true</tt> is returned.\r
+     *\r
+     * @param o object to be compared for equality with this map\r
+     * @return <tt>true</tt> if the specified object is equal to this map\r
+     */\r
+    @Override\r
+    @SuppressWarnings("unchecked")\r
+    public boolean equals(Object o) {\r
+        if (o == this)\r
+            return true;\r
+\r
+        if (!(o instanceof Map))\r
+            return false;\r
+        Map<K, V> m = (Map<K, V>) o;\r
+        if (m.size() != size())\r
+            return false;\r
+\r
+        try {\r
+            int l = data.length;\r
+            for (int i = 0; i < l; i += 2) {\r
+                K key = (K) data[i];\r
+                V value = (V) data[i+1];\r
+                if (value == null) {\r
+                    if (!(m.get(key)==null && m.containsKey(key)))\r
+                        return false;\r
+                } else {\r
+                    if (!value.equals(m.get(key)))\r
+                        return false;\r
+                }\r
+            }\r
+        } catch (ClassCastException unused) {\r
+            return false;\r
+        } catch (NullPointerException unused) {\r
+            return false;\r
+        }\r
+\r
+        return true;\r
+    }\r
+\r
+    @Override\r
+    public String toString() {\r
+        Iterator<Map.Entry<K,V>> i = entrySet().iterator();\r
+        if (! i.hasNext())\r
+            return "{}";\r
+\r
+        StringBuilder sb = new StringBuilder();\r
+        sb.append('{');\r
+        for (;;) {\r
+            Map.Entry<K,V> e = i.next();\r
+            K key = e.getKey();\r
+            V value = e.getValue();\r
+            sb.append(key   == this ? "(this Map)" : key);\r
+            sb.append('=');\r
+            sb.append(value == this ? "(this Map)" : value);\r
+            if (! i.hasNext())\r
+                return sb.append('}').toString();\r
+            sb.append(", ");\r
+        }\r
+    }\r
+}\r