bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/LightweightList.java

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