*/
Collections.sort(ranges, intervalSorter);
- List<SubList> sublists = findSubranges(ranges);
+ List<SubList> sublists = buildSubranges(ranges);
/*
* convert each subrange to an NCNode consisting of a range and
* @param ranges
* @return
*/
- protected List<SubList> findSubranges(List<T> ranges)
+ protected List<SubList> buildSubranges(List<T> ranges)
{
List<SubList> sublists = new ArrayList<SubList>();
}
/**
- * Adds one entry to the stored set
+ * Adds one entry to the stored set (with duplicates allowed)
*
* @param entry
*/
- public synchronized void add(T entry)
+ public void add(T entry)
{
+ add(entry, true);
+ }
+
+ /**
+ * Adds one entry to the stored set, and returns true, unless allowDuplicates
+ * is set to false and it is already contained (by object equality test), in
+ * which case it is not added and this method returns false.
+ *
+ * @param entry
+ * @param allowDuplicates
+ * @return
+ */
+ public synchronized boolean add(T entry, boolean allowDuplicates)
+ {
+ if (!allowDuplicates && contains(entry))
+ {
+ return false;
+ }
+
size++;
long start = entry.getBegin();
long end = entry.getEnd();
* all subranges precede this one - add it on the end
*/
subranges.add(new NCNode<T>(entry));
- return;
+ return true;
}
/*
* new entry lies between subranges j-1 j
*/
subranges.add(j, new NCNode<T>(entry));
- return;
+ return true;
}
if (subrange.getStart() <= start && subrange.getEnd() >= end)
* push new entry inside this subrange as it encloses it
*/
subrange.add(entry);
- return;
+ return true;
}
if (start <= subrange.getStart())
* entry encloses one or more preceding subranges
*/
addEnclosingRange(entry, firstEnclosed, lastEnclosed);
- return;
+ return true;
}
else
{
* so just add it
*/
subranges.add(j, new NCNode<T>(entry));
- return;
+ return true;
}
}
}
{
subranges.add(new NCNode<T>(entry));
}
+
+ return true;
}
/**
+ * Answers true if this NCList contains the given entry (by object equality
+ * test), else false
+ *
+ * @param entry
+ * @return
+ */
+ public boolean contains(T entry)
+ {
+ /*
+ * find the first sublist that might overlap, i.e.
+ * the first whose end position is >= from
+ */
+ int candidateIndex = findFirstOverlap(entry.getBegin());
+
+ if (candidateIndex == -1)
+ {
+ return false;
+ }
+
+ int to = entry.getEnd();
+
+ for (int i = candidateIndex; i < subranges.size(); i++)
+ {
+ NCNode<T> candidate = subranges.get(i);
+ if (candidate.getStart() > to)
+ {
+ /*
+ * we are past the end of our target range
+ */
+ break;
+ }
+ if (candidate.contains(entry))
+ {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
* Update the tree so that the range of the new entry encloses subranges i to
* j (inclusive). That is, replace subranges i-j (inclusive) with a new
* subrange that contains them.
* @param to
* @param result
*/
- protected void findOverlaps(long from, long to,
- List<T> result)
+ protected void findOverlaps(long from, long to, List<T> result)
{
/*
* find the first sublist that might overlap, i.e.
subrange.getEntries(result);
}
}
+
+ /**
+ * Deletes the given entry from the store, returning true if it was found (and
+ * deleted), else false. This method makes no assumption that the entry is in
+ * the 'expected' place in the store, in case it has been modified since it
+ * was added. Only the first 'same object' match is deleted, not 'equal' or
+ * multiple objects.
+ *
+ * @param entry
+ */
+ public synchronized boolean delete(T entry)
+ {
+ if (entry == null)
+ {
+ return false;
+ }
+ for (int i = 0; i < subranges.size(); i++)
+ {
+ NCNode<T> subrange = subranges.get(i);
+ NCList<T> subRegions = subrange.getSubRegions();
+
+ if (subrange.getRegion() == entry)
+ {
+ /*
+ * if the subrange is rooted on this entry, promote its
+ * subregions (if any) to replace the subrange here
+ */
+ subranges.remove(i);
+ if (subRegions != null)
+ {
+ subranges.addAll(i, subRegions.subranges);
+ }
+ size--;
+ return true;
+ }
+ else
+ {
+ if (subRegions != null && subRegions.delete(entry))
+ {
+ size--;
+ 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<NCNode<T>> getSubregions()
+ {
+ return subranges;
+ }
}