// Copyright 2025 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

///| 创建一个新的XOR链表
pub fn[A] new() -> T[A] {
  T::{
    head: -1,
    tail: -1,
    nodes: Array::new(capacity=10),
    free_ids: Array::new(capacity=10),
    size: 0,
  }
}

///| 链表是否为空
pub fn[A] is_empty(self : T[A]) -> Bool {
  self.size == 0
}

///| 获取链表大小
pub fn[A] len(self : T[A]) -> Int {
  self.size
}

///| 分配新节点ID
pub fn[A] allocate_node_id(self : T[A]) -> Int {
  // 优先使用空闲ID
  if !self.free_ids.is_empty() {
    return self.free_ids.pop().unwrap()
  }

  // 否则添加新节点到数组末尾
  let id = self.nodes.length()
  self.nodes.push(None)
  id
}

///| 释放节点ID（添加到空闲列表）
pub fn[A] free_node_id(self : T[A], id : Int) -> Unit {
  self.free_ids.push(id)
}

///| 在链表前端添加元素
pub fn[A] push_front(self : T[A], value : A) -> Unit {
  // 分配新节点ID
  let new_id = self.allocate_node_id()

  // 修改：创建新节点，link 值为 (-1) ^ 当前头节点ID
  let new_node = Node::{ value, link: -1 ^ self.head }
  self.nodes[new_id] = Some(new_node)
  if self.size == 0 {
    // 链表为空
    self.head = new_id
    self.tail = new_id
  } else {
    // 更新原头节点的链接值
    let old_head_node = self.nodes[self.head].unwrap()
    // 原头节点的前驱为 -1，后继可以从 link 推导：next = (-1) ^ link
    let next = -1 ^ old_head_node.link
    // 新的链接值为：new_id ^ next
    old_head_node.link = new_id ^ next
    self.nodes[self.head] = Some(old_head_node)

    // 更新头节点指针
    self.head = new_id
  }
  self.size += 1
}

///| 在链表后端添加元素
pub fn[A] push_back(self : T[A], value : A) -> Unit {
  // 分配新节点ID
  let new_id = self.allocate_node_id()

  // 修改：创建新节点，link 值为 当前尾节点ID ^ (-1)
  let new_node = Node::{ value, link: self.tail ^ -1 }
  self.nodes[new_id] = Some(new_node)
  if self.size == 0 {
    // 链表为空
    self.head = new_id
    self.tail = new_id
  } else {
    // 更新原尾节点的链接值
    let old_tail_node = self.nodes[self.tail].unwrap()
    // 原尾节点的后继为 -1，前驱可以从 link 推导：prev = link ^ (-1)
    let prev = old_tail_node.link ^ -1
    // 新的链接值为：prev ^ new_id
    old_tail_node.link = prev ^ new_id
    self.nodes[self.tail] = Some(old_tail_node)

    // 更新尾节点指针
    self.tail = new_id
  }
  self.size += 1
}

///| 从链表前端移除元素
pub fn[A] pop_front(self : T[A]) -> A? {
  if self.size == 0 {
    return None
  }

  // 获取头节点
  let head_node = self.nodes[self.head].unwrap()
  let value = head_node.value
  if self.size == 1 {
    // 链表只有一个元素
    self.free_node_id(self.head)
    self.nodes[self.head] = None
    self.head = -1
    self.tail = -1
    self.size = 0
  } else {
    // 链表有多个元素
    // 获取第二个节点ID（头节点的后继）：next = (-1) ^ link
    let next = -1 ^ head_node.link

    // 获取第二个节点
    let next_node = self.nodes[next].unwrap()

    // 计算第二个节点的后继
    let next_next = self.head ^ next_node.link

    // 更新第二个节点的link值，现在它成为新的头节点（前驱为-1）
    next_node.link = -1 ^ next_next
    self.nodes[next] = Some(next_node)

    // 释放原头节点
    self.free_node_id(self.head)
    self.nodes[self.head] = None

    // 更新头指针
    self.head = next
    self.size -= 1
  }
  Some(value)
}

