From dd85e0fbce881a3c71ad20026311a28a10eb12de Mon Sep 17 00:00:00 2001 From: Jim Procter Date: Mon, 4 Apr 2016 14:13:08 +0100 Subject: [PATCH] JAL-2001 JAL-1722 - store selection as ArrayList and BitSet for fast addition of very large numbers of columns - all tests pass but needs verification --- src/jalview/datamodel/ColumnSelection.java | 228 ++++++++++++++++++---------- 1 file changed, 150 insertions(+), 78 deletions(-) diff --git a/src/jalview/datamodel/ColumnSelection.java b/src/jalview/datamodel/ColumnSelection.java index 6fb584c..9795570 100644 --- a/src/jalview/datamodel/ColumnSelection.java +++ b/src/jalview/datamodel/ColumnSelection.java @@ -25,6 +25,7 @@ import jalview.viewmodel.annotationfilter.AnnotationFilterParameter; import jalview.viewmodel.annotationfilter.AnnotationFilterParameter.SearchableAnnotationField; import java.util.ArrayList; +import java.util.BitSet; import java.util.Collections; import java.util.List; import java.util.Vector; @@ -34,11 +35,143 @@ import java.util.Vector; */ public class ColumnSelection { - /* - * list of selected columns (not ordered) - */ - Vector selected = new Vector(); + private class IntList + { + /* + * list of selected columns (ordered by selection order, not column order) + */ + private List order = new ArrayList(); + + /** + * bitfield for column selection - allows quick lookup + */ + private BitSet selected = new BitSet(); + + /** + * adds a new column i to the selection - only if i is not already selected + * + * @param i + */ + public void add(int i) + { + if (!selected.get(i)) + { + order.add(Integer.valueOf(i)); + selected.set(i); + } + } + + public void clear() + { + order.clear(); + selected.clear(); + } + + public void remove(int col) + { + + Integer colInt = new Integer(col); + + if (selected.get(col)) + { + // if this ever changes to List.remove(), ensure Integer not int + // argument + // as List.remove(int i) removes the i'th item which is wrong + order.remove(colInt); + selected.clear(col); + } + } + + public boolean contains(Integer colInt) + { + return selected.get(colInt); + } + + public boolean isEmpty() + { + return order.isEmpty(); + } + + public List getList() + { + return order; + } + + public int size() + { + return order.size(); + } + + /** + * gets the column that was selected first, second or i'th + * + * @param i + * @return + */ + public int elementAt(int i) + { + return order.get(i); + } + + protected boolean pruneColumnList(final List shifts) + { + int s = 0, t = shifts.size(); + int[] sr = shifts.get(s++); + boolean pruned = false; + int i = 0, j = order.size(); + while (i < j && s <= t) + { + int c = order.get(i++).intValue(); + if (sr[0] <= c) + { + if (sr[1] + sr[0] >= c) + { // sr[1] -ve means inseriton. + order.remove(--i); + selected.clear(c); + j--; + } + else + { + if (s < t) + { + sr = shifts.get(s); + } + s++; + } + } + } + return pruned; + } + + /** + * shift every selected column at or above start by change + * + * @param start + * - leftmost column to be shifted + * @param change + * - delta for shift + */ + public void compensateForEdits(int start, int change) + { + BitSet mask = new BitSet(); + for (int i = 0; i < order.size(); i++) + { + int temp = order.get(i); + + if (temp >= start) + { + // clear shifted bits and update List of selected columns + selected.clear(temp); + mask.set(temp - change); + order.set(i, new Integer(temp - change)); + } + } + // lastly update the bitfield all at once + selected.or(mask); + } + } + IntList selected = new IntList(); /* * list of hidden column [start, end] ranges; the list is maintained in * ascending start column order @@ -53,11 +186,7 @@ public class ColumnSelection */ public void addElement(int col) { - Integer column = new Integer(col); - if (!selected.contains(column)) - { - selected.addElement(column); - } + selected.add(col); } /** @@ -65,7 +194,7 @@ public class ColumnSelection */ public void clear() { - selected.removeAllElements(); + selected.clear(); } /** @@ -76,14 +205,7 @@ public class ColumnSelection */ public void removeElement(int col) { - Integer colInt = new Integer(col); - - if (selected.contains(colInt)) - { - // if this ever changes to List.remove(), ensure Integer not int argument - // as List.remove(int i) removes the i'th item which is wrong - selected.removeElement(colInt); - } + selected.remove(col); } /** @@ -102,7 +224,7 @@ public class ColumnSelection colInt = new Integer(i); if (selected.contains(colInt)) { - selected.removeElement(colInt); + selected.remove(colInt); } } } @@ -113,7 +235,7 @@ public class ColumnSelection */ public List getSelected() { - return selected; + return selected.getList(); } /** @@ -187,16 +309,7 @@ public class ColumnSelection public List compensateForEdit(int start, int change) { List deletedHiddenColumns = null; - for (int i = 0; i < selected.size(); i++) - { - int temp = selected.get(i); - - if (temp >= start) - { - // if this ever changes to List.set(), swap parameter order!! - selected.setElementAt(new Integer(temp - change), i); - } - } + selected.compensateForEdits(start, change); if (hiddenColumns != null) { @@ -245,16 +358,8 @@ public class ColumnSelection */ private void compensateForDelEdits(int start, int change) { - for (int i = 0; i < selected.size(); i++) - { - int temp = selected.get(i); - if (temp >= start) - { - // if this ever changes to List.set(), must swap parameter order!!! - selected.setElementAt(new Integer(temp - change), i); - } - } + selected.compensateForEdits(start, change); if (hiddenColumns != null) { @@ -409,36 +514,6 @@ public class ColumnSelection // operations. } - private boolean pruneColumnList(final List shifts, - Vector list) - { - int s = 0, t = shifts.size(); - int[] sr = shifts.get(s++); - boolean pruned = false; - int i = 0, j = list.size(); - while (i < j && s <= t) - { - int c = list.elementAt(i++).intValue(); - if (sr[0] <= c) - { - if (sr[1] + sr[0] >= c) - { // sr[1] -ve means inseriton. - list.removeElementAt(--i); - j--; - } - else - { - if (s < t) - { - sr = shifts.get(s); - } - s++; - } - } - } - return pruned; - } - /** * remove any hiddenColumns or selected columns and shift remaining based on a * series of position, range deletions. @@ -463,7 +538,7 @@ public class ColumnSelection } if (selected != null && selected.size() > 0) { - pruneColumnList(shifts, selected); + selected.pruneColumnList(shifts); if (selected != null && selected.size() == 0) { selected = null; @@ -631,7 +706,7 @@ public class ColumnSelection { while (!selected.isEmpty()) { - int column = selected.get(0).intValue(); + int column = selected.elementAt(0); hideColumns(column); } @@ -812,10 +887,10 @@ public class ColumnSelection { if (copy.selected != null) { - selected = new Vector(); + selected = new IntList(); for (int i = 0, j = copy.selected.size(); i < j; i++) { - selected.addElement(copy.selected.elementAt(i)); + selected.add(copy.selected.elementAt(i)); } } if (copy.hiddenColumns != null) @@ -1112,10 +1187,7 @@ public class ColumnSelection { if (hiddenColumns != null && isVisible(col.intValue())) { - if (!selected.contains(col)) - { - selected.addElement(col); - } + selected.add(col); } } } @@ -1129,7 +1201,7 @@ public class ColumnSelection */ public void setElementsFrom(ColumnSelection colsel) { - selected = new Vector(); + selected = new IntList(); if (colsel.selected != null && colsel.selected.size() > 0) { if (hiddenColumns != null && hiddenColumns.size() > 0) -- 1.7.10.2