bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/persistent/ImmutableSet.java

   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
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.utils.datastructures.persistent;\r
  13 \r
  14 import gnu.trove.procedure.TObjectProcedure;\r
  15 \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
  21 \r
  22 public class ImmutableSet<T extends Comparable<T>> {\r
  23         \r
  24         @SuppressWarnings({ "rawtypes" })\r
  25         static final ImmutableSet EMPTY = new EmptyImmutableSet();\r
  26         \r
  27         private static class EmptyImmutableSet<T extends Comparable<T>> extends ImmutableSet<T> {\r
  28                 public EmptyImmutableSet() {\r
  29                         isBlack = true;\r
  30                 }\r
  31                 \r
  32                 protected org.simantics.utils.datastructures.persistent.ImmutableSet<T> addRec(T obj) {\r
  33                         return new ImmutableSet<T>(obj);\r
  34                 }\r
  35                 \r
  36                 protected org.simantics.utils.datastructures.persistent.ImmutableSet<T> removeRec(T obj) {\r
  37                         return null;\r
  38                 }\r
  39                 \r
  40                 public boolean contains(T obj) {\r
  41                         return false;\r
  42                 }\r
  43                 \r
  44                 @Override\r
  45                 public boolean forEach(TObjectProcedure<T> arg0) {\r
  46                         return true;\r
  47                 }\r
  48                 \r
  49                 @Override\r
  50                 void print(int arg0) {          \r
  51                 }\r
  52         }\r
  53         \r
  54         ImmutableSet<T> left;\r
  55         T key;\r
  56         ImmutableSet<T> right;\r
  57         boolean isBlack;\r
  58         \r
  59         protected ImmutableSet(\r
  60                         ImmutableSet<T> left,\r
  61                         T key,\r
  62                         ImmutableSet<T> right,                  \r
  63                         boolean isBlack) {\r
  64                 this.left = left;\r
  65                 this.right = right;\r
  66                 this.key = key;\r
  67                 this.isBlack = isBlack;\r
  68         }\r
  69 \r
  70         @SuppressWarnings("unchecked")\r
  71         public ImmutableSet(T key) {\r
  72                 this(EMPTY, key, EMPTY, false);\r
  73         }\r
  74         \r
  75         @SuppressWarnings("unchecked")\r
  76         public static <T extends Comparable<T>> ImmutableSet<T> of(T ... array) {\r
  77                 if(array.length == 0)\r
  78                         return EMPTY;\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
  82                 return ret;\r
  83         }\r
  84         \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
  88                 if(!it.hasNext())\r
  89                         return EMPTY;           \r
  90                 ImmutableSet<T> ret = new ImmutableSet<T>(it.next());\r
  91                 while(it.hasNext())\r
  92                         ret = ret.add(it.next());\r
  93                 return ret;\r
  94         }\r
  95 \r
  96         private ImmutableSet() {        \r
  97         }\r
  98         \r
  99         public boolean contains(T obj) {\r
 100                 int cmp = obj.compareTo(key);\r
 101                 if(cmp < 0)\r
 102                         return left.contains(obj);\r
 103                 else if(cmp > 0)\r
 104                         return right.contains(obj);\r
 105                 else\r
 106                         return true;\r
 107         }       \r
 108         \r
 109         protected ImmutableSet<T> addRec(T obj) {\r
 110                 int cmp = obj.compareTo(key);\r
 111                 if(cmp < 0) {\r
 112                         ImmutableSet<T> newLeft = left.addRec(obj);\r
 113                         if(newLeft == left)\r
 114                                 return this;                    \r
 115                         if(isBlack)\r
 116                                 return balance(newLeft, key, right);\r
 117                         else\r
 118                                 return red(newLeft, key, right);\r
 119                 }\r
 120                 else if(cmp > 0) {\r
 121                         ImmutableSet<T> newRight = right.addRec(obj);\r
 122                         if(newRight == right)\r
 123                                 return this;\r
 124                         if(isBlack)\r
 125                                 return balance(left, key, newRight);\r
 126                         else\r
 127                                 return red(left, key, newRight);\r
 128                 }\r
 129                 else\r
 130                         return this;\r
 131         }\r
 132         \r
 133         /**\r
 134          * Assumes this is a black nonempty node. \r
 135          * \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
 138          * removed).\r
 139          *   \r
 140          * @param obj\r
 141          * @return\r
 142          */\r
 143         protected ImmutableSet<T> removeRec(T obj) {            \r
 144                 int cmp = obj.compareTo(key);\r
 145                 if(cmp < 0) {\r
 146                         ImmutableSet<T> newLeft = left.removeRec(obj);\r
 147                         if(newLeft == null)\r
 148                                 return null;\r
 149                         else if(left.isBlack)\r
 150                                 return balleft(newLeft, key, right);\r
 151                         else\r
 152                                 return red(newLeft, key, right);\r
 153                 }\r
 154                 else if(cmp > 0) {\r
 155                         ImmutableSet<T> newRight = right.removeRec(obj);\r
 156                         if(newRight == null)\r
 157                                 return null;\r
 158                         else if(right.isBlack)\r
 159                                 return balright(left, key, newRight);\r
 160                         else\r
 161                                 return red(left, key, newRight);                        \r
 162                 }\r
 163                 else\r
 164                         return append(left, right);\r
 165         }\r
 166         \r
 167         /**\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
 170          * \r
 171          * @param <T>\r
 172          * @param a\r
 173          * @param b\r
 174          * @return\r
 175          */\r
 176         protected static <T extends Comparable<T>> ImmutableSet<T> append(ImmutableSet<T> a, ImmutableSet<T> b) {\r
 177                 if(a==EMPTY)\r
 178                         return b;\r
 179                 if(b==EMPTY)\r
 180                         return a;\r
 181                 if(a.isBlack) {\r
 182                         if(b.isBlack) {\r
 183                                 ImmutableSet<T> middle = append(a.right, b.left);\r
 184                                 if(middle.isBlack)\r
 185                                         return balleft(a.left, a.key, black(middle, b.key, b.right));\r
 186                                 else\r
 187                                         return red(black(a.left, a.key, middle.left), middle.key, black(middle.right, b.key, b.right));\r
 188                         }\r
 189                         else\r
 190                                 return red(append(a, b.left), b.key, b.right);\r
 191                 }\r
 192                 else {\r
 193                         if(b.isBlack)\r
 194                                 return red(a.left, a.key, append(a.right, b));\r
 195                         else {\r
 196                                 ImmutableSet<T> middle = append(a.right, b.left);\r
 197                                 if(middle.isBlack)\r
 198                                         return red(a.left, a.key, red(middle, b.key, b.right));\r
 199                                 else\r
 200                                         return red(red(a.left, a.key, middle.left), middle.key, red(middle.right, b.key, b.right));\r
 201                         }\r
 202                 }\r
 203         }\r
 204         \r
 205         public T getFirst() {\r
 206                 if(left == EMPTY)\r
 207                         return key;\r
 208                 else\r
 209                         return left.getFirst();\r
 210         }       \r
 211         \r
 212         static private <T extends Comparable<T>> ImmutableSet<T> balance(\r
 213                         ImmutableSet<T> left,\r
 214                         T key,\r
 215                         ImmutableSet<T> right) {\r
 216                 if(!left.isBlack) {\r
 217                         if(!left.left.isBlack) \r
 218                                 return red(\r
 219                                         toBlack(left.left),\r
 220                                         left.key,\r
 221                                         black(left.right, key, right)\r
 222                                 );\r
 223                         else if(!left.right.isBlack)\r
 224                                 return red(\r
 225                                         black(left.left, left.key, left.right.left),\r
 226                                         left.right.key,\r
 227                                         black(left.right.right, key, right)                                     \r
 228                                 );                              \r
 229                 }\r
 230                 if(!right.isBlack) {\r
 231                         if(!right.left.isBlack)\r
 232                                 return red(\r
 233                                         black(left, key, right.left.left),\r
 234                                         right.left.key,\r
 235                                         black(right.left.right, right.key, right.right)\r
 236                                 );\r
 237                         else if(!right.right.isBlack)\r
 238                                 return red(\r
 239                                         black(left, key, right.left),\r
 240                                         right.key,\r
 241                                         toBlack(right.right)\r
 242                                 );              \r
 243                 }\r
 244                 return black(left, key, right);\r
 245         }\r
 246         \r
 247         static private <T extends Comparable<T>> ImmutableSet<T> black(\r
 248                         ImmutableSet<T> left,\r
 249                         T key,\r
 250                         ImmutableSet<T> right) {\r
 251                 return new ImmutableSet<T>(left, key, right, true);\r
 252         }\r
 253         \r
 254         static private <T extends Comparable<T>> ImmutableSet<T> red(\r
 255                         ImmutableSet<T> left,\r
 256                         T key,\r
 257                         ImmutableSet<T> right) {\r
 258                 return new ImmutableSet<T>(left, key, right, false);\r
 259         }\r
 260         \r
 261         static private <T extends Comparable<T>> ImmutableSet<T> toBlack(ImmutableSet<T> tree) {\r
 262                 if(tree.isBlack)\r
 263                         return tree;\r
 264                 else\r
 265                         return black(tree.left, tree.key, tree.right);\r
 266         }\r
 267         \r
 268         static private <T extends Comparable<T>> ImmutableSet<T> toRed(ImmutableSet<T> tree) {\r
 269                 if(tree.isBlack)\r
 270                         return red(tree.left, tree.key, tree.right);\r
 271                 else\r
 272                         return tree;\r
 273         }\r
 274                         \r
 275         \r
 276         static private <T extends Comparable<T>> ImmutableSet<T> balleft(\r
 277                         ImmutableSet<T> left,\r
 278                         T key,\r
 279                         ImmutableSet<T> right) {\r
 280                 if(left.isBlack) {\r
 281                         if(right.isBlack)\r
 282                                 return balance(left, key, toRed(right));\r
 283                         else\r
 284                                 return red(black(left, key, right.left.left), right.left.key, balance(right.left.right, right.key, toRed(right.right)));\r
 285                 }\r
 286                 else\r
 287                         return red(toBlack(left), key, right);\r
 288         }\r
 289         \r
 290         static private <T extends Comparable<T>> ImmutableSet<T> balright(\r
 291                         ImmutableSet<T> left,\r
 292                         T key,\r
 293                         ImmutableSet<T> right) {\r
 294                 if(right.isBlack) {\r
 295                         if(left.isBlack)\r
 296                                 return balance(toRed(left), key, right);\r
 297                         else\r
 298                                 return red(balance(toRed(left.left), left.key, left.right.left), left.right.key, black(left.right.right, key, right));\r
 299                 }\r
 300                 else\r
 301                         return red(left, key, toBlack(right));\r
 302         }\r
 303 \r
 304         public ImmutableSet<T> add(T obj) {\r
 305                 ImmutableSet<T> tree = addRec(obj);\r
 306                 tree.isBlack = true;\r
 307                 return tree;\r
 308         }\r
 309 \r
 310         public ImmutableSet<T> remove(T obj) {\r
 311                 ImmutableSet<T> tree = removeRec(obj);\r
 312                 if(tree == null)\r
 313                         return this;\r
 314                 if(tree.isBlack)\r
 315                         return tree;\r
 316                 else\r
 317                         return black(tree.left, tree.key, tree.right);\r
 318         }\r
 319 \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
 324                 return false;\r
 325         }\r
 326         \r
 327         public ImmutableSet<T> addAll(Iterable<T> c) {\r
 328                 ImmutableSet<T> ret = this;\r
 329                 for(T t : c)\r
 330                         ret = ret.add(t);\r
 331                 return ret;\r
 332         }\r
 333         \r
 334         static class AddAll<T extends Comparable<T>> implements TObjectProcedure<T> {\r
 335 \r
 336                 ImmutableSet<T> result;         \r
 337                 \r
 338                 public AddAll(ImmutableSet<T> result) {\r
 339                         this.result = result;\r
 340                 }\r
 341 \r
 342                 @Override\r
 343                 public boolean execute(T arg0) {\r
 344                         result = result.add(arg0);\r
 345                         return true;\r
 346                 }\r
 347                 \r
 348         }\r
 349         \r
 350         public ImmutableSet<T> addAll(ImmutableSet<T> c) {\r
 351                 if(this==EMPTY)\r
 352                         return c;\r
 353                 if(c==EMPTY)\r
 354                         return this;\r
 355                 AddAll<T> proc = new AddAll<T>(this);\r
 356                 c.forEach(proc);\r
 357                 return proc.result;\r
 358         }\r
 359         \r
 360         /**************************************************************************\r
 361          * \r
 362          *  Testing\r
 363          * \r
 364          ************************************************************************** \r
 365          */\r
 366         \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
 373         }\r
 374         \r
 375         private int validateRec() {\r
 376                 if(this==EMPTY)\r
 377                         return 1;\r
 378                 int lh = left.validateRec();\r
 379                 int rh = right.validateRec();\r
 380                 if(lh != rh)\r
 381                         System.out.println("Unbalanced!");\r
 382                 if(!isBlack) {\r
 383                         if(!left.isBlack || !right.isBlack)\r
 384                                 System.out.println("Red under red");\r
 385                         return lh;\r
 386                 }\r
 387                 else\r
 388                         return lh+1;\r
 389         }       \r
 390 \r
 391         @SuppressWarnings("unchecked")\r
 392         public static <T extends Comparable<T>> ImmutableSet<T> empty() {\r
 393                 return EMPTY;\r
 394         }\r
 395         \r
 396         public void validate() {\r
 397                 validateRec();\r
 398                 if(!isBlack)\r
 399                         System.out.println("Root is not black");\r
 400         }\r
 401 \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
 406 \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
 411                         set = set.add(r1);\r
 412                         set = set.remove(r2);\r
 413                         set2.add(r1);\r
 414                         set2.remove(r2);\r
 415                         set.validate();                 \r
 416                         \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
 421 \r
 422                                 @Override\r
 423                                 public boolean execute(Integer arg0) {\r
 424                                         if(!set2.contains(arg0))\r
 425                                                 System.out.println("set has more elements");\r
 426                                         return true;\r
 427                                 }\r
 428                                 \r
 429                         });\r
 430                 }\r
 431                                         \r
 432                 /*\r
 433                 map.forEach(new TObjectProcedure<Integer>() {\r
 434 \r
 435                         @Override\r
 436                         public boolean execute(Integer arg0) {\r
 437                                 System.out.println(arg0);\r
 438                                 return true;\r
 439                         }\r
 440                         \r
 441                 });\r
 442                 */\r
 443         }\r
 444         \r
 445 }\r