RelationSet.java
001 /*
002  *  RelationData.java
003  *
004  *  Copyright (c) 1995-2012, The University of Sheffield. See the file
005  *  COPYRIGHT.txt in the software or at http://gate.ac.uk/gate/COPYRIGHT.txt
006  *
007  *  This file is part of GATE (see http://gate.ac.uk/), and is free
008  *  software, licenced under the GNU Library General Public License,
009  *  Version 2, June 1991 (in the distribution as file licence.html,
010  *  and also available at http://gate.ac.uk/gate/licence.html).
011  *
012  *  Valentin Tablan, 27 Feb 2012
013  *
014  *  $Id: RelationSet.java 18589 2015-02-26 14:15:49Z markagreenwood $
015  */
016 package gate.relations;
017 
018 import gate.Annotation;
019 import gate.AnnotationSet;
020 import gate.corpora.DocumentImpl;
021 import gate.event.AnnotationSetEvent;
022 import gate.event.AnnotationSetListener;
023 import gate.event.RelationSetEvent;
024 import gate.event.RelationSetListener;
025 
026 import java.io.IOException;
027 import java.io.ObjectInputStream;
028 import java.io.ObjectOutputStream;
029 import java.io.Serializable;
030 import java.util.ArrayList;
031 import java.util.BitSet;
032 import java.util.Collection;
033 import java.util.Collections;
034 import java.util.HashMap;
035 import java.util.HashSet;
036 import java.util.Iterator;
037 import java.util.List;
038 import java.util.Map;
039 import java.util.NoSuchElementException;
040 import java.util.Set;
041 import java.util.Vector;
042 import java.util.regex.Matcher;
043 
044 /**
045  * Utility class for managing a set of GATE relations (usually each
046  * annotation set of a document will have one set of associated
047  * relations).
048  */
049 public class RelationSet implements Serializable, AnnotationSetListener,
050                         Set<Relation> {
051 
052   private static final long serialVersionUID = 8552798130184595465L;
053 
054   /**
055    * Annotation ID used when calling {@link #getRelations(int...)} for
056    * positions with no restrictions.
057    */
058   public static final int ANY = -1;
059 
060   /**
061    * Index for relations by type.
062    */
063   protected Map<String, BitSet> indexByType;
064 
065   /**
066    * Index for relations by id.
067    */
068   protected Map<Integer, Relation> indexById;
069 
070   /**
071    * Indexes for relations by member. Each element in the list refers to
072    * a given position in the members array: the element at position zero
073    * refers to the first member of all relations.
074    
075    * The element at position <code>pos</code> is a map from annotation
076    * ID (representing a relation member) to a {@link BitSet} indicating
077    * which of the relation indexes correspond to
078    * relations that contain the given annotation (i.e. member) on the
079    * position <code>pos</code>.
080    */
081   protected List<Map<Integer, BitSet>> indexesByMember;
082 
083   /**
084    * The {@link AnnotationSet} this set of relations relates to. The
085    * assumption (which is actively enforced) is that all members of this
086    * RelationSet will be either {@link Annotation} instances from this
087    {@link AnnotationSet} or other {@link Relation} instances within
088    * this set.
089    */
090   protected AnnotationSet annSet;
091 
092   private Vector<RelationSetListener> listeners = null;
093 
094   /**
095    * The max ID of any relation within this set which is needed for some
096    * of the index access operations
097    */
098   private int maxID = 0;
099   
100   /**
101    * Use only for serialization
102    */
103   private Relation[] relations;
104 
105   /**
106    * The {@link AnnotationSet} which this instance belongs to.
107    
108    @return the AnnotationSet which this instance belongs to.
109    */
110   public AnnotationSet getAnnotationSet() {
111     return annSet;
112   }
113 
114   /**
115    * An unmodifiable view of the contents of this RelationSet.
116    
117    @return an unmodifiable view of the contents of this RelationSet.
118    */
119   public Collection<Relation> get() {
120     return Collections.unmodifiableCollection(indexById.values());
121   }
122 
123   /**
124    * You should never create a RelationSet directly, instead get if via
125    * the AnnotationSet
126    */
127   public RelationSet(AnnotationSet annSet) {
128     this.annSet = annSet;
129     indexByType = new HashMap<String, BitSet>();
130     indexesByMember = new ArrayList<Map<Integer, BitSet>>();
131     indexById = new HashMap<Integer, Relation>();
132 
133     annSet.addAnnotationSetListener(this);
134   }
135 
136   /**
137    * Empties the relation set
138    */
139   @Override
140   public void clear() {
141 
142     // clearing the indexes won't fire the events so we fire the events
143     // first and then clear the indexes, hopefully we won't end up with
144     // any weird side effects from this but I can't think of a
145     // safer/better way of doing it other than calling delete on each
146     // relation which would be horribly inefficient
147     for(Relation r : indexById.values()) {
148       fireRelationRemoved(new RelationSetEvent(this,
149               RelationSetEvent.RELATION_REMOVED, r));
150     }
151 
152     indexByType.clear();
153     indexesByMember.clear();
154     indexById.clear();
155   }
156 
157   /**
158    * The number of relations in this set.
159    
160    @return the number of relations in this set.
161    */
162   @Override
163   public int size() {
164     return indexById.size();
165   }
166 
167   /**
168    * Creates a new {@link Relation} and adds it to this set. Uses the
169    * default relation implementation at {@link SimpleRelation}.
170    
171    @param type the type for the new relation.
172    @param members the annotation IDs for the annotations that are
173    *          members in this relation.
174    @return the newly created {@link Relation} instance.
175    */
176   public Relation addRelation(String type, int... members)
177           throws IllegalArgumentException {
178 
179     if(members.length < 2)
180       throw new IllegalArgumentException(
181               "A relation needs to have atleast two members");
182 
183     for(int member : members) {
184       if(!indexById.containsKey(member&& annSet.get(member== null)
185         throw new IllegalArgumentException(
186                 "Member must be from within this annotation set");
187     }
188 
189     if(type == null || type.trim().equals(""))
190       throw new IllegalArgumentException("A relation must have a type");
191 
192     // now we have sanity checked the params create the relation
193     Relation rel =
194             new SimpleRelation(
195                     ((DocumentImpl)annSet.getDocument()).getNextAnnotationId(),
196                     type, members);
197 
198     // add the relation to the set
199     add(rel);
200 
201     // return the relation to the calling method
202     return rel;
203   }
204 
205   /**
206    * Adds an externally-created {@link Relation} instance.
207    
208    @param rel the {@link Relation} to be added.
209    @return true if the {@link Relation} was added to the set, false otherwise
210    */
211   @Override
212   public boolean add(Relation rel) {
213 
214     // keep a track of the max ID we now of to support the index access
215     maxID = Math.max(maxID, rel.getId());
216 
217     /** index by ID **/
218     indexById.put(rel.getId(), rel);
219 
220     /** index by type **/
221     BitSet sameType = indexByType.get(rel.getType());
222     if(sameType == null) {
223       sameType = new BitSet(rel.getId());
224       indexByType.put(rel.getType(), sameType);
225     }
226     sameType.set(rel.getId());
227 
228     /** index by member **/
229     // widen the index by member list, if needed
230     for(int i = indexesByMember.size(); i < rel.getMembers().length; i++) {
231       indexesByMember.add(new HashMap<Integer, BitSet>());
232     }
233 
234     for(int memeberPos = 0; memeberPos < rel.getMembers().length; memeberPos++) {
235       int member = rel.getMembers()[memeberPos];
236       Map<Integer, BitSet> indexByMember = indexesByMember.get(memeberPos);
237       BitSet sameMember = indexByMember.get(member);
238       if(sameMember == null) {
239         sameMember = new BitSet(maxID);
240         indexByMember.put(member, sameMember);
241       }
242       sameMember.set(rel.getId());
243     }
244 
245     // notify anyone who cares that a new relation has been added
246     fireRelationAdded(new RelationSetEvent(this,
247             RelationSetEvent.RELATION_ADDED, rel));
248 
249     return true;
250   }
251 
252   /**
253    * Returns the maximum arity for any relation in this
254    {@link RelationSet}.
255    
256    @return an int value.
257    */
258   public int getMaximumArity() {
259     return indexesByMember.size();
260   }
261 
262   /**
263    * Finds relations based on their type.
264    
265    @param type the type of relation being sought.
266    @return the list of all relations in this {@link RelationSet} that
267    *         have the required type.
268    */
269   public Collection<Relation> getRelations(String type) {
270     List<Relation> res = new ArrayList<Relation>();
271     BitSet rels = indexByType.get(type);
272     if(rels != null) {
273       for(int relPos = 0; relPos <= maxID; relPos++) {
274         if(rels.get(relPos)) res.add(indexById.get(relPos));
275       }
276     }
277     return res;
278   }
279 
280   public Relation get(Integer id) {
281     return indexById.get(id);
282   }
283 
284   /**
285    * Finds relations based on their members.
286    
287    @param members an array containing annotation IDs. If a constraint
288    *          is not required for a given member position, then the
289    *          {@link #ANY}. value should be used.
290    @return all the relations that have the given annotation IDs
291    *         (members) on the specified positions.
292    */
293   public Collection<Relation> getRelations(int... members) {
294     // get the lists of relations for each member
295     return getRelations(null, members);
296   }
297 
298   public Collection<Relation> getRelations(String type, int... members) {
299     // get the lists of relations for each member
300     BitSet[] postingLists =
301             new BitSet[getMaximumArity() (type != null 0)];
302     for(int i = 0; i < postingLists.length; i++) {
303       if(i < members.length && members[i>= 0) {
304         postingLists[i= indexesByMember.get(i).get(members[i]);
305       else {
306         postingLists[inull;
307       }
308 
309     }
310 
311     if(type != null) {
312       postingLists[postingLists.length - 1= indexByType.get(type);
313     }
314 
315     return intersection(postingLists);
316   }
317 
318   /**
319    * Deletes the specified relation.
320    
321    @param relation the relation to be deleted.
322    @return <code>true</code> if the given relation was deleted, or
323    *         <code>false</code> if it was not found.
324    */
325   public boolean deleteRelation(Relation relation) {
326 
327     // don't do anything if this relation isn't part of this set
328     if(!indexById.containsValue(relation)) return false;
329 
330     // find all relations which include the annotation and remove them
331     for(Relation r : getReferencing(relation.getId())) {
332       deleteRelation(r);
333     }
334 
335     // delete this relation from the type index
336     indexByType.get(relation.getType()).clear(relation.getId());
337 
338     // delete this relation from the ID index
339     indexById.remove(relation.getId());
340 
341     // delete from the member index
342     for(int memeberPos = 0; memeberPos < relation.getMembers().length; memeberPos++) {
343       int member = relation.getMembers()[memeberPos];
344 
345       Map<Integer, BitSet> indexByMember = indexesByMember.get(memeberPos);
346       BitSet sameMember = indexByMember.get(member);
347       sameMember.clear(relation.getId());
348     }
349 
350     // notify anyone who cares enough to listen that we have deleted a
351     // relation
352     fireRelationRemoved(new RelationSetEvent(this,
353             RelationSetEvent.RELATION_REMOVED, relation));
354     return true;
355 
356   }
357 
358   /**
359    * Returns a collection of all {@link Relation} instances within this
360    * set which include the specified {@link Annotation} or
361    {@link Relation}
362    
363    @param id the ID of the {@link Annotation} or {@link Relation} to
364    *          look for
365    @return a set of all {@link Relation} instances within this set
366    *         which include the specified id
367    */
368   public Collection<Relation> getReferencing(Integer id) {
369 
370     Set<Relation> relations = new HashSet<Relation>();
371     for(int pos = 0; pos < getMaximumArity(); pos++) {
372       int[] constraint = new int[pos + 1];
373       for(int i = 0; i < pos; i++)
374         constraint[i= RelationSet.ANY;
375       constraint[pos= id;
376       relations.addAll(getRelations(null, constraint));
377     }
378 
379     return relations;
380   }
381 
382   /**
383    * Calculates the intersection of a set of lists containing relation
384    * IDs
385    
386    @param indexLists the list to be intersected.
387    @return the list of relations contained in all the supplied index
388    *         lists.
389    */
390   protected Collection<Relation> intersection(BitSet... indexLists) {
391 
392     Set<Relation> res = new HashSet<Relation>();
393 
394     BitSet relIds = new BitSet(maxID + 1);
395     relIds.set(0, maxID + 1);
396 
397     boolean found = false;
398 
399     for(BitSet aList : indexLists) {
400       if(aList != null) {
401         found = true;
402         relIds.and(aList);
403 
404         // if there is no intersection then return the empty list
405         if(relIds.isEmpty()) return res;
406       }
407     }
408 
409     if(!foundreturn res;
410 
411     for(int relIdx = 0; relIdx < (maxID + 1); relIdx++) {
412       if(relIds.get(relIdx)) {
413         res.add(indexById.get(relIdx));
414       }
415     }
416     return res;
417   }
418 
419   /*
420    * (non-Javadoc)
421    
422    * @see java.lang.Object#toString()
423    */
424   @Override
425   public String toString() {
426 
427     StringBuilder str = new StringBuilder();
428     str.append("[");
429     boolean first = true;
430     for(Relation r : indexById.values()) {
431       if(first) {
432         first = false;
433       else {
434         str.append("; ");
435       }
436       String relStr = r.toString();
437       relStr = relStr.replaceAll(";", Matcher.quoteReplacement("\\;"));
438       if(!r.getClass().equals(SimpleRelation.class)) {
439         relStr = "(" + r.getClass().getName() ")" + relStr;
440       }
441       str.append(relStr);
442 
443     }
444     str.append("]");
445     return str.toString();
446   }
447 
448   @Override
449   public void annotationAdded(AnnotationSetEvent e) {
450     // we don't care about annotations being added so we do nothing
451   }
452 
453   @Override
454   public void annotationRemoved(AnnotationSetEvent e) {
455 
456     Annotation a = e.getAnnotation();
457 
458     // find all relations which include the annotation and remove them
459     for(Relation r : getReferencing(a.getId())) {
460       deleteRelation(r);
461     }
462   }
463 
464   public synchronized void removeRelationSetListener(RelationSetListener l) {
465     if(listeners != null && listeners.contains(l)) {
466       @SuppressWarnings("unchecked")
467       Vector<RelationSetListener> v =
468               (Vector<RelationSetListener>)listeners.clone();
469       v.removeElement(l);
470       listeners = v;
471     }
472   }
473 
474   public synchronized void addRelationSetListener(RelationSetListener l) {
475     @SuppressWarnings("unchecked")
476     Vector<RelationSetListener> v =
477             listeners == null
478                     new Vector<RelationSetListener>(2)
479                     (Vector<RelationSetListener>)listeners.clone();
480     if(!v.contains(l)) {
481       v.addElement(l);
482       listeners = v;
483     }
484   }
485 
486   protected void fireRelationAdded(RelationSetEvent e) {
487     if(listeners != null) {
488       int count = listeners.size();
489       for(int i = 0; i < count; i++) {
490         listeners.elementAt(i).relationAdded(e);
491       }
492     }
493   }
494 
495   protected void fireRelationRemoved(RelationSetEvent e) {
496     if(listeners != null) {
497       int count = listeners.size();
498       for(int i = 0; i < count; i++) {
499         listeners.elementAt(i).relationRemoved(e);
500       }
501     }
502   }
503 
504   @Override
505   public boolean addAll(Collection<? extends Relation> relations) {
506     boolean modified = false;
507 
508     for(Relation r : relations) {
509       modified |= add(r);
510     }
511 
512     return modified;
513   }
514 
515   @Override
516   public boolean contains(Object obj) {
517     return indexById.containsValue(obj);
518   }
519 
520   @Override
521   public boolean containsAll(Collection<?> relations) {
522     boolean all = true;
523 
524     for(Object r : relations) {
525       all &= contains(r);
526     }
527 
528     return all;
529   }
530 
531   @Override
532   public boolean isEmpty() {
533     return indexById.isEmpty();
534   }
535 
536   @Override
537   public Iterator<Relation> iterator() {
538 
539     final Set<Relation> copy = new HashSet<Relation>(indexById.values());
540 
541     return new Iterator<Relation>() {
542       private Relation nextElement, currentElement;
543 
544       private boolean hasNext;
545 
546       private Iterator<Relation> iterator = copy.iterator();
547 
548       {
549         nextMatch();
550       }
551 
552       @Override
553       public boolean hasNext() {
554         return hasNext;
555       }
556 
557       @Override
558       public Relation next() {
559         if(!hasNext) {
560           throw new NoSuchElementException();
561         }
562 
563         return (currentElement = nextMatch());
564       }
565 
566       private Relation nextMatch() {
567         Relation oldMatch = nextElement;
568 
569         while(iterator.hasNext()) {
570           Relation o = iterator.next();
571 
572           if(indexById.containsValue(o)) {
573             hasNext = true;
574             nextElement = o;
575 
576             return oldMatch;
577           }
578         }
579 
580         hasNext = false;
581 
582         return oldMatch;
583       }
584 
585       @Override
586       public void remove() {
587         if(currentElement != nulldeleteRelation(currentElement);
588       }
589 
590     };
591   }
592 
593   @Override
594   public boolean remove(Object obj) {
595     if(!(obj instanceof Relation)) return false;
596     return deleteRelation((Relation)obj);
597   }
598 
599   @Override
600   public boolean removeAll(Collection<?> relations) {
601     boolean modified = false;
602 
603     for(Object r : relations) {
604       if(instanceof Relation) {
605         modified |= deleteRelation((Relation)r);
606       }
607     }
608 
609     return modified;
610   }
611 
612   @Override
613   public boolean retainAll(Collection<?> relations) {
614     boolean modified = false;
615 
616     Iterator<Relation> it = iterator();
617     while(it.hasNext()) {
618       Relation r = it.next();
619 
620       if(!relations.contains(r)) {
621         //deleteRelation(r);
622         it.remove();
623         modified = true;
624       }
625     }
626 
627     return modified;
628   }
629 
630   @Override
631   public Object[] toArray() {
632     return indexById.values().toArray();
633   }
634 
635   @Override
636   public <T> T[] toArray(T[] store) {
637     return indexById.values().toArray(store);
638   }
639   
640   private void writeObject(java.io.ObjectOutputStream outthrows IOException {
641     ObjectOutputStream.PutField pf = out.putFields();
642     
643     pf.put("annSet", annSet);
644     pf.put("relations", toArray(new Relation[size()]));
645     out.writeFields();
646   }
647   
648   private void readObject(java.io.ObjectInputStream inthrows IOException,
649           ClassNotFoundException {
650     ObjectInputStream.GetField gf = in.readFields();
651     
652     annSet = (AnnotationSet)gf.get("annSet"null);
653     relations = (Relation[])gf.get("relations"null);
654     
655     indexByType = new HashMap<String, BitSet>();
656     indexesByMember = new ArrayList<Map<Integer, BitSet>>();
657     indexById = new HashMap<Integer, Relation>();
658 
659     annSet.addAnnotationSetListener(this);
660     
661     if (relations != null) {
662       for (Relation r : relations) {
663         add(r);
664       }      
665     }
666     
667     relations = null;
668   }
669 }