1   /*
2    *  SimpleArraySet.java
3    *
4    *  Copyright (c) 2001, The University of Sheffield.
5    *
6    *  This file is part of GATE (see http://gate.ac.uk/), and is free
7    *  software, licenced under the GNU Library General Public License,
8    *  Version 2, June 1991 (in the distribution as file licence.html,
9    *  and also available at http://gate.ac.uk/gate/licence.html).
10   *
11   *   D.Ognyanoff, 5/Nov/2001
12   *
13   *  $Id: SimpleArraySet.java,v 1.4 2005/10/07 16:07:36 nirajaswani Exp $
14   */
15  
16  
17  package gate.util;
18  
19  import java.io.Serializable;
20  import java.util.ArrayList;
21  import java.util.Arrays;
22  import java.util.Collection;
23  
24  
25  /**
26   * A specific *partial* implementation of the Set interface used for
27   * high performance and memory reduction on small sets. Used in
28   * gate.fsm.State, for example
29   */
30  public class SimpleArraySet implements Serializable
31  {
32    /**
33     * The array storing the elements
34     */
35    Object[] theArray = null;
36  
37    public int size()
38    {
39        return theArray == null ? 0 : theArray.length;
40    }
41  
42    public Collection asCollection()
43    {
44        if (theArray == null) return new ArrayList();
45        return Arrays.asList(theArray);
46    }
47  
48    public boolean add(Object tr)
49    {
50      if (theArray == null)
51      {
52        theArray = new Object[1];
53        theArray[0] = tr;
54      } else {
55        int newsz = theArray.length+1;
56        int index = java.util.Arrays.binarySearch(theArray, tr);
57        if (index < 0)
58        {
59          index = ~index;
60          Object[] temp = new Object[newsz];
61          int i;
62          for (i = 0; i < index; i++)
63          {
64            temp[i] = theArray[i]; theArray[i] = null;
65          }
66          for (i = index+1; i<newsz; i++)
67          {
68            temp[i] = theArray[i-1]; theArray[i-1] = null;
69          }
70          temp[index] = tr;
71          theArray = temp;
72        } else {
73          theArray[index] = tr;
74        }
75      } // if initially empty
76      return true;
77    } // add
78  
79    /**
80     * iterator
81     */
82    public java.util.Iterator iterator()
83    {
84      if (theArray == null)
85        return new java.util.Iterator()
86          {
87            public boolean hasNext() {return false;}
88            public Object next() { return null; }
89            public void remove() {}
90          };
91      else
92        return new java.util.Iterator()
93          {
94            int count = 0;
95            public boolean hasNext()
96            {
97              if (theArray == null)
98                throw new RuntimeException("");
99              return count < theArray.length;
100           }
101           public Object next() {
102             if (theArray == null)
103               throw new RuntimeException("");
104             return theArray[count++];
105           }
106           public void remove() {}
107         }; // anonymous iterator
108   } // iterator
109 
110 } // SimpleArraySet
111