X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FNCList.java;h=a6a23e70518fa7257a61998579778ca06219fdc8;hb=ffa5c07d90b4a933762a5d9faa0578c11693d63a;hp=17e08eb6ac985772c4ae8157b7ab3f7cf3c2ecfa;hpb=fdea751663ec46a587cfdf45bfae9ec667043efb;p=jalview.git diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java index 17e08eb..a6a23e7 100644 --- a/src/jalview/datamodel/features/NCList.java +++ b/src/jalview/datamodel/features/NCList.java @@ -1,8 +1,10 @@ package jalview.datamodel.features; +import jalview.datamodel.ContiguousI; +import jalview.datamodel.Range; + import java.util.ArrayList; import java.util.Collections; -import java.util.Comparator; import java.util.List; /** @@ -28,12 +30,6 @@ public class NCList */ private List> subranges; - /* - * a comparator to sort intervals by start position ascending, with - * longer (enclosing) intervals preceding those they enclose - */ - Comparator intervalSorter = new RangeComparator(true); - /** * Constructor given a list of things that are each located on a contiguous * interval. Note that the constructor may reorder the list. @@ -50,6 +46,9 @@ public class NCList } /** + * Sort and group ranges into sublists where each sublist represents a region + * and its contained subregions + * * @param ranges */ protected void build(List ranges) @@ -58,18 +57,18 @@ public class NCList * sort by start ascending so that contained intervals * follow their containing interval */ - Collections.sort(ranges, intervalSorter); + Collections.sort(ranges, RangeComparator.BY_START_POSITION); - List sublists = buildSubranges(ranges); + List sublists = buildSubranges(ranges); /* * convert each subrange to an NCNode consisting of a range and * (possibly) its contained NCList */ - for (SubList sublist : sublists) + for (Range sublist : sublists) { - subranges.add(new NCNode(ranges.subList(sublist.startIndex, - sublist.endIndex + 1))); + subranges.add(new NCNode(ranges.subList(sublist.start, + sublist.end + 1))); } size = ranges.size(); @@ -78,9 +77,8 @@ public class NCList public NCList(T entry) { this(); - List ranges = new ArrayList(); - ranges.add(entry); - build(ranges); + subranges.add(new NCNode(entry)); + size = 1; } public NCList() @@ -95,10 +93,15 @@ public class NCList * @param ranges * @return */ - protected List buildSubranges(List ranges) + protected List buildSubranges(List ranges) { - List sublists = new ArrayList(); + List sublists = new ArrayList(); + if (ranges.isEmpty()) + { + return sublists; + } + int listStartIndex = 0; long lastEndPos = Long.MAX_VALUE; @@ -113,13 +116,13 @@ public class NCList * this interval is not contained in the preceding one * close off the last sublist */ - sublists.add(new SubList(listStartIndex, i - 1)); + sublists.add(new Range(listStartIndex, i - 1)); listStartIndex = i; } lastEndPos = nextEnd; } - sublists.add(new SubList(listStartIndex, ranges.size() - 1)); + sublists.add(new Range(listStartIndex, ranges.size() - 1)); return sublists; } @@ -188,7 +191,7 @@ public class NCList { NCNode subrange = subranges.get(j); - if (end < subrange.getStart() && !overlapping && !enclosing) + if (end < subrange.getBegin() && !overlapping && !enclosing) { /* * new entry lies between subranges j-1 j @@ -197,7 +200,7 @@ public class NCList return true; } - if (subrange.getStart() <= start && subrange.getEnd() >= end) + if (subrange.getBegin() <= start && subrange.getEnd() >= end) { /* * push new entry inside this subrange as it encloses it @@ -206,7 +209,7 @@ public class NCList return true; } - if (start <= subrange.getStart()) + if (start <= subrange.getBegin()) { if (end >= subrange.getEnd()) { @@ -293,7 +296,7 @@ public class NCList for (int i = candidateIndex; i < subranges.size(); i++) { NCNode candidate = subranges.get(i); - if (candidate.getStart() > to) + if (candidate.getBegin() > to) { /* * we are past the end of our target range @@ -321,7 +324,7 @@ public class NCList final int j) { NCList newNCList = new NCList(); - newNCList.subranges.addAll(subranges.subList(i, j + 1)); + newNCList.addNodes(subranges.subList(i, j + 1)); NCNode newNode = new NCNode(entry, newNCList); for (int k = j; k >= i; k--) { @@ -330,6 +333,15 @@ public class NCList subranges.add(i, newNode); } + protected void addNodes(List> nodes) + { + for (NCNode node : nodes) + { + subranges.add(node); + size += node.size(); + } + } + /** * Returns a (possibly empty) list of items whose extent overlaps the given * range @@ -373,7 +385,7 @@ public class NCList for (int i = candidateIndex; i < subranges.size(); i++) { NCNode candidate = subranges.get(i); - if (candidate.getStart() > to) + if (candidate.getBegin() > to) { /* * we are past the end of our target range @@ -396,8 +408,12 @@ public class NCList */ protected int findFirstOverlap(long from) { - // TODO binary search - // for now quick cheat linear search + /* + * The NCList paper describes binary search for this step, + * but this not implemented here as (a) I haven't understood it yet + * and (b) it seems to imply complications for adding to an NCList + */ + int i = 0; if (subranges != null) { @@ -427,7 +443,7 @@ public class NCList } /** - * Returns a string representation of the data where containment is shown bgy + * Returns a string representation of the data where containment is shown by * indentation on new lines * * @return @@ -438,6 +454,7 @@ public class NCList int offset = 0; int indent = 2; prettyPrint(sb, offset, indent); + sb.append(System.lineSeparator()); return sb.toString(); } @@ -488,7 +505,7 @@ public class NCList int lastStart = start; for (NCNode subrange : subranges) { - if (subrange.getStart() < lastStart) + if (subrange.getBegin() < lastStart) { System.err.println("error in NCList: range " + subrange.toString() + " starts before " + lastStart); @@ -500,7 +517,7 @@ public class NCList + " ends after " + end); return false; } - lastStart = subrange.getStart(); + lastStart = subrange.getBegin(); if (!subrange.isValid()) { @@ -517,7 +534,7 @@ public class NCList */ public int getStart() { - return subranges.isEmpty() ? 0 : subranges.get(0).getStart(); + return subranges.isEmpty() ? 0 : subranges.get(0).getBegin(); } /** @@ -525,7 +542,7 @@ public class NCList * * @return */ - public int getSize() + public int size() { return size; } @@ -579,12 +596,17 @@ public class NCList { /* * if the subrange is rooted on this entry, promote its - * subregions (if any) to replace the subrange here + * subregions (if any) to replace the subrange here; + * NB have to resort subranges after doing this since e.g. + * [10-30 [12-20 [16-18], 13-19]] + * after deleting 12-20, 16-18 is promoted to sibling of 13-19 + * but should follow it in the list of subranges of 10-30 */ subranges.remove(i); if (subRegions != null) { - subranges.addAll(i, subRegions.subranges); + subranges.addAll(subRegions.subranges); + Collections.sort(subranges, RangeComparator.BY_START_POSITION); } size--; return true; @@ -594,30 +616,11 @@ public class NCList if (subRegions != null && subRegions.delete(entry)) { size--; + subrange.deleteSubRegionsIfEmpty(); return true; } } } return false; } - - /** - * Answers true if this contains no ranges - * - * @return - */ - public boolean isEmpty() - { - return getSize() == 0; - } - - /** - * Answer the list of subranges held in this NCList - * - * @return - */ - List> getSubregions() - { - return subranges; - } }