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