///| 从链表后端移除元素
pub fn[A] pop_back(self : T[A]) -> A? {
  if self.size == 0 {
    return None
  }

  // 获取尾节点
  let tail_node = self.nodes[self.tail].unwrap()
  let value = tail_node.value
  if self.size == 1 {
    // 链表只有一个元素
    self.free_node_id(self.tail)
    self.nodes[self.tail] = None
    self.head = -1
    self.tail = -1
    self.size = 0
  } else {
    // 链表有多个元素
    // 获取倒数第二个节点ID（尾节点的前驱）：prev = link ^ (-1)
    let prev = tail_node.link ^ -1

    // 获取倒数第二个节点
    let prev_node = self.nodes[prev].unwrap()

    // 计算倒数第二个节点的前驱
    let prev_prev = self.tail ^ prev_node.link

    // 更新倒数第二个节点的link值，现在它成为新的尾节点（后继为-1）
    prev_node.link = prev_prev ^ -1
    self.nodes[prev] = Some(prev_node)

    // 释放原尾节点
    self.free_node_id(self.tail)
    self.nodes[self.tail] = None

    // 更新尾指针
    self.tail = prev
    self.size -= 1
  }
  Some(value)
}

///| 遍历链表（从头到尾）
pub fn[A] each(self : T[A], f : (A) -> Unit) -> Unit {
  if self.head < 0 || self.size == 0 {
    return
  }

  // 从头节点开始遍历
  let mut prev_id = -1
  let mut current_id = self.head
  let mut count = 0
  while current_id >= 0 && count < self.size {
    match self.nodes[current_id] {
      Some(node) => {
        // 处理当前节点
        f(node.value)

        // 计算下一个节点ID
        let next_id = prev_id ^ node.link

        // 移动到下一个节点
        prev_id = current_id
        current_id = next_id
        count += 1
      }
      None => break
    }
  }
}

///| 反向遍历链表（从尾到头）
pub fn[A] each_reverse(self : T[A], f : (A) -> Unit) -> Unit {
  if self.tail < 0 || self.size == 0 {
    return
  }

  // 从尾节点开始遍历
  let mut next_id = -1
  let mut current_id = self.tail
  let mut count = 0
  while current_id >= 0 && count < self.size {
    match self.nodes[current_id] {
      Some(node) => {
        // 处理当前节点
        f(node.value)

        // 计算前一个节点ID
        let prev_id = next_id ^ node.link

        // 移动到前一个节点
        next_id = current_id
        current_id = prev_id
        count += 1
      }
      None => break
    }
  }
}

///| 转换为数组
pub fn[A] to_array(self : T[A]) -> Array[A] {
  let result = Array::new(capacity=self.len()) // 添加mut关键字

  // 使用简单遍历方法替代 each
  if self.size > 0 {
    // 手动遍历链表
    let mut current = self.head
    let mut prev = -1
    let mut count = 0
    while current >= 0 && count < self.size {
      match self.nodes[current] {
        Some(node) => {
          result.push(node.value)
          let next = prev ^ node.link
          prev = current
          current = next
          count += 1
        }
        None => break
      }
    }
  }
  result
}

///| 清空链表
pub fn[A] clear(self : T[A]) -> Unit {
  // 重置链表状态
  self.head = -1
  self.tail = -1
  self.nodes = Array::new(capacity=10)
  self.free_ids = Array::new(capacity=10)
  self.size = 0
}

///| 获取指定位置的元素（从0开始计数）
pub fn[A] get(self : T[A], index : Int) -> A? {
  if index < 0 || index >= self.size {
    return None
  }

  // 从头节点开始遍历
  let mut prev_id = -1
  let mut current_id = self.head
  let mut i = 0
  while i < index && current_id >= 0 {
    // 获取当前节点
    match self.nodes[current_id] {
      Some(node) => {
        // 计算下一个节点ID
        let next_id = prev_id ^ node.link
        // 移动到下一个节点
        prev_id = current_id
        current_id = next_id
        i += 1
      }
      None => return None
    }
  }

  // 返回找到的节点值
  if current_id >= 0 {
    match self.nodes[current_id] {
      Some(node) => Some(node.value)
      None => None
    }
  } else {
    None
  }
}

///| 获取链表的第一个元素
pub fn[A] head(self : T[A]) -> A? {
  if self.size == 0 || self.head < 0 {
    return None
  }
  match self.nodes[self.head] {
    Some(node) => Some(node.value)
    None => None
  }
}

