| SimpleArraySet.java |
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.2 2004/03/25 13:00:53 valyt Exp $
14 */
15
16
17 package gate.util;
18
19
20 /**
21 * A specific *partial* implementation of the Set interface used for
22 * high performance and memory reduction on small sets. Used in
23 * gate.fsm.State, for example
24 */
25 public class SimpleArraySet
26 {
27 /**
28 * The array storing the elements
29 */
30 Object[] theArray = null;
31
32 public boolean add(Object tr)
33 {
34 if (theArray == null)
35 {
36 theArray = new Object[1];
37 theArray[0] = tr;
38 } else {
39 int newsz = theArray.length+1;
40 int index = java.util.Arrays.binarySearch(theArray, tr);
41 if (index < 0)
42 {
43 index = ~index;
44 Object[] temp = new Object[newsz];
45 int i;
46 for (i = 0; i < index; i++)
47 {
48 temp[i] = theArray[i]; theArray[i] = null;
49 }
50 for (i = index+1; i<newsz; i++)
51 {
52 temp[i] = theArray[i-1]; theArray[i-1] = null;
53 }
54 temp[index] = tr;
55 theArray = temp;
56 } else {
57 theArray[index] = tr;
58 }
59 } // if initially empty
60 return true;
61 } // add
62
63 /**
64 * iterator
65 */
66 public java.util.Iterator iterator()
67 {
68 if (theArray == null)
69 return new java.util.Iterator()
70 {
71 public boolean hasNext() {return false;}
72 public Object next() { return null; }
73 public void remove() {}
74 };
75 else
76 return new java.util.Iterator()
77 {
78 int count = 0;
79 public boolean hasNext()
80 {
81 if (theArray == null)
82 throw new RuntimeException("");
83 return count < theArray.length;
84 }
85 public Object next() {
86 if (theArray == null)
87 throw new RuntimeException("");
88 return theArray[count++];
89 }
90 public void remove() {}
91 }; // anonymous iterator
92 } // iterator
93
94 } // SimpleArraySet
95