1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.utils.datastructures.persistent;
14 import gnu.trove.procedure.TObjectProcedure;
16 import java.util.Collection;
17 import java.util.HashSet;
18 import java.util.Iterator;
19 import java.util.Random;
22 public class ImmutableSet<T extends Comparable<T>> {
24 @SuppressWarnings({ "rawtypes" })
25 static final ImmutableSet EMPTY = new EmptyImmutableSet();
27 private static class EmptyImmutableSet<T extends Comparable<T>> extends ImmutableSet<T> {
28 public EmptyImmutableSet() {
32 protected org.simantics.utils.datastructures.persistent.ImmutableSet<T> addRec(T obj) {
33 return new ImmutableSet<T>(obj);
36 protected org.simantics.utils.datastructures.persistent.ImmutableSet<T> removeRec(T obj) {
40 public boolean contains(T obj) {
45 public boolean forEach(TObjectProcedure<T> arg0) {
50 void print(int arg0) {
56 ImmutableSet<T> right;
59 protected ImmutableSet(
62 ImmutableSet<T> right,
67 this.isBlack = isBlack;
70 @SuppressWarnings("unchecked")
71 public ImmutableSet(T key) {
72 this(EMPTY, key, EMPTY, false);
75 @SuppressWarnings("unchecked")
76 public static <T extends Comparable<T>> ImmutableSet<T> of(T ... array) {
79 ImmutableSet<T> ret = new ImmutableSet<T>(array[0]);
80 for(int i=1;i<array.length;++i)
81 ret = ret.add(array[i]);
85 @SuppressWarnings("unchecked")
86 public static <T extends Comparable<T>> ImmutableSet<T> of(Collection<T> c) {
87 Iterator<T> it = c.iterator();
90 ImmutableSet<T> ret = new ImmutableSet<T>(it.next());
92 ret = ret.add(it.next());
96 private ImmutableSet() {
99 public boolean contains(T obj) {
100 int cmp = obj.compareTo(key);
102 return left.contains(obj);
104 return right.contains(obj);
109 protected ImmutableSet<T> addRec(T obj) {
110 int cmp = obj.compareTo(key);
112 ImmutableSet<T> newLeft = left.addRec(obj);
116 return balance(newLeft, key, right);
118 return red(newLeft, key, right);
121 ImmutableSet<T> newRight = right.addRec(obj);
122 if(newRight == right)
125 return balance(left, key, newRight);
127 return red(left, key, newRight);
134 * Assumes this is a black nonempty node.
136 * Removes obj from the tree. The returned tree has always
137 * one black node less in every branch (even if nothing is
143 protected ImmutableSet<T> removeRec(T obj) {
144 int cmp = obj.compareTo(key);
146 ImmutableSet<T> newLeft = left.removeRec(obj);
149 else if(left.isBlack)
150 return balleft(newLeft, key, right);
152 return red(newLeft, key, right);
155 ImmutableSet<T> newRight = right.removeRec(obj);
158 else if(right.isBlack)
159 return balright(left, key, newRight);
161 return red(left, key, newRight);
164 return append(left, right);
168 * Assumes a and b have the same black depth and keys in a are strictly less
169 * than keys in b. Creates a new tree with the same black depth as a and b.
176 protected static <T extends Comparable<T>> ImmutableSet<T> append(ImmutableSet<T> a, ImmutableSet<T> b) {
183 ImmutableSet<T> middle = append(a.right, b.left);
185 return balleft(a.left, a.key, black(middle, b.key, b.right));
187 return red(black(a.left, a.key, middle.left), middle.key, black(middle.right, b.key, b.right));
190 return red(append(a, b.left), b.key, b.right);
194 return red(a.left, a.key, append(a.right, b));
196 ImmutableSet<T> middle = append(a.right, b.left);
198 return red(a.left, a.key, red(middle, b.key, b.right));
200 return red(red(a.left, a.key, middle.left), middle.key, red(middle.right, b.key, b.right));
205 public T getFirst() {
209 return left.getFirst();
212 static private <T extends Comparable<T>> ImmutableSet<T> balance(
213 ImmutableSet<T> left,
215 ImmutableSet<T> right) {
217 if(!left.left.isBlack)
221 black(left.right, key, right)
223 else if(!left.right.isBlack)
225 black(left.left, left.key, left.right.left),
227 black(left.right.right, key, right)
231 if(!right.left.isBlack)
233 black(left, key, right.left.left),
235 black(right.left.right, right.key, right.right)
237 else if(!right.right.isBlack)
239 black(left, key, right.left),
244 return black(left, key, right);
247 static private <T extends Comparable<T>> ImmutableSet<T> black(
248 ImmutableSet<T> left,
250 ImmutableSet<T> right) {
251 return new ImmutableSet<T>(left, key, right, true);
254 static private <T extends Comparable<T>> ImmutableSet<T> red(
255 ImmutableSet<T> left,
257 ImmutableSet<T> right) {
258 return new ImmutableSet<T>(left, key, right, false);
261 static private <T extends Comparable<T>> ImmutableSet<T> toBlack(ImmutableSet<T> tree) {
265 return black(tree.left, tree.key, tree.right);
268 static private <T extends Comparable<T>> ImmutableSet<T> toRed(ImmutableSet<T> tree) {
270 return red(tree.left, tree.key, tree.right);
276 static private <T extends Comparable<T>> ImmutableSet<T> balleft(
277 ImmutableSet<T> left,
279 ImmutableSet<T> right) {
282 return balance(left, key, toRed(right));
284 return red(black(left, key, right.left.left), right.left.key, balance(right.left.right, right.key, toRed(right.right)));
287 return red(toBlack(left), key, right);
290 static private <T extends Comparable<T>> ImmutableSet<T> balright(
291 ImmutableSet<T> left,
293 ImmutableSet<T> right) {
296 return balance(toRed(left), key, right);
298 return red(balance(toRed(left.left), left.key, left.right.left), left.right.key, black(left.right.right, key, right));
301 return red(left, key, toBlack(right));
304 public ImmutableSet<T> add(T obj) {
305 ImmutableSet<T> tree = addRec(obj);
310 public ImmutableSet<T> remove(T obj) {
311 ImmutableSet<T> tree = removeRec(obj);
317 return black(tree.left, tree.key, tree.right);
320 public boolean forEach(TObjectProcedure<T> procedure) {
321 if(left.forEach(procedure))
322 if(procedure.execute(key))
323 return right.forEach(procedure);
327 public ImmutableSet<T> addAll(Iterable<T> c) {
328 ImmutableSet<T> ret = this;
334 static class AddAll<T extends Comparable<T>> implements TObjectProcedure<T> {
336 ImmutableSet<T> result;
338 public AddAll(ImmutableSet<T> result) {
339 this.result = result;
343 public boolean execute(T arg0) {
344 result = result.add(arg0);
350 public ImmutableSet<T> addAll(ImmutableSet<T> c) {
355 AddAll<T> proc = new AddAll<T>(this);
360 /**************************************************************************
364 **************************************************************************
367 void print(int indentation) {
368 left.print(indentation + 1);
369 for(int i=0;i<indentation;++i)
370 System.out.print(" ");
371 System.out.println(key + " " + (isBlack ? "BLACK" : "RED"));
372 right.print(indentation + 1);
375 private int validateRec() {
378 int lh = left.validateRec();
379 int rh = right.validateRec();
381 System.out.println("Unbalanced!");
383 if(!left.isBlack || !right.isBlack)
384 System.out.println("Red under red");
391 @SuppressWarnings("unchecked")
392 public static <T extends Comparable<T>> ImmutableSet<T> empty() {
396 public void validate() {
399 System.out.println("Root is not black");
402 @SuppressWarnings("unchecked")
403 public static void main(String[] args) {
404 ImmutableSet<Integer> set = ImmutableSet.EMPTY;
405 final Set<Integer> set2 = new HashSet<Integer>();
407 Random random = new Random();
408 for(int i=0;i<10000;++i) {
409 int r1 = random.nextInt(1000);
410 int r2 = random.nextInt(1000);
412 set = set.remove(r2);
417 for(Integer v : set2)
419 System.out.println("set2 has more elements");
420 set.forEach(new TObjectProcedure<Integer>() {
423 public boolean execute(Integer arg0) {
424 if(!set2.contains(arg0))
425 System.out.println("set has more elements");
433 map.forEach(new TObjectProcedure<Integer>() {
436 public boolean execute(Integer arg0) {
437 System.out.println(arg0);