| SimpleSortedSet.java |
1 /*
2 * SimpleSortedSet.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, 15/Nov/2001
12 *
13 */
14 package gate.util;
15 import java.util.ArrayList;
16
17 /**
18 * The purpose of this Map is to combine the functionality found in
19 * TreeSet, especially first() and tailSet() with the hashcode driven map
20 * using native long as key to hold the annotations ordered by their offset.
21 * It is used in the SinglePhaseTransducer.transduce()
22 */
23 public class SimpleSortedSet {
24
25 /**
26 * the Map contianing Lists with the annotations by offset as key
27 */
28 HashMapLong m = new HashMapLong();
29
30 /**
31 * the initial dimension of the offsets array
32 */
33 static final int INCREMENT = 4;
34 /**
35 * the array containing the distinct offsets in the map
36 * It should be sorted before usinf the first and tailSet methods
37 */
38 long[] theArray = new long[INCREMENT];
39 /**
40 * tailSet generated index - this is the index found to be les or equl to the
41 * argument provided when tailSet() methos was invoked
42 */
43 int tsindex = 0;
44 /**
45 * size of the offset's array
46 */
47 int size = 0;
48
49 /**
50 * the Contructor. fills the allocated offset's array with the large possible
51 * valuse so any valis value will be placed on front of them.
52 */
53 public SimpleSortedSet()
54 {
55 java.util.Arrays.fill(theArray, Long.MAX_VALUE);
56 }
57 /**
58 * the get method retrive the List element by offset key given as argument
59 * @param elValue the offset to which the list should be retrived.
60 * @return the list with annotations by this offset or null if there is no
61 * such offset placed in the map
62 */
63 public Object get(long elValue)
64 {
65 return m.get(elValue);
66 }
67 /**
68 * add the new annotation to the annotation list for the given offset
69 * Note: if the offset is not in the map new empty list is created and the
70 * annotation is added to it
71 * @param elValue the offset of the annotation
72 * @param o the annotation instance to be placed in the list
73 * @return true if the offset is already in the map false otherwise
74 */
75 public boolean add(long elValue, Object o)
76 {
77 // get the list by offset
78 Object f = m.get(elValue);
79 if (f == null)
80 {
81 // there is no such offset in the map
82 // create one empty list
83 f = new ArrayList();
84 // put it in the map
85 m.put(elValue, f);
86 // add the annotation to it
87 ((ArrayList)f).add(o);
88 // update the size of the offsets array if necessery
89 if (theArray.length == size)
90 {
91 // allocate
92 long[] temp = new long[theArray.length*2]; // + INCREMENT
93 // copy the old
94 System.arraycopy(theArray, 0, temp, 0, theArray.length);
95 // fill the rest wit the large possible value
96 java.util.Arrays.fill(temp, theArray.length, temp.length , Integer.MAX_VALUE);
97 // get it
98 theArray = temp;
99 }
100 // put the offset into the array
101 theArray[size++] = elValue;
102 // indicate the 'new element' condition
103 return false;
104 }
105 // yes we already have an annotation liss for this offset
106 // add the annotation to it
107 ((ArrayList)f).add(o);
108
109 return true;
110 } // add
111
112 /**
113 * sort the offset's array in ascending way
114 */
115 public void sort()
116 {
117 java.util.Arrays.sort(theArray,0,size);
118 }
119 /**
120 * retrive the smallest offset of the array. If there was a tailset before
121 * then retrive the smallest or equal element given the index calculated ad tailSet() method
122 * @return the offset value conforming the above conditions
123 */
124 public long first()
125 {
126 if (tsindex >= size) return -1;
127 return theArray[tsindex];
128 } // first()
129
130 /**
131 * calculate the index of the first element in the offset's array that is
132 * equal or not greater then the given one
133 * @param elValue the value to search for
134 * @return actually <B>this</B>. Used to mimic the TreeSet.tailSet()
135 */
136 public SimpleSortedSet tailSet(long elValue)
137 {
138 // small speedup opt. because most of the queries are about to the same
139 // or the next element in the array
140 if (tsindex < theArray.length && elValue != theArray[tsindex])
141 {
142 if (tsindex<(size-1) && elValue > theArray[tsindex] &&
143 elValue <= theArray[tsindex+1])
144 {
145 tsindex++;
146 return this;
147 }
148 int index = java.util.Arrays.binarySearch(theArray, elValue);
149 if (index < 0)
150 index = ~index;
151 tsindex = index;
152 }
153 return this;
154 } // tailSet()
155
156 /**
157 * is the map is empty
158 * @return true if teher is no element in the map
159 */
160 public boolean isEmpty()
161 {
162 return m.isEmpty();
163 } // isEmpty
164
165 // return the number of distinct offsets in the map
166 public int size()
167 {
168 return size;
169 }
170 } //SimpleSortedSet
171
172