SimpleArraySet.java
001 /*
002  *  SimpleArraySet.java
003  *
004  *  Copyright (c) 2001, The University of Sheffield.
005  *
006  *  This file is part of GATE (see http://gate.ac.uk/), and is free
007  *  software, licenced under the GNU Library General Public License,
008  *  Version 2, June 1991 (in the distribution as file licence.html,
009  *  and also available at http://gate.ac.uk/gate/licence.html).
010  *
011  *   D.Ognyanoff, 5/Nov/2001
012  *
013  *  $Id: SimpleArraySet.java 17600 2014-03-08 18:47:11Z markagreenwood $
014  */
015 
016 
017 package gate.util;
018 
019 import java.io.Serializable;
020 import java.util.ArrayList;
021 import java.util.Arrays;
022 import java.util.Collection;
023 
024 
025 /**
026  * A specific *partial* implementation of the Set interface used for
027  * high performance and memory reduction on small sets. Used in
028  * gate.fsm.State, for example
029  */
030 public class SimpleArraySet<T> implements Serializable, Iterable<T>
031 {
032 
033   private static final long serialVersionUID = 7356655846408155644L;
034 
035   /**
036    * The array storing the elements
037    */
038   T[] theArray = null;
039 
040   public int size()
041   {
042       return theArray == null : theArray.length;
043   }
044 
045   public Collection<T> asCollection()
046   {
047       if (theArray == nullreturn new ArrayList<T>();
048       return Arrays.asList(theArray);
049   }
050 
051   @SuppressWarnings("unchecked")
052   public boolean add(T tr)
053   {
054     if (theArray == null)
055     {
056       theArray = (T[])new Object[1];
057       theArray[0= tr;
058     else {
059       int newsz = theArray.length+1;
060       int index = java.util.Arrays.binarySearch(theArray, tr);
061       if (index < 0)
062       {
063         index = ~index;
064         T[] temp = (T[])new Object[newsz];
065         int i;
066         for (i = 0; i < index; i++)
067         {
068           temp[i= theArray[i]; theArray[inull;
069         }
070         for (i = index+1; i<newsz; i++)
071         {
072           temp[i= theArray[i-1]; theArray[i-1null;
073         }
074         temp[index= tr;
075         theArray = temp;
076       else {
077         theArray[index= tr;
078       }
079     // if initially empty
080     return true;
081   // add
082 
083   /**
084    * iterator
085    */
086   @Override
087   public java.util.Iterator<T> iterator()
088   {
089     if (theArray == null)
090       return new java.util.Iterator<T>()
091         {
092           @Override
093           public boolean hasNext() {return false;}
094           @Override
095           public T next() { return null}
096           @Override
097           public void remove() {}
098         };
099     else
100       return new java.util.Iterator<T>()
101         {
102           int count = 0;
103           @Override
104           public boolean hasNext()
105           {
106             if (theArray == null)
107               throw new RuntimeException("");
108             return count < theArray.length;
109           }
110           @Override
111           public T next() {
112             if (theArray == null)
113               throw new RuntimeException("");
114             return theArray[count++];
115           }
116           @Override
117           public void remove() {}
118         }// anonymous iterator
119   // iterator
120 
121 // SimpleArraySet