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.TObjectObjectProcedure;
16 public class ImmutableMap<T extends Comparable<T>, V> {
18 @SuppressWarnings({ "rawtypes" })
19 static final ImmutableMap EMPTY = new EmptyImmutableSet();
21 private static class EmptyImmutableSet<T extends Comparable<T>, V> extends ImmutableMap<T, V> {
22 public EmptyImmutableSet() {
26 protected ImmutableMap<T, V> putRec(T key, V value) {
27 return new ImmutableMap<T, V>(key, value);
30 protected ImmutableMap<T, V> removeRec(T obj) {
34 public boolean contains(T obj) {
43 public boolean forEach(TObjectObjectProcedure<T, V> arg0) {
48 ImmutableMap<T, V> left;
51 ImmutableMap<T, V> right;
54 protected ImmutableMap(
55 ImmutableMap<T, V> left,
58 ImmutableMap<T, V> right,
64 this.isBlack = isBlack;
67 @SuppressWarnings("unchecked")
68 public ImmutableMap(T key, V value) {
69 this(EMPTY, key, value, EMPTY, false);
72 private ImmutableMap() {
75 public boolean contains(T obj) {
76 int cmp = obj.compareTo(key);
78 return left.contains(obj);
80 return right.contains(obj);
86 int cmp = key.compareTo(key);
90 return right.get(key);
95 protected ImmutableMap<T, V> putRec(T obj, V value) {
96 int cmp = obj.compareTo(key);
98 ImmutableMap<T, V> newLeft = left.putRec(obj, value);
102 return balance(newLeft, key, value, right);
104 return red(newLeft, key, value, right);
107 ImmutableMap<T, V> newRight = right.putRec(obj, value);
108 if(newRight == right)
111 return balance(left, key, value, newRight);
113 return red(left, key, value, newRight);
120 * Assumes this is a black nonempty node.
122 * Removes obj from the tree. The returned tree has always
123 * one black node less in every branch (even if nothing is
129 protected ImmutableMap<T, V> removeRec(T obj) {
130 int cmp = obj.compareTo(key);
132 ImmutableMap<T, V> newLeft = left.removeRec(obj);
135 else if(left.isBlack)
136 return balleft(newLeft, key, value, right);
138 return red(newLeft, key, value, right);
141 ImmutableMap<T, V> newRight = right.removeRec(obj);
144 else if(right.isBlack)
145 return balright(left, key, value, newRight);
147 return red(left, key, value, newRight);
150 return append(left, right);
154 * Assumes a and b have the same black depth and keys in a are strictly less
155 * than keys in b. Creates a new tree with the same black depth as a and b.
162 protected static <T extends Comparable<T>, V> ImmutableMap<T, V> append(ImmutableMap<T, V> a, ImmutableMap<T, V> b) {
169 ImmutableMap<T, V> middle = append(a.right, b.left);
171 return balleft(a.left, a.key, a.value, black(middle, b.key, b.value, b.right));
173 return red(black(a.left, a.key, a.value, middle.left), middle.key, middle.value, black(middle.right, b.key, b.value, b.right));
176 return red(append(a, b.left), b.key, b.value, b.right);
180 return red(a.left, a.key, a.value, append(a.right, b));
182 ImmutableMap<T, V> middle = append(a.right, b.left);
184 return red(a.left, a.key, a.value, red(middle, b.key, b.value, b.right));
186 return red(red(a.left, a.key, a.value, middle.left), middle.key, middle.value, red(middle.right, b.key, b.value, b.right));
191 public T getFirst() {
195 return left.getFirst();
198 static private <T extends Comparable<T>, V> ImmutableMap<T, V> balance(
199 ImmutableMap<T, V> left,
202 ImmutableMap<T, V> right) {
204 if(!left.left.isBlack)
209 black(left.right, key, value, right)
211 else if(!left.right.isBlack)
213 black(left.left, left.key, left.value, left.right.left),
214 left.right.key, left.right.value,
215 black(left.right.right, key, value, right)
219 if(!right.left.isBlack)
221 black(left, key, value, right.left.left),
222 right.left.key, right.left.value,
223 black(right.left.right, right.key, right.value, right.right)
225 else if(!right.right.isBlack)
227 black(left, key, value, right.left),
233 return black(left, key, value, right);
236 static private <T extends Comparable<T>, V> ImmutableMap<T, V> black(
237 ImmutableMap<T, V> left,
240 ImmutableMap<T, V> right) {
241 return new ImmutableMap<T, V>(left, key, value, right, true);
244 static private <T extends Comparable<T>, V> ImmutableMap<T, V> red(
245 ImmutableMap<T, V> left,
248 ImmutableMap<T, V> right) {
249 return new ImmutableMap<T, V>(left, key, value, right, false);
252 static private <T extends Comparable<T>, V> ImmutableMap<T, V> toBlack(ImmutableMap<T, V> tree) {
256 return black(tree.left, tree.key, tree.value, tree.right);
259 static private <T extends Comparable<T>, V> ImmutableMap<T, V> toRed(ImmutableMap<T, V> tree) {
261 return red(tree.left, tree.key, tree.value, tree.right);
267 static private <T extends Comparable<T>, V> ImmutableMap<T, V> balleft(
268 ImmutableMap<T, V> left,
271 ImmutableMap<T, V> right) {
274 return balance(left, key, value, toRed(right));
276 return red(black(left, key, value, right.left.left), right.left.key, right.left.value,
277 balance(right.left.right, right.key, right.value, toRed(right.right)));
280 return red(toBlack(left), key, value, right);
283 static private <T extends Comparable<T>, V> ImmutableMap<T, V> balright(
284 ImmutableMap<T, V> left,
287 ImmutableMap<T, V> right) {
290 return balance(toRed(left), key, value, right);
292 return red(balance(toRed(left.left), left.key, left.value, left.right.left), left.right.key, left.right.value,
293 black(left.right.right, key, value, right));
296 return red(left, key, value, toBlack(right));
299 public ImmutableMap<T, V> put(T key, V value) {
300 ImmutableMap<T, V> tree = putRec(key, value);
305 public ImmutableMap<T, V> remove(T obj) {
306 ImmutableMap<T, V> tree = removeRec(obj);
312 return black(tree.left, tree.key, tree.value, tree.right);
315 public boolean forEach(TObjectObjectProcedure<T, V> proc) {
316 if(left.forEach(proc))
317 if(proc.execute(key, value))
318 return right.forEach(proc);