// 程序 = 数据结构 + 算法

// example:
// a -> b -> c -> null

// 单向链表节点
class ListNode {

  constructor(data) {
    // 双向链表
    // this.last = null;
    this.next = null;
    this.data = data;
  }

  // 添加子节点
  append(data) {
    this.next = new ListNode(data);
    return this.next;
  }

  // 是否为尾节点
  isTail() {
    return !this.next;
  }

  // 获取第n个子节点
  nextNth(n) {
    if (n < 1 || !this.next) { return null; }
    else if (n === 1) { return this.next; }
    else { return this.next.nextNth(n - 1); }
  }

}

class LinkedList {

  constructor(dataSet) {
    if (Array.isArray(dataSet)) {
      this.buildFromArray(dataSet);
    } else {
      this.buildFromObject(dataSet);
    }
  }

  // 从数组中构建链表
  buildFromArray(dataSet) {
    if (dataSet.length < 1) { throw 'empty data set'; }

    this.head = new ListNode(dataSet[0]);
    for (let i = 1; i < dataSet.length; i++) {
      this.head.append(dataSet[i]);
    }
  }

  // 构建单节点链表
  buildFromObject(data) {
    this.head = new ListNode(data);
  }

  // 判断链表是否有环
  hasLoop() {
    let fastPointer = this.head;
    let slowPointer = this.head;

    while (fastPointer) {
      slowPointer = slowPointer.next;
      fastPointer = fastPointer.nextNth(2);
      if (slowPointer && fastPointer && slowPointer === fastPointer) { return true; }
    }

    return false;
  }

}

let list = new LinkedList('a');
let a = list.head;
let b = a.append('b');
let c = b.append('c');

console.log(`c is tail: ${c.isTail()}`);

console.log(`list has no loop yet: ${!list.hasLoop()}`);

c.next = a;

console.log(`list has loop now: ${list.hasLoop()}`);

// 链表实际上有啥用呢？
// 实现更高级的数据结构: 动态数组, 栈, 队列, 哈希表...
// 大致思路

// 栈
class Stack {

  constructor(data) {
    this.list = new LinkedList(data);
  }

  push(data) {
    let node = new ListNode(data);
    node.next = this.list.head;
    this.list.head = node;
  }

  // example:
  // a -> null
  // push b: b -> a -> null

  pop() {
    let node = this.list.head;
    if (!node) { return null; }
    this.list.head = node.next;
    return node.data;
  }

  // example:
  // b -> a -> null
  // pop b: a -> null
}

// 队列

class Queue {

  constructor(data) {
    this.list = new LinkedList(data);
    this.tail = this.list.head;
  }

  enqueue(data) {
    if (this.tail) {
      this.tail = this.tail.append(data);
    } else {
      this.list.head = new ListNode(data);
      this.tail = this.list.head;
    }
  }

  // example:
  // a -> null
  // enqueue b: a -> b -> null

  dequeue() {
    let node = this.list.head;
    if (node) {
      this.list.head = node.next;
      if (this.tail === node) { this.tail = null; }
      return node.data;
    } else {
      return null;
    }
  }

  // example:
  // a -> b -> null
  // dequeue a: b -> null
}