#ifndef LIST_HPP
#define LIST_HPP

#include <iostream>
#include "Node.hpp"

// 这里列举了链表类模板的最基本功能，对原教材当中的写法进行了修订
// 更多功能改进，见对应的实战练习

template <typename T>
class List
{
    Node<T> *head, *tail; // 链表头指针和尾指针
public:
    List();                             // 只生成头结点
    ~List();                            // 删除整个链表
    void clear();                       // 清空链表，只余表头结点
    Node<T> *find(const T &data) const; // 返回数值为data的节点
    int length() const;                 // 计算单链表长度
    void print() const;                 // 打印链表的数据域
    void insert_front(Node<T> *p);      // 表头插入
    void insert_rear(Node<T> *p);       // 表尾插入
    Node<T> *delete_node(Node<T> *p);   // 删除并返回地址为p的节点
};

template <typename T>
List<T>::List()
{
    // 当链表为空时，tail指向头节点，否则指向链表最后一个节点
    head = tail = new Node<T>{};
}

template <typename T>
List<T>::~List()
{
    clear();
    delete head;
}

template <typename T>
void List<T>::clear()
{
    while (head->link)
        delete head->remove_after();
    tail = head; // 务必注意本类当中的操作是否会影响tail
}

template <typename T>
Node<T> *List<T>::find(const T &data) const
{
    Node<T> *tempP{head->link};
    while (tempP && tempP->info != data)
        tempP = tempP->link;
    return tempP; // 搜索成功返回指点节点的指针，不成功返回nullptr
}

template <typename T>
int List<T>::length() const
{
    int count{0};
    Node<T> *tempP{head->link};
    while (tempP)
    {
        tempP = tempP->link;
        ++count;
    }
    return count;
}

template <typename T>
void List<T>::print() const
{
    Node<T> *tempP{head->link};
    while (tempP)
    {
        //tempP->print();
        std::cout << tempP->get_info() << '\t';
        tempP = tempP->link;
    }
    std::cout << '\n';
}

template <typename T>
void List<T>::insert_front(Node<T> *p)
{
    head->insert_after(p);
    if (tail == head)
        tail = p; // 注意可能修正tail
}

template <typename T>
void List<T>::insert_rear(Node<T> *p)
{
    tail->insert_after(p);
    tail = p;
}

template <typename T>
Node<T> *List<T>::delete_node(Node<T> *p)
{
    Node<T> *tempP{head};                   // 注意与之前的不同
    while (tempP->link && tempP->link != p) // 找到p的位置
        tempP = tempP->link;
    if (p == tail)
        tail = tempP; // 修正tail
    return tempP->remove_after();
}

#endif