From 70a93ebbabd80e25c60a0e6444013ed4260b09a5 Mon Sep 17 00:00:00 2001 From: gmungoc Date: Fri, 2 Jun 2017 16:33:44 +0100 Subject: [PATCH] JAL-2526 additional tests for findPosition with/without cursor/edit --- src/jalview/datamodel/Sequence.java | 123 ++++++-- src/jalview/datamodel/SequenceCursor.java | 49 ++++ test/jalview/datamodel/SequenceTest.java | 294 +++++++++++++++++--- .../schemes/AnnotationColourGradientTest.java | 2 +- 4 files changed, 402 insertions(+), 66 deletions(-) diff --git a/src/jalview/datamodel/Sequence.java b/src/jalview/datamodel/Sequence.java index cc4a0dc..24f904c 100755 --- a/src/jalview/datamodel/Sequence.java +++ b/src/jalview/datamodel/Sequence.java @@ -664,19 +664,16 @@ public class Sequence extends ASequence implements SequenceI return this.description; } - /* - * (non-Javadoc) - * - * @see jalview.datamodel.SequenceI#findIndex(int) + /** + * {@inheritDoc} */ @Override public int findIndex(int pos) { /* - * use a valid nearby cursor if available + * use a valid, hopefully nearby, cursor if available */ - if (cursor != null && cursor.sequence == this - && cursor.token == changeCount) + if (isValidCursor(cursor)) { return findIndex(pos, cursor); } @@ -693,20 +690,25 @@ public class Sequence extends ASequence implements SequenceI i++; } - if ((j == end) && (j < pos)) + if (j == end && j < pos) { return end + 1; } - else - { - updateCursor(pos, i); - return i; - } + + updateCursor(pos, i); + return i; } + /** + * Updates the cursor to the latest found residue and column position + * + * @param residuePos + * (start..) + * @param column + * (1..) + */ protected void updateCursor(int residuePos, int column) { - // TODO probably want to synchronize this on something cursor = new SequenceCursor(this, residuePos, column, this.changeCount); } @@ -721,7 +723,7 @@ public class Sequence extends ASequence implements SequenceI */ protected int findIndex(int pos, SequenceCursor curs) { - if (curs.sequence != this || curs.token != changeCount) + if (!isValidCursor(curs)) { /* * wrong or invalidated cursor, compute de novo @@ -761,40 +763,93 @@ public class Sequence extends ASequence implements SequenceI return col; } + /** + * {@inheritDoc} + */ @Override - public int findPosition(final int i) + public int findPosition(final int column) { /* - * use a valid nearby cursor if available + * use a valid, hopefully nearby, cursor if available */ - if (cursor != null && cursor.sequence == this - && cursor.token == changeCount) + if (isValidCursor(cursor)) { - return findPosition(i + 1, cursor); + return findPosition(column + 1, cursor); + } + + // TODO recode this more naturally i.e. count residues only + // as they are found, not 'in anticipation' + + int lastPosFound = 0; + int lastPosFoundColumn = 0; + int seqlen = sequence.length; + if (seqlen > 0 && !Comparison.isGap(sequence[0])) + { + lastPosFound = start; + lastPosFoundColumn = 0; } int j = 0; int pos = start; - int seqlen = sequence.length; - while ((j < i) && (j < seqlen)) + + while (j < column && j < seqlen) { if (!Comparison.isGap(sequence[j])) { + lastPosFound = pos; + lastPosFoundColumn = j; pos++; } - j++; } + if (j < seqlen && !Comparison.isGap(sequence[j])) + { + lastPosFound = pos; + lastPosFoundColumn = j; + } - if (j == i && !Comparison.isGap(sequence[i])) + /* + * update the cursor to the last residue position found (if any) + * (converting column position to base 1) + */ + if (lastPosFound != 0) { - updateCursor(pos, i + 1); + updateCursor(lastPosFound, lastPosFoundColumn + 1); } return pos; } /** + * Answers true if the given cursor is not null, is for this sequence object, + * and has a token value that matches this object's changeCount, else false. + * This allows us to ignore a cursor as 'stale' if the sequence has been + * modified since the cursor was created. + * + * @param curs + * @return + */ + protected boolean isValidCursor(SequenceCursor curs) + { + if (curs == null || curs.sequence != this || curs.token != changeCount) + { + return false; + } + /* + * sanity check against range + */ + if (curs.columnPosition < 0 || curs.columnPosition >= sequence.length) + { + return false; + } + if (curs.residuePosition < start || curs.residuePosition > end) + { + return false; + } + return true; + } + + /** * Answers the sequence position (start..) for the given aligned column * position (1..), given a hint of a cursor in the neighbourhood. The cursor * may lie left of, at, or to the right of the column position. @@ -805,7 +860,7 @@ public class Sequence extends ASequence implements SequenceI */ protected int findPosition(final int col, SequenceCursor curs) { - if (curs.sequence != this || curs.token != changeCount) + if (!isValidCursor(curs)) { /* * wrong or invalidated cursor, compute de novo @@ -815,6 +870,7 @@ public class Sequence extends ASequence implements SequenceI if (curs.columnPosition == col) { + cursor = curs; // in case this method becomes public return curs.residuePosition; // easy case :-) } @@ -825,6 +881,8 @@ public class Sequence extends ASequence implements SequenceI int newPos = curs.residuePosition; int delta = curs.columnPosition > col ? -1 : 1; boolean gapped = false; + int lastFoundPosition = curs.residuePosition; + int lastFoundPositionColumn = curs.columnPosition; while (column != col - 1) { @@ -837,14 +895,21 @@ public class Sequence extends ASequence implements SequenceI if (!gapped) { newPos += delta; + lastFoundPosition = newPos; + lastFoundPositionColumn = column + 1; } } + if (cursor == null || lastFoundPosition != cursor.residuePosition) + { + updateCursor(lastFoundPosition, lastFoundPositionColumn); + } + /* * hack to give position to the right if on a gap - * pending resolution of JAL-2562 + * or beyond the length of the sequence (see JAL-2562) */ - if (delta > 0 && gapped) + if (delta > 0 && (gapped || column >= sequence.length)) { newPos++; } @@ -934,7 +999,7 @@ public class Sequence extends ASequence implements SequenceI */ protected Range findPositions(int fromCol, int toCol, SequenceCursor curs) { - if (curs.sequence != this || curs.token != changeCount) + if (!isValidCursor(curs)) { /* * wrong or invalidated cursor, compute de novo diff --git a/src/jalview/datamodel/SequenceCursor.java b/src/jalview/datamodel/SequenceCursor.java index 482e0fa..f439ee1 100644 --- a/src/jalview/datamodel/SequenceCursor.java +++ b/src/jalview/datamodel/SequenceCursor.java @@ -27,6 +27,19 @@ public class SequenceCursor */ public final int token; + /** + * Constructor + * + * @param seq + * sequence this cursor applies to + * @param resPos + * residue position in sequence (start..) + * @param column + * column position in alignment (1..) + * @param tok + * a token that may be validated by the sequence to check the cursor + * is not stale + */ public SequenceCursor(SequenceI seq, int resPos, int column, int tok) { sequence = seq; @@ -34,4 +47,40 @@ public class SequenceCursor columnPosition = column; token = tok; } + + @Override + public int hashCode() + { + int hash = 31 * residuePosition; + hash = 31 * hash + columnPosition; + hash = 31 * hash + token; + if (sequence != null) + { + hash += sequence.hashCode(); + } + return hash; + } + + /** + * Two cursors are equal if they refer to the same sequence object and have + * the same residue position, column position and token value + */ + @Override + public boolean equals(Object obj) + { + if (!(obj instanceof SequenceCursor)) + { + return false; + } + SequenceCursor sc = (SequenceCursor) obj; + return sequence == sc.sequence && residuePosition == sc.residuePosition + && columnPosition == sc.columnPosition && token == sc.token; + } + + @Override + public String toString() + { + return (sequence == null ? "" : sequence.getName()) + ":Pos" + + residuePosition + ":Col" + columnPosition + ":tok" + token; + } } diff --git a/test/jalview/datamodel/SequenceTest.java b/test/jalview/datamodel/SequenceTest.java index e2e14b4..4f42947 100644 --- a/test/jalview/datamodel/SequenceTest.java +++ b/test/jalview/datamodel/SequenceTest.java @@ -28,6 +28,8 @@ import static org.testng.AssertJUnit.assertNull; import static org.testng.AssertJUnit.assertSame; import static org.testng.AssertJUnit.assertTrue; +import jalview.commands.EditCommand; +import jalview.commands.EditCommand.Action; import jalview.datamodel.PDBEntry.Type; import jalview.gui.JvOptionPane; import jalview.util.MapList; @@ -224,72 +226,152 @@ public class SequenceTest @Test(groups = { "Functional" }) public void testFindIndex() { + /* + * call sequenceChanged() after each test to invalidate any cursor, + * forcing the 1-arg findIndex to be executed + */ SequenceI sq = new Sequence("test", "ABCDEF"); assertEquals(0, sq.findIndex(0)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(1, sq.findIndex(1)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(5, sq.findIndex(5)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(6, sq.findIndex(6)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(6, sq.findIndex(9)); sq = new Sequence("test/8-13", "-A--B-C-D-E-F--"); assertEquals(2, sq.findIndex(8)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(5, sq.findIndex(9)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(7, sq.findIndex(10)); // before start returns 0 - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(0, sq.findIndex(0)); - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(0, sq.findIndex(-1)); // beyond end returns last residue column - PA.setValue(sq, "cursor", null); + sq.sequenceChanged(); assertEquals(13, sq.findIndex(99)); } /** - * Tests for the method that returns a dataset sequence position (base 1) for + * Tests for the method that returns a dataset sequence position (start..) for * an aligned column position (base 0). */ @Test(groups = { "Functional" }) public void testFindPosition() { - SequenceI sq = new Sequence("test", "ABCDEF"); - assertEquals(1, sq.findPosition(0)); - assertEquals(6, sq.findPosition(5)); + /* + * call sequenceChanged() after each test to invalidate any cursor, + * forcing the 1-arg findPosition to be executed + */ + SequenceI sq = new Sequence("test/8-13", "ABCDEF"); + assertEquals(8, sq.findPosition(0)); + // Sequence should now hold a cursor at [8, 0] + SequenceCursor cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + int token = (int) PA.getValue(sq, "changeCount"); + assertEquals(new SequenceCursor(sq, 8, 1, token), cursor); + + sq.sequenceChanged(); + + /* + * find F13 at column offset 5, cursor should update to [13, 6] + */ + assertEquals(13, sq.findPosition(5)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(++token, (int) PA.getValue(sq, "changeCount")); + assertEquals(new SequenceCursor(sq, 13, 6, token), cursor); + // assertEquals(-1, seq.findPosition(6)); // fails - sq = new Sequence("test", "AB-C-D--"); - assertEquals(1, sq.findPosition(0)); - assertEquals(2, sq.findPosition(1)); + sq = new Sequence("test/8-11", "AB-C-D--"); + token = (int) PA.getValue(sq, "changeCount"); // 0 + assertEquals(8, sq.findPosition(0)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 8, 1, token), cursor); + + sq.sequenceChanged(); + assertEquals(9, sq.findPosition(1)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 9, 2, ++token), cursor); + + sq.sequenceChanged(); // gap position 'finds' residue to the right (not the left as per javadoc) - assertEquals(3, sq.findPosition(2)); - assertEquals(3, sq.findPosition(3)); - assertEquals(4, sq.findPosition(4)); - assertEquals(4, sq.findPosition(5)); + // cursor is set to the last residue position found [B 2] + assertEquals(10, sq.findPosition(2)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 9, 2, ++token), cursor); + + sq.sequenceChanged(); + assertEquals(10, sq.findPosition(3)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 10, 4, ++token), cursor); + + sq.sequenceChanged(); + // column[4] is the gap after C - returns D11 + // cursor is set to [C 4] + assertEquals(11, sq.findPosition(4)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 10, 4, ++token), cursor); + + sq.sequenceChanged(); + assertEquals(11, sq.findPosition(5)); // D + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 11, 6, ++token), cursor); + + sq.sequenceChanged(); // returns 1 more than sequence length if off the end ?!? - assertEquals(5, sq.findPosition(6)); - assertEquals(5, sq.findPosition(7)); + assertEquals(12, sq.findPosition(6)); - sq = new Sequence("test", "--AB-C-DEF--"); - assertEquals(1, sq.findPosition(0)); - assertEquals(1, sq.findPosition(1)); - assertEquals(1, sq.findPosition(2)); - assertEquals(2, sq.findPosition(3)); - assertEquals(3, sq.findPosition(4)); - assertEquals(3, sq.findPosition(5)); - assertEquals(4, sq.findPosition(6)); - assertEquals(4, sq.findPosition(7)); - assertEquals(5, sq.findPosition(8)); - assertEquals(6, sq.findPosition(9)); - assertEquals(7, sq.findPosition(10)); - assertEquals(7, sq.findPosition(11)); + sq.sequenceChanged(); + assertEquals(12, sq.findPosition(7)); + + sq = new Sequence("test/8-13", "--AB-C-DEF--"); + assertEquals(8, sq.findPosition(0)); + + sq.sequenceChanged(); + assertEquals(8, sq.findPosition(1)); + + sq.sequenceChanged(); + assertEquals(8, sq.findPosition(2)); + + sq.sequenceChanged(); + assertEquals(9, sq.findPosition(3)); + + sq.sequenceChanged(); + assertEquals(10, sq.findPosition(4)); + + sq.sequenceChanged(); + assertEquals(10, sq.findPosition(5)); + + sq.sequenceChanged(); + assertEquals(11, sq.findPosition(6)); + + sq.sequenceChanged(); + assertEquals(11, sq.findPosition(7)); + + sq.sequenceChanged(); + assertEquals(12, sq.findPosition(8)); + + sq.sequenceChanged(); + assertEquals(13, sq.findPosition(9)); + + sq.sequenceChanged(); + assertEquals(14, sq.findPosition(10)); + + /* + * findPosition for column beyond sequence length + * returns 1 more than last residue position + */ + sq.sequenceChanged(); + assertEquals(14, sq.findPosition(11)); + sq.sequenceChanged(); + assertEquals(14, sq.findPosition(99)); } @Test(groups = { "Functional" }) @@ -1212,23 +1294,62 @@ public class SequenceTest // find F pos given A assertEquals(13, sq.findPosition(10, new SequenceCursor(sq, 8, 2, 0))); - + int token = (int) PA.getValue(sq, "changeCount"); // 0 + SequenceCursor cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 13, 10, token), cursor); + // find A pos given F assertEquals(8, sq.findPosition(2, new SequenceCursor(sq, 13, 10, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 8, 2, token), cursor); // find C pos given C assertEquals(10, sq.findPosition(6, new SequenceCursor(sq, 10, 6, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 10, 6, token), cursor); // now the grey area - what residue position for a gapped column? JAL-2562 // find 'residue' for column 3 given cursor for D (so working left) + // returns B9; cursor is updated to [B 5] assertEquals(9, sq.findPosition(3, new SequenceCursor(sq, 11, 7, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 9, 5, token), cursor); // find 'residue' for column 8 given cursor for D (so working right) + // returns E12; cursor is updated to [D 7] assertEquals(12, sq.findPosition(8, new SequenceCursor(sq, 11, 7, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 11, 7, token), cursor); // find 'residue' for column 12 given cursor for B + // returns 1 more than last residue position; cursor is updated to [F 10] assertEquals(14, sq.findPosition(12, new SequenceCursor(sq, 9, 5, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 13, 10, token), cursor); + + /* + * findPosition for column beyond length of sequence + * returns 1 more than the last residue position + * cursor is set to last real residue position [F 10] + */ + assertEquals(14, sq.findPosition(99, new SequenceCursor(sq, 8, 2, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 13, 10, token), cursor); + + /* + * and the case without a trailing gap + */ + sq = new Sequence("test/8-13", "-A--BCD-EF"); + // first find C from A + assertEquals(10, sq.findPosition(6, new SequenceCursor(sq, 8, 2, 0))); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 10, 6, token), cursor); + // now 'find' 99 from C + // cursor is set to [F 10] + assertEquals(14, sq.findPosition(99, cursor)); + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 13, 10, token), cursor); } @Test @@ -1272,4 +1393,105 @@ public class SequenceTest range = sq.findPositions(2, 6, new SequenceCursor(sq, 13, 9, 0)); assertEquals(new Range(10, 12), range); } + + @Test + public void testIsValidCursor() + { + Sequence sq = new Sequence("Seq", "ABC--DE-F", 8, 13); + assertFalse(sq.isValidCursor(null)); + + /* + * cursor is valid if it has valid sequence ref and changeCount token + * and positions within the range of the sequence + */ + int changeCount = (int) PA.getValue(sq, "changeCount"); + SequenceCursor cursor = new SequenceCursor(sq, 13, 1, changeCount); + assertTrue(sq.isValidCursor(cursor)); + + /* + * column position outside [0 - length-1] is rejected + */ + cursor = new SequenceCursor(sq, 13, -1, changeCount); + assertFalse(sq.isValidCursor(cursor)); + cursor = new SequenceCursor(sq, 13, 9, changeCount); + assertFalse(sq.isValidCursor(cursor)); + cursor = new SequenceCursor(sq, 7, 8, changeCount); + assertFalse(sq.isValidCursor(cursor)); + cursor = new SequenceCursor(sq, 14, 2, changeCount); + assertFalse(sq.isValidCursor(cursor)); + + /* + * wrong sequence is rejected + */ + cursor = new SequenceCursor(null, 13, 1, changeCount); + assertFalse(sq.isValidCursor(cursor)); + cursor = new SequenceCursor(new Sequence("Seq", "abc"), 13, 1, + changeCount); + assertFalse(sq.isValidCursor(cursor)); + + /* + * wrong token value is rejected + */ + cursor = new SequenceCursor(sq, 13, 1, changeCount + 1); + assertFalse(sq.isValidCursor(cursor)); + cursor = new SequenceCursor(sq, 13, 1, changeCount - 1); + assertFalse(sq.isValidCursor(cursor)); + } + + @Test(groups = { "Functional" }) + public void testFindPosition_withCursorAndEdits() + { + Sequence sq = new Sequence("test/8-13", "-A--BCD-EF--"); + + // find F pos given A + assertEquals(13, sq.findPosition(10, new SequenceCursor(sq, 8, 2, 0))); + int token = (int) PA.getValue(sq, "changeCount"); // 0 + SequenceCursor cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 13, 10, token), cursor); + + /* + * setSequence should invalidate the cursor cached by the sequence + */ + sq.setSequence("-A-BCD-EF---"); // one gap removed + assertEquals(8, sq.getStart()); // sanity check + assertEquals(11, sq.findPosition(5)); // D11 + // cursor should now be at [D 6] + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 11, 6, ++token), cursor); + + /* + * deleteChars should invalidate the cached cursor + */ + sq.deleteChars(2, 5); // delete -BC + assertEquals("-AD-EF---", sq.getSequenceAsString()); + assertEquals(8, sq.getStart()); // sanity check + assertEquals(10, sq.findPosition(4)); // E10 + // cursor should now be at [E 5] + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 10, 5, ++token), cursor); + + /* + * Edit to insert gaps should invalidate the cached cursor + * insert 2 gaps at column[3] to make -AD---EF--- + */ + SequenceI[] seqs = new SequenceI[] { sq }; + AlignmentI al = new Alignment(seqs); + new EditCommand().appendEdit(Action.INSERT_GAP, seqs, 3, 2, al, true); + assertEquals("-AD---EF---", sq.getSequenceAsString()); + assertEquals(10, sq.findPosition(4)); // E10 + // cursor should now be at [D 3] + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 9, 3, ++token), cursor); + + /* + * insertCharAt should invalidate the cached cursor + * insert CC at column[4] to make -AD-CC--EF--- + */ + sq.insertCharAt(4, 2, 'C'); + assertEquals("-AD-CC--EF---", sq.getSequenceAsString()); + assertEquals(13, sq.findPosition(9)); // F13 + // cursor should now be at [F 10] + cursor = (SequenceCursor) PA.getValue(sq, "cursor"); + assertEquals(new SequenceCursor(sq, 13, 10, ++token), cursor); + } } diff --git a/test/jalview/schemes/AnnotationColourGradientTest.java b/test/jalview/schemes/AnnotationColourGradientTest.java index 1c93856..b7a5164 100644 --- a/test/jalview/schemes/AnnotationColourGradientTest.java +++ b/test/jalview/schemes/AnnotationColourGradientTest.java @@ -49,7 +49,7 @@ public class AnnotationColourGradientTest anns[col] = new Annotation("a", "a", 'a', col, colour); } - seq = new Sequence("", ""); + seq = new Sequence("Seq", ""); al = new Alignment(new SequenceI[]{ seq}); /* -- 1.7.10.2