export default interface ILinkedList<T> extends IList<T> {
  append(value: T): void
  traverse(): void
  insert(position: number, value: T): void
  removeAt(position: number): T | null
  getValue(position: number): T | null
  update(position: number, value: T): void
  indexOf(value: T): number
  remove(value: T): boolean
}

class Node<T> {
  value: T

  next: Node<T> | null = null

  constructor(value: T) {
    this.value = value
  }
}

export default class LinkedList<T> implements ILinkedList<T> {
  protected head: Node<T> | null = null
  protected length: number = 0

  protected tail: Node<T> | null = null

  get size() {
    return this.length
  }

  peek() {
    return this.head?.value
  }

  // 私有方法，根据position获取链表节点
  private getNode(position: number) {
    let index = 0
    let current = this.head
    while (index++ < position) {
      current = current?.next ?? null
    }
    return current
  }

  // 添加链表元素
  append(value: T) {
    const newNode = new Node(value)

    if (!this.head) {
      this.head = newNode
    } else {
      this.tail!.next = newNode
    }
    this.tail = newNode

    this.length++
  }

  // 最后节点的判断
  private isLastNode(node: Node<T>) {
    return this.tail === node
  }

  // 遍历链表的方法
  traverse() {
    const values: T[] = []

    let current = this.head
    while (current) {
      values.push(current.value)
      if(this.isLastNode(current!)) {
        if(this.head && current.next === this.head) {
          values.push(this.head.value)
        }
        console.log(values.join(' -> '))
        return
      }
      current = current.next
    }
  }

  // 插入节点
  insert(position: number, value: T) {
    if (position < 0 || position > this.length) { throw new Error('position越界')
   }
    const newNode = new Node(value)
    // 头部插入
    if (position === 0) {
      newNode.next = this.head
      this.head = newNode
    } else { // 非头部插入
      let previous = this.getNode(position - 1)
      newNode.next = previous!.next
      previous!.next = newNode
    }
    if(position === this.length) this.tail = newNode
    this.length++
  }

  // 移除节点
  removeAt(position: number): T | null {
    if (position < 0 || position > this.length - 1) { throw new Error('position越界') }

    let value: T | null = null
    if (position === 0) {
      value = this.head!.value
      this.head = this.head!.next
      // this.head = this.head?.next ?? null 三目运算简写
      if(this.length === 1) this.tail = null
    } else {
      let previous = this.getNode(position - 1)
      value = previous!.next!.value
      previous!.next = previous!.next!.next
      if(position === this.length - 1) this.tail = previous
    }

    this.length--
    return value
  }

  // 根据下标获取元素值
  getValue(position: number): T | null {
    if (position < 0 || position >= this.length) {
      throw new Error('position越界')
    }
    let current = this.getNode(position)
    return current?.value ?? null
  }

  // 修改某个节点值
  update(position: number, value: T) {
    if (position < 0 || position >= this.length) {
      throw new Error('position越界')
    }
    let current = this.getNode(position)
    current!.value = value
    return true
  }

  // indexOf实现
  indexOf(value: T): number {
    let current = this.head
    if (!current) { return -1 }
    let index = 0
    while (index < this.length) {
      console.log(index)
      if (current!.value === value) {
        return index
      } else {
        current = current!.next
      }
      index++
    }

    return -1
  }

  // 根据value删除
  remove(value: T): boolean {
    let index = this.indexOf(value)
    return this.removeAt(index) ? true : false
  }

  // 为空判断
  isEmpty(): boolean {
    return this.length > 0 ? false : true
  }
}