// 测试文件
const { DoublyLinkedList, Node } = require('./DoublyLinkedList')

// 先创建3个节点
const node1 = new Node(1)
const node2 = new Node(2)
const node3 = new Node(3)

// 接下来，将这3个节点串联成一个双向链表
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2

// 创建一个 DoublyLinkedList 并将 node1 作为头节点
const dl = new DoublyLinkedList()
dl.head = node1
dl.tail = node3
dl.size = 3

// 打印双向链表
dl.print()

// 接收一个参数
// 该参数为新的节点的数据
add(item){
  // 生成新的节点
  const newNode = new Node(item);

  if(!this.head){
    // 进入此分支，说明 this.head 为 null
    // this.head 为 null 说明是一个空链表
    // 当前就一个节点，头部也是它，尾部也是它
    this.head = newNode;
    this.tail = newNode;
  } else {
    // 说明当前的双向链表是有节点
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }

  // 无论上面进入哪个分支，都是添加
  // 长度会增长
  this.size++;
}

// 接收两个参数
// 1. 要插入的下标
// 2. 新节点的数据
addAt(index, item){
  if(index < 0 || index > this.size){
    throw new Error("索引值无效");
  }

  // 创建新的节点
  const newNode = new Node(item);

  // 没有进入上面的if，说明索引没有问题，接下来开始根据索引进行插入操作
  if(index === 0){
    // 进入此分支，说明是要插入到头部
    newNode.next = this.head;
    if(this.head){
      // 因为头节点可能是null，例如空链表的情况
      this.head.prev = newNode;
    }
    this.head = newNode; // 更新头节点
    if(!this.tail){
      // 没有尾节点的时候，会进入此分支
      this.tail = newNode;
    }
  } else if(index === this.size){
    // 进入此分支，说明是要插入到尾部
    this.add(item);
  } else {
    // 插入到中间
    // 这里会涉及到需要找到具体的位置
    let current = this.head;
    let counter = 0; // 计数器，用于标注节点的个数，起到一个类似于数组下标的作用
    while(current){
      if(counter === index){
        // 更新各个节点的指向
        newNode.prev = current.prev;
        newNode.next = current;
        current.prev.next = newNode;
        current.prev = newNode;
        break;
      }
      // 不停的更新节点
      current = current.next;
      counter++;
    }
  }
  this.size++;
}

// 接收一个参数
// 要删除的数据节点对应的数据
remove(item){
  let current = this.head; // 一开始指向头节点
  while(current){
    // 这里面就需要去寻找对应数据的那个节点
    if(current.data === item){
      // 进入此分支，说明找到了要删除的节点
      if(current === this.head && current === this.tail){
        // 进入此分支，说明整个双向链表只有一个节点
        // 将头尾节点都置为空
        this.head = null;
        this.tail = null;
      } else if(current === this.head){
        // 说明当前要删除的节点是头节点
        this.head = this.head.next;
        this.head.prev = null;
      } else if(current === this.tail){
        // 说明要删除的节点为尾节点
        this.tail = this.tail.prev
        this.tail.next = null;
      } else {
        // 说明就是中间节点
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
      // 无论上面进入哪一个分支，都会删除一个节点
      this.size--;
      return true;
    }
    current = current.next;
  }
  return false;
}

// 接收一个参数
// 要删除的节点所对应的索引值
removeAt(index){
  if(index < 0 || index >= this.size){
    throw new Error("索引值有误");
  }

  let current = this.head; // 先记录头节点
  let counter = 0; // 计数器，对下标进行计数
  if(index === 0){
    // 进入此分支，说明删除的是头节点
    if(this.head === this.tail){
      // 说明当前的双链表只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
  } else {
    // 说明删除的是后面的节点
    while(current){
      if(counter === index){
        // 找到要删除的节点的时候，会进入该分支
        if(current === this.tail){
          // 说明要删除的节点是尾节点
          this.tail = current.prev; // 更新尾节点
          this.tail.next = null;
        } else {
          // 说明就是中间的节点
          current.prev.next = current.next;
          current.next.prev = current.prev;
        }
        break;
      }
      // 不断的更新节点
      current = current.next;
      counter++;
    }
  }
  this.size--;
}

reverse(){
  if(!this.head) return; // 如果是空链表，直接返回

  let current = this.head; // 缓存头节点
  let prev = null; // 用于缓存上一个节点
  let next = null; // 用于缓存下一个节点

  while(current){
    next = current.next;
    current.next = prev;
    current.prev = next;
    prev = current;
    current = next;
  }

  // 更新头节点和尾节点
  this.tail = this.head; // 原来的头变成了尾巴
  this.head = prev; // 然后更新头节点
}

// 接收2个参数
// 是两个下标值
swap(index1, index2){
  if(index1 === index2) return false; // 如果索引相等，不需要交换
  if(index1 < 0 || index1 >= this.size || index2 < 0 || index2 >= this.size){
    throw new Error("索引值有错误");
  }

  let current = this.head; // 记录头节点
  let counter = 0; //计数器，用于记录索引的，类似于数组的下标
  let node1 = null;
  let node2 = null;

  while(current){
    if(counter === index1) node1 = current;
    if(counter === index2) node2 = current;
    if(node1 && node2) break; // 两个节点都找到了，跳出循环
    current = current.next;
    counter++;
  }

  // 找到了两个节点，接下来进行交换操作
  if(node1 && node2){
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }

  return false;
}

length(){
  return this.size;
}
isEmpty(){
  return this.size === 0;
}

const arr = [1, 2, 3]
arr.forEach((item, index) => {
  console.log(item, index)
})

// 接收一个参数
// 该参数是一个回调函数
forEach(fn){
  // 遍历整个链表，将所有的节点扔给这个回调函数
  let current = this.head;
  while(current){
    fn(current);
    current = current.next;
  }
}

1000 --> 0
100 --> 7

// 接收一个参数
// 要查找的节点的数据是什么
find(item){
  let current = this.head;
  let counter = 0;
  while(current){
    if(current.data === item){
      // 说明找到了
      return counter;
    }
    current = current.next;
    counter++;
  }
  // 代码走到这儿，说明没有进入过 while 里面的 if
  // 说明没有找到
  return -1;
}