///| 获取链表的最后一个元素
pub fn[A] last(self : T[A]) -> A? {
  if self.size == 0 || self.tail < 0 {
    return None
  }
  match self.nodes[self.tail] {
    Some(node) => Some(node.value)
    None => None
  }
}

///| 检查链表是否包含指定元素
pub fn[A : Eq] contains(self : T[A], value : A) -> Bool {
  if self.size == 0 {
    return false
  }
  let mut found = false
  self.each(fn(item) { if item == value { found = true } })
  found
}

///| 查找符合条件的第一个元素
pub fn[A] find(self : T[A], predicate : (A) -> Bool) -> A? {
  if self.size == 0 {
    return None
  }

  // 从头节点开始遍历
  let mut prev_id = -1
  let mut current_id = self.head
  let mut count = 0
  while current_id >= 0 && count < self.size {
    match self.nodes[current_id] {
      Some(node) => {
        if predicate(node.value) {
          return Some(node.value)
        }

        // 计算下一个节点ID
        let next_id = prev_id ^ node.link

        // 移动到下一个节点
        prev_id = current_id
        current_id = next_id
        count += 1
      }
      None => break
    }
  }
  None
}

///| 查找符合条件的第一个元素的索引
pub fn[A] find_index(self : T[A], predicate : (A) -> Bool) -> Int? {
  if self.size == 0 {
    return None
  }

  // 从头节点开始遍历
  let mut prev_id = -1
  let mut current_id = self.head
  let mut index = 0
  while current_id >= 0 && index < self.size {
    match self.nodes[current_id] {
      Some(node) => {
        if predicate(node.value) {
          return Some(index)
        }

        // 计算下一个节点ID
        let next_id = prev_id ^ node.link

        // 移动到下一个节点
        prev_id = current_id
        current_id = next_id
        index += 1
      }
      None => break
    }
  }
  None
}

///| 查找特定元素的索引
pub fn[A : Eq] index_of(self : T[A], value : A) -> Int? {
  self.find_index(fn(item) { item == value })
}

///| 将函数应用到所有元素并创建新链表
pub fn[A, B] map(self : T[A], f : (A) -> B) -> T[B] {
  let result = new()
  self.each(fn(item) { result.push_back(f(item)) })
  result
}

///| 筛选符合条件的元素并创建新链表
pub fn[A] filter(self : T[A], predicate : (A) -> Bool) -> T[A] {
  let result = new()
  self.each(fn(item) { if predicate(item) { result.push_back(item) } })
  result
}

///| 聚合链表元素
pub fn[A, B] fold(self : T[A], initial : B, f : (B, A) -> B) -> B {
  let mut acc = initial
  self.each(fn(item) { acc = f(acc, item) })
  acc
}

///| 获取前n个元素组成的新链表
pub fn[A] take(self : T[A], n : Int) -> T[A] {
  if n <= 0 {
    return new()
  }
  if n >= self.size {
    return self
  }
  let result = new()
  let mut count = 0
  self.each(fn(item) {
    if count < n {
      result.push_back(item)
      count += 1
    }
  })
  result
}

///| 丢弃前n个元素，保留剩余元素
pub fn[A] drop(self : T[A], n : Int) -> T[A] {
  if n <= 0 {
    return self
  }
  if n >= self.size {
    return new()
  }
  let result = new()
  let mut count = 0
  self.each(fn(item) {
    if count >= n {
      result.push_back(item)
    }
    count += 1
  })
  result
}

///| 移除指定位置的元素
pub fn[A] remove_at(self : T[A], index : Int) -> A? {
  if index < 0 || index >= self.size {
    return None
  }
  if index == 0 {
    return self.pop_front()
  }
  if index == self.size - 1 {
    return self.pop_back()
  }

  // 遍历到指定位置
  let mut prev_id = -1
  let mut current_id = self.head
  let mut i = 0
  while i < index && current_id >= 0 {
    match self.nodes[current_id] {
      Some(node) => {
        let next_id = prev_id ^ node.link
        prev_id = current_id
        current_id = next_id
        i += 1
      }
      None => return None
    }
  }

  // 找到要删除的节点
  match self.nodes[current_id] {
    Some(node) => {
      let value = node.value

      // 获取前驱和后继节点ID
      let prev_node_id = prev_id
      let next_node_id = prev_id ^ node.link

      // 更新前驱节点的link
      if prev_node_id >= 0 {
        ignore(
          match self.nodes[prev_node_id] {
            Some(prev_node) => {
              let prev_prev = prev_node.link ^ current_id
              prev_node.link = prev_prev ^ next_node_id
              self.nodes[prev_node_id] = Some(prev_node)
            }
            None => ()
          },
        )
      }

      // 更新后继节点的link
      if next_node_id >= 0 {
        ignore(
          match self.nodes[next_node_id] {
            Some(next_node) => {
              let next_next = next_node.link ^ current_id
              next_node.link = next_next ^ prev_node_id
              self.nodes[next_node_id] = Some(next_node)
            }
            None => ()
          },
        )
      }

      // 释放被删除的节点
      self.free_node_id(current_id)
      self.nodes[current_id] = None
      self.size -= 1
      Some(value)
    }
    None => None
  }
}

///| 移除第一个匹配的元素
pub fn[A : Eq] remove(self : T[A], value : A) -> Bool {
  match self.index_of(value) {
    Some(index) => {
      ignore(self.remove_at(index))
      true
    }
    None => false
  }
}

///| 反转链表
pub fn[A] reverse(self : T[A]) -> Unit {
  if self.size <= 1 {
    return
  }

  // 交换头尾指针
  let temp = self.head
  self.head = self.tail
  self.tail = temp

  // 遍历并重新计算每个节点的link值
  let mut current_id = self.head
  let mut next_id = -1
  let mut count = 0
  while current_id >= 0 && count < self.size {
    match self.nodes[current_id] {
      Some(node) => {
        let prev_id = next_id ^ node.link
        node.link = next_id ^ prev_id // 交换前后指针的异或值
        self.nodes[current_id] = Some(node)
        next_id = current_id
        current_id = prev_id
        count += 1
      }
      None => break
    }
  }
}

///| 将两个链表合并为一个包含元组的链表
pub fn[A, B] zip(self : T[A], other : T[B]) -> T[(A, B)] {
  let result = new()
  let min_size = self.size.min(other.size)
  if min_size == 0 {
    return result
  }

  // 遍历两个链表
  let mut prev_id1 = -1
  let mut current_id1 = self.head
  let mut prev_id2 = -1
  let mut current_id2 = other.head
  let mut count = 0
  while current_id1 >= 0 && current_id2 >= 0 && count < min_size {
    match (self.nodes[current_id1], other.nodes[current_id2]) {
      (Some(node1), Some(node2)) => {
        // 添加元组到结果链表
        result.push_back((node1.value, node2.value))

        // 计算下一个节点ID
        let next_id1 = prev_id1 ^ node1.link
        let next_id2 = prev_id2 ^ node2.link

        // 移动到下一个节点
        prev_id1 = current_id1
        current_id1 = next_id1
        prev_id2 = current_id2
        current_id2 = next_id2
        count += 1
      }
      _ => break
    }
  }
  result
}

///| 在元素之间插入分隔值
pub fn[A] intersperse(self : T[A], separator : A) -> T[A] {
  if self.size <= 1 {
    return self
  }
  let result = new()
  let mut is_first = true
  self.each(fn(item) {
    if is_first {
      is_first = false
    } else {
      result.push_back(separator)
    }
    result.push_back(item)
  })
  result
}

///| 检查链表元素是否按升序排列
pub fn[A : Compare] is_sorted(self : T[A]) -> Bool {
  if self.size <= 1 {
    return true
  }
  let mut prev_value : A? = None
  let mut is_sorted = true
  self.each(fn(item) {
    match prev_value {
      Some(prev) => if prev > item { is_sorted = false }
      None => ()
    }
    prev_value = Some(item)
  })
  is_sorted
}

///| 排序链表（使用归并排序）
pub fn[A : Compare] sort(self : T[A]) -> Unit {
  if self.size <= 1 {
    return
  }

  // 将链表转换为数组，排序后再转回链表
  let arr = self.to_array()
  arr.sort()

  // 清空原链表
  self.clear()

  // 重建链表
  for i = 0; i < arr.length(); i = i + 1 {
    self.push_back(arr[i])
  }
}