git://source.jalview.org
/
jalview.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Merge branch 'develop' into features/JAL-2446NCList
[jalview.git]
/
src
/
jalview
/
datamodel
/
features
/
NCList.java
diff --git
a/src/jalview/datamodel/features/NCList.java
b/src/jalview/datamodel/features/NCList.java
index
9906884
..
a6a23e7
100644
(file)
--- a/
src/jalview/datamodel/features/NCList.java
+++ b/
src/jalview/datamodel/features/NCList.java
@@
-1,8
+1,10
@@
package jalview.datamodel.features;
package jalview.datamodel.features;
+import jalview.datamodel.ContiguousI;
+import jalview.datamodel.Range;
+
import java.util.ArrayList;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Collections;
-import java.util.Comparator;
import java.util.List;
/**
import java.util.List;
/**
@@
-28,12
+30,6
@@
public class NCList<T extends ContiguousI>
*/
private List<NCNode<T>> subranges;
*/
private List<NCNode<T>> subranges;
- /*
- * a comparator to sort intervals by start position ascending, with
- * longer (enclosing) intervals preceding those they enclose
- */
- Comparator<ContiguousI> 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.
/**
* 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<T extends ContiguousI>
}
/**
}
/**
+ * Sort and group ranges into sublists where each sublist represents a region
+ * and its contained subregions
+ *
* @param ranges
*/
protected void build(List<T> ranges)
* @param ranges
*/
protected void build(List<T> ranges)
@@
-58,18
+57,18
@@
public class NCList<T extends ContiguousI>
* sort by start ascending so that contained intervals
* follow their containing interval
*/
* sort by start ascending so that contained intervals
* follow their containing interval
*/
- Collections.sort(ranges, intervalSorter);
+ Collections.sort(ranges, RangeComparator.BY_START_POSITION);
- List<SubList> sublists = buildSubranges(ranges);
+ List<Range> sublists = buildSubranges(ranges);
/*
* convert each subrange to an NCNode consisting of a range and
* (possibly) its contained NCList
*/
/*
* 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<T>(ranges.subList(sublist.startIndex,
- sublist.endIndex + 1)));
+ subranges.add(new NCNode<T>(ranges.subList(sublist.start,
+ sublist.end + 1)));
}
size = ranges.size();
}
size = ranges.size();
@@
-78,9
+77,8
@@
public class NCList<T extends ContiguousI>
public NCList(T entry)
{
this();
public NCList(T entry)
{
this();
- List<T> ranges = new ArrayList<T>();
- ranges.add(entry);
- build(ranges);
+ subranges.add(new NCNode<T>(entry));
+ size = 1;
}
public NCList()
}
public NCList()
@@
-95,9
+93,9
@@
public class NCList<T extends ContiguousI>
* @param ranges
* @return
*/
* @param ranges
* @return
*/
- protected List<SubList> buildSubranges(List<T> ranges)
+ protected List<Range> buildSubranges(List<T> ranges)
{
{
- List<SubList> sublists = new ArrayList<SubList>();
+ List<Range> sublists = new ArrayList<Range>();
if (ranges.isEmpty())
{
if (ranges.isEmpty())
{
@@
-118,13
+116,13
@@
public class NCList<T extends ContiguousI>
* this interval is not contained in the preceding one
* close off the last sublist
*/
* 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;
}
listStartIndex = i;
}
lastEndPos = nextEnd;
}
- sublists.add(new SubList(listStartIndex, ranges.size() - 1));
+ sublists.add(new Range(listStartIndex, ranges.size() - 1));
return sublists;
}
return sublists;
}
@@
-326,7
+324,7
@@
public class NCList<T extends ContiguousI>
final int j)
{
NCList<T> newNCList = new NCList<T>();
final int j)
{
NCList<T> newNCList = new NCList<T>();
- newNCList.subranges.addAll(subranges.subList(i, j + 1));
+ newNCList.addNodes(subranges.subList(i, j + 1));
NCNode<T> newNode = new NCNode<T>(entry, newNCList);
for (int k = j; k >= i; k--)
{
NCNode<T> newNode = new NCNode<T>(entry, newNCList);
for (int k = j; k >= i; k--)
{
@@
-335,6
+333,15
@@
public class NCList<T extends ContiguousI>
subranges.add(i, newNode);
}
subranges.add(i, newNode);
}
+ protected void addNodes(List<NCNode<T>> nodes)
+ {
+ for (NCNode<T> node : nodes)
+ {
+ subranges.add(node);
+ size += node.size();
+ }
+ }
+
/**
* Returns a (possibly empty) list of items whose extent overlaps the given
* range
/**
* Returns a (possibly empty) list of items whose extent overlaps the given
* range
@@
-401,8
+408,12
@@
public class NCList<T extends ContiguousI>
*/
protected int findFirstOverlap(long from)
{
*/
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)
{
int i = 0;
if (subranges != null)
{
@@
-531,7
+542,7
@@
public class NCList<T extends ContiguousI>
*
* @return
*/
*
* @return
*/
- public int getSize()
+ public int size()
{
return size;
}
{
return size;
}
@@
-594,8
+605,8
@@
public class NCList<T extends ContiguousI>
subranges.remove(i);
if (subRegions != null)
{
subranges.remove(i);
if (subRegions != null)
{
- subranges.addAll(i, subRegions.subranges);
- Collections.sort(subranges, intervalSorter);
+ subranges.addAll(subRegions.subranges);
+ Collections.sort(subranges, RangeComparator.BY_START_POSITION);
}
size--;
return true;
}
size--;
return true;
@@
-605,6
+616,7
@@
public class NCList<T extends ContiguousI>
if (subRegions != null && subRegions.delete(entry))
{
size--;
if (subRegions != null && subRegions.delete(entry))
{
size--;
+ subrange.deleteSubRegionsIfEmpty();
return true;
}
}
return true;
}
}