/*
#### 使用ECMAScript提供的sort API实现

#### 思路：
- 使用两个数组分别存放未排序的数组以及排好序的数组：original, sorted
- 每次pop操作，调用original的pop方法，然后复制original对其调用sort方法，得到新的sorted数组
- 同样的方式处理push操作

#### 缺点：
api-solution的主要问题在于，每次入栈出栈都要执行sort
而sort(v8的实现是优化过的快排)的时间复杂度平均为O(nlogn)

#### 优化方案：
请参见optimized-solution.js
*/

var utils = {
  compare: function (value1, value2) {
    return value1 - value2;
  },
  sort: function (arr) {
    return arr.concat().sort(this.compare);
  }
};

var app = {
  original: [],
  sorted: [],

  initialize: function () {
    this.initOriginal();
    this.initSorted();
    this.render();

    this.subscribe();
  },

  initOriginal: function () {
    var stringArr = document.querySelector('#original').innerHTML.split(',');
    this.original = stringArr.map(function (item) {
      return parseInt(item, 10);
    });
  },

  initSorted: function () {
    this.sorted = utils.sort(this.original);
  },

  subscribe: function () {
    document.querySelector('#pop').addEventListener('click', (function () {
      this.original.pop();
      this.sorted = utils.sort(this.original);

      this.render();
    }).bind(this));

    document.querySelector('#push').addEventListener('click', (function () {
      var input = document.querySelector('input');
      var number = parseInt(input.value, 10);

      if (!isNaN(number)) {
        this.original.push(number);
        this.sorted = utils.sort(this.original);
      }

      input.value = '';
      this.render();
    }).bind(this));
  },

  render: function () {
    document.querySelector('#original').innerHTML = this.original.join(',');
    document.querySelector('#sorted').innerHTML = this.sorted.join(',');
  }
};

app.initialize();

/*
#### 思路：
- 利用Hash找到pop元素的位置 - O(1)
- 利用链表根据找到的位置进行删除 - O(1)
- 利用链表遍历hash在相应位置进行插入 - O(logn)

#### 具体实现：
- 初始化两个数组original, sorted
- 初始化一个哈希linkListHash，其key随机生成，其值为对象，存放original的值，对象之间实现成一个双向链表
- 初始化一个数组originalList，每一项的值是一个对象，存放original对应的值和该值在linkListHash中对应的key
- 对originalList进行pop出栈，根据出栈元素的key找到linkListHash中对应的属性，在链表中删除出栈元素，最后删除该属性
- 对originalList进行push入栈，遍历链表，找到相应的位置插入入栈元素，为linkListHash添加新key及其值
*/

var utils = {
  compare: function (value1, value2) {
    return value1 - value2;
  },
  sort: function (arr) {
    return arr.concat().sort(this.compare);
  },
  findKey: function (hash, data) {
    for (var key in hash) {
      if (hash[key].data === data) {
        return key;
      }
    }
  }
};

var app = {
  original: [],
  sorted: [],
  linkListHash: {},
  originalList: [],

  head: null,

  initialize: function () {
    this.initOriginal();
    this.initSorted();
    this.initLinkListHash();
    this.initOriginalList();
    this.render();

    this.subscribe();
  },

  initOriginal: function () {
    var stringArr = document.querySelector('#original').innerHTML.split(',');
    this.original = stringArr.map(function (item) {
      return parseInt(item, 10);
    });
  },

  initSorted: function () {
    this.sorted = utils.sort(this.original);
  },

  initLinkListHash: function () {
    var head = null;
    var linkListHash = {};
    var lastNode = null;

    for (var i = 0; i < this.sorted.length; i++) {
      var obj = {
        data: this.sorted[i],
        prev: lastNode
      };
      if (!lastNode) {
        head = obj;
      } else {
        lastNode.next = obj;
      }
      linkListHash[Math.random()] = obj;
      lastNode = obj;
    }

    this.head = head;
    this.linkListHash = linkListHash;
  },

  initOriginalList: function () {
    var originalList = [];
    for (var i = 0; i < this.original.length; i++) {
      var obj = {
        data: this.original[i],
        key: utils.findKey(this.linkListHash, this.original[i])
      };
      originalList.push(obj);
    }

    this.originalList = originalList;
  },

  subscribe: function () {
    document.querySelector('#pop').addEventListener('click', (function () {
      this.original.pop();
      this.popHash();

      this.render();
    }).bind(this));

    document.querySelector('#push').addEventListener('click', (function () {
      var input = document.querySelector('input');
      var number = parseInt(input.value, 10);

      if (!isNaN(number)) {
        this.original.push(number);
        this.pushHash(number);
      }

      input.value = '';
      this.render();
    }).bind(this));
  },

  popHash: function () {
    if (this.originalList.length === 0) {
      return;
    }

    var key = (this.originalList.pop()).key;
    var targetObj = this.linkListHash[key];

    if (!targetObj.next && !targetObj.prev) {
      this.head = null;
    } else if (!targetObj.prev) {
      this.head = targetObj.next;
      targetObj.next.prev = null;
    } else if (targetObj.next) {
      targetObj.prev.next = targetObj.next;
      targetObj.next.prev = targetObj.prev;
    } else {
      targetObj.prev.next = null;
      targetObj.prev = null;
    }

    delete this.linkListHash[key];
  },

  pushHash: function (data) {
    var key = Math.random();
    this.originalList.push({data: data, key: key});

    var newObj = {
      data: data,
      key: key,
      next: null,
      prev: null
    };
    var node = this.head;

    if (!node) {
      this.head = newObj;
    } else {
      while (node) {
        if (data < node.data) {
          if (!node.prev) {
            newObj.next = node;
            node.prev = newObj;
            this.head = newObj;
          } else {
            node.prev.next = newObj;
            newObj.prev = node.prev;
            newObj.next = node;
            node.prev = newObj;
          }
          break;
        } else if (!node.next) {
          node.next = newObj;
          newObj.prev = node;
          break;
        }

        node = node.next;
      }
    }

    this.linkListHash[key] = newObj;
  },

  renderOriginal: function () {
    document.querySelector('#original').innerHTML = this.original.join(',');
  },

  renderSorted: function () {
    var arr = [];
    var node = this.head;
    while (node) {
      arr.push(node.data);
      node = node.next;
    }
    document.querySelector('#sorted').innerHTML = arr.join(',');
  },

  render: function () {
    this.renderOriginal();
    this.renderSorted();
  }
};

app.initialize();