platform/util/src/com/intellij/util/SmartList.java

   1 /*
   2  * Copyright 2000-2014 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.util;
  17
  18 import com.intellij.util.containers.EmptyIterator;
  19 import com.intellij.util.containers.SingletonIteratorBase;
  20 import org.jetbrains.annotations.NotNull;
  21
  22 import java.lang.reflect.Array;
  23 import java.util.*;
  24
  25 /**
  26  * A List which is optimised for the sizes of 0 and 1,
  27  * in which cases it would not allocate array at all.
  28  */
  29 @SuppressWarnings({"unchecked"})
  30 public class SmartList<E> extends AbstractList<E> implements RandomAccess {
  31   private int mySize = 0;
  32   private Object myElem = null; // null if mySize==0, (E)elem if mySize==1, Object[] if mySize>=2
  33
  34   public SmartList() { }
  35
  36   public SmartList(E element) {
  37     add(element);
  38   }
  39
  40   public SmartList(@NotNull Collection<? extends E> elements) {
  41     int size = elements.size();
  42     if (size == 1) {
  43       E element = elements instanceof List ? (E)((List)elements).get(0) : elements.iterator().next();
  44       add(element);
  45     }
  46     else if (size > 0) {
  47       mySize = size;
  48       myElem = elements.toArray(new Object[size]);
  49     }
  50   }
  51
  52   public SmartList(@NotNull E... elements) {
  53     if (elements.length == 1) {
  54       add(elements[0]);
  55     }
  56     else if (elements.length > 0) {
  57       mySize = elements.length;
  58       myElem = Arrays.copyOf(elements, mySize);
  59     }
  60   }
  61
  62   @Override
  63   public E get(int index) {
  64     if (index < 0 || index >= mySize) {
  65       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
  66     }
  67     if (mySize == 1) {
  68       return (E)myElem;
  69     }
  70     return (E)((Object[])myElem)[index];
  71   }
  72
  73   @Override
  74   public boolean add(E e) {
  75     if (mySize == 0) {
  76       myElem = e;
  77     }
  78     else if (mySize == 1) {
  79       Object[] array = new Object[2];
  80       array[0] = myElem;
  81       array[1] = e;
  82       myElem = array;
  83     }
  84     else {
  85       Object[] array = (Object[])myElem;
  86       int oldCapacity = array.length;
  87       if (mySize >= oldCapacity) {
  88         // have to resize
  89         int newCapacity = oldCapacity * 3 / 2 + 1;
  90         int minCapacity = mySize + 1;
  91         if (newCapacity < minCapacity) {
  92           newCapacity = minCapacity;
  93         }
  94         Object[] oldArray = array;
  95         myElem = array = new Object[newCapacity];
  96         System.arraycopy(oldArray, 0, array, 0, oldCapacity);
  97       }
  98       array[mySize] = e;
  99     }
 100
 101     mySize++;
 102     modCount++;
 103     return true;
 104   }
 105
 106   @Override
 107   public void add(int index, E e) {
 108     if (index < 0 || index > mySize) {
 109       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
 110     }
 111
 112     if (mySize == 0) {
 113       myElem = e;
 114     }
 115     else if (mySize == 1 && index == 0) {
 116       Object[] array = new Object[2];
 117       array[0] = e;
 118       array[1] = myElem;
 119       myElem = array;
 120     }
 121     else {
 122       Object[] array = new Object[mySize + 1];
 123       if (mySize == 1) {
 124         array[0] = myElem; // index == 1
 125       }
 126       else {
 127         Object[] oldArray = (Object[])myElem;
 128         System.arraycopy(oldArray, 0, array, 0, index);
 129         System.arraycopy(oldArray, index, array, index + 1, mySize - index);
 130       }
 131       array[index] = e;
 132       myElem = array;
 133     }
 134
 135     mySize++;
 136     modCount++;
 137   }
 138
 139   @Override
 140   public int size() {
 141     return mySize;
 142   }
 143
 144   @Override
 145   public void clear() {
 146     myElem = null;
 147     mySize = 0;
 148     modCount++;
 149   }
 150
 151   @Override
 152   public E set(final int index, final E element) {
 153     if (index < 0 || index >= mySize) {
 154       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
 155     }
 156
 157     final E oldValue;
 158     if (mySize == 1) {
 159       oldValue = (E)myElem;
 160       myElem = element;
 161     }
 162     else {
 163       final Object[] array = (Object[])myElem;
 164       oldValue = (E)array[index];
 165       array[index] = element;
 166     }
 167     return oldValue;
 168   }
 169
 170   @Override
 171   public E remove(final int index) {
 172     if (index < 0 || index >= mySize) {
 173       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
 174     }
 175
 176     final E oldValue;
 177     if (mySize == 1) {
 178       oldValue = (E)myElem;
 179       myElem = null;
 180     }
 181     else {
 182       Object[] array = (Object[])myElem;
 183       oldValue = (E)array[index];
 184
 185       if (mySize == 2) {
 186         myElem = array[1 - index];
 187       }
 188       else {
 189         int numMoved = mySize - index - 1;
 190         if (numMoved > 0) {
 191           System.arraycopy(array, index + 1, array, index, numMoved);
 192         }
 193         array[mySize - 1] = null;
 194       }
 195     }
 196     mySize--;
 197     modCount++;
 198     return oldValue;
 199   }
 200
 201   @NotNull
 202   @Override
 203   public Iterator<E> iterator() {
 204     if (mySize == 0) {
 205       return EmptyIterator.getInstance();
 206     }
 207     if (mySize == 1) {
 208       return new SingletonIterator();
 209     }
 210     return super.iterator();
 211   }
 212
 213   private class SingletonIterator extends SingletonIteratorBase<E> {
 214     private final int myInitialModCount;
 215
 216     public SingletonIterator() {
 217       myInitialModCount = modCount;
 218     }
 219
 220     @Override
 221     protected E getElement() {
 222       return (E)myElem;
 223     }
 224
 225     @Override
 226     protected void checkCoModification() {
 227       if (modCount != myInitialModCount) {
 228         throw new ConcurrentModificationException("ModCount: " + modCount + "; expected: " + myInitialModCount);
 229       }
 230     }
 231
 232     @Override
 233     public void remove() {
 234       checkCoModification();
 235       clear();
 236     }
 237   }
 238
 239   public void sort(Comparator<? super E> comparator) {
 240     if (mySize >= 2) {
 241       Arrays.sort((E[])myElem, 0, mySize, comparator);
 242     }
 243   }
 244
 245   public int getModificationCount() {
 246     return modCount;
 247   }
 248
 249   @NotNull
 250   @Override
 251   public <T> T[] toArray(@NotNull T[] a) {
 252     int aLength = a.length;
 253     if (mySize == 1) {
 254       if (aLength != 0) {
 255         a[0] = (T)myElem;
 256       }
 257       else {
 258         T[] r = (T[])Array.newInstance(a.getClass().getComponentType(), 1);
 259         r[0] = (T)myElem;
 260         return r;
 261       }
 262     }
 263     else if (aLength < mySize) {
 264       return (T[])Arrays.copyOf((E[])myElem, mySize, a.getClass());
 265     }
 266     else if (mySize != 0) {
 267       //noinspection SuspiciousSystemArraycopy
 268       System.arraycopy(myElem, 0, a, 0, mySize);
 269     }
 270
 271     if (aLength > mySize) {
 272       a[mySize] = null;
 273     }
 274     return a;
 275   }
 276
 277   /**
 278    * Trims the capacity of this list to be the
 279    * list's current size.  An application can use this operation to minimize
 280    * the storage of a list instance.
 281    */
 282   public void trimToSize() {
 283     if (mySize < 2) return;
 284     Object[] array = (Object[])myElem;
 285     int oldCapacity = array.length;
 286     if (mySize < oldCapacity) {
 287       modCount++;
 288       myElem = Arrays.copyOf(array, mySize);
 289     }
 290   }
 291 }