SimpleSortedSet.java
001 /*
002  *  SimpleSortedSet.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, 15/Nov/2001
012  *
013  */
014 package gate.util;
015 import java.util.*;
016 
017 /**
018  * The purpose of this Map is to combine the functionality found in
019  * TreeSet, especially first() and tailSet() with the hashcode driven map
020  * using native long as key to hold the annotations ordered by their offset.
021  * It is used in the SinglePhaseTransducer.transduce()
022  */
023 public class SimpleSortedSet {
024 
025 /**
026  * the Map contianing Lists with the annotations by offset as key
027  */
028     HashMapLong m = new HashMapLong();
029 
030 /**
031  * the initial dimension of the offsets array
032  */
033     static final int INCREMENT = 4;
034 /**
035  * the array containing the distinct offsets in the map
036  * It should be sorted before usinf the first and tailSet methods
037  */
038     long[] theArray = new long[INCREMENT];
039 /**
040  * tailSet generated index - this is the index found to be les or equl to the
041  * argument provided when tailSet() methos was invoked
042  */
043     int tsindex = 0;
044 /**
045  * size of the offset's array
046  */
047     int size = 0;
048 
049 /**
050  * the Contructor. fills the allocated offset's array with the large possible
051  * valuse so any valis value will be placed on front of them.
052  */
053     public SimpleSortedSet()
054     {
055         java.util.Arrays.fill(theArray, Long.MAX_VALUE);
056     }
057 /**
058  * the get method retrive the List element by offset key given as argument
059  @param elValue the offset to which the list should be retrived.
060  @return the list with annotations by this offset or null if there is no
061  * such offset placed in the map
062  */
063     public Object get(long elValue)
064     {
065         return m.get(elValue);
066     }
067 /**
068  * add the new annotation to the annotation list for the given offset
069  * Note: if the offset is not in the map new empty list is created and the
070  * annotation is added to it
071  @param elValue the offset of the annotation
072  @param o the annotation instance to be placed in the list
073  @return true if the offset is already in the map false otherwise
074  */
075     @SuppressWarnings("unchecked")
076     public boolean add(long elValue, Object o)
077     {
078 // get the list by offset
079         Object f = m.get(elValue);
080         if (f == null)
081         {
082 // there is no such offset in the map
083 // create one empty list
084             f = new ArrayList<Object>();
085 // put it in the map
086             m.put(elValue, f);
087 // add the annotation to it
088             ((List<Object>)f).add(o);
089 // update the size of the offsets array if necessery
090             if (theArray.length == size)
091             {
092             // allocate
093                 long[] temp = new long[theArray.length*2]// + INCREMENT
094             // copy the old
095                 System.arraycopy(theArray, 0, temp, 0, theArray.length);
096             // fill the rest wit the large possible value
097                 java.util.Arrays.fill(temp, theArray.length, temp.length , Integer.MAX_VALUE);
098             // get it
099                 theArray = temp;
100             }
101             // put the offset into the array
102             theArray[size++= elValue;
103             // indicate the 'new element' condition
104             return false;
105         }
106         // yes we already have an annotation liss for this offset
107         // add the annotation to it
108         ((List<Object>)f).add(o);
109 
110         return true;
111     // add
112 
113     /**
114      * sort the offset's array in ascending way
115      */
116     public void sort()
117     {
118       java.util.Arrays.sort(theArray,0,size);
119     }
120     /**
121      * retrive the smallest offset of the array. If there was a tailset before
122      * then retrive the smallest or equal element given the index calculated ad tailSet() method
123      @return the offset value conforming the above conditions
124      */
125     public long first()
126     {
127         if (tsindex >= sizereturn -1;
128         return theArray[tsindex];
129     // first()
130 
131     /**
132      * calculate the index of the first element in the offset's array that is
133      * equal or not greater then the given one
134      @param elValue the value to search for
135      @return actually <B>this</B>. Used to mimic the TreeSet.tailSet()
136      */
137     public SimpleSortedSet tailSet(long elValue)
138     {
139         // small speedup opt. because most of the queries are about to the same
140         // or the next element in the array
141 //        if (tsindex < theArray.length && elValue != theArray[tsindex])
142 //        {
143             if (tsindex<(size-1&& elValue > theArray[tsindex&&
144                 elValue <= theArray[tsindex+1])
145                 {
146                     tsindex++;
147                    return this;
148                 }
149             int index = java.util.Arrays.binarySearch(theArray, elValue);
150             if (index < 0)
151                 index = ~index;
152             tsindex = index;
153 //        }
154         return this;
155     // tailSet()
156 
157     /**
158      * is the map is empty
159      @return true if teher is no element in the map
160      */
161     public boolean isEmpty()
162     {
163         return m.isEmpty();
164     // isEmpty
165 
166     // return the number of distinct offsets in the map
167     public int size()
168     {
169         return size;
170     }
171 //SimpleSortedSet