bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/LightweightList.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.collections;\r
  13 \r
  14 import java.util.Arrays;\r
  15 \r
  16 \r
  17 public class LightweightList {\r
  18 \r
  19         public static final Object EMPTY = new LL0();\r
  20         \r
  21         public static Object add(Object list, Object value) {\r
  22                 if(list instanceof LL)\r
  23                         return ((LL)list).add(value);\r
  24                 else\r
  25                         return new LL2(list, value);\r
  26         }\r
  27         \r
  28         public static Object remove(Object list, Object value) {\r
  29                 if(list instanceof LL)\r
  30                         return ((LL)list).remove(value);\r
  31                 else\r
  32                         return value.equals(list) ? EMPTY : list;\r
  33         }\r
  34 \r
  35         public static int size(Object list) {\r
  36                 if(list instanceof LL)\r
  37                         return ((LL)list).size();\r
  38                 else\r
  39                         return 1;\r
  40         }\r
  41         \r
  42         public static boolean isEmpty(Object list) {\r
  43                 return list==EMPTY;\r
  44         }        \r
  45         \r
  46         public static Object[] toArray(Object list) {\r
  47                 if(list == null)\r
  48                         return EMPTY_ARRAY;\r
  49                 else if(list instanceof LL)\r
  50                         return ((LL)list).toArray();\r
  51                 else\r
  52                         return new Object[] { list };\r
  53         }\r
  54         \r
  55         public static interface IProcedure {\r
  56                 void exec(Object obj);\r
  57         }\r
  58         \r
  59         public static void forEach(Object list, IProcedure proc) {\r
  60                 if(list == null)\r
  61                         return;\r
  62                 else if(list instanceof LL)\r
  63                         ((LL)list).forEach(proc);\r
  64                 else\r
  65                         proc.exec(list);\r
  66         }\r
  67         \r
  68         private static interface LL {\r
  69                 Object add(Object value);\r
  70                 Object remove(Object value);\r
  71                 int size();\r
  72                 Object[] toArray();\r
  73                 void forEach(IProcedure proc);\r
  74         }\r
  75         \r
  76         static final Object[] EMPTY_ARRAY = new Object[0];\r
  77         private static class LL0 implements LL {                \r
  78 \r
  79                 @Override\r
  80                 public Object add(Object value) {\r
  81                         return value;\r
  82                 }\r
  83 \r
  84                 @Override\r
  85                 public Object remove(Object value) {\r
  86                         return this;\r
  87                 }\r
  88 \r
  89                 @Override\r
  90                 public int size() {\r
  91                         return 0;\r
  92                 }\r
  93 \r
  94                 @Override\r
  95                 public Object[] toArray() {\r
  96                         return EMPTY_ARRAY;\r
  97                 }\r
  98 \r
  99                 @Override\r
 100                 public void forEach(IProcedure proc) {\r
 101                 }\r
 102                 \r
 103         }\r
 104         \r
 105         private static class LL2 implements LL {\r
 106 \r
 107                 Object v0, v1;          \r
 108                 \r
 109                 public LL2(Object v0, Object v1) {\r
 110                         this.v0 = v0;\r
 111                         this.v1 = v1;\r
 112                 }\r
 113 \r
 114                 @Override\r
 115                 public Object add(Object value) {\r
 116                         return new LL3(v0, v1, value);\r
 117                 }\r
 118 \r
 119                 @Override\r
 120                 public Object remove(Object value) {\r
 121                         if(value.equals(v0))\r
 122                                 return v1;\r
 123                         else if(value.equals(v1))\r
 124                                 return v0;\r
 125                         else\r
 126                                 return this;\r
 127                 }\r
 128 \r
 129                 @Override\r
 130                 public int size() {\r
 131                         return 2;\r
 132                 }\r
 133 \r
 134                 @Override\r
 135                 public Object[] toArray() {\r
 136                         return new Object[] { v0, v1 };\r
 137                 }\r
 138 \r
 139                 @Override\r
 140                 public void forEach(IProcedure proc) {\r
 141                         proc.exec(v0);\r
 142                         proc.exec(v1);\r
 143                 }\r
 144                 \r
 145         }\r
 146         \r
 147         private static class LL3 implements LL {\r
 148 \r
 149                 Object v0, v1, v2;              \r
 150                 \r
 151                 public LL3(Object v0, Object v1, Object v2) {\r
 152                         this.v0 = v0;\r
 153                         this.v1 = v1;\r
 154                         this.v2 = v2;\r
 155                 }\r
 156 \r
 157                 @Override\r
 158                 public Object add(Object value) {\r
 159                         return new LLN(v0, v1, v2, value);\r
 160                 }\r
 161 \r
 162                 @Override\r
 163                 public Object remove(Object value) {\r
 164                         if(value.equals(v0))\r
 165                                 return new LL2(v1, v2);\r
 166                         else if(value.equals(v1))\r
 167                                 return new LL2(v0, v2);\r
 168                         else if(value.equals(v2))\r
 169                                 return new LL2(v0, v1);\r
 170                         else\r
 171                                 return this;\r
 172                 }\r
 173 \r
 174                 @Override\r
 175                 public int size() {\r
 176                         return 3;\r
 177                 }\r
 178                 \r
 179                 @Override\r
 180                 public Object[] toArray() {\r
 181                         return new Object[] { v0, v1, v2 };\r
 182                 }\r
 183                 \r
 184                 @Override\r
 185                 public void forEach(IProcedure proc) {\r
 186                         proc.exec(v0);\r
 187                         proc.exec(v1);\r
 188                         proc.exec(v2);\r
 189                 }\r
 190         }\r
 191         \r
 192         private static class LLN implements LL {\r
 193 \r
 194                 Object[] array;\r
 195                 int size;\r
 196                 \r
 197                 public LLN(Object v0, Object v1, Object v2, Object v3) {\r
 198                         array = new Object[] { v0, v1, v2, v3, null, null };\r
 199                         size = 4;\r
 200                 }\r
 201 \r
 202                 @Override\r
 203                 public Object add(Object value) {\r
 204                         if(size==array.length)\r
 205                                 array = Arrays.copyOf(array, (size*3)/2+1);                     \r
 206                         array[size++] = value;\r
 207                         return this;\r
 208                 }\r
 209 \r
 210                 @Override\r
 211                 public Object remove(Object value) {\r
 212                         for(int i=0;i<size;++i) {\r
 213                                 if(value.equals(array[i])) {\r
 214                                         while(i < size-1) { \r
 215                                                 array[i] = array[i+1];\r
 216                                                 ++i;\r
 217                                         }\r
 218                                         array[--size] = null;\r
 219                                         if(size == 3)\r
 220                                                 return new LL3(array[0], array[1], array[2]);\r
 221                                         else\r
 222                                                 return this;\r
 223                                 }\r
 224                         }\r
 225                         return this;                    \r
 226                 }\r
 227 \r
 228                 @Override\r
 229                 public int size() {\r
 230                         return size;\r
 231                 }\r
 232                 \r
 233                 @Override\r
 234                 public Object[] toArray() {\r
 235                         return Arrays.copyOf(array, size);\r
 236                 }\r
 237                 \r
 238                 @Override\r
 239                 public void forEach(IProcedure proc) {\r
 240                         for(int i=0;i<size;++i)\r
 241                                 proc.exec(array[i]);\r
 242                 }\r
 243         }       \r
 244         \r
 245 }\r