JAL-1834 removed quotes around truncated strings with ellipsis
[jalview.git] / src / jalview / analysis / SequenceIdMatcher.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.analysis;
22
23 import jalview.datamodel.DBRefEntry;
24 import jalview.datamodel.SequenceI;
25
26 import java.util.ArrayList;
27 import java.util.Arrays;
28 import java.util.HashMap;
29 import java.util.List;
30 import java.util.Vector;
31
32 /**
33  * Routines for approximate Sequence Id resolution by name using string
34  * containment (on word boundaries) rather than equivalence. It also attempts to
35  * resolve ties where no exact match is available by picking the the id closest
36  * to the query.
37  */
38 public class SequenceIdMatcher
39 {
40   private HashMap<SeqIdName, SequenceI> names;
41
42   public SequenceIdMatcher(List<SequenceI> seqs)
43   {
44     names = new HashMap<SeqIdName, SequenceI>();
45     addAll(seqs);
46   }
47
48   /**
49    * add more sequences to this matcher - also used by the constructor
50    * 
51    * @param seqs
52    */
53   public void addAll(List<SequenceI> seqs)
54   {
55     for (SequenceI seq : seqs)
56     {
57       // TODO: deal with ID collisions - SequenceI should be appended to list
58       // associated with this key.
59       names.put(new SeqIdName(seq.getDisplayId(true)), seq);
60       SequenceI dbseq = seq;
61       while (dbseq.getDatasetSequence()!=null)
62       {
63         dbseq = dbseq.getDatasetSequence();
64       }
65       // add in any interesting identifiers
66       if (dbseq.getDBRef() != null)
67       {
68         DBRefEntry dbr[] = dbseq.getDBRef();
69         SeqIdName sid = null;
70         for (int r = 0; r < dbr.length; r++)
71         {
72           sid = new SeqIdName(dbr[r].getAccessionId());
73           if (!names.containsKey(sid))
74           {
75             names.put(sid, seq);
76           }
77         }
78       }
79     }
80   }
81
82   /**
83    * convenience method to make a matcher from concrete array
84    * 
85    * @param sequences
86    */
87   public SequenceIdMatcher(SequenceI[] sequences)
88   {
89     this(Arrays.asList(sequences));
90   }
91
92   /**
93    * returns the closest SequenceI in matches to SeqIdName and returns all the
94    * matches to the names hash.
95    * 
96    * @param candName
97    *          SeqIdName
98    * @param matches
99    *          List of SequenceI objects
100    * @return SequenceI closest SequenceI to SeqIdName
101    */
102   private SequenceI pickbestMatch(SeqIdName candName,
103           List<SequenceI> matches)
104   {
105     List<SequenceI> st = pickbestMatches(candName, matches);
106     return st == null || st.size() == 0 ? null : st.get(0);
107   }
108
109   /**
110    * returns the closest SequenceI in matches to SeqIdName and returns all the
111    * matches to the names hash.
112    * 
113    * @param candName
114    *          SeqIdName
115    * @param matches
116    *          Vector of SequenceI objects
117    * @return Object[] { SequenceI closest SequenceI to SeqIdName, SequenceI[]
118    *         ties }
119    */
120   private List<SequenceI> pickbestMatches(SeqIdName candName,
121           List<SequenceI> matches)
122   {
123     ArrayList<SequenceI> best = new ArrayList<SequenceI>();
124     if (candName == null || matches == null || matches.size() == 0)
125     {
126       return null;
127     }
128     SequenceI match = matches.remove(0);
129     best.add(match);
130     names.put(new SeqIdName(match.getName()), match);
131     int matchlen = match.getName().length();
132     int namlen = candName.id.length();
133     while (matches.size() > 0)
134     {
135       // look through for a better one.
136       SequenceI cand = matches.remove(0);
137       names.put(new SeqIdName(cand.getName()), cand);
138       int q, w, candlen = cand.getName().length();
139       // keep the one with an id 'closer' to the given seqnam string
140       if ((q = Math.abs(matchlen - namlen)) > (w = Math.abs(candlen
141               - namlen))
142               && candlen > matchlen)
143       {
144         best.clear();
145         match = cand;
146         matchlen = candlen;
147         best.add(match);
148       }
149       if (q == w && candlen == matchlen)
150       {
151         // record any ties
152         best.add(cand);
153       }
154     }
155     if (best.size() == 0)
156     {
157       return null;
158     }
159     ;
160     return best;
161   }
162
163   /**
164    * get SequenceI with closest SequenceI.getName() to seq.getName()
165    * 
166    * @param seq
167    *          SequenceI
168    * @return SequenceI
169    */
170   public SequenceI findIdMatch(SequenceI seq)
171   {
172     SeqIdName nam = new SeqIdName(seq.getName());
173     return findIdMatch(nam);
174   }
175
176   public SequenceI findIdMatch(String seqnam)
177   {
178     SeqIdName nam = new SeqIdName(seqnam);
179     return findIdMatch(nam);
180   }
181
182   /**
183    * Find all matches for a given sequence name.
184    * 
185    * @param seqnam
186    *          string to query Matcher with.
187    * @return a new array or (possibly) null
188    */
189   public SequenceI[] findAllIdMatches(String seqnam)
190   {
191
192     SeqIdName nam = new SeqIdName(seqnam);
193     List<SequenceI> m = findAllIdMatches(nam);
194     if (m!=null)
195     {
196       return m.toArray(new SequenceI[m.size()]);
197     }
198     return null;
199   }
200
201   /**
202    * findIdMatch
203    * 
204    * Return pointers to sequences (or sequence object containers) which have
205    * same Id as a given set of different sequence objects
206    * 
207    * @param seqs
208    *          SequenceI[]
209    * @return SequenceI[]
210    */
211   public SequenceI[] findIdMatch(SequenceI[] seqs)
212   {
213     SequenceI[] namedseqs = null;
214     int i = 0;
215     SeqIdName nam;
216
217     if (seqs.length > 0)
218     {
219       namedseqs = new SequenceI[seqs.length];
220       do
221       {
222         nam = new SeqIdName(seqs[i].getName());
223
224         if (names.containsKey(nam))
225         {
226           namedseqs[i] = findIdMatch(nam);
227         }
228         else
229         {
230           namedseqs[i] = null;
231         }
232       } while (++i < seqs.length);
233     }
234
235     return namedseqs;
236   }
237
238   /**
239    * core findIdMatch search method
240    * 
241    * @param nam
242    *          SeqIdName
243    * @return SequenceI
244    */
245   private SequenceI findIdMatch(
246           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
247   {
248     Vector matches = new Vector();
249     while (names.containsKey(nam))
250     {
251       matches.addElement(names.remove(nam));
252     }
253     return pickbestMatch(nam, matches);
254   }
255
256   /**
257    * core findIdMatch search method for finding all equivalent matches
258    * 
259    * @param nam
260    *          SeqIdName
261    * @return SequenceI[]
262    */
263   private List<SequenceI> findAllIdMatches(
264           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
265   {
266     ArrayList<SequenceI> matches = new ArrayList<SequenceI>();
267     while (names.containsKey(nam))
268     {
269       matches.add(names.remove(nam));
270     }
271     List<SequenceI> r = pickbestMatches(nam, matches);
272     return r;
273   }
274
275   private class SeqIdName
276   {
277     String id;
278
279     SeqIdName(String s)
280     {
281       if (s != null)
282       {
283         id = new String(s);
284       }
285       else
286       {
287         id = "";
288       }
289     }
290
291     @Override
292     public int hashCode()
293     {
294       return ((id.length() >= 4) ? id.substring(0, 4).hashCode() : id
295               .hashCode());
296     }
297
298     @Override
299     public boolean equals(Object s)
300     {
301       if (s == null)
302       {
303         return false;
304       }
305       if (s instanceof SeqIdName)
306       {
307         return this.equals((SeqIdName) s);
308       }
309       else
310       {
311         if (s instanceof String)
312         {
313           return this.equals((String) s);
314         }
315       }
316
317       return false;
318     }
319
320     /**
321      * Characters that define the end of a unique sequence ID at the beginning
322      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
323      * arbritrarily extended sequence id's (like portions of an aligned set of
324      * repeats from one sequence)
325      */
326     private String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4)
327             + "$%^*)}[@',?_";
328
329     /**
330      * matches if one ID properly contains another at a whitespace boundary.
331      * TODO: (JBPNote) These are not efficient. should use char[] for speed
332      * todo: (JBPNote) Set separator characters appropriately
333      * 
334      * @param s
335      *          SeqIdName
336      * @return boolean
337      */
338     public boolean equals(SeqIdName s)
339     {
340       // TODO: JAL-732 patch for cases when name includes a list of IDs, and the
341       // match contains one ID flanked
342       if (id.length() > s.id.length())
343       {
344         return id.startsWith(s.id) ? (WORD_SEP.indexOf(id.charAt(s.id
345                 .length())) > -1) : false;
346       }
347       else
348       {
349         return s.id.startsWith(id) ? (s.id.equals(id) ? true : (WORD_SEP
350                 .indexOf(s.id.charAt(id.length())) > -1)) : false;
351       }
352     }
353
354     public boolean equals(String s)
355     {
356       if (id.length() > s.length())
357       {
358         return id.startsWith(s) ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
359                 : false;
360       }
361       else
362       {
363         return s.startsWith(id) ? (s.equals(id) ? true : (WORD_SEP
364                 .indexOf(s.charAt(id.length())) > -1)) : false;
365       }
366     }
367   }
368 }