package gw.rating.rtm.matchop

uses gw.rating.rtm.domain.OrderedPersistenceAdapter

uses java.util.ArrayList
uses java.util.Arrays
uses java.util.Collections
uses java.util.LinkedList
uses java.lang.IllegalStateException
uses java.util.List

class SubrangeMerger {

  var _matchOps : List<StatelessMatchOperator> as ops
  var _pos : int as readonly Pos
  var _comparisonOrder: int[]

  construct(matchops : List<StatelessMatchOperator>, opPosition : int, sortOrder: int[]) {
    _matchOps = matchops
    _pos = opPosition
    _comparisonOrder = extractComparisonOrder(opPosition, sortOrder)
    if (_comparisonOrder?.length == 0) {
      throw new IllegalStateException("Attempt to instantiate SubrangeMerger with an empty MatchOp comparison order")
    }
  }

  function findAndMergeSubranges(input : List<OrderedPersistenceAdapter>, numOps : int) : List<OrderedPersistenceAdapter> {
    if (input.size() < 2) return input
    return Collections.unmodifiableList(naturalMerge(input.partition(\ col -> col.get(Pos)).Values.toList(), numOps))
  }

  // need to compare from next matchop on.
  private function subCompare(row1 : OrderedPersistenceAdapter, row2 : OrderedPersistenceAdapter, numOps : int) : int {
    for (i in _comparisonOrder) {
        var colValue1 = row1.get(i)
        var colValue2 = row2.get(i)
        if (colValue1 == null) return (colValue2 == null) ? 0 : 1
        // null sorts to the end
        var value = ops.get(i).compareRowValues(colValue1, colValue2)
        if (value != 0) return value
      }
    return 0
  }

  private function naturalMerge(input : List<List<OrderedPersistenceAdapter>>, numOps : int) : List<OrderedPersistenceAdapter> {
    var ranges = new java.util.LinkedList<List<OrderedPersistenceAdapter>>(input.sortBy(\ elt -> elt.size()))
    while (ranges.size() > 1) {
      insert(mergeTwo(ranges.poll(), ranges.poll(), numOps), ranges)
    }
    return ranges.poll()
  }

  private function insert(o : List<OrderedPersistenceAdapter>, l : LinkedList<List<OrderedPersistenceAdapter>>) {
    var i = l.listIterator()
    while (i.hasNext()) {
      var elt = i.next()
      if (elt.size() >= o.size()) {
        i.previous()
        break
      }
    }

    i.add(o)
  }

  private function mergeTwo(l1 : List<OrderedPersistenceAdapter>, l2 : List<OrderedPersistenceAdapter>, numOps : int) : List<OrderedPersistenceAdapter> {
    if (l1.size() == 0) return l2
    else if (l2.size() == 0) return l1

    var result = new ArrayList<OrderedPersistenceAdapter>(l1.size() + l2.size())
    var a = l1.get(0)
    var b = l2.get(0)
    do {
      var cmp = subCompare(a, b, numOps)
      if (cmp <= 0) {
        result.add(a)
        l1.remove(0)
        a = l1.size() == 0 ? null : l1.get(0)
      } else {
        result.add(b)
        l2.remove(0)
        b = l2.size() == 0 ? null : l2.get(0)
      }
    } while (a != null and b != null)

    if (a != null) {
      result.addAll(l1)
    } else if (b != null) {
      result.addAll(l2)
    }

    return result
  }

  /**
   * Extracts the sorting order from after the specified MatchOp index on
   */
  private static function extractComparisonOrder(opPosition: int, sortOrder: int[]): int[] {
    for(pos in sortOrder index i) {
      if(pos == opPosition) {
        return Arrays.copyOfRange(sortOrder, i + 1, sortOrder.length)
      }
    }
    return null
  }
}