4 Copyright (c) 2018, Mungo Carstairs
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
10 * Redistributions of source code must retain the above copyright notice, this
11 list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 this list of conditions and the following disclaimer in the documentation
15 and/or other materials provided with the distribution.
17 * Neither the name of the copyright holder nor the names of its
18 contributors may be used to endorse or promote products derived from
19 this software without specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 package intervalstore.impl;
34 import java.util.Iterator;
35 import java.util.List;
36 import java.util.NoSuchElementException;
38 import intervalstore.api.IntervalI;
41 * Each node of the NCList tree consists of a range, and (optionally) the NCList
42 * of ranges it encloses
46 class NCNode<T extends IntervalI> implements IntervalI
49 * A depth-first iterator over the intervals stored in the NCNode. The
50 * optional <code>remove</code> operation is not supported.
55 private class NCNodeIterator implements Iterator<T>
58 Iterator<T> subregionIterator;
61 public boolean hasNext()
64 || (subregionIterator != null && subregionIterator.hasNext());
68 * Answers the next interval - initially the top level interval for this
69 * node, thereafter the intervals returned by the NCList's iterator
76 subregionIterator = subregions == null ? null
77 : subregions.iterator();
81 if (subregionIterator == null || !subregionIterator.hasNext())
83 throw new NoSuchElementException();
85 return subregionIterator.next();
92 * null, or an object holding contained subregions of this nodes region
94 private NCList<T> subregions;
97 * Constructor given a list of ranges. The list not be empty, and should be
98 * ordered so that the first range contains all the others. If not, behaviour
99 * will likely be invalid.
102 * @throws IllegalArgumentException
103 * if the list is empty
105 NCNode(List<T> ranges)
107 if (ranges.isEmpty())
109 throw new IllegalArgumentException("List may not be empty");
111 region = ranges.get(0);
113 if (ranges.size() > 1)
115 subregions = new NCList<>(ranges.subList(1, ranges.size()));
120 * Constructor given a single range
130 public int getBegin()
132 return region.getBegin();
138 return region.getEnd();
142 * Formats the node as a bracketed list e.g.
145 * [1-100 [10-30 [10-20]], 15-30 [20-20]]
148 * where the format for each interval is as given by <code>T.toString()</code>
151 public String toString()
153 StringBuilder sb = new StringBuilder(10 * size());
154 sb.append(region.toString());
155 if (subregions != null)
157 sb.append(" ").append(subregions.toString());
159 return sb.toString();
162 void prettyPrint(StringBuilder sb, int offset, int indent)
164 for (int i = 0; i < offset; i++)
168 sb.append(region.toString());
169 if (subregions != null)
171 sb.append(System.lineSeparator());
172 subregions.prettyPrint(sb, offset + 2, indent);
177 * Add any ranges that overlap the from-to range to the result list
183 void findOverlaps(long from, long to, List<T> result)
185 if (region.getBegin() <= to && region.getEnd() >= from)
188 if (subregions != null)
190 subregions.findOverlaps(from, to, result);
196 * Add one node to this node's subregions.
199 * @throws IllegalArgumentException
200 * if the added node is not contained by the node's start-end range
202 synchronized void addNode(NCNode<T> entry)
204 if (!region.containsInterval(entry))
206 throw new IllegalArgumentException(
207 String.format("adding improper subrange %d-%d to range %d-%d",
208 entry.getBegin(), entry.getEnd(), region.getBegin(),
211 if (subregions == null)
213 subregions = new NCList<>();
216 subregions.addNode(entry);
220 * Answers true if the data held satisfy the rules of construction of an
228 * we don't handle reverse ranges
230 if (region != null && region.getBegin() > region.getEnd())
234 if (subregions == null)
238 if (subregions.isEmpty())
241 * we expect empty subregions to be nulled
245 return subregions.isValid(getBegin(), getEnd());
249 * Adds all contained entries to the given list
253 void getEntries(List<T> entries)
256 if (subregions != null)
258 subregions.getEntries(entries);
263 * Answers true if this object contains the given entry (by object equals
269 boolean contains(IntervalI entry)
275 if (entry.equals(region))
279 return subregions == null ? false : subregions.contains(entry);
283 * Answers the 'root' region modelled by this object
293 * Answers the (possibly null) contained regions within this object
297 NCList<T> getSubRegions()
303 * Answers the (deep) size of this node i.e. the number of intervals it models
309 return subregions == null ? 1 : 1 + subregions.size();
313 * Answers the depth of NCNode / NCList nesting in the data tree
319 return subregions == null ? 1 : 1 + subregions.getDepth();
323 * Answers an iterator over the intervals stored in this node. The iterator
324 * does not support the optional <code>remove</code> operation (throws
325 * <code>UnsupportedOperationException</code> if attempted).
329 public Iterator<T> iterator()
331 return new NCNodeIterator();
335 * Removes the first interval found equal to the given entry. Answers true if
336 * a matching interval is found and removed, else false.
341 boolean remove(T entry)
343 if (region.equals(entry))
346 * this case must be handled by NCList, to allow any
347 * children of a deleted interval to be promoted
349 throw new IllegalArgumentException("NCNode can't remove self");
351 if (subregions == null)
355 if (subregions.remove(entry))
357 if (subregions.isEmpty())