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