// Generated by CoffeeScript 1.4.0
var Node, SortedCircularDoublyLinkedList;

Node = (function() {

  function Node(datum, prev, next) {
    this.datum = datum;
    this.prev = prev;
    this.next = next;
  }

  return Node;

})();

SortedCircularDoublyLinkedList = (function() {

  function SortedCircularDoublyLinkedList(options) {
    var opt = options || {};
    this.head = opt.head;
    this.tail = opt.tail;
    this.length = 0;
    if( opt.compare) 
      this.compare = opt.compare; 
  }

  SortedCircularDoublyLinkedList.prototype.compare = function(datum1, datum2) {
    return datum1 - datum2;
  };

  SortedCircularDoublyLinkedList.prototype.insertAll = function(list) {
    var x, _i, _len;
    if (list == null) {
      list = [];
    }
    for (_i = 0, _len = list.length; _i < _len; _i++) {
      x = list[_i];
      this.insert(x);
    }
    return this.head;
  };

  SortedCircularDoublyLinkedList.prototype.insert = function(datum) {
    var current, insertAfter, insertBefore, next, node;
    node = new Node(datum);
    insertBefore = function(a, b) {
      if (b === this.head) {
        a.prev = this.tail;
        this.head = a;
        this.tail.next = this.head;
      } else {
        a.prev = b.prev;
        b.prev.next = a;
      }
      a.next = b;
      return b.prev = a;
    };
    insertAfter = function(a, b) {
      if (b === this.tail) {
        a.next = this.head;
        this.tail = a;
        this.head.prev = this.tail;
      } else {
        a.next = b.next;
        b.next.prev = a;
      }
      a.prev = b;
      return b.next = a;
    };
    this.length++; //TODO it should be before return statement
    if (this.head == null) {
      this.head = node;
      this.head.next = node;
      this.head.prev = node;
      this.tail = this.head;
      return node;
    }
    if (this.compare(this.head.datum, node.datum) > 0) {
      insertBefore(node, this.head);
      this.head = node;
    } else {
      current = this.head;
      while (current !== this.tail) {
        next = current.next;
        if (this.compare(next.datum, node.datum) > 0) {
          break;
        }
        current = current.next;
      }
      insertAfter(node, current);
      if (current === this.tail) {
        this.tail = node;
      }
    }
    /*if (this.compare(node.datum, this.head.datum) < 0) {
      this.head = node;
    }
    if (this.compare(node.datum, this.tail.datum) > 0) {
      this.tail = node;
    }*/
    return node;
  };

  SortedCircularDoublyLinkedList.prototype.remove = function(datum) {
    var current;
    current = this.head;
    //TODO can be current.datum !== datum
    //while (this.compare(current.datum, datum) !== 0) {
    while (current.datum !== datum) {
      current = current.next;
      if (current === this.head) {
        break;
      }
    }
    this.length--;
    if(current === this.head && current === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      if (current === this.head) {
        this.head = current.next;
        this.tail.next = this.head;
        this.head.prev = this.tail;
      } else {
        current.prev.next = current.next;
      }
      if (current === this.tail) {
        this.tail = current.prev;
        this.head.prev = this.tail;
        return this.tail.next = this.head;
      } else {
        return current.next.prev = current.prev;
      }
    }
  };

  SortedCircularDoublyLinkedList.prototype.contains = function(datum) {
    return this.find(datum) != null;
  };

  SortedCircularDoublyLinkedList.prototype.find = function(datum) {
    var current;
    if (!this.head) {
      return null;
    } else {
      current = this.head;
      do {
        if (this.compare(current.datum, datum) === 0) {
          return current;
        }
        current = current.next;
      } while (current !== this.head);
      return null;
    }
  };

  SortedCircularDoublyLinkedList.prototype.print = function() {
    var current, output;
    output = "";
    if (!(this.head != null)) {
      return;
    }
    current = this.head;
    output += "" + current.datum;
    while (current.next !== this.head) {
      current = current.next;
      output += ", " + current.datum;
    }
    return output;
  };
  
  SortedCircularDoublyLinkedList.prototype.pop = function() {
    var datum = this.head.datum;
    this.remove(datum);
    return datum;
  };

  SortedCircularDoublyLinkedList.prototype.upperBound = function(datum) {
    var upper = [];
    var cur = this.find(datum);
    if (cur && cur !== this.tail) {
      do {
        upper.push(cur.next.datum);
        cur = cur.next;
      } while (cur !== this.tail);
    }
    return upper;
  };

  SortedCircularDoublyLinkedList.prototype.lowerBound = function(datum) {
    var lower = [];
    var cur = this.find(datum);
    if (cur && cur !== this.head) {
      do {
        lower.push(cur.prev.datum);
        cur = cur.prev;
      } while (cur !== this.head);
    }
    return lower;
  };
  SortedCircularDoublyLinkedList.prototype.lowerCount = function(datum) {
    var count = 0;
    var cur = this.find(datum);
    if (cur && cur !== this.head) {
      do {
        count++;
        cur = cur.prev;
      } while (cur !== this.head);
    }
    return count;
  };

  SortedCircularDoublyLinkedList.prototype.upperCount = function(datum) {
    var count = 0;
    var cur = this.find(datum);
    if (cur && cur !== this.tail) {
      do {
        count++;
        cur = cur.next;
      } while (cur !== this.tail);
    }
    return count;
  };

  return SortedCircularDoublyLinkedList;

})();

module.exports = SortedCircularDoublyLinkedList;
