/*
BSD 3-Clause License

Copyright (c) 2018, Mungo Carstairs
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.

* Neither the name of the copyright holder nor the names of its
  contributors may be used to endorse or promote products derived from
  this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package intervalstore.impl;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import intervalstore.api.IntervalI;

/**
 * Each node of the NCList tree consists of a range, and (optionally) the NCList
 * of ranges it encloses
 *
 * @param <T>
 */
class NCNode<T extends IntervalI> implements IntervalI
{
  /**
   * A depth-first iterator over the intervals stored in the NCNode. The
   * optional <code>remove</code> operation is not supported.
   * 
   * @author gmcarstairs
   *
   */
  private class NCNodeIterator implements Iterator<T>
  {
    boolean first = true;
    Iterator<T> subregionIterator;

    @Override
    public boolean hasNext()
    {
      return first
              || (subregionIterator != null && subregionIterator.hasNext());
    }

    /**
     * Answers the next interval - initially the top level interval for this
     * node, thereafter the intervals returned by the NCList's iterator
     */
    @Override
    public T next()
    {
      if (first)
      {
        subregionIterator = subregions == null ? null
                : subregions.iterator();
        first = false;
        return region;
      }
      if (subregionIterator == null || !subregionIterator.hasNext())
      {
        throw new NoSuchElementException();
      }
      return subregionIterator.next();
    }
  }

  private T region;

  /*
   * null, or an object holding contained subregions of this nodes region
   */
  private NCList<T> subregions;

  /**
   * Constructor given a list of ranges. The list not be empty, and should be
   * ordered so that the first range contains all the others. If not, behaviour
   * will likely be invalid.
   * 
   * @param ranges
   * @throws IllegalArgumentException
   *           if the list is empty
   */
  NCNode(List<T> ranges)
  {
    if (ranges.isEmpty())
    {
      throw new IllegalArgumentException("List may not be empty");
    }
    region = ranges.get(0);

    if (ranges.size() > 1)
    {
      subregions = new NCList<>(ranges.subList(1, ranges.size()));
    }
  }

  /**
   * Constructor given a single range
   * 
   * @param range
   */
  NCNode(T range)
  {
    region = range;
  }

  @Override
  public int getBegin()
  {
    return region.getBegin();
  }

  @Override
  public int getEnd()
  {
    return region.getEnd();
  }

  /**
   * Formats the node as a bracketed list e.g.
   * 
   * <pre>
   * [1-100 [10-30 [10-20]], 15-30 [20-20]]
   * </pre>
   * 
   * where the format for each interval is as given by <code>T.toString()</code>
   */
  @Override
  public String toString()
  {
    StringBuilder sb = new StringBuilder(10 * size());
    sb.append(region.toString());
    if (subregions != null)
    {
      sb.append(" ").append(subregions.toString());
    }
    return sb.toString();
  }

  void prettyPrint(StringBuilder sb, int offset, int indent)
  {
    for (int i = 0; i < offset; i++)
    {
      sb.append(" ");
    }
    sb.append(region.toString());
    if (subregions != null)
    {
      sb.append(System.lineSeparator());
      subregions.prettyPrint(sb, offset + 2, indent);
    }
  }

  /**
   * Add any ranges that overlap the from-to range to the result list
   * 
   * @param from
   * @param to
   * @param result
   */
  void findOverlaps(long from, long to, List<T> result)
  {
    if (region.getBegin() <= to && region.getEnd() >= from)
    {
      result.add(region);
      if (subregions != null)
      {
        subregions.findOverlaps(from, to, result);
      }
    }
  }

  /**
   * Add one node to this node's subregions.
   * 
   * @param entry
   * @throws IllegalArgumentException
   *           if the added node is not contained by the node's start-end range
   */
  synchronized void addNode(NCNode<T> entry)
  {
    if (!region.containsInterval(entry))
    {
      throw new IllegalArgumentException(
              String.format("adding improper subrange %d-%d to range %d-%d",
                      entry.getBegin(), entry.getEnd(), region.getBegin(),
                      region.getEnd()));
    }
    if (subregions == null)
    {
      subregions = new NCList<>();
    }

    subregions.addNode(entry);
  }

  /**
   * Answers true if the data held satisfy the rules of construction of an
   * NCList, else false
   * 
   * @return
   */
  boolean isValid()
  {
    /*
     * we don't handle reverse ranges
     */
    if (region != null && region.getBegin() > region.getEnd())
    {
      return false;
    }
    if (subregions == null)
    {
      return true;
    }
    if (subregions.isEmpty())
    {
      /*
       * we expect empty subregions to be nulled
       */
      return false;
    }
    return subregions.isValid(getBegin(), getEnd());
  }

  /**
   * Adds all contained entries to the given list
   * 
   * @param entries
   */
  void getEntries(List<T> entries)
  {
    entries.add(region);
    if (subregions != null)
    {
      subregions.getEntries(entries);
    }
  }

  /**
   * Answers true if this object contains the given entry (by object equals
   * test), else false
   * 
   * @param entry
   * @return
   */
  boolean contains(IntervalI entry)
  {
    if (entry == null)
    {
      return false;
    }
    if (entry.equals(region))
    {
      return true;
    }
    return subregions == null ? false : subregions.contains(entry);
  }

  /**
   * Answers the 'root' region modelled by this object
   * 
   * @return
   */
  T getRegion()
  {
    return region;
  }

  /**
   * Answers the (possibly null) contained regions within this object
   * 
   * @return
   */
  NCList<T> getSubRegions()
  {
    return subregions;
  }

  /**
   * Answers the (deep) size of this node i.e. the number of intervals it models
   * 
   * @return
   */
  int size()
  {
    return subregions == null ? 1 : 1 + subregions.size();
  }

  /**
   * Answers the depth of NCNode / NCList nesting in the data tree
   * 
   * @return
   */
  int getDepth()
  {
    return subregions == null ? 1 : 1 + subregions.getDepth();
  }

  /**
   * Answers an iterator over the intervals stored in this node. The iterator
   * does not support the optional <code>remove</code> operation (throws
   * <code>UnsupportedOperationException</code> if attempted).
   * 
   * @return
   */
  public Iterator<T> iterator()
  {
    return new NCNodeIterator();
  }

  /**
   * Removes the first interval found equal to the given entry. Answers true if
   * a matching interval is found and removed, else false.
   * 
   * @param entry
   * @return
   */
  boolean remove(T entry)
  {
    if (region.equals(entry))
    {
      /*
       * this case must be handled by NCList, to allow any
       * children of a deleted interval to be promoted
       */
      throw new IllegalArgumentException("NCNode can't remove self");
    }
    if (subregions == null)
    {
      return false;
    }
    if (subregions.remove(entry))
    {
      if (subregions.isEmpty())
      {
        subregions = null;
      }
      return true;
    }
    return false;
  }

  @SuppressWarnings("unchecked")
  @Override
  public boolean equals(Object o)
  {
    return o != null && o instanceof NCNode
            && equalsInterval((NCNode<T>) o);
  }

  @Override
  public boolean equalsInterval(IntervalI i)
  {
    return getBegin() == i.getBegin() && getEnd() == i.getEnd();

  }

}