// ListNode.hpp
///////////////////////////////
#pragma once
#define NULL 0

template<typename T> 
struct ListNode {
    ListNode() : pred(NULL), succ(NULL) { }
    ListNode(T e, ListNode<T>* p = NULL, ListNode<T>* s = NULL)
        : pred(p), succ(s), data(e) { }
    ListNode<T>* insertAsPred(T const& e);
    ListNode<T>* insertAsSucc(T const& e);
    ListNode<T>* pred;
    ListNode<T>* succ;
    T data;
};

template<typename T>
ListNode<T>* ListNode<T>::insertAsPred(T const& e) {
    auto x = new ListNode(e, pred, this); //创建新节点
    if (!x) return NULL;
    pred->succ = x; //设置正向链接 
    pred = x;
    return x;       //返回新节点的位置
}

template<typename T>
ListNode<T>* ListNode<T>::insertAsSucc(T const& e) {
    auto x = new ListNode(e, this, succ); //创建新节点
    if (!x) return NULL;
    succ->pred = x;  //设置逆向链接 
    succ = x;
    return x;        //返回新节点的位置
}

// List.hpp
/////////////////////////////////////
#pragma once
#include "ListNode.h"

template<typename T> 
struct ListNode;

template<typename T>
class list {
public:
    list() { init(); }
    list(ListNode<T>* p, int n);
    list(list<T> const& lst);
    list(list<T> const& lst, int r, int n);
    ~list();
public:
    bool valid(ListNode<T>* p);
    int size() { return _size; }
    bool empty() { return _size <= 0; }
    ListNode <T>* first() const { return _head->succ; }
    ListNode <T>* last( ) const { return _tail->pred; }
    T& operator[](int r) const;
    // 无序链表中的查找
    ListNode<T>* find(T const& e, int n = size(), ListNode<T>* p = tail()) const; 
    // 有序链表中的查找
    ListNode<T>* search(T const& e, int n = size(), ListNode<T>* p = tail()) const; 
    ListNode<T>* insertAsLast(T const& e);
    ListNode<T>* insertAsFirst(T const& e);
    ListNode<T>* insertAfter(T const& e, ListNode<T>* p);
    ListNode<T>* insertBefore(T const& e, ListNode<T>* p);
    T remove(ListNode<T>* p);
    int remove(T const& e, bool bDelSame = false);
    int duplicate();
    int uniquify();
    void travel();
    void reverseAboutMid();  // 关于中间对称轴颠倒节点
    void reverseAdjacent();  // 颠倒两两相邻的节点
    void reverseAround();    // 整个链表的颠倒
protected:
    void init();
    int clear();
    ListNode<T>* head() { return _head; }
    ListNode<T>* tail() { return _tail; }
    void copyNodes(ListNode<T>* p, int n);

private:
    int _size;
    ListNode<T>* _head;  // 头哨兵
    ListNode<T>* _tail; // 尾哨兵
};

template<typename T>
list<T>::~list() { 
    clear();
    delete _head;
    delete _tail;
    _size = 0;
    _head = _tail = NULL;
}

template<typename T>
list<T>::list(ListNode<T>* p, int n) {
    copyNodes(p, n);
}

template<typename T>
list<T>::list(list<T> const& lst) {
    copyNodes(lst.header, lst.size());
}

template<typename T>
list<T>::list(list<T> const& lst, int r, int n) {
    copyNodes(list[r], n);
}

template<typename T>
void list<T>::init() {
    _head = new ListNode<T>;
    _tail = new ListNode<T>;

    _head->succ  = _tail;
    _head->pred  = NULL;
    _tail->succ = NULL;
    _tail->pred = _head; 
    _size = 0;
}

template<typename T>
T& list<T>::operator[](int r) const {
    ListNode<T>* p = first();
    while (0 < r--) p = p->succ;
    return p->data;
}

template<typename T>
bool list<T>::valid(ListNode<T>* p) {
    if (p == head() || p == tail()) 
        return false;
    return true;
}

