bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/persistent/ImmutableMap.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.TObjectObjectProcedure;\r
  15 \r
  16 public class ImmutableMap<T extends Comparable<T>, V> {\r
  17         \r
  18         @SuppressWarnings({ "rawtypes" })\r
  19         static final ImmutableMap EMPTY = new EmptyImmutableSet();\r
  20         \r
  21         private static class EmptyImmutableSet<T extends Comparable<T>, V> extends ImmutableMap<T, V> {\r
  22                 public EmptyImmutableSet() {\r
  23                         isBlack = true;\r
  24                 }\r
  25                 \r
  26                 protected ImmutableMap<T, V> putRec(T key, V value) {\r
  27                         return new ImmutableMap<T, V>(key, value);\r
  28                 }\r
  29                 \r
  30                 protected ImmutableMap<T, V> removeRec(T obj) {\r
  31                         return null;\r
  32                 }\r
  33                 \r
  34                 public boolean contains(T obj) {\r
  35                         return false;\r
  36                 }\r
  37         \r
  38                 public V get(T key) {\r
  39                         return null;\r
  40                 }\r
  41                 \r
  42                 @Override\r
  43                 public boolean forEach(TObjectObjectProcedure<T, V> arg0) {\r
  44                         return true;\r
  45                 }\r
  46         }\r
  47         \r
  48         ImmutableMap<T, V> left;\r
  49         T key;\r
  50         V value;\r
  51         ImmutableMap<T, V> right;\r
  52         boolean isBlack;\r
  53         \r
  54         protected ImmutableMap(\r
  55                         ImmutableMap<T, V> left,\r
  56                         T key,\r
  57                         V value,\r
  58                         ImmutableMap<T, V> right,                       \r
  59                         boolean isBlack) {\r
  60                 this.left = left;\r
  61                 this.right = right;\r
  62                 this.key = key;\r
  63                 this.value = value;\r
  64                 this.isBlack = isBlack;\r
  65         }\r
  66 \r
  67         @SuppressWarnings("unchecked")\r
  68         public ImmutableMap(T key, V value) {\r
  69                 this(EMPTY, key, value, EMPTY, false);\r
  70         }               \r
  71 \r
  72         private ImmutableMap() {        \r
  73         }\r
  74         \r
  75         public boolean contains(T obj) {\r
  76                 int cmp = obj.compareTo(key);\r
  77                 if(cmp < 0)\r
  78                         return left.contains(obj);\r
  79                 else if(cmp > 0)\r
  80                         return right.contains(obj);\r
  81                 else\r
  82                         return true;\r
  83         }       \r
  84         \r
  85         public V get(T key) {\r
  86                 int cmp = key.compareTo(key);\r
  87                 if(cmp < 0)\r
  88                         return left.get(key);\r
  89                 else if(cmp > 0)\r
  90                         return right.get(key);\r
  91                 else\r
  92                         return value;\r
  93         }       \r
  94         \r
  95         protected ImmutableMap<T, V> putRec(T obj, V value) {\r
  96                 int cmp = obj.compareTo(key);\r
  97                 if(cmp < 0) {\r
  98                         ImmutableMap<T, V> newLeft = left.putRec(obj, value);\r
  99                         if(newLeft == left)\r
 100                                 return this;                    \r
 101                         if(isBlack)\r
 102                                 return balance(newLeft, key, value, right);\r
 103                         else\r
 104                                 return red(newLeft, key, value, right);\r
 105                 }\r
 106                 else if(cmp > 0) {\r
 107                         ImmutableMap<T, V> newRight = right.putRec(obj, value);\r
 108                         if(newRight == right)\r
 109                                 return this;\r
 110                         if(isBlack)\r
 111                                 return balance(left, key, value, newRight);\r
 112                         else\r
 113                                 return red(left, key, value, newRight);\r
 114                 }\r
 115                 else\r
 116                         return this;\r
 117         }\r
 118         \r
 119         /**\r
 120          * Assumes this is a black nonempty node. \r
 121          * \r
 122          * Removes obj from the tree. The returned tree has always\r
 123          * one black node less in every branch (even if nothing is\r
 124          * removed).\r
 125          *   \r
 126          * @param obj\r
 127          * @return\r
 128          */\r
 129         protected ImmutableMap<T, V> removeRec(T obj) {         \r
 130                 int cmp = obj.compareTo(key);\r
 131                 if(cmp < 0) {\r
 132                         ImmutableMap<T, V> newLeft = left.removeRec(obj);\r
 133                         if(newLeft == null)\r
 134                                 return null;\r
 135                         else if(left.isBlack)\r
 136                                 return balleft(newLeft, key, value, right);\r
 137                         else\r
 138                                 return red(newLeft, key, value, right);\r
 139                 }\r
 140                 else if(cmp > 0) {\r
 141                         ImmutableMap<T, V> newRight = right.removeRec(obj);\r
 142                         if(newRight == null)\r
 143                                 return null;\r
 144                         else if(right.isBlack)\r
 145                                 return balright(left, key, value, newRight);\r
 146                         else\r
 147                                 return red(left, key, value, newRight);                 \r
 148                 }\r
 149                 else\r
 150                         return append(left, right);\r
 151         }\r
 152         \r
 153         /**\r
 154          * Assumes a and b have the same black depth and keys in a are strictly less\r
 155          * than keys in b. Creates a new tree with the same black depth as a and b. \r
 156          * \r
 157          * @param <T>\r
 158          * @param a\r
 159          * @param b\r
 160          * @return\r
 161          */\r
 162         protected static <T extends Comparable<T>, V> ImmutableMap<T, V> append(ImmutableMap<T, V> a, ImmutableMap<T, V> b) {\r
 163                 if(a==EMPTY)\r
 164                         return b;\r
 165                 if(b==EMPTY)\r
 166                         return a;\r
 167                 if(a.isBlack) {\r
 168                         if(b.isBlack) {\r
 169                                 ImmutableMap<T, V> middle = append(a.right, b.left);\r
 170                                 if(middle.isBlack)\r
 171                                         return balleft(a.left, a.key, a.value, black(middle, b.key, b.value, b.right));\r
 172                                 else\r
 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));\r
 174                         }\r
 175                         else\r
 176                                 return red(append(a, b.left), b.key, b.value, b.right);\r
 177                 }\r
 178                 else {\r
 179                         if(b.isBlack)\r
 180                                 return red(a.left, a.key, a.value, append(a.right, b));\r
 181                         else {\r
 182                                 ImmutableMap<T, V> middle = append(a.right, b.left);\r
 183                                 if(middle.isBlack)\r
 184                                         return red(a.left, a.key, a.value, red(middle, b.key, b.value, b.right));\r
 185                                 else\r
 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));\r
 187                         }\r
 188                 }\r
 189         }\r
 190         \r
 191         public T getFirst() {\r
 192                 if(left == EMPTY)\r
 193                         return key;\r
 194                 else\r
 195                         return left.getFirst();\r
 196         }       \r
 197         \r
 198         static private <T extends Comparable<T>, V> ImmutableMap<T, V> balance(\r
 199                         ImmutableMap<T, V> left,\r
 200                         T key,\r
 201                         V value,\r
 202                         ImmutableMap<T, V> right) {\r
 203                 if(!left.isBlack) {\r
 204                         if(!left.left.isBlack) \r
 205                                 return red(\r
 206                                         toBlack(left.left),\r
 207                                         left.key,\r
 208                                         left.value,\r
 209                                         black(left.right, key, value, right)\r
 210                                 );\r
 211                         else if(!left.right.isBlack)\r
 212                                 return red(\r
 213                                         black(left.left, left.key, left.value, left.right.left),\r
 214                                         left.right.key, left.right.value,\r
 215                                         black(left.right.right, key, value, right)                                      \r
 216                                 );                              \r
 217                 }\r
 218                 if(!right.isBlack) {\r
 219                         if(!right.left.isBlack)\r
 220                                 return red(\r
 221                                         black(left, key, value, right.left.left),\r
 222                                         right.left.key, right.left.value,\r
 223                                         black(right.left.right, right.key, right.value, right.right)\r
 224                                 );\r
 225                         else if(!right.right.isBlack)\r
 226                                 return red(\r
 227                                         black(left, key, value, right.left),\r
 228                                         right.key,\r
 229                                         right.value,\r
 230                                         toBlack(right.right)\r
 231                                 );              \r
 232                 }\r
 233                 return black(left, key, value, right);\r
 234         }\r
 235         \r
 236         static private <T extends Comparable<T>, V> ImmutableMap<T, V> black(\r
 237                         ImmutableMap<T, V> left,\r
 238                         T key,\r
 239                         V value,\r
 240                         ImmutableMap<T, V> right) {\r
 241                 return new ImmutableMap<T, V>(left, key, value, right, true);\r
 242         }\r
 243         \r
 244         static private <T extends Comparable<T>, V> ImmutableMap<T, V> red(\r
 245                         ImmutableMap<T, V> left,\r
 246                         T key,\r
 247                         V value,\r
 248                         ImmutableMap<T, V> right) {\r
 249                 return new ImmutableMap<T, V>(left, key, value, right, false);\r
 250         }\r
 251         \r
 252         static private <T extends Comparable<T>, V> ImmutableMap<T, V> toBlack(ImmutableMap<T, V> tree) {\r
 253                 if(tree.isBlack)\r
 254                         return tree;\r
 255                 else\r
 256                         return black(tree.left, tree.key, tree.value, tree.right);\r
 257         }\r
 258         \r
 259         static private <T extends Comparable<T>, V> ImmutableMap<T, V> toRed(ImmutableMap<T, V> tree) {\r
 260                 if(tree.isBlack)\r
 261                         return red(tree.left, tree.key, tree.value, tree.right);\r
 262                 else\r
 263                         return tree;\r
 264         }\r
 265                         \r
 266         \r
 267         static private <T extends Comparable<T>, V> ImmutableMap<T, V> balleft(\r
 268                         ImmutableMap<T, V> left,\r
 269                         T key,\r
 270                         V value,\r
 271                         ImmutableMap<T, V> right) {\r
 272                 if(left.isBlack) {\r
 273                         if(right.isBlack)\r
 274                                 return balance(left, key, value, toRed(right));\r
 275                         else\r
 276                                 return red(black(left, key, value, right.left.left), right.left.key, right.left.value,\r
 277                                         balance(right.left.right, right.key, right.value, toRed(right.right)));\r
 278                 }\r
 279                 else\r
 280                         return red(toBlack(left), key, value, right);\r
 281         }\r
 282         \r
 283         static private <T extends Comparable<T>, V> ImmutableMap<T, V> balright(\r
 284                         ImmutableMap<T, V> left,\r
 285                         T key,\r
 286                         V value,\r
 287                         ImmutableMap<T, V> right) {\r
 288                 if(right.isBlack) {\r
 289                         if(left.isBlack)\r
 290                                 return balance(toRed(left), key, value, right);\r
 291                         else\r
 292                                 return red(balance(toRed(left.left), left.key, left.value, left.right.left), left.right.key, left.right.value,\r
 293                                         black(left.right.right, key, value, right));\r
 294                 }\r
 295                 else\r
 296                         return red(left, key, value, toBlack(right));\r
 297         }\r
 298 \r
 299         public ImmutableMap<T, V> put(T key, V value) {\r
 300                 ImmutableMap<T, V> tree = putRec(key, value);\r
 301                 tree.isBlack = true;\r
 302                 return tree;\r
 303         }\r
 304 \r
 305         public ImmutableMap<T, V> remove(T obj) {\r
 306                 ImmutableMap<T, V> tree = removeRec(obj);\r
 307                 if(tree == null)\r
 308                         return this;\r
 309                 if(tree.isBlack)\r
 310                         return tree;\r
 311                 else\r
 312                         return black(tree.left, tree.key, tree.value, tree.right);\r
 313         }\r
 314         \r
 315         public boolean forEach(TObjectObjectProcedure<T, V> proc) {\r
 316                 if(left.forEach(proc))\r
 317                         if(proc.execute(key, value))\r
 318                                 return right.forEach(proc);\r
 319                 return false;\r
 320         }       \r
 321                         \r
 322 }\r