1   /*
2    *  AnnotationSetImpl.java
3    *
4    *  Copyright (c) 1998-2004, 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   *  Hamish Cunningham, 7/Feb/2000
12   *
13   *  Developer notes:
14   *  ---
15   *
16   *  the addToIndex... and indexBy... methods could be refactored as I'm
17   *  sure they can be made simpler
18   *
19   *  every set to which annotation will be added has to have positional
20   *  indexing, so that we can find or create the nodes on the new annotations
21   *
22   *  note that annotations added anywhere other than sets that are
23   *  stored on the document will not get stored anywhere...
24   *
25   *  nodes aren't doing anything useful now. needs some interface that allows
26   *  their creation, defaulting to no coterminous duplicates, but allowing such
27   *  if required
28   *
29   *  $Id: AnnotationSetImpl.java,v 1.92 2004/07/21 17:10:02 akshay Exp $
30   */
31  
32  package gate.annotation;
33  
34  import java.util.*;
35  
36  import gate.*;
37  import gate.corpora.DocumentImpl;
38  import gate.event.*;
39  import gate.util.InvalidOffsetException;
40  import gate.util.RBTreeMap;
41  
42  /** Implementation of AnnotationSet. Has a number of indices, all bar one
43   * of which are null by default and are only constructed when asked
44   * for. Has lots of get methods with various selection criteria; these
45   * return views into the set, which are nonetheless valid sets in
46   * their own right (but will not necesarily be fully indexed).
47   * Has a name, which is null by default; clients of Document can
48   * request named AnnotationSets if they so desire. Has a reference to the
49   * Document it is attached to. Contrary to Collections convention,
50   * there is no no-arg constructor, as this would leave the set in
51   * an inconsistent state.
52   * <P>
53   * There are five indices: annotation by id, annotations by type, annotations
54   * by start/end node and nodes by offset. The last three jointly provide
55   * positional indexing; construction of these is triggered by
56   * indexByStart/EndOffset(),
57   * or by calling a get method that selects on offset. The type
58   * index is triggered by indexByType(), or calling a get method that selects
59   * on type. The id index is always present.
60   */
61  public class AnnotationSetImpl
62      extends AbstractSet
63      implements AnnotationSet {
64    /** Debug flag */
65    private static final boolean DEBUG = false;
66  
67    /** Construction from Document. */
68    public AnnotationSetImpl(Document doc) {
69  //    annotsById = new VerboseHashMap();
70      annotsById = new HashMap();
71      this.doc = (DocumentImpl) doc;
72    } // construction from document
73  
74    /** Construction from Document and name. */
75    public AnnotationSetImpl(Document doc, String name) {
76      this(doc);
77      this.name = name;
78    } // construction from document and name
79  
80    /** Construction from Collection (which must be an AnnotationSet) */
81  //<<<dam: speedup constructor
82    /*
83      public AnnotationSetImpl(Collection c) throws ClassCastException {
84        this(((AnnotationSet) c).getDocument());
85        addAll(c);
86      } // construction from collection
87     */
88  //===dam: now
89    /** Construction from Collection (which must be an AnnotationSet) */
90    public AnnotationSetImpl(Collection c) throws ClassCastException {
91      this( ( (AnnotationSet) c).getDocument(), ( (AnnotationSet) c).getName());
92      if (c instanceof AnnotationSetImpl) {
93        AnnotationSetImpl theC = (AnnotationSetImpl) c;
94        annotsById = (HashMap) theC.annotsById.clone();
95        if (theC.annotsByEndNode != null) {
96          annotsByEndNode = (Map) ( (HashMap) theC.annotsByEndNode).clone();
97          annotsByStartNode = (Map) ( (HashMap) theC.annotsByStartNode).clone();
98        }
99        if (theC.annotsByType != null)
100         annotsByType = (Map) ( (HashMap) theC.annotsByType).clone();
101       if (theC.nodesByOffset != null) {
102         nodesByOffset = (RBTreeMap) theC.nodesByOffset.clone();
103       }
104     }
105     else
106       addAll(c);
107   } // construction from collection
108 
109 //>>>dam: end
110 
111   /** This inner class serves as the return value from the iterator()
112    * method.
113    */
114   class AnnotationSetIterator
115       implements Iterator {
116     private Iterator iter;
117     protected Annotation lastNext = null;
118     AnnotationSetIterator() {
119       iter = annotsById.values().iterator();
120     }
121 
122     public boolean hasNext() {
123       return iter.hasNext();
124     }
125 
126     public Object next() {
127       return (lastNext = (Annotation) iter.next());
128     }
129 
130     public void remove() {
131       // this takes care of the ID index
132       iter.remove();
133       // remove from type index
134       removeFromTypeIndex(lastNext);
135       // remove from offset indices
136       removeFromOffsetIndex(lastNext);
137       //that's the second way of removing annotations from a set
138       //apart from calling remove() on the set itself
139       fireAnnotationRemoved(new AnnotationSetEvent(
140           AnnotationSetImpl.this,
141           AnnotationSetEvent.ANNOTATION_REMOVED,
142           getDocument(), (Annotation) lastNext));      
143     } // remove()
144   }; // AnnotationSetIterator
145 
146   /**
147    *  This is a {@link java.util.HashMap}
148    * that fires events when elements are removed.
149    * 
150    * This class has been used in a previous version for the indexById structure 
151    * which now uses a simple HashMap.
152    * 
153    * This class is kept here for backwards compatibility of old serial 
154    * datastores.
155    *  
156    */
157   public class VerboseHashMap
158       extends HashMap {
159     VerboseHashMap() {
160       super(Gate.HASH_STH_SIZE);
161     } //contructor
162 
163     public Object remove(Object key) {
164       Object res = super.remove(key);
165       if (res != null) {
166         if (owner == null) {
167           fireAnnotationRemoved(new AnnotationSetEvent(
168               AnnotationSetImpl.this,
169               AnnotationSetEvent.ANNOTATION_REMOVED,
170               getDocument(), (Annotation) res));
171         }
172         else {
173           owner.fireAnnotationRemoved(new AnnotationSetEvent(
174               AnnotationSetImpl.this,
175               AnnotationSetEvent.ANNOTATION_REMOVED,
176               getDocument(), (Annotation) res));
177         }
178       }
179       return res;
180     } //public Object remove(Object key)
181 
182     static final long serialVersionUID = -4832487354063073511L;
183 
184     /**
185      * The annotation set this maps is part of.
186      * This is an ugly hack in order to fix a bug: database annotation sets
187      * didn't fire annotation removed events.
188      */
189     private transient AnnotationSetImpl owner;
190 
191     /**
192      * Sets the annotation set this maps is part of.
193      * This is an ugly hack in order to fix a bug: database annotation sets
194      * didn't fire annotation removed events.
195      */
196     public void setOwner(AnnotationSetImpl newOwner) {
197       this.owner = newOwner;
198     }
199   } //protected class VerboseHashMap extends HashMap
200 
201   /** Get an iterator for this set */
202   public Iterator iterator() {
203     return new AnnotationSetIterator();
204   }
205 
206   /** Remove an element from this set. */
207   public boolean remove(Object o) throws ClassCastException {
208     Annotation a = (Annotation) o;
209     boolean wasPresent = removeFromIdIndex(a);
210     if (wasPresent) {
211       removeFromTypeIndex(a);
212       removeFromOffsetIndex(a);
213     }
214     //fire the event
215     fireAnnotationRemoved(new AnnotationSetEvent(
216         AnnotationSetImpl.this,
217         AnnotationSetEvent.ANNOTATION_REMOVED,
218         getDocument(), a));
219     
220     return wasPresent;
221   } // remove(o)
222   
223 
224   /** Remove from the ID index. */
225   protected boolean removeFromIdIndex(Annotation a) {
226     if (annotsById.remove(a.getId()) == null)
227       return false;
228     return true;
229   } // removeFromIdIndex(a)
230 
231   /** Remove from the type index. */
232   protected void removeFromTypeIndex(Annotation a) {
233     if (annotsByType != null) {
234       AnnotationSet sameType = (AnnotationSet) annotsByType.get(a.getType());
235       if (sameType != null)
236         sameType.remove(a);
237       if (sameType.isEmpty()) // none left of this type
238         annotsByType.remove(a.getType());
239     }
240   } // removeFromTypeIndex(a)
241 
242   /** Remove from the offset indices. */
243   protected void removeFromOffsetIndex(Annotation a) {
244     if (nodesByOffset != null) {
245       // knowing when a node is no longer needed would require keeping a reference
246       // count on annotations, or using a weak reference to the nodes in
247       // nodesByOffset
248     }
249     if (annotsByStartNode != null) {
250       Integer id = a.getStartNode().getId();
251       AnnotationSet starterAnnots = (AnnotationSet) annotsByStartNode.get(id);
252       starterAnnots.remove(a);
253       if (starterAnnots.isEmpty()) // no annotations start here any more
254         annotsByStartNode.remove(id);
255     }
256     if (annotsByEndNode != null) {
257       Integer id = a.getEndNode().getId();
258       AnnotationSet endingAnnots = (AnnotationSet) annotsByEndNode.get(id);
259       endingAnnots.remove(a);
260       if (endingAnnots.isEmpty()) // no annotations start here any more
261         annotsByEndNode.remove(id);
262     }
263   } // removeFromOffsetIndex(a)
264 
265   /** The size of this set */
266   public int size() {
267     return annotsById.size();
268   }
269 
270   /** Find annotations by id */
271   public Annotation get(Integer id) {
272     return (Annotation) annotsById.get(id);
273   } // get(id)
274 
275   /** Get all annotations */
276   public AnnotationSet get() {
277     AnnotationSetImpl resultSet = new AnnotationSetImpl(doc);
278     resultSet.addAllKeepIDs(annotsById.values());
279     if (resultSet.isEmpty())
280       return null;
281     return resultSet;
282   } // get()
283 
284   /** Select annotations by type */
285   public AnnotationSet get(String type) {
286     if (annotsByType == null)
287       indexByType();
288       // the aliasing that happens when returning a set directly from the
289       // types index can cause concurrent access problems; but the fix below
290       // breaks the tests....
291       //AnnotationSet newSet =
292       //  new AnnotationSetImpl((Collection) annotsByType.get(type));
293       //return newSet;
294     return (AnnotationSet) annotsByType.get(type);
295   } // get(type)
296 
297   /** Select annotations by a set of types. Expects a Set of String. */
298   public AnnotationSet get(Set types) throws ClassCastException {
299     if (annotsByType == null)
300       indexByType();
301     Iterator iter = types.iterator();
302     AnnotationSetImpl resultSet = new AnnotationSetImpl(doc);
303     while (iter.hasNext()) {
304       String type = (String) iter.next();
305       AnnotationSet as = (AnnotationSet) annotsByType.get(type);
306       if (as != null)
307         resultSet.addAllKeepIDs(as);
308         // need an addAllOfOneType method
309     } // while
310     if (resultSet.isEmpty())
311       return null;
312     return resultSet;
313   } // get(types)
314 
315   /** Select annotations by type and features */
316   public AnnotationSet get(String type, FeatureMap constraints) {
317     if (annotsByType == null)
318       indexByType();
319     AnnotationSet typeSet = get(type);
320     if (typeSet == null)
321       return null;
322     AnnotationSet resultSet = new AnnotationSetImpl(doc);
323     Iterator iter = typeSet.iterator();
324     while (iter.hasNext()) {
325       Annotation a = (Annotation) iter.next();
326       // we check for matching constraints by simple equality. a
327       // feature map satisfies the constraints if it contains all the
328       // key/value pairs from the constraints map
329 
330 //      if (a.getFeatures().entrySet().containsAll(constraints.entrySet()))
331       if( a.getFeatures().subsumes(constraints))
332         resultSet.add(a);
333     } // while
334     if (resultSet.isEmpty())
335       return null;
336     return resultSet;
337   } // get(type, constraints)
338 
339   /** Select annotations by type and feature names */
340   public AnnotationSet get(String type, Set featureNames) {
341     if (annotsByType == null)
342       indexByType();
343     AnnotationSet typeSet = null;
344     if (type != null) {
345       //if a type is provided, try finding annotations of this type
346       typeSet = get(type);
347       //if none exist, then return coz nothing left to do
348       if (typeSet == null)
349         return null;
350     }
351     AnnotationSet resultSet = new AnnotationSetImpl(doc);
352     Iterator iter = null;
353     if (type != null)
354       iter = typeSet.iterator();
355     else
356       iter = annotsById.values().iterator();
357     while (iter.hasNext()) {
358       Annotation a = (Annotation) iter.next();
359       // we check for matching constraints by simple equality. a
360       // feature map satisfies the constraints if it contains all the
361       // key/value pairs from the constraints map
362       if (a.getFeatures().keySet().containsAll(featureNames))
363         resultSet.add(a);
364     } // while
365     if (resultSet.isEmpty())
366       return null;
367     return resultSet;
368   } // get(type, featureNames)
369 
370   /** Select annotations by offset. This returns the set of annotations
371    * whose start node is the least such that it is less than or equal
372    * to offset. If a positional index doesn't exist it is created.
373    * If there are no nodes at or beyond the offset param then it will return
374    * null.
375    */
376   public AnnotationSet get(Long offset) {
377     if (annotsByStartNode == null)
378       indexByStartOffset();
379       // find the next node at or after offset; get the annots starting there
380     Node nextNode = (Node) nodesByOffset.getNextOf(offset);
381     if (nextNode == null) // no nodes at or beyond this offset
382       return null;
383     AnnotationSet res = (AnnotationSet) annotsByStartNode.get(nextNode.getId());
384     //get ready for next test
385     nextNode = (Node) nodesByOffset.getNextOf(new Long(offset.longValue() + 1));
386     //skip all the nodes that have no starting annotations
387     while (res == null && nextNode != null) {
388       res = (AnnotationSet) annotsByStartNode.get(nextNode.getId());
389       //get ready for next test
390       nextNode = (Node) nodesByOffset.getNextOf(
391           new Long(nextNode.getOffset().longValue() + 1)
392           );
393     }
394     //res it either null (no suitable node found) or the correct result
395     return res;
396   } // get(offset)
397 
398   /**
399    * Select annotations by offset. This returns the set of annotations
400    * that overlap totaly or partially with the interval defined by the two
401    * provided offsets.The result will include all the annotations that either:
402    * <ul>
403    * <li>start before the start offset and end strictly after it</li>
404    * <li>OR</li>
405    * <li>start at a position between the start and the end offsets</li>
406    */
407   public AnnotationSet get(Long startOffset, Long endOffset) {
408     //the result will include all the annotations that either:
409     //-start before the start offset and end strictly after it
410     //or
411     //-start at a position between the start and the end offsets
412     if (annotsByStartNode == null)
413       indexByStartOffset();
414     AnnotationSetImpl resultSet = new AnnotationSetImpl(doc);
415     Iterator nodesIter;
416     Iterator annotsIter;
417     Node currentNode;
418     Annotation currentAnnot;
419     //find all the annots that start strictly before the start offset and end
420     //strictly after it
421     nodesIter = nodesByOffset.headMap(startOffset).values().iterator();
422     while (nodesIter.hasNext()) {
423       currentNode = (Node) nodesIter.next();
424       Set fromPoint = (Set) annotsByStartNode.get(currentNode.getId());
425       if (fromPoint != null) {
426         annotsIter = (fromPoint).iterator();
427         while (annotsIter.hasNext()) {
428           currentAnnot = (Annotation) annotsIter.next();
429           if (currentAnnot.getEndNode().getOffset().compareTo(startOffset) > 0) {
430             resultSet.add(currentAnnot);
431           }
432         }
433       }
434     }
435     //find all the annots that start at or after the start offset but strictly
436     //before the end offset
437     nodesIter = nodesByOffset.subMap(startOffset, endOffset).values().iterator();
438     while (nodesIter.hasNext()) {
439       currentNode = (Node) nodesIter.next();
440       Set fromPoint = (Set) annotsByStartNode.get(currentNode.getId());
441       if (fromPoint != null)
442         resultSet.addAllKeepIDs(fromPoint);
443     }
444     return resultSet;
445   } //get(startOfset, endOffset)
446 
447   /**
448    * Select annotations by offset. This returns the set of annotations
449    * that overlap strictly with the interval defined by the two
450    * provided offsets.The result will include all the annotations that
451    * start at the start offset and end strictly at the end offset
452    */
453   public AnnotationSet getStrict(Long startOffset, Long endOffset) {
454     //the result will include all the annotations that
455     //start at the start offset and end strictly at the end offset
456     if (annotsByStartNode == null)
457       indexByStartOffset();
458     AnnotationSet resultSet = new AnnotationSetImpl(doc);
459     Iterator nodesIter;
460     Iterator annotsIter;
461     Node currentNode;
462     Annotation currentAnnot;
463     //find all the annots that start at the start offset
464     currentNode = (Node) nodesByOffset.get(startOffset);
465     if (currentNode != null) {
466       Set fromPoint = (Set) annotsByStartNode.get(currentNode.getId());
467       if (fromPoint != null) {
468         annotsIter = fromPoint.iterator();
469         while (annotsIter.hasNext()) {
470           currentAnnot = (Annotation) annotsIter.next();
471           if (currentAnnot.getEndNode().getOffset().compareTo(endOffset) == 0) {
472             resultSet.add(currentAnnot);
473           } // if
474         } // while
475       } // if
476     } // if
477     return resultSet;
478   } //getStrict(startOfset, endOffset)
479 
480   /**
481    * Select annotations by offset. This returns the set of annotations
482    * of the given type
483    * that overlap totaly or partially with the interval defined by the two
484    * provided offsets.The result will include all the annotations that either:
485    * <ul>
486    * <li>start before the start offset and end strictly after it</li>
487    * <li>OR</li>
488    * <li>start at a position between the start and the end offsets</li>
489    */
490   public AnnotationSet get(String neededType, Long startOffset, Long endOffset) {
491     //the result will include all the annotations that either:
492     //-start before the start offset and end strictly after it
493     //or
494     //-start at a position between the start and the end offsets
495     if (annotsByStartNode == null)
496       indexByStartOffset();
497     AnnotationSet resultSet = new AnnotationSetImpl(doc);
498     Iterator nodesIter;
499     Iterator annotsIter;
500     Node currentNode;
501     Annotation currentAnnot;
502     //find all the annots that start strictly before the start offset and end
503     //strictly after it
504     nodesIter = nodesByOffset.headMap(startOffset).values().iterator();
505     while (nodesIter.hasNext()) {
506       currentNode = (Node) nodesIter.next();
507       Set fromPoint = (Set) annotsByStartNode.get(currentNode.getId());
508       if (fromPoint != null) {
509         annotsIter = (fromPoint).iterator();
510         while (annotsIter.hasNext()) {
511           currentAnnot = (Annotation) annotsIter.next();
512           if (currentAnnot.getType().equals(neededType) &&
513               currentAnnot.getEndNode().getOffset().compareTo(startOffset) > 0
514               ) {
515             resultSet.add(currentAnnot);
516           } //if
517         } //while
518       }
519     }
520     //find all the annots that start at or after the start offset but strictly
521     //before the end offset
522     nodesIter = nodesByOffset.subMap(startOffset, endOffset).values().iterator();
523     while (nodesIter.hasNext()) {
524       currentNode = (Node) nodesIter.next();
525       Set fromPoint = (Set) annotsByStartNode.get(currentNode.getId());
526       if (fromPoint != null) {
527         annotsIter = (fromPoint).iterator();
528         while (annotsIter.hasNext()) {
529           currentAnnot = (Annotation) annotsIter.next();
530           if (currentAnnot.getType().equals(neededType)) {
531             resultSet.add(currentAnnot);
532           } //if
533         } //while
534       } //if
535     }
536     return resultSet;
537   } //get(type, startOfset, endOffset)
538 
539   /** Select annotations by type, features and offset */
540   public AnnotationSet get(String type, FeatureMap constraints, Long offset) {
541     // select by offset
542     AnnotationSet nextAnnots = (AnnotationSet) get(offset);
543     if (nextAnnots == null)
544       return null;
545     // select by type and constraints from the next annots
546     return nextAnnots.get(type, constraints);
547   } // get(type, constraints, offset)
548 
549   /**
550    * Select annotations by offset that
551    * start at a position between the start and end before the end offset
552    */
553   public AnnotationSet getContained(Long startOffset, Long endOffset) {
554     //the result will include all the annotations that either:
555     //start at a position between the start and end before the end offsets
556     if (annotsByStartNode == null)
557       indexByStartOffset();
558     AnnotationSet resultSet = new AnnotationSetImpl(doc);
559     Iterator nodesIter;
560     Iterator annotsIter;
561     Node currentNode;
562     Annotation currentAnnot;
563     //find all the annots that start at or after the start offset but strictly
564     //before the end offset
565     nodesIter = nodesByOffset.subMap(startOffset, endOffset).values().iterator();
566     while (nodesIter.hasNext()) {
567       currentNode = (Node) nodesIter.next();
568       Set fromPoint = (Set) annotsByStartNode.get(currentNode.getId());
569       if (fromPoint == null)
570         continue;
571       //loop through the annotations and find only those that
572       //also end before endOffset
573       Iterator annotIter = fromPoint.iterator();
574       while (annotIter.hasNext()) {
575         Annotation annot = (Annotation) annotIter.next();
576         if (annot.getEndNode().getOffset().compareTo(endOffset) <= 0)
577           resultSet.add(annot);
578       }
579     }
580     return resultSet;
581   } //get(startOfset, endOffset)
582 
583   /** Get the node with the smallest offset */
584   public Node firstNode() {
585     indexByStartOffset();
586     if (nodesByOffset.isEmpty())
587       return null;
588     else
589       return (Node) nodesByOffset.get(nodesByOffset.firstKey());
590   } // firstNode
591 
592   /** Get the node with the largest offset */
593   public Node lastNode() {
594     indexByStartOffset();
595     indexByEndOffset();
596     if (nodesByOffset.isEmpty())
597       return null;
598     else
599       return (Node) nodesByOffset.get(nodesByOffset.lastKey());
600   } // lastNode
601 
602   /**
603    * Get the first node that is relevant for this annotation set and which has
604    * the offset larger than the one of the node provided.
605    */
606   public Node nextNode(Node node) {
607     indexByStartOffset();
608     indexByEndOffset();
609     return (Node) nodesByOffset.getNextOf(
610         new Long(node.getOffset().longValue() + 1)
611         );
612   }
613 
614   /** Create and add an annotation with pre-existing nodes,
615    * and return its id
616    */
617   public Integer add(Node start, Node end, String type, FeatureMap features) {
618     // the id of the new annotation
619     Integer id = doc.getNextAnnotationId();
620     // construct an annotation
621     Annotation a = new AnnotationImpl(id, start, end, type, features);
622     // delegate to the method that adds existing annotations
623     add(a);
624     return id;
625   } // add(Node, Node, String, FeatureMap)
626 
627   /** Add an existing annotation. Returns true when the set is modified. */
628   public boolean add(Object o) throws ClassCastException {
629     Annotation a = (Annotation) o;
630     Object oldValue = annotsById.put(a.getId(), a);
631     if (annotsByType != null)
632       addToTypeIndex(a);
633     if (annotsByStartNode != null || annotsByEndNode != null)
634       addToOffsetIndex(a);
635     AnnotationSetEvent evt = new AnnotationSetEvent(
636         this,
637         AnnotationSetEvent.ANNOTATION_ADDED,
638         doc, a);
639     fireAnnotationAdded(evt);
640     fireGateEvent(evt);
641     return oldValue != a;
642   } // add(o)
643 
644   /**
645    * Adds multiple annotations to this set in one go.
646    * All the objects in the provided collection should be of
647    * {@link gate.Annotation} type, otherwise a ClassCastException will be
648    * thrown.
649    * The provided annotations will be used to create new annotations using the
650    * appropriate add() methods from this set. The new annotations will have
651        * different IDs from the old ones (which is required in order to preserve the
652    * uniqueness of IDs inside an annotation set).
653    * @param c a collection of annotations
654    * @return <tt>true</tt> if the set has been modified as a result of this
655    * call.
656    */
657   public boolean addAll(Collection c) {
658     Iterator annIter = c.iterator();
659     boolean changed = false;
660     while (annIter.hasNext()) {
661       Annotation a = (Annotation) annIter.next();
662       try {
663         add(a.getStartNode().getOffset(),
664             a.getEndNode().getOffset(),
665             a.getType(),
666             a.getFeatures());
667         changed = true;
668       }
669       catch (InvalidOffsetException ioe) {
670         throw new IllegalArgumentException(ioe.toString());
671       }
672     }
673     return changed;
674   }
675 
676   /**
677    * Adds multiple annotations to this set in one go.
678    * All the objects in the provided collection should be of
679    * {@link gate.Annotation} type, otherwise a ClassCastException will be
680    * thrown.
681    * This method does not create copies of the annotations like addAll() does
682    * but simply adds the new annotations to the set.
683    * It is intended to be used solely by annotation sets in order to construct
684    * the results for various get(...) methods.
685    * @param c a collection of annotations
686    * @return <tt>true</tt> if the set has been modified as a result of this
687    * call.
688    */
689   protected boolean addAllKeepIDs(Collection c) {
690     Iterator annIter = c.iterator();
691     boolean changed = false;
692     while (annIter.hasNext()) {
693       Annotation a = (Annotation) annIter.next();
694       changed |= add(a);
695     }
696     return changed;
697   }
698 
699   /** Create and add an annotation and return its id */
700   public Integer add(
701       Long start, Long end, String type, FeatureMap features
702       ) throws InvalidOffsetException {
703     // are the offsets valid?
704     if (!doc.isValidOffsetRange(start, end))
705       throw new InvalidOffsetException();
706     // the set has to be indexed by position in order to add, as we need
707     // to find out if nodes need creating or if they exist already
708     if (nodesByOffset == null) {
709       indexByStartOffset();
710       indexByEndOffset();
711     }
712     // find existing nodes if appropriate nodes don't already exist, create them
713     Node startNode = (Node) nodesByOffset.getNextOf(start);
714     if (startNode == null || !startNode.getOffset().equals(start))
715       startNode = new NodeImpl(doc.getNextNodeId(), start);
716     Node endNode = null;
717     if (start.equals(end))
718       endNode = startNode;
719     else
720       endNode = (Node) nodesByOffset.getNextOf(end);
721     if (endNode == null || !endNode.getOffset().equals(end))
722       endNode = new NodeImpl(doc.getNextNodeId(), end);
723       // delegate to the method that adds annotations with existing nodes
724     return add(startNode, endNode, type, features);
725   } // add(start, end, type, features)
726 
727   /** Create and add an annotation from database read data
728    * In this case the id is already known being previously fetched from the
729    * database
730    */
731   public void add(
732       Integer id, Long start, Long end, String type, FeatureMap features
733       ) throws InvalidOffsetException {
734     // are the offsets valid?
735     if (!doc.isValidOffsetRange(start, end))
736       throw new InvalidOffsetException();
737     // the set has to be indexed by position in order to add, as we need
738     // to find out if nodes need creating or if they exist already
739     if (nodesByOffset == null) {
740       indexByStartOffset();
741       indexByEndOffset();
742     }
743     // find existing nodes if appropriate nodes don't already exist, create them
744     Node startNode = (Node) nodesByOffset.getNextOf(start);
745     if (startNode == null || !startNode.getOffset().equals(start))
746       startNode = new NodeImpl(doc.getNextNodeId(), start);
747     Node endNode = null;
748     if (start.equals(end))
749       endNode = startNode;
750     else
751       endNode = (Node) nodesByOffset.getNextOf(end);
752     if (endNode == null || !endNode.getOffset().equals(end))
753       endNode = new NodeImpl(doc.getNextNodeId(), end);
754       // construct an annotation
755     Annotation a = new AnnotationImpl(id, startNode, endNode, type, features);
756     add(a);
757   } // add(id, start, end, type, features)
758 
759   /** Construct the positional index. */
760   protected void indexByType() {
761     if (annotsByType != null)
762       return;
763     annotsByType = new HashMap(Gate.HASH_STH_SIZE);
764     Annotation a;
765     Iterator annotIter = annotsById.values().iterator();
766     while (annotIter.hasNext())
767       addToTypeIndex( (Annotation) annotIter.next());
768   } // indexByType()
769 
770   /** Construct the positional indices for annotation start */
771   protected void indexByStartOffset() {
772     if (annotsByStartNode != null) return;
773     if (nodesByOffset == null) nodesByOffset = new RBTreeMap();
774     annotsByStartNode = new HashMap(Gate.HASH_STH_SIZE);
775     Iterator annotIter = annotsById.values().iterator();
776     while (annotIter.hasNext())
777       addToStartOffsetIndex( (Annotation) annotIter.next());
778   } // indexByStartOffset()
779 
780   /** Construct the positional indices for annotation end */
781   protected void indexByEndOffset() {
782     if (annotsByEndNode != null)
783       return;
784     if (nodesByOffset == null)
785       nodesByOffset = new RBTreeMap();
786     annotsByEndNode = new HashMap(Gate.HASH_STH_SIZE);
787     Annotation a;
788     Iterator annotIter = annotsById.values().iterator();
789     while (annotIter.hasNext())
790       addToEndOffsetIndex( (Annotation) annotIter.next());
791   } // indexByEndOffset()
792 
793   /** Add an annotation to the type index. Does nothing if the index
794    * doesn't exist.
795    */
796   void addToTypeIndex(Annotation a) {
797     if (annotsByType == null)
798       return;
799     String type = a.getType();
800     AnnotationSet sameType = (AnnotationSet) annotsByType.get(type);
801     if (sameType == null) {
802       sameType = new AnnotationSetImpl(doc);
803       annotsByType.put(type, sameType);
804     }
805     sameType.add(a);
806   } // addToTypeIndex(a)
807 
808   /** Add an annotation to the offset indices. Does nothing if they
809    * don't exist.
810    */
811   void addToOffsetIndex(Annotation a) {
812     addToStartOffsetIndex(a);
813     addToEndOffsetIndex(a);
814   } // addToOffsetIndex(a)
815 
816   /** Add an annotation to the start offset index. Does nothing if the
817    * index doesn't exist.
818    */
819   void addToStartOffsetIndex(Annotation a) {
820     Node startNode = a.getStartNode();
821     Node endNode = a.getEndNode();
822     Long start = startNode.getOffset();
823     Long end = endNode.getOffset();
824     // add a's nodes to the offset index
825     if (nodesByOffset != null)
826       nodesByOffset.put(start, startNode);
827       // if there's no appropriate index give up
828     if (annotsByStartNode == null)
829       return;
830     // get the annotations that start at the same node, or create new set
831     AnnotationSet thisNodeAnnots =
832         (AnnotationSet) annotsByStartNode.get(startNode.getId());
833     if (thisNodeAnnots == null) {
834       thisNodeAnnots = new AnnotationSetImpl(doc);
835       annotsByStartNode.put(startNode.getId(), thisNodeAnnots);
836     }
837     // add to the annots listed for a's start node
838     thisNodeAnnots.add(a);
839   } // addToStartOffsetIndex(a)
840 
841   /** Add an annotation to the end offset index. Does nothing if the
842    * index doesn't exist.
843    */
844   void addToEndOffsetIndex(Annotation a) {
845     Node startNode = a.getStartNode();
846     Node endNode = a.getEndNode();
847     Long start = startNode.getOffset();
848     Long end = endNode.getOffset();
849     // add a's nodes to the offset index
850     if (nodesByOffset != null)
851       nodesByOffset.put(end, endNode);
852       // if there's no appropriate index give up
853     if (annotsByEndNode == null)
854       return;
855     // get the annotations that start at the same node, or create new set
856     AnnotationSet thisNodeAnnots =
857         (AnnotationSet) annotsByEndNode.get(endNode.getId());
858     if (thisNodeAnnots == null) {
859       thisNodeAnnots = new AnnotationSetImpl(doc);
860       annotsByEndNode.put(endNode.getId(), thisNodeAnnots);
861     }
862     // add to the annots listed for a's start node
863     thisNodeAnnots.add(a);
864   } // addToEndOffsetIndex(a)
865 
866   /** Propagate changes to the document content. Has, unfortunately,
867    * to be public, to allow DocumentImpls to get at it. Oh for a
868    * "friend" declaration. Doesn't throw InvalidOffsetException as
869    * DocumentImpl is the only client, and that checks the offsets
870    * before calling this method.
871    */
872   public void edit(Long start, Long end, DocumentContent replacement) {
873     //make sure we have the indices computed
874     indexByStartOffset();
875     indexByEndOffset();
876     if(end.compareTo(start) > 0){
877       //get the nodes that need to be processed (the nodes internal to the
878       //removed section plus the marginal ones
879       List affectedNodes = new ArrayList(nodesByOffset.subMap(start,
880           new Long(end.longValue() + 1)).values());
881       //if we have more than 1 node we need to delete all apart from the first
882       //and move the annotations so that they refer to the one we keep (the first)
883       NodeImpl firstNode = null;
884       if (!affectedNodes.isEmpty()) {
885         firstNode = (NodeImpl) affectedNodes.get(0);
886         List startingAnnotations = new ArrayList();
887         List endingAnnotations = new ArrayList();
888         for (int i = 1; i < affectedNodes.size(); i++) {
889           Node aNode = (Node) affectedNodes.get(i);
890           //save the annotations
891           AnnotationSet annSet = (AnnotationSet) annotsByStartNode.get(aNode.
892               getId());
893           if (annSet != null)
894             startingAnnotations.addAll(annSet);
895           annSet = (AnnotationSet) annotsByEndNode.get(aNode.getId());
896           if (annSet != null)
897             endingAnnotations.addAll(annSet);
898             //remove the node
899             nodesByOffset.remove(aNode.getOffset());
900             annotsByStartNode.remove(aNode);
901             annotsByEndNode.remove(aNode);
902         }
903         //modify the annotations so they point to the saved node
904         Iterator annIter = startingAnnotations.iterator();
905         while (annIter.hasNext()) {
906           AnnotationImpl anAnnot = (AnnotationImpl) annIter.next();
907           anAnnot.start = firstNode;
908           addToStartOffsetIndex(anAnnot);
909         }
910         annIter = endingAnnotations.iterator();
911         while (annIter.hasNext()) {
912           AnnotationImpl anAnnot = (AnnotationImpl) annIter.next();
913           anAnnot.end = firstNode;
914           addToEndOffsetIndex(anAnnot);
915         }
916         //repair the first node
917         //remove from offset index
918         nodesByOffset.remove(firstNode.getOffset());
919         //change the offset for the saved node
920         firstNode.setOffset(start);
921         //add back to the offset index
922         nodesByOffset.put(firstNode.getOffset(), firstNode);
923       }
924     }
925 
926     //now handle the insert and/or update the rest of the nodes' position
927     //get the user selected behaviour (defaults to append)
928     boolean shouldPrepend = Gate.getUserConfig().
929         getBoolean(GateConstants.DOCEDIT_INSERT_PREPEND).booleanValue();
930 
931     long s = start.longValue(), e = end.longValue();
932     long rlen = // length of the replacement value
933         ( (replacement == null) ? 0 : replacement.size().longValue());
934 
935     // update the offsets and the index by offset for the rest of the nodes
936     List nodesAfterReplacement = new ArrayList(
937         nodesByOffset.tailMap(start).values());
938 
939     //remove from the index by offset
940     Iterator nodesAfterReplacementIter = nodesAfterReplacement.iterator();
941     while (nodesAfterReplacementIter.hasNext()) {
942       NodeImpl n = (NodeImpl) nodesAfterReplacementIter.next();
943       nodesByOffset.remove(n.getOffset());
944     }
945     //change the offsets
946     nodesAfterReplacementIter = nodesAfterReplacement.iterator();
947     while (nodesAfterReplacementIter.hasNext()) {
948       NodeImpl n = (NodeImpl) nodesAfterReplacementIter.next();
949       long oldOffset = n.getOffset().longValue();
950       //by default we move all nodes back
951       long newOffset = oldOffset - (e - s) + rlen;
952       //for the first node we need behave differently
953       if (oldOffset == s){
954         //the first offset never moves back
955         if(newOffset < s) newOffset = s;
956         //if we're prepending we don't move forward
957         if(shouldPrepend) newOffset = s;
958       }
959       n.setOffset(new Long(newOffset));
960     }
961     //add back to the index by offset with the new offsets
962     nodesAfterReplacementIter = nodesAfterReplacement.iterator();
963     while (nodesAfterReplacementIter.hasNext()) {
964       NodeImpl n = (NodeImpl) nodesAfterReplacementIter.next();
965       nodesByOffset.put(n.getOffset(), n);
966     }
967 
968 //    //rebuild the indices with the new offsets
969 //    nodesByOffset = null;
970 //    annotsByStartNode = null;
971 //    annotsByEndNode = null;
972 //    indexByStartOffset();
973 //    indexByEndOffset();
974   } // edit(start,end,replacement)
975 
976   /** Get the name of this set. */
977   public String getName() {
978     return name;
979   }
980 
981   /** Get the document this set is attached to. */
982   public Document getDocument() {
983     return doc;
984   }
985 
986   /** Get a set of java.lang.String objects representing all the annotation
987    * types present in this annotation set.
988    */
989   public Set getAllTypes() {
990     indexByType();
991     return annotsByType.keySet();
992   }
993 
994   /**
995    *
996    * @return a clone of this set.
997    * @throws CloneNotSupportedException
998    */
999   public Object clone() throws CloneNotSupportedException {
1000    return super.clone();
1001  }
1002
1003  /**
1004   *
1005   * @param l
1006   */
1007  public synchronized void removeAnnotationSetListener(AnnotationSetListener l) {
1008    if (annotationSetListeners != null && annotationSetListeners.contains(l)) {
1009      Vector v = (Vector) annotationSetListeners.clone();
1010      v.removeElement(l);
1011      annotationSetListeners = v;
1012    }
1013  }
1014
1015  /**
1016   *
1017   * @param l
1018   */
1019  public synchronized void addAnnotationSetListener(AnnotationSetListener l) {
1020    Vector v = annotationSetListeners == null ? new Vector(2) :
1021        (Vector) annotationSetListeners.clone();
1022    if (!v.contains(l)) {
1023      v.addElement(l);
1024      annotationSetListeners = v;
1025    }
1026  }
1027
1028  /** String representation of the set */
1029  /*public String toString() {
1030    // annotsById
1031    SortedSet sortedAnnots = new TreeSet();
1032    sortedAnnots.addAll(annotsById.values());
1033    String aBI = sortedAnnots.toString();
1034    // annotsByType
1035    StringBuffer buf = new StringBuffer();
1036    Iterator iter = annotsByType.iterator();
1037    while(iter.hasNext()) {
1038      HashMap thisType = iter.next().entrySet();
1039      sortedAnnots.clear();
1040      sortedAnnots.addAll(thisType.);
1041      buf.append("[type: " +
1042    }
1043    return
1044      "AnnotationSetImpl: " +
1045      "name=" + name +
1046    //  "; doc.getURL()=" + doc +
1047      "; annotsById=" + aBI +
1048    //  "; annotsByType=" + aBT +
1049      "; "
1050      ;
1051     } // toString()
1052   */
1053//  public int hashCode() {
1054//    int hash = 0;
1055//    Iterator i = this.iterator();
1056//    while (i.hasNext()) {
1057//        Annotation annot = (Annotation)i.next();
1058//        if ( annot != null)
1059//            hash += annot.hashCode();
1060//    }
1061//    int nameHash = (name == null ? 0 : name.hashCode());
1062//    //int docHash = (doc == null ? 0 : doc.hashCode());
1063//
1064//    return hash ^ nameHash;// ^ docHash;
1065//  }
1066  /** The name of this set */
1067  String name = null;
1068  /** The document this set belongs to */
1069  DocumentImpl doc;
1070  /** Maps annotation ids (Integers) to Annotations */
1071  protected HashMap annotsById;
1072  /** Maps annotation types (Strings) to AnnotationSets */
1073  Map annotsByType = null;
1074  /** Maps offsets (Longs) to nodes */
1075  RBTreeMap nodesByOffset = null;
1076  /** Maps node ids (Integers) to AnnotationSets representing those
1077   * annotations that start from that node
1078   */
1079  Map annotsByStartNode;
1080  /** Maps node ids (Integers) to AnnotationSets representing those
1081   * annotations that end at that node
1082   */
1083  Map annotsByEndNode;
1084  protected transient Vector annotationSetListeners;
1085  private transient Vector gateListeners;
1086  /**
1087   *
1088   * @param e
1089   */
1090  protected void fireAnnotationAdded(AnnotationSetEvent e) {
1091    if (annotationSetListeners != null) {
1092      Vector listeners = annotationSetListeners;
1093      int count = listeners.size();
1094      for (int i = 0; i < count; i++) {
1095        ( (AnnotationSetListener) listeners.elementAt(i)).annotationAdded(e);
1096      }
1097    }
1098  }
1099
1100  /**
1101   *
1102   * @param e
1103   */
1104  protected void fireAnnotationRemoved(AnnotationSetEvent e) {
1105    if (annotationSetListeners != null) {
1106      Vector listeners = annotationSetListeners;
1107      int count = listeners.size();
1108      for (int i = 0; i < count; i++) {
1109        ( (AnnotationSetListener) listeners.elementAt(i)).annotationRemoved(e);
1110      }
1111    }
1112  }
1113
1114  /**
1115   *
1116   * @param l
1117   */
1118  public synchronized void removeGateListener(GateListener l) {
1119    if (gateListeners != null && gateListeners.contains(l)) {
1120      Vector v = (Vector) gateListeners.clone();
1121      v.removeElement(l);
1122      gateListeners = v;
1123    }
1124  }
1125
1126  /**
1127   *
1128   * @param l
1129   */
1130  public synchronized void addGateListener(GateListener l) {
1131    Vector v = gateListeners == null ? new Vector(2) :
1132        (Vector) gateListeners.clone();
1133    if (!v.contains(l)) {
1134      v.addElement(l);
1135      gateListeners = v;
1136    }
1137  }
1138
1139  /**
1140   *
1141   * @param e
1142   */
1143  protected void fireGateEvent(GateEvent e) {
1144    if (gateListeners != null) {
1145      Vector listeners = gateListeners;
1146      int count = listeners.size();
1147      for (int i = 0; i < count; i++) {
1148        ( (GateListener) listeners.elementAt(i)).processGateEvent(e);
1149      }
1150    }
1151  }
1152
1153  /** Freeze the serialization UID. */
1154  static final long serialVersionUID = 1479426765310434166L;
1155} // AnnotationSetImpl