src/intervalstore/impl/NCNode.java

   1 /*
   2 BSD 3-Clause License
   3
   4 Copyright (c) 2018, Mungo Carstairs
   5 All rights reserved.
   6
   7 Redistribution and use in source and binary forms, with or without
   8 modification, are permitted provided that the following conditions are met:
   9
  10 * Redistributions of source code must retain the above copyright notice, this
  11   list of conditions and the following disclaimer.
  12
  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.
  16
  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.
  20
  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.
  31 */
  32 package intervalstore.impl;
  33
  34 import java.util.Iterator;
  35 import java.util.List;
  36 import java.util.NoSuchElementException;
  37
  38 import intervalstore.api.IntervalI;
  39
  40 /**
  41  * Each node of the NCList tree consists of a range, and (optionally) the NCList
  42  * of ranges it encloses
  43  *
  44  * @param <T>
  45  */
  46 class NCNode<T extends IntervalI> implements IntervalI
  47 {
  48   /**
  49    * A depth-first iterator over the intervals stored in the NCNode. The
  50    * optional <code>remove</code> operation is not supported.
  51    *
  52    * @author gmcarstairs
  53    *
  54    */
  55   private class NCNodeIterator implements Iterator<T>
  56   {
  57     boolean first = true;
  58     Iterator<T> subregionIterator;
  59
  60     @Override
  61     public boolean hasNext()
  62     {
  63       return first
  64               || (subregionIterator != null && subregionIterator.hasNext());
  65     }
  66
  67     /**
  68      * Answers the next interval - initially the top level interval for this
  69      * node, thereafter the intervals returned by the NCList's iterator
  70      */
  71     @Override
  72     public T next()
  73     {
  74       if (first)
  75       {
  76         subregionIterator = subregions == null ? null
  77                 : subregions.iterator();
  78         first = false;
  79         return region;
  80       }
  81       if (subregionIterator == null || !subregionIterator.hasNext())
  82       {
  83         throw new NoSuchElementException();
  84       }
  85       return subregionIterator.next();
  86     }
  87   }
  88
  89   private T region;
  90
  91   /*
  92    * null, or an object holding contained subregions of this nodes region
  93    */
  94   private NCList<T> subregions;
  95
  96   /**
  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.
 100    *
 101    * @param ranges
 102    * @throws IllegalArgumentException
 103    *           if the list is empty
 104    */
 105   NCNode(List<T> ranges)
 106   {
 107     if (ranges.isEmpty())
 108     {
 109       throw new IllegalArgumentException("List may not be empty");
 110     }
 111     region = ranges.get(0);
 112
 113     if (ranges.size() > 1)
 114     {
 115       subregions = new NCList<>(ranges.subList(1, ranges.size()));
 116     }
 117   }
 118
 119   /**
 120    * Constructor given a single range
 121    *
 122    * @param range
 123    */
 124   NCNode(T range)
 125   {
 126     region = range;
 127   }
 128
 129   @Override
 130   public int getBegin()
 131   {
 132     return region.getBegin();
 133   }
 134
 135   @Override
 136   public int getEnd()
 137   {
 138     return region.getEnd();
 139   }
 140
 141   /**
 142    * Formats the node as a bracketed list e.g.
 143    *
 144    * <pre>
 145    * [1-100 [10-30 [10-20]], 15-30 [20-20]]
 146    * </pre>
 147    *
 148    * where the format for each interval is as given by <code>T.toString()</code>
 149    */
 150   @Override
 151   public String toString()
 152   {
 153     StringBuilder sb = new StringBuilder(10 * size());
 154     sb.append(region.toString());
 155     if (subregions != null)
 156     {
 157       sb.append(" ").append(subregions.toString());
 158     }
 159     return sb.toString();
 160   }
 161
 162   void prettyPrint(StringBuilder sb, int offset, int indent)
 163   {
 164     for (int i = 0; i < offset; i++)
 165     {
 166       sb.append(" ");
 167     }
 168     sb.append(region.toString());
 169     if (subregions != null)
 170     {
 171       sb.append(System.lineSeparator());
 172       subregions.prettyPrint(sb, offset + 2, indent);
 173     }
 174   }
 175
 176   /**
 177    * Add any ranges that overlap the from-to range to the result list
 178    *
 179    * @param from
 180    * @param to
 181    * @param result
 182    */
 183   void findOverlaps(long from, long to, List<T> result)
 184   {
 185     if (region.getBegin() <= to && region.getEnd() >= from)
 186     {
 187       result.add(region);
 188       if (subregions != null)
 189       {
 190         subregions.findOverlaps(from, to, result);
 191       }
 192     }
 193   }
 194
 195   /**
 196    * Add one node to this node's subregions.
 197    *
 198    * @param entry
 199    * @throws IllegalArgumentException
 200    *           if the added node is not contained by the node's start-end range
 201    */
 202   synchronized void addNode(NCNode<T> entry)
 203   {
 204     if (!region.containsInterval(entry))
 205     {
 206       throw new IllegalArgumentException(
 207               String.format("adding improper subrange %d-%d to range %d-%d",
 208                       entry.getBegin(), entry.getEnd(), region.getBegin(),
 209                       region.getEnd()));
 210     }
 211     if (subregions == null)
 212     {
 213       subregions = new NCList<>();
 214     }
 215
 216     subregions.addNode(entry);
 217   }
 218
 219   /**
 220    * Answers true if the data held satisfy the rules of construction of an
 221    * NCList, else false
 222    *
 223    * @return
 224    */
 225   boolean isValid()
 226   {
 227     /*
 228      * we don't handle reverse ranges
 229      */
 230     if (region != null && region.getBegin() > region.getEnd())
 231     {
 232       return false;
 233     }
 234     if (subregions == null)
 235     {
 236       return true;
 237     }
 238     if (subregions.isEmpty())
 239     {
 240       /*
 241        * we expect empty subregions to be nulled
 242        */
 243       return false;
 244     }
 245     return subregions.isValid(getBegin(), getEnd());
 246   }
 247
 248   /**
 249    * Adds all contained entries to the given list
 250    *
 251    * @param entries
 252    */
 253   void getEntries(List<T> entries)
 254   {
 255     entries.add(region);
 256     if (subregions != null)
 257     {
 258       subregions.getEntries(entries);
 259     }
 260   }
 261
 262   /**
 263    * Answers true if this object contains the given entry (by object equals
 264    * test), else false
 265    *
 266    * @param entry
 267    * @return
 268    */
 269   boolean contains(IntervalI entry)
 270   {
 271     if (entry == null)
 272     {
 273       return false;
 274     }
 275     if (entry.equals(region))
 276     {
 277       return true;
 278     }
 279     return subregions == null ? false : subregions.contains(entry);
 280   }
 281
 282   /**
 283    * Answers the 'root' region modelled by this object
 284    *
 285    * @return
 286    */
 287   T getRegion()
 288   {
 289     return region;
 290   }
 291
 292   /**
 293    * Answers the (possibly null) contained regions within this object
 294    *
 295    * @return
 296    */
 297   NCList<T> getSubRegions()
 298   {
 299     return subregions;
 300   }
 301
 302   /**
 303    * Answers the (deep) size of this node i.e. the number of intervals it models
 304    *
 305    * @return
 306    */
 307   int size()
 308   {
 309     return subregions == null ? 1 : 1 + subregions.size();
 310   }
 311
 312   /**
 313    * Answers the depth of NCNode / NCList nesting in the data tree
 314    *
 315    * @return
 316    */
 317   int getDepth()
 318   {
 319     return subregions == null ? 1 : 1 + subregions.getDepth();
 320   }
 321
 322   /**
 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).
 326    *
 327    * @return
 328    */
 329   public Iterator<T> iterator()
 330   {
 331     return new NCNodeIterator();
 332   }
 333
 334   /**
 335    * Removes the first interval found equal to the given entry. Answers true if
 336    * a matching interval is found and removed, else false.
 337    *
 338    * @param entry
 339    * @return
 340    */
 341   boolean remove(T entry)
 342   {
 343     if (region.equals(entry))
 344     {
 345       /*
 346        * this case must be handled by NCList, to allow any
 347        * children of a deleted interval to be promoted
 348        */
 349       throw new IllegalArgumentException("NCNode can't remove self");
 350     }
 351     if (subregions == null)
 352     {
 353       return false;
 354     }
 355     if (subregions.remove(entry))
 356     {
 357       if (subregions.isEmpty())
 358       {
 359         subregions = null;
 360       }
 361       return true;
 362     }
 363     return false;
 364   }
 365
 366   @SuppressWarnings("unchecked")
 367   @Override
 368   public boolean equals(Object o)
 369   {
 370     return o != null && o instanceof NCNode
 371             && equalsInterval((NCNode<T>) o);
 372   }
 373
 374   @Override
 375   public boolean equalsInterval(IntervalI i)
 376   {
 377     return getBegin() == i.getBegin() && getEnd() == i.getEnd();
 378
 379   }
 380
 381 }