001package org.biojava.bio.program.ssaha;
002
003import java.util.ArrayList;
004import java.util.Collections;
005import java.util.List;
006
007/**
008 * A listener that merges overlapping hits and culls all hits under a given
009 * length.
010 *
011 * @author Matthew Pocock
012 */
013public class HitMerger implements SearchListener {
014  private List hitList;
015  private int minLength;
016  private SearchListener delegate;
017  
018  /**
019   * Build a new HitMerger that will pass events on to a delegate.
020   *
021   * @param delegate  the SearchListener to inform of all merged and
022   *                  filtered hits
023   * @param minLength the minimum length a hit must reach to be passed on
024   */
025  public HitMerger(SearchListener delegate, int minLength) {
026    this.hitList = new ArrayList();
027    this.delegate = delegate;
028    this.minLength = minLength;
029  }
030  
031  public void startSearch(String seqID) {
032    hitList.clear();
033    delegate.startSearch(seqID);
034  }
035  
036  public void hit(
037    int hitID,
038    int queryOffset,
039    int hitOffset,
040    int hitLength
041  ) {
042    Hit hit = new Hit(hitID, queryOffset, hitOffset, hitLength);
043    hitList.add(hit);
044  }
045
046  public void endSearch(String seqID) {
047    Collections.sort(hitList);
048
049   OUTER:
050    for(int i = 0 ; i < hitList.size(); i++) {
051      Hit low = (Hit) hitList.get(i);
052      int ubound = low.queryOffset + low.hitOffset + low.hitLength * 2;
053
054      for(int j = i+1; j < hitList.size(); j++) {
055        Hit high = (Hit) hitList.get(j);
056
057        if(ubound < high.queryOffset + high.hitOffset) {
058          break;
059        }
060
061        if(doOverlap(low, high)) {
062          hitList.set(j, merge(low, high));
063          continue OUTER;
064        }
065      }
066
067      if(low.hitLength >= minLength) {
068        delegate.hit(low.hitID, low.queryOffset, low.hitOffset, low.hitLength);
069      }
070    }
071
072    delegate.endSearch(seqID);
073  }
074
075  private Hit merge(Hit a, Hit b) {
076    int qo = Math.min(a.queryOffset, b.queryOffset);
077    int ho = Math.min(a.hitOffset, b.hitOffset);
078    int len = Math.max(
079      a.queryOffset + a.hitLength,
080      b.queryOffset + b.hitLength ) -
081      qo;
082
083    return new Hit(a.hitID, qo, ho, len);
084  }
085
086  private boolean doOverlap(Hit a, Hit b) {
087    return
088      // same sequence
089      (a.hitID == b.hitID) &&
090      // overlap in query offset space
091      ( !(a.queryOffset + a.hitLength < b.queryOffset ||
092          a.queryOffset > b.queryOffset + b.hitLength ) ) && 
093      // on the same diagonal
094      ( a.queryOffset - b.queryOffset == a.hitOffset - b.hitOffset);
095  }
096  
097  private static class Hit
098  implements Comparable {
099    public int hitID;
100    public int queryOffset;
101    public int hitOffset;
102    public int hitLength;
103    
104    public Hit(
105      int hitID,
106      int queryOffset,
107      int hitOffset,
108      int hitLength
109    ) {
110      this.hitID = hitID;
111      this.queryOffset = queryOffset;
112      this.hitOffset = hitOffset;
113      this.hitLength = hitLength;
114    }
115    
116    public boolean equals(Object o) {
117      if(o instanceof Hit) {
118        Hit r = (Hit) o;
119        return
120          hitID == r.hitID &&
121          queryOffset == r.queryOffset &&
122          hitOffset == r.hitOffset &&
123          hitLength == r.hitLength;
124      }
125      return false;
126    }
127    
128    public int compareTo(Object o) {
129      Hit r = (Hit) o;
130      
131      if(hitID > r.hitID) {
132        return 1;
133      } else if(hitID < r.hitID) {
134        return -1;
135      }
136      
137      int relDist = queryOffset + hitOffset - (r.queryOffset + r.hitOffset);
138      
139      if(relDist > 0) {
140        return 1;
141      } else if(relDist < 0) {
142        return -1;
143      } else if(hitOffset > r.hitOffset) {
144        return 1;
145      } else if(hitOffset < r.hitOffset) {
146        return -1;
147      } else if(hitLength > r.hitLength) {
148        return 1;
149      } else if(hitLength < r.hitLength) {
150        return -1;
151      } else {
152        return 0;
153      }
154    }
155    
156    public String toString() {
157      return hitID + " " + queryOffset + " " + hitOffset + " " + hitLength;
158    }
159  }
160}