-/*******************************************************************************\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
+/*******************************************************************************
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management
+ * in Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VTT Technical Research Centre of Finland - initial API and implementation
+ *******************************************************************************/
+package org.simantics.utils.datastructures.persistent;
+
+ import gnu.trove.procedure.TObjectObjectProcedure;
+
+public class ImmutableMap<T extends Comparable<T>, V> {
+
+ @SuppressWarnings({ "rawtypes" })
+ static final ImmutableMap EMPTY = new EmptyImmutableSet();
+
+ private static class EmptyImmutableSet<T extends Comparable<T>, V> extends ImmutableMap<T, V> {
+ public EmptyImmutableSet() {
+ isBlack = true;
+ }
+
+ protected ImmutableMap<T, V> putRec(T key, V value) {
+ return new ImmutableMap<T, V>(key, value);
+ }
+
+ protected ImmutableMap<T, V> removeRec(T obj) {
+ return null;
+ }
+
+ public boolean contains(T obj) {
+ return false;
+ }
+
+ public V get(T key) {
+ return null;
+ }
+
+ @Override
+ public boolean forEach(TObjectObjectProcedure<T, V> arg0) {
+ return true;
+ }
+ }
+
+ ImmutableMap<T, V> left;
+ T key;
+ V value;
+ ImmutableMap<T, V> right;
+ boolean isBlack;
+
+ protected ImmutableMap(
+ ImmutableMap<T, V> left,
+ T key,
+ V value,
+ ImmutableMap<T, V> right,
+ boolean isBlack) {
+ this.left = left;
+ this.right = right;
+ this.key = key;
+ this.value = value;
+ this.isBlack = isBlack;
+ }
+
+ @SuppressWarnings("unchecked")
+ public ImmutableMap(T key, V value) {
+ this(EMPTY, key, value, EMPTY, false);
+ }
+
+ private ImmutableMap() {
+ }
+
+ public boolean contains(T obj) {
+ int cmp = obj.compareTo(key);
+ if(cmp < 0)
+ return left.contains(obj);
+ else if(cmp > 0)
+ return right.contains(obj);
+ else
+ return true;
+ }
+
+ public V get(T key) {
+ int cmp = key.compareTo(key);
+ if(cmp < 0)
+ return left.get(key);
+ else if(cmp > 0)
+ return right.get(key);
+ else
+ return value;
+ }
+
+ protected ImmutableMap<T, V> putRec(T obj, V value) {
+ int cmp = obj.compareTo(key);
+ if(cmp < 0) {
+ ImmutableMap<T, V> newLeft = left.putRec(obj, value);
+ if(newLeft == left)
+ return this;
+ if(isBlack)
+ return balance(newLeft, key, value, right);
+ else
+ return red(newLeft, key, value, right);
+ }
+ else if(cmp > 0) {
+ ImmutableMap<T, V> newRight = right.putRec(obj, value);
+ if(newRight == right)
+ return this;
+ if(isBlack)
+ return balance(left, key, value, newRight);
+ else
+ return red(left, key, value, newRight);
+ }
+ else
+ return this;
+ }
+
+ /**
+ * Assumes this is a black nonempty node.
+ *
+ * Removes obj from the tree. The returned tree has always
+ * one black node less in every branch (even if nothing is
+ * removed).
+ *
+ * @param obj
+ * @return
+ */
+ protected ImmutableMap<T, V> removeRec(T obj) {
+ int cmp = obj.compareTo(key);
+ if(cmp < 0) {
+ ImmutableMap<T, V> newLeft = left.removeRec(obj);
+ if(newLeft == null)
+ return null;
+ else if(left.isBlack)
+ return balleft(newLeft, key, value, right);
+ else
+ return red(newLeft, key, value, right);
+ }
+ else if(cmp > 0) {
+ ImmutableMap<T, V> newRight = right.removeRec(obj);
+ if(newRight == null)
+ return null;
+ else if(right.isBlack)
+ return balright(left, key, value, newRight);
+ else
+ return red(left, key, value, newRight);
+ }
+ else
+ return append(left, right);
+ }
+
+ /**
+ * Assumes a and b have the same black depth and keys in a are strictly less
+ * than keys in b. Creates a new tree with the same black depth as a and b.
+ *
+ * @param <T>
+ * @param a
+ * @param b
+ * @return
+ */
+ protected static <T extends Comparable<T>, V> ImmutableMap<T, V> append(ImmutableMap<T, V> a, ImmutableMap<T, V> b) {
+ if(a==EMPTY)
+ return b;
+ if(b==EMPTY)
+ return a;
+ if(a.isBlack) {
+ if(b.isBlack) {
+ ImmutableMap<T, V> middle = append(a.right, b.left);
+ if(middle.isBlack)
+ return balleft(a.left, a.key, a.value, black(middle, b.key, b.value, b.right));
+ else
+ return red(black(a.left, a.key, a.value, middle.left), middle.key, middle.value, black(middle.right, b.key, b.value, b.right));
+ }
+ else
+ return red(append(a, b.left), b.key, b.value, b.right);
+ }
+ else {
+ if(b.isBlack)
+ return red(a.left, a.key, a.value, append(a.right, b));
+ else {
+ ImmutableMap<T, V> middle = append(a.right, b.left);
+ if(middle.isBlack)
+ return red(a.left, a.key, a.value, red(middle, b.key, b.value, b.right));
+ else
+ return red(red(a.left, a.key, a.value, middle.left), middle.key, middle.value, red(middle.right, b.key, b.value, b.right));
+ }
+ }
+ }
+
+ public T getFirst() {
+ if(left == EMPTY)
+ return key;
+ else
+ return left.getFirst();
+ }
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> balance(
+ ImmutableMap<T, V> left,
+ T key,
+ V value,
+ ImmutableMap<T, V> right) {
+ if(!left.isBlack) {
+ if(!left.left.isBlack)
+ return red(
+ toBlack(left.left),
+ left.key,
+ left.value,
+ black(left.right, key, value, right)
+ );
+ else if(!left.right.isBlack)
+ return red(
+ black(left.left, left.key, left.value, left.right.left),
+ left.right.key, left.right.value,
+ black(left.right.right, key, value, right)
+ );
+ }
+ if(!right.isBlack) {
+ if(!right.left.isBlack)
+ return red(
+ black(left, key, value, right.left.left),
+ right.left.key, right.left.value,
+ black(right.left.right, right.key, right.value, right.right)
+ );
+ else if(!right.right.isBlack)
+ return red(
+ black(left, key, value, right.left),
+ right.key,
+ right.value,
+ toBlack(right.right)
+ );
+ }
+ return black(left, key, value, right);
+ }
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> black(
+ ImmutableMap<T, V> left,
+ T key,
+ V value,
+ ImmutableMap<T, V> right) {
+ return new ImmutableMap<T, V>(left, key, value, right, true);
+ }
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> red(
+ ImmutableMap<T, V> left,
+ T key,
+ V value,
+ ImmutableMap<T, V> right) {
+ return new ImmutableMap<T, V>(left, key, value, right, false);
+ }
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> toBlack(ImmutableMap<T, V> tree) {
+ if(tree.isBlack)
+ return tree;
+ else
+ return black(tree.left, tree.key, tree.value, tree.right);
+ }
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> toRed(ImmutableMap<T, V> tree) {
+ if(tree.isBlack)
+ return red(tree.left, tree.key, tree.value, tree.right);
+ else
+ return tree;
+ }
+
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> balleft(
+ ImmutableMap<T, V> left,
+ T key,
+ V value,
+ ImmutableMap<T, V> right) {
+ if(left.isBlack) {
+ if(right.isBlack)
+ return balance(left, key, value, toRed(right));
+ else
+ return red(black(left, key, value, right.left.left), right.left.key, right.left.value,
+ balance(right.left.right, right.key, right.value, toRed(right.right)));
+ }
+ else
+ return red(toBlack(left), key, value, right);
+ }
+
+ static private <T extends Comparable<T>, V> ImmutableMap<T, V> balright(
+ ImmutableMap<T, V> left,
+ T key,
+ V value,
+ ImmutableMap<T, V> right) {
+ if(right.isBlack) {
+ if(left.isBlack)
+ return balance(toRed(left), key, value, right);
+ else
+ return red(balance(toRed(left.left), left.key, left.value, left.right.left), left.right.key, left.right.value,
+ black(left.right.right, key, value, right));
+ }
+ else
+ return red(left, key, value, toBlack(right));
+ }
+
+ public ImmutableMap<T, V> put(T key, V value) {
+ ImmutableMap<T, V> tree = putRec(key, value);
+ tree.isBlack = true;
+ return tree;
+ }
+
+ public ImmutableMap<T, V> remove(T obj) {
+ ImmutableMap<T, V> tree = removeRec(obj);
+ if(tree == null)
+ return this;
+ if(tree.isBlack)
+ return tree;
+ else
+ return black(tree.left, tree.key, tree.value, tree.right);
+ }
+
+ public boolean forEach(TObjectObjectProcedure<T, V> proc) {
+ if(left.forEach(proc))
+ if(proc.execute(key, value))
+ return right.forEach(proc);
+ return false;
+ }
+
+}
Code Review / simantics / platform.git / blobdiff