template<typename T>
ListNode<T>* list<T>::find(T const& e, int n, ListNode<T>* p) const { 
    while (0 <= n--)  // [0, n - 1)
        if (e == (p = p->pred)->data) break;
    if (!valid(p)) 
        return NULL;
    return p;
}

template<typename T>
ListNode<T>* list<T>::search(T const& e, int n, ListNode<T>* p) const {
    while (0 <= n--) // [0, n)
        if (e >= ((p = p->pred)->data)) 
            break;
    if (!valid(p)) 
        return NULL;
    return p;
} 

template<typename T>
ListNode<T>* list<T>::insertAsFirst(T const& e) {
    _size++;
    return head()->insertAsSucc(e);
}

template<typename T>
ListNode<T>* list<T>::insertAsLast(T const& e) {
    _size++;
    return tail()->insertAsPred(e);
}

template<typename T>
ListNode<T>* list<T>::insertAfter(T const& e, ListNode<T>* p) {
    _size++;
    return p->insertAsSucc(e);
}

template<typename T>
ListNode<T>* list<T>::insertBefore(T const& e, ListNode<T>* p) {
    _size++;
    return p->insertAsPred(e);
}

template<typename T>
void list<T>::copyNodes(ListNode<T>* p, int n) {
    init();
    for ( ; n--; p = p->succ) 
        insertAsLast(p->data);
}

template<typename T>
T list<T>::remove(ListNode<T>* p) { 
    T e = p->data;
    p->succ->pred = p->pred;
    p->pred->succ = p->succ;
    delete p;
    _size--;
    return e;
}

template<typename T>
int list<T>::remove(T const& e, bool bDelSame) {
    int nSize = 0;
    if (!(nSize = size())) return 0;
    for (auto p = head(), q = p->succ; q; q = q->succ) {
        while (p->data == e || q->data == e) {
            if (p->data == e) {
                remove(p);    // 删除符合条件的前驱节点
                p = q;        // 用后继节点的地址更新前驱节点的地址
            }
            else if (q->data == e) {
                remove(q);   // 删除符合条件的后继节点
                q = p->succ; // 用前驱的后继节点的地址更新后驱节点的地址
            }
            else if (q == tail()) break;
        }
    }
    return nSize - size();
}

template<typename T>
int list<T>::clear() {
    int tmp = size();
    while (!empty())
        remove(head()->succ);
    return tmp;
}

template<typename T>
int list<T>::duplicate() {
    if (size() < 2) return 0;
    int tmp = size();
    auto p = head;
    int r = 0;
    while (tail() != (p = p->succ)) {
        auto q = find(p->data, r, p);
        q ? remove(q) : r++;
    }
    return tmp - size();
}

template<typename T>
int list<T>::uniquify() {
    if (size() < 2) return 0;
    int tmp = size();
    auto p = first(), q = last();
    while (tail() != (q = p->succ))
        if (p->data != q->data) p = q;
        else remove(q);
    return tmp - size();
}

template<typename T>
void list<T>::reverseAboutMid() {
    auto p = head(), q = tail();
    for (int i = 1; i < size(); i += 2)
        swap((p = p->succ)->data, (q = q->pred)->data);
}

template<typename T>
void list<T>::reverseAdjacent() {
    if (size() < 2) return;
    for (auto p = head(); p; p = p->succ)
        swap(p->pred, p->succ);
    swap(head, tail);
}

template<typename T>
void list<T>::reverseAround() {
    if (size() < 2) return;
    for (auto p = head(), q = p->succ; p != tail(); p = q, q = q->succ) 
        p->pred = q;
    tail()->pred = NULL;
    for (auto p = tail(), q = p->pred; p != head(); p = q, q = q->pred)
        q->succ = p;
    head()->succ = NULL;

}

#include <iostream>
using namespace std;

template<typename T>
void list<T>::travel() {
    for (auto p = first(); p != tail(); p = p->succ) 
        cout << "[ " << p->data << " ]" << " " << "[ " << p << " ]" << endl;
}