--- /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.TObjectProcedure;\r
+\r
+import java.util.Collection;\r
+import java.util.HashSet;\r
+import java.util.Iterator;\r
+import java.util.Random;\r
+import java.util.Set;\r
+\r
+public class ImmutableSet<T extends Comparable<T>> {\r
+ \r
+ @SuppressWarnings({ "rawtypes" })\r
+ static final ImmutableSet EMPTY = new EmptyImmutableSet();\r
+ \r
+ private static class EmptyImmutableSet<T extends Comparable<T>> extends ImmutableSet<T> {\r
+ public EmptyImmutableSet() {\r
+ isBlack = true;\r
+ }\r
+ \r
+ protected org.simantics.utils.datastructures.persistent.ImmutableSet<T> addRec(T obj) {\r
+ return new ImmutableSet<T>(obj);\r
+ }\r
+ \r
+ protected org.simantics.utils.datastructures.persistent.ImmutableSet<T> removeRec(T obj) {\r
+ return null;\r
+ }\r
+ \r
+ public boolean contains(T obj) {\r
+ return false;\r
+ }\r
+ \r
+ @Override\r
+ public boolean forEach(TObjectProcedure<T> arg0) {\r
+ return true;\r
+ }\r
+ \r
+ @Override\r
+ void print(int arg0) { \r
+ }\r
+ }\r
+ \r
+ ImmutableSet<T> left;\r
+ T key;\r
+ ImmutableSet<T> right;\r
+ boolean isBlack;\r
+ \r
+ protected ImmutableSet(\r
+ ImmutableSet<T> left,\r
+ T key,\r
+ ImmutableSet<T> right, \r
+ boolean isBlack) {\r
+ this.left = left;\r
+ this.right = right;\r
+ this.key = key;\r
+ this.isBlack = isBlack;\r
+ }\r
+\r
+ @SuppressWarnings("unchecked")\r
+ public ImmutableSet(T key) {\r
+ this(EMPTY, key, EMPTY, false);\r
+ }\r
+ \r
+ @SuppressWarnings("unchecked")\r
+ public static <T extends Comparable<T>> ImmutableSet<T> of(T ... array) {\r
+ if(array.length == 0)\r
+ return EMPTY;\r
+ ImmutableSet<T> ret = new ImmutableSet<T>(array[0]);\r
+ for(int i=1;i<array.length;++i)\r
+ ret = ret.add(array[i]);\r
+ return ret;\r
+ }\r
+ \r
+ @SuppressWarnings("unchecked")\r
+ public static <T extends Comparable<T>> ImmutableSet<T> of(Collection<T> c) {\r
+ Iterator<T> it = c.iterator();\r
+ if(!it.hasNext())\r
+ return EMPTY; \r
+ ImmutableSet<T> ret = new ImmutableSet<T>(it.next());\r
+ while(it.hasNext())\r
+ ret = ret.add(it.next());\r
+ return ret;\r
+ }\r
+\r
+ private ImmutableSet() { \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
+ protected ImmutableSet<T> addRec(T obj) {\r
+ int cmp = obj.compareTo(key);\r
+ if(cmp < 0) {\r
+ ImmutableSet<T> newLeft = left.addRec(obj);\r
+ if(newLeft == left)\r
+ return this; \r
+ if(isBlack)\r
+ return balance(newLeft, key, right);\r
+ else\r
+ return red(newLeft, key, right);\r
+ }\r
+ else if(cmp > 0) {\r
+ ImmutableSet<T> newRight = right.addRec(obj);\r
+ if(newRight == right)\r
+ return this;\r
+ if(isBlack)\r
+ return balance(left, key, newRight);\r
+ else\r
+ return red(left, key, 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 ImmutableSet<T> removeRec(T obj) { \r
+ int cmp = obj.compareTo(key);\r
+ if(cmp < 0) {\r
+ ImmutableSet<T> newLeft = left.removeRec(obj);\r
+ if(newLeft == null)\r
+ return null;\r
+ else if(left.isBlack)\r
+ return balleft(newLeft, key, right);\r
+ else\r
+ return red(newLeft, key, right);\r
+ }\r
+ else if(cmp > 0) {\r
+ ImmutableSet<T> newRight = right.removeRec(obj);\r
+ if(newRight == null)\r
+ return null;\r
+ else if(right.isBlack)\r
+ return balright(left, key, newRight);\r
+ else\r
+ return red(left, key, 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>> ImmutableSet<T> append(ImmutableSet<T> a, ImmutableSet<T> b) {\r
+ if(a==EMPTY)\r
+ return b;\r
+ if(b==EMPTY)\r
+ return a;\r
+ if(a.isBlack) {\r
+ if(b.isBlack) {\r
+ ImmutableSet<T> middle = append(a.right, b.left);\r
+ if(middle.isBlack)\r
+ return balleft(a.left, a.key, black(middle, b.key, b.right));\r
+ else\r
+ return red(black(a.left, a.key, middle.left), middle.key, black(middle.right, b.key, b.right));\r
+ }\r
+ else\r
+ return red(append(a, b.left), b.key, b.right);\r
+ }\r
+ else {\r
+ if(b.isBlack)\r
+ return red(a.left, a.key, append(a.right, b));\r
+ else {\r
+ ImmutableSet<T> middle = append(a.right, b.left);\r
+ if(middle.isBlack)\r
+ return red(a.left, a.key, red(middle, b.key, b.right));\r
+ else\r
+ return red(red(a.left, a.key, middle.left), middle.key, red(middle.right, b.key, 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>> ImmutableSet<T> balance(\r
+ ImmutableSet<T> left,\r
+ T key,\r
+ ImmutableSet<T> right) {\r
+ if(!left.isBlack) {\r
+ if(!left.left.isBlack) \r
+ return red(\r
+ toBlack(left.left),\r
+ left.key,\r
+ black(left.right, key, right)\r
+ );\r
+ else if(!left.right.isBlack)\r
+ return red(\r
+ black(left.left, left.key, left.right.left),\r
+ left.right.key,\r
+ black(left.right.right, key, right) \r
+ ); \r
+ }\r
+ if(!right.isBlack) {\r
+ if(!right.left.isBlack)\r
+ return red(\r
+ black(left, key, right.left.left),\r
+ right.left.key,\r
+ black(right.left.right, right.key, right.right)\r
+ );\r
+ else if(!right.right.isBlack)\r
+ return red(\r
+ black(left, key, right.left),\r
+ right.key,\r
+ toBlack(right.right)\r
+ ); \r
+ }\r
+ return black(left, key, right);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>> ImmutableSet<T> black(\r
+ ImmutableSet<T> left,\r
+ T key,\r
+ ImmutableSet<T> right) {\r
+ return new ImmutableSet<T>(left, key, right, true);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>> ImmutableSet<T> red(\r
+ ImmutableSet<T> left,\r
+ T key,\r
+ ImmutableSet<T> right) {\r
+ return new ImmutableSet<T>(left, key, right, false);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>> ImmutableSet<T> toBlack(ImmutableSet<T> tree) {\r
+ if(tree.isBlack)\r
+ return tree;\r
+ else\r
+ return black(tree.left, tree.key, tree.right);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>> ImmutableSet<T> toRed(ImmutableSet<T> tree) {\r
+ if(tree.isBlack)\r
+ return red(tree.left, tree.key, tree.right);\r
+ else\r
+ return tree;\r
+ }\r
+ \r
+ \r
+ static private <T extends Comparable<T>> ImmutableSet<T> balleft(\r
+ ImmutableSet<T> left,\r
+ T key,\r
+ ImmutableSet<T> right) {\r
+ if(left.isBlack) {\r
+ if(right.isBlack)\r
+ return balance(left, key, toRed(right));\r
+ else\r
+ return red(black(left, key, right.left.left), right.left.key, balance(right.left.right, right.key, toRed(right.right)));\r
+ }\r
+ else\r
+ return red(toBlack(left), key, right);\r
+ }\r
+ \r
+ static private <T extends Comparable<T>> ImmutableSet<T> balright(\r
+ ImmutableSet<T> left,\r
+ T key,\r
+ ImmutableSet<T> right) {\r
+ if(right.isBlack) {\r
+ if(left.isBlack)\r
+ return balance(toRed(left), key, right);\r
+ else\r
+ return red(balance(toRed(left.left), left.key, left.right.left), left.right.key, black(left.right.right, key, right));\r
+ }\r
+ else\r
+ return red(left, key, toBlack(right));\r
+ }\r
+\r
+ public ImmutableSet<T> add(T obj) {\r
+ ImmutableSet<T> tree = addRec(obj);\r
+ tree.isBlack = true;\r
+ return tree;\r
+ }\r
+\r
+ public ImmutableSet<T> remove(T obj) {\r
+ ImmutableSet<T> 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.right);\r
+ }\r
+\r
+ public boolean forEach(TObjectProcedure<T> procedure) {\r
+ if(left.forEach(procedure))\r
+ if(procedure.execute(key))\r
+ return right.forEach(procedure);\r
+ return false;\r
+ }\r
+ \r
+ public ImmutableSet<T> addAll(Iterable<T> c) {\r
+ ImmutableSet<T> ret = this;\r
+ for(T t : c)\r
+ ret = ret.add(t);\r
+ return ret;\r
+ }\r
+ \r
+ static class AddAll<T extends Comparable<T>> implements TObjectProcedure<T> {\r
+\r
+ ImmutableSet<T> result; \r
+ \r
+ public AddAll(ImmutableSet<T> result) {\r
+ this.result = result;\r
+ }\r
+\r
+ @Override\r
+ public boolean execute(T arg0) {\r
+ result = result.add(arg0);\r
+ return true;\r
+ }\r
+ \r
+ }\r
+ \r
+ public ImmutableSet<T> addAll(ImmutableSet<T> c) {\r
+ if(this==EMPTY)\r
+ return c;\r
+ if(c==EMPTY)\r
+ return this;\r
+ AddAll<T> proc = new AddAll<T>(this);\r
+ c.forEach(proc);\r
+ return proc.result;\r
+ }\r
+ \r
+ /**************************************************************************\r
+ * \r
+ * Testing\r
+ * \r
+ ************************************************************************** \r
+ */\r
+ \r
+ void print(int indentation) {\r
+ left.print(indentation + 1);\r
+ for(int i=0;i<indentation;++i)\r
+ System.out.print(" ");\r
+ System.out.println(key + " " + (isBlack ? "BLACK" : "RED"));\r
+ right.print(indentation + 1);\r
+ }\r
+ \r
+ private int validateRec() {\r
+ if(this==EMPTY)\r
+ return 1;\r
+ int lh = left.validateRec();\r
+ int rh = right.validateRec();\r
+ if(lh != rh)\r
+ System.out.println("Unbalanced!");\r
+ if(!isBlack) {\r
+ if(!left.isBlack || !right.isBlack)\r
+ System.out.println("Red under red");\r
+ return lh;\r
+ }\r
+ else\r
+ return lh+1;\r
+ } \r
+\r
+ @SuppressWarnings("unchecked")\r
+ public static <T extends Comparable<T>> ImmutableSet<T> empty() {\r
+ return EMPTY;\r
+ }\r
+ \r
+ public void validate() {\r
+ validateRec();\r
+ if(!isBlack)\r
+ System.out.println("Root is not black");\r
+ }\r
+\r
+ @SuppressWarnings("unchecked")\r
+ public static void main(String[] args) {\r
+ ImmutableSet<Integer> set = ImmutableSet.EMPTY;\r
+ final Set<Integer> set2 = new HashSet<Integer>();\r
+\r
+ Random random = new Random();\r
+ for(int i=0;i<10000;++i) {\r
+ int r1 = random.nextInt(1000);\r
+ int r2 = random.nextInt(1000);\r
+ set = set.add(r1);\r
+ set = set.remove(r2);\r
+ set2.add(r1);\r
+ set2.remove(r2);\r
+ set.validate(); \r
+ \r
+ for(Integer v : set2)\r
+ if(!set.contains(v))\r
+ System.out.println("set2 has more elements");\r
+ set.forEach(new TObjectProcedure<Integer>() {\r
+\r
+ @Override\r
+ public boolean execute(Integer arg0) {\r
+ if(!set2.contains(arg0))\r
+ System.out.println("set has more elements");\r
+ return true;\r
+ }\r
+ \r
+ });\r
+ }\r
+ \r
+ /*\r
+ map.forEach(new TObjectProcedure<Integer>() {\r
+\r
+ @Override\r
+ public boolean execute(Integer arg0) {\r
+ System.out.println(arg0);\r
+ return true;\r
+ }\r
+ \r
+ });\r
+ */\r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff