SortedList = require './sorted-list'
Node       = require './node'
Point      = require './point'
Interval   = require './interval'
Util       = require './util'
 
 
###*
interval tree
 
@class IntervalTree
@module interval-tree2
###
class IntervalTree
 
 
    ###*
    @constructor
    @param {Number} center center of the root node
    ###
    constructor: (center) ->
 
        Util.assertNumber center, 'IntervalTree: center'
 
        ###*
        center => node
 
        @property {Object(Node)} nodesByCenter
        ###
        @nodesByCenter = {}
 
 
        ###*
        root node
 
        @property {Node} root
        ###
        @root = @createNode(center)
 
 
        ###*
        interval id => interval
 
        @property {Object(Interval)} intervalsById
        ###
        @intervalsById = {}
 
 
        ###*
        interval id => node
 
        @property {Object(Node)} nodesById
        ###
        @nodesById = {}
 
 
        ###*
        sorted list of whole point
 
        @property {SortedList(Point)} pointTree
        ###
        @pointTree = new SortedList('val')
 
 
        ###*
        unique id candidate of interval without id to be added next time
 
        @property {Number} idCandidate
        ###
        @idCandidate = 0
 
 
 
    ###*
    add one interval
 
    @method add
    @public
    @param {Number} start start of the interval to create
    @param {Number} end   end of the interval to create
    @param {String|Number} [id] identifier to distinguish intervals. Automatically defiend when not set.
    @return {Interval}
    ###
    add: (start, end, id) ->
 
        if @intervalsById[id]?
            throw new Error('id ' + id + ' is already registered.')
 
        if not id?
            while @intervalsById[@idCandidate]?
                @idCandidate++
            id = @idCandidate
 
 
        Util.assertNumber(start, '1st argument of IntervalTree#add()')
        Util.assertNumber(end, '2nd argument of IntervalTree#add()')
 
        if start >= end
            Util.assertOrder(start, end, 'start', 'end')
 
 
        interval = new Interval(start, end, id)
 
        @pointTree.insert new Point(interval.start, id)
        @pointTree.insert new Point(interval.end,   id)
 
        @intervalsById[id] = interval
 
        return @insert interval, @root
 
 
    ###*
    search intervals
    when only one argument is given, return intervals which contains the value
    when two arguments are given, ...
 
    @method search
    @public
    @param {Number} val1
    @param {Number} val2
    @return {Array(Interval)} intervals
    ###
    search: (val1, val2) ->
 
        Util.assertNumber val1, '1st argument at IntervalTree#search()'
 
        if not val2?
 
            return @pointSearch val1
 
        else
 
            Util.assertNumber val2, '2nd argument at IntervalTree#search()'
            Util.assertOrder val1, val2, '1st argument', '2nd argument', 'IntervalTree#search()'
 
            return @rangeSearch val1, val2
 
 
    ###*
    removes an interval of the given id
 
    @method remove
    @public
    @param {Number|String} id id of the interval to remove
    ###
    remove: (id) ->
 
        interval = @intervalsById[id]
 
        return if not interval?
 
        node = @nodesById[id]
 
        node.remove(interval)
 
        delete @nodesById[id]
        delete @intervalsById[id]
 
 
 
    ###*
    search intervals at the given node
 
    @method pointSearch
    @public
    @param {Number} val
    @param {Node} [node] current node to search. default is this.root
    @return {Array(Interval)}
    ###
    pointSearch: (val, node = @root, results = []) ->
 
        Util.assertNumber(val, '1st argument of IntervalTree#pointSearch()')
 
        if val < node.center
 
            results = results.concat node.startPointSearch(val)
 
            if node.left?
                return @pointSearch(val, node.left, results)
 
            else
                return results
 
 
        if val > node.center
 
            results = results.concat node.endPointSearch(val)
 
            if node.right?
                return @pointSearch(val, node.right, results)
 
            else
                return results
 
        # if val is node.center
        return results.concat node.getAllIntervals()
 
 
    ###*
    returns intervals which covers the given start-end interval
 
    @method rangeSearch
    @public
    @param {Number} start start of the interval
    @param {Number} end end of the interval
    @return {Array(Interval)}
    ###
    rangeSearch: (start, end) ->
 
        Util.assertNumber start, '1st argument at IntervalTree#rangeSearch()'
        Util.assertNumber end, '2nd argument at IntervalTree#rangeSearch()'
        Util.assertOrder start, end, '1st argument', '2nd argument', 'IntervalTree#rangeSearch()'
 
        resultsById = {}
 
        # 1. pointSearch to arbitrary point between start and end (here: point = start) 
        for interval in @pointSearch(start)
            resultsById[interval.id] = interval
 
        # 2. add intervals whose either point is included in the given range
        firstPos = @pointTree.firstPositionOf new Point(start)
        lastPos  = @pointTree.lastPositionOf new Point(end)
 
        for point in @pointTree.slice(firstPos, lastPos + 1)
 
            resultsById[point.id] = @intervalsById[point.id]
 
        return (interval for id, interval of resultsById)
 
 
 
    ###*
    insert interval to the given node
 
    @method insert
    @private
    @param {Interval} interval
    @param {Node} node node to insert the interval
    @return {Interval} inserted interval
    ###
    insert: (interval, node) ->
 
        if interval.end < node.center
 
            node.left ?= @createNode(interval.end)
 
            return @insert(interval, node.left)
 
        if node.center < interval.start
 
            node.right ?= @createNode(interval.start)
 
            return @insert(interval, node.right)
 
        node.insert interval
 
        @nodesById[interval.id] = node
 
        return interval
 
 
 
    ###*
    create node by center
 
    @method createNode
    @private
    @param {Number} center
    @return {Node} node
    ###
    createNode: (center) ->
 
        node = new Node(center)
 
        @nodesByCenter[center] = node
 
        return node
 
 
module.exports = IntervalTree