--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2010 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
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.utils.datastructures.persistent;\r
+\r
+ import gnu.trove.procedure.TObjectObjectProcedure;\r
+\r
+public class ImmutableMap<T extends Comparable<T>, V> {\r
+ \r
+ @SuppressWarnings({ "rawtypes" })\r
+ static final ImmutableMap EMPTY = new EmptyImmutableSet();\r
+ \r
+ private static class EmptyImmutableSet<T extends Comparable<T>, V> extends ImmutableMap<T, V> {\r
+ public EmptyImmutableSet() {\r
+ isBlack = true;\r
+ }\r
+ \r
+ protected ImmutableMap<T, V> putRec(T key, V value) {\r
+ return new ImmutableMap<T, V>(key, value);\r
+ }\r
+ \r
+ protected ImmutableMap<T, V> removeRec(T obj) {\r
+ return null;\r
+ }\r
+ \r
+ public boolean contains(T obj) {\r
+ return false;\r
+ }\r
+ \r
+ public V get(T key) {\r
+ return null;\r
+ }\r
+ \r
+ @Override\r
+ public boolean forEach(TObjectObjectProcedure<T, V> arg0) {\r
+ return true;\r
+ }\r
+ }\r
+ \r
+ ImmutableMap<T, V> left;\r
+ T key;\r
+ V value;\r
+ ImmutableMap<T, V> right;\r
+ boolean isBlack;\r
+ \r
+ protected ImmutableMap(\r
+ ImmutableMap<T, V> left,\r
+ T key,\r
+ V value,\r
+ ImmutableMap<T, V> right, \r
+ boolean isBlack) {\r
+ this.left = left;\r
+ this.right = right;\r
+ this.key = key;\r
+ this.value = value;\r
+ this.isBlack = isBlack;\r
+ }\r
+\r
+ @SuppressWarnings("unchecked")\r
+ public ImmutableMap(T key, V value) {\r
+ this(EMPTY, key, value, EMPTY, false);\r
+ } \r
+\r
+ private ImmutableMap() { \r
+ }\r
+ \r
+ public boolean contains(T obj) {\r
+ int cmp = obj.compareTo(key);\r
+ if(cmp < 0)\r
+ return left.contains(obj);\r
+ else if(cmp > 0)\r
+ return right.contains(obj);\r
+ else\r
+ return true;\r
+ } \r
+ \r
+ public V get(T key) {\r
+ int cmp = key.compareTo(key);\r
+ if(cmp < 0)\r
+ return left.get(key);\r
+ else if(cmp > 0)\r
+ return right.get(key);\r
+ else\r
+ return value;\r
+ } \r
+ \r
+ protected ImmutableMap<T, V> putRec(T obj, V value) {\r
+ int cmp = obj.compareTo(key);\r
+ if(cmp < 0) {\r
+ ImmutableMap<T, V> newLeft = left.putRec(obj, value);\r
+ if(newLeft == left)\r
+ return this; \r
+ if(isBlack)\r
+ return balance(newLeft, key, value, right);\r
+ else\r
+ return red(newLeft, key, value, right);\r
+ }\r
+ else if(cmp > 0) {\r
+ ImmutableMap<T, V> newRight = right.putRec(obj, value);\r
+ if(newRight == right)\r
+ return this;\r
+ if(isBlack)\r
+ return balance(left, key, value, newRight);\r
+ else\r
+ return red(left, key, value, newRight);\r
+ }\r
+ else\r
+ return this;\r
+ }\r
+ \r
+ /**\r
+ * Assumes this is a black nonempty node. \r
+ * \r
+ * Removes obj from the tree. The returned tree has always\r
+ * one black node less in every branch (even if nothing is\r
+ * removed).\r
+ * \r
+ * @param obj\r
+ * @return\r
+ */\r
+ protected ImmutableMap<T, V> removeRec(T obj) { \r
+ int cmp = obj.compareTo(key);\r
+ if(cmp < 0) {\r
+ ImmutableMap<T, V> newLeft = left.removeRec(obj);\r
+ if(newLeft == null)\r
+ return null;\r
+ else if(left.isBlack)\r
+ return balleft(newLeft, key, value, right);\r
+ else\r
+ return red(newLeft, key, value, right);\r
+ }\r
+ else if(cmp > 0) {\r
+ ImmutableMap<T, V> newRight = right.removeRec(obj);\r
+ if(newRight == null)\r
+ return null;\r
+ else if(right.isBlack)\r
+ return balright(left, key, value, newRight);\r
+ else\r
+ return red(left, key, value, newRight); \r
+ }\r
+ else\r
+ return append(left, right);\r
+ }\r
+ \r
+ /**\r
+ * Assumes a and b have the same black depth and keys in a are strictly less\r
+ * than keys in b. Creates a new tree with the same black depth as a and b. \r
+ * \r
+ * @param <T>\r
+ * @param a\r
+ * @param b\r
+ * @return\r
+ */\r
+ protected static <T extends Comparable<T>, V> ImmutableMap<T, V> append(ImmutableMap<T, V> a, ImmutableMap<T, V> b) {\r
+ if(a==EMPTY)\r
+ return b;\r
+ if(b==EMPTY)\r
+ return a;\r
+ if(a.isBlack) {\r
+ if(b.isBlack) {\r
+ ImmutableMap<T, V> middle = append(a.right, b.left);\r
+ if(middle.isBlack)\r
+ return balleft(a.left, a.key, a.value, black(middle, b.key, b.value, b.right));\r
+ else\r
+ return red(black(a.left, a.key, a.value, middle.left), middle.key, middle.value, black(middle.right, b.key, b.value, b.right));\r
+ }\r
+ else\r
+ return red(append(a, b.left), b.key, b.value, b.right);\r
+ }\r
+ else {\r
+ if(b.isBlack)\r
+ return red(a.left, a.key, a.value, append(a.right, b));\r
+ else {\r
+ ImmutableMap<T, V> middle = append(a.right, b.left);\r
+ if(middle.isBlack)\r
+ return red(a.left, a.key, a.value, red(middle, b.key, b.value, b.right));\r
+ else\r
+ return red(red(a.left, a.key, a.value, middle.left), middle.key, middle.value, red(middle.right, b.key, b.value, b.right));\r
+ }\r
+ }\r
+ }\r
+ \r
+ public T getFirst() {\r
+ if(left == EMPTY)\r
+ return key;\r
+ else\r
+ return left.getFirst();\r
+ } \r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> balance(\r
+ ImmutableMap<T, V> left,\r
+ T key,\r
+ V value,\r
+ ImmutableMap<T, V> right) {\r
+ if(!left.isBlack) {\r
+ if(!left.left.isBlack) \r
+ return red(\r
+ toBlack(left.left),\r
+ left.key,\r
+ left.value,\r
+ black(left.right, key, value, right)\r
+ );\r
+ else if(!left.right.isBlack)\r
+ return red(\r
+ black(left.left, left.key, left.value, left.right.left),\r
+ left.right.key, left.right.value,\r
+ black(left.right.right, key, value, right) \r
+ ); \r
+ }\r
+ if(!right.isBlack) {\r
+ if(!right.left.isBlack)\r
+ return red(\r
+ black(left, key, value, right.left.left),\r
+ right.left.key, right.left.value,\r
+ black(right.left.right, right.key, right.value, right.right)\r
+ );\r
+ else if(!right.right.isBlack)\r
+ return red(\r
+ black(left, key, value, right.left),\r
+ right.key,\r
+ right.value,\r
+ toBlack(right.right)\r
+ ); \r
+ }\r
+ return black(left, key, value, right);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> black(\r
+ ImmutableMap<T, V> left,\r
+ T key,\r
+ V value,\r
+ ImmutableMap<T, V> right) {\r
+ return new ImmutableMap<T, V>(left, key, value, right, true);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> red(\r
+ ImmutableMap<T, V> left,\r
+ T key,\r
+ V value,\r
+ ImmutableMap<T, V> right) {\r
+ return new ImmutableMap<T, V>(left, key, value, right, false);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> toBlack(ImmutableMap<T, V> tree) {\r
+ if(tree.isBlack)\r
+ return tree;\r
+ else\r
+ return black(tree.left, tree.key, tree.value, tree.right);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> toRed(ImmutableMap<T, V> tree) {\r
+ if(tree.isBlack)\r
+ return red(tree.left, tree.key, tree.value, tree.right);\r
+ else\r
+ return tree;\r
+ }\r
+ \r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> balleft(\r
+ ImmutableMap<T, V> left,\r
+ T key,\r
+ V value,\r
+ ImmutableMap<T, V> right) {\r
+ if(left.isBlack) {\r
+ if(right.isBlack)\r
+ return balance(left, key, value, toRed(right));\r
+ else\r
+ return red(black(left, key, value, right.left.left), right.left.key, right.left.value,\r
+ balance(right.left.right, right.key, right.value, toRed(right.right)));\r
+ }\r
+ else\r
+ return red(toBlack(left), key, value, right);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> balright(\r
+ ImmutableMap<T, V> left,\r
+ T key,\r
+ V value,\r
+ ImmutableMap<T, V> right) {\r
+ if(right.isBlack) {\r
+ if(left.isBlack)\r
+ return balance(toRed(left), key, value, right);\r
+ else\r
+ return red(balance(toRed(left.left), left.key, left.value, left.right.left), left.right.key, left.right.value,\r
+ black(left.right.right, key, value, right));\r
+ }\r
+ else\r
+ return red(left, key, value, toBlack(right));\r
+ }\r
+\r
+ public ImmutableMap<T, V> put(T key, V value) {\r
+ ImmutableMap<T, V> tree = putRec(key, value);\r
+ tree.isBlack = true;\r
+ return tree;\r
+ }\r
+\r
+ public ImmutableMap<T, V> remove(T obj) {\r
+ ImmutableMap<T, V> tree = removeRec(obj);\r
+ if(tree == null)\r
+ return this;\r
+ if(tree.isBlack)\r
+ return tree;\r
+ else\r
+ return black(tree.left, tree.key, tree.value, tree.right);\r
+ }\r
+ \r
+ public boolean forEach(TObjectObjectProcedure<T, V> proc) {\r
+ if(left.forEach(proc))\r
+ if(proc.execute(key, value))\r
+ return right.forEach(proc);\r
+ return false;\r
+ } \r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff