/*
 * @Author: Student author@example.com
 * @Date: 2025-01-02 01:17:31
 * @LastEditors: Student author@example.com
 * @LastEditTime: 2025-01-03 02:00:59
 * @FilePath: \LibraryManageSystem\src\STL\LinkList.cpp
 * @Description: Coding with UTF-8
 * 
 * Copyright (c) 2025 by Student, All Rights Reserved. 
 */
#include "../../include/STL/LinkList.h"

// 构造函数
LinkList::LinkList() : head(new ListNode()), len(0) {}

// 拷贝构造函数
LinkList::LinkList(const LinkList &other) : head(new ListNode()), len(0)
{
    copyFrom(other);
}

// 析构函数
LinkList::~LinkList()
{
    clear();
    delete head;
}

// 赋值运算符
LinkList &LinkList::operator=(const LinkList &other)
{
    if (this != &other)
    {
        clear();
        copyFrom(other);
    }
    return *this;
}

// 在链表头部插入数据
void LinkList::addNodeToFront(int x)
{
    ListNode *newNode = new ListNode(x);
    newNode->next = head->next;
    head->next = newNode;
    len++;
}

// 在链表尾部插入数据
void LinkList::addNodeToEnd(intptr_t x)
{
    ListNode *newNode = new ListNode(x);
    ListNode *p = head;
    while (p->next != nullptr)
    {
        p = p->next;
    }
    p->next = newNode;
    len++;
}

// 在指定位置插入数据
void LinkList::insertNode(int i, int item)
{
    if (i <= 0 || i > len + 1)
    {
        throw std::out_of_range("Invalid position for insertion");
    }

    ListNode *p = head;
    for (int k = 1; k < i; k++)
    {
        p = p->next;
    }

    ListNode *newNode = new ListNode(item);
    newNode->next = p->next;
    p->next = newNode;
    len++;
}

// 删除指定位置的节点
void LinkList::deleteNode(int i)
{
    if (i <= 0 || i > len)
    {
        throw std::out_of_range("Invalid position for deletion");
    }

    ListNode *p = head;
    for (int k = 1; k < i; k++)
    {
        p = p->next;
    }

    ListNode *temp = p->next;
    p->next = temp->next;
    delete temp;
    len--;
}

// 获取指定位置的节点指针
ListNode *LinkList::getPointer(int i)
{
    if (i <= 0 || i > len)
    {
        return nullptr;
    }

    ListNode *p = head->next;
    for (int k = 1; k < i; k++)
    {
        p = p->next;
    }
    return p;
}

// const版本的getPointer
const ListNode *LinkList::getPointer(int i) const
{
    if (i <= 0 || i > len)
    {
        return nullptr;
    }

    const ListNode *p = head->next;
    for (int k = 1; k < i; k++)
    {
        p = p->next;
    }
    return p;
}

// 查找指定值的位置
int LinkList::findValue(int value) const
{
    const ListNode *p = head->next;
    int pos = 1;
    while (p != nullptr)
    {
        if (p->data == value)
        {
            return pos;
        }
        p = p->next;
        pos++;
    }
    return -1;
}

// 打印指定位置的数据
void LinkList::getData(int i) const
{
    const ListNode *node = getPointer(i);
    if (node != nullptr)
    {
        std::cout << node->data;
    }
    else
    {
        throw std::out_of_range("Invalid position");
    }
}

// 打印所有节点
void LinkList::displayAllNodes() const
{
    const ListNode *p = head->next;
    while (p != nullptr)
    {
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

// 交换两个节点
void LinkList::swapNodes(int pa, int pb)
{
    if (pa == pb || pa <= 0 || pb <= 0 || pa > len || pb > len)
    {
        return;
    }

    // 确保pa < pb
    if (pa > pb)
    {
        std::swap(pa, pb);
    }

    ListNode *prevA = head;
    for (int i = 1; i < pa; i++)
    {
        prevA = prevA->next;
    }

    ListNode *prevB = head;
    for (int i = 1; i < pb; i++)
    {
        prevB = prevB->next;
    }

    ListNode *nodeA = prevA->next;
    ListNode *nodeB = prevB->next;
    ListNode *nextB = nodeB->next;

    if (nodeA == prevB)
    { // 相邻节点的特殊情况
        prevA->next = nodeB;
        nodeB->next = nodeA;
        nodeA->next = nextB;
    }
    else
    {
        prevA->next = nodeB;
        nodeB->next = nodeA->next;
        prevB->next = nodeA;
        nodeA->next = nextB;
    }
}

// 链表排序
void LinkList::sortForLinkList()
{
    if (len <= 1)
        return;
    quickSort(1, len);
}

// 快速排序实现
void LinkList::quickSort(int left, int right)
{
    if (left >= right)
        return;

    int pivot = getPointer(left)->data;
    int i = left, j = right;

    while (i < j)
    {
        while (i < j && getPointer(j)->data >= pivot)
            j--;
        while (i < j && getPointer(i)->data <= pivot)
            i++;
        if (i < j)
            swapNodes(i, j);
    }
    swapNodes(left, i);

    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

// 合并两个链表
LinkList LinkList::mergeLinkLists(LinkList &La, LinkList &Lb)
{
    LinkList result;
    ListNode *pa = La.head->next;
    ListNode *pb = Lb.head->next;

    while (pa != nullptr && pb != nullptr)
    {
        if (pa->data <= pb->data)
        {
            result.addNodeToEnd(pa->data);
            pa = pa->next;
        }
        else
        {
            result.addNodeToEnd(pb->data);
            pb = pb->next;
        }
    }

    while (pa != nullptr)
    {
        result.addNodeToEnd(pa->data);
        pa = pa->next;
    }

    while (pb != nullptr)
    {
        result.addNodeToEnd(pb->data);
        pb = pb->next;
    }

    return result;
}

// 清空链表
void LinkList::clear()
{
    ListNode *current = head->next;
    while (current != nullptr)
    {
        ListNode *next = current->next;
        delete current;
        current = next;
    }
    head->next = nullptr;
    len = 0;
}

// 复制辅助函数
void LinkList::copyFrom(const LinkList &other)
{
    const ListNode *p = other.head->next;
    while (p != nullptr)
    {
        addNodeToEnd(p->data);
        p = p->next;
    }
}