pred();             //当前节点前驱节点的位置
succ();             //同上,后继
data();             //当前节点所存数据对象
insertAsPred(e);    //插入前驱节点,存入被引用对象e,返回新节点位置
insertAsSucc(e);    //同上,后继

/*列表节点:LIstNode模板类*/

#define Posi(T) ListNode<T>*            //列表节点位置(ISO C++.0x, template alias)
template<typename T>
struct ListNode{                        //不过度封装,列表节点模板类,以双向链表形式实现
    T data;                             //数值
    Posi(T) pred;                       //前驱
    Posi(T) succ;                       //后继
    ListNode(){}                        //针对header和trailer的构造
    ListNode(T e, Posi(T) p=NULL, Posi(T) s=NULL)
    : data(e),pred(p),succ(s){}         //默认constructor
    Posi(T) insertAsPred(T const & e);  
    Posi(T) insertAsSucc(T const & e);
}

#include "listNode.h"               //引入list节点类

template<typename T> class List {   //list模板类
  private: 
    int _size;
    Posi(T) header; Posi(T) trailer;
    /*
    头/尾哨兵,对外不可见
    firstNode/lastNode, 首元素/末元素对外可见
    头尾一定存在,firstNode和lastNode不一定存在
    头,首,末,尾
    -1, 0,n-1,n (rank)                          

  protected:
    /*内部函数*/

  public:
    /*constructor,destructor,只读接口,可写接口,遍历接口*/
}

/*构造*/

template<typename T> void List<T>::init(){      //初始化,创建列表对象时统一调用
    header  = new ListNode<T>;
    trailer = new ListNode<T>;
    header->succ = trailer; header->pred = NULL;//互联
    trailer->pred = header; trailer->succ= NULL;//互连
    _size = 0;                                  //记录规模
}

template <typename T>                   //assert 0<= rank <size
T List<T>::operator[](Rank r) const {   //O(r), 效率低下,可偶尔为之,不宜长用
    Posi(T) p = first();                //从首节点出发
    while(r-- > 0) p = p->succ;         //顺数第r个节点即是
    return p->data;                     //目标节点
}//任一节点的秩,亦即其前驱的总数

问题: Rank是什么类型? 是int,回头看vector那一章

template <typename T>                                       //从外部调用时,0 <= n <= rank(p) < _size
Posi(T) List<T>::find(T const & e,int n,Posi(T) p) const{   //顺序查找, O(n)
    while(n-- > 0)  //从右向左,逐个将p的前驱与e比对
        if(e == ( p = p->pred )->data ) return p; //神奇
    return NULL;
}//header的存在使得处理更为简洁

find(e,n,p) //查找前驱pred
find(e,p,n) //查找后继succ

//自己更易懂的写法
template <typename T>
Posi(T) List<T>::find(T const & e,int n,Posi(T) p) const{   //顺序查找, O(n)
    while(n--){
    p = p->pred;
    if(e == p->data ) 
        return p; 
    }

    return NULL;
}//header的存在使得处理更为简洁

/*insert*/

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

template <typename T>                           //前插入算法(后插入完全对称)
Posi(T) ListNode<T>::insertAsPred(T const & e){ //O(1)
    Posi(T) x = new ListNode(e,pred,this);      //创建(耗时100倍(?))
    pred->succ = x;                             //建立连接
    pred = x;
    return x;                                   //返回新节点的位置
}

//即便当前node是first node,它的pred依然存在, 是header

/*construction based on copy*/

template <typename T>                      //基本接口
void List<T>::copyNodes(Posi(T) p,int n){  //O(n)
    init();                                //创建header/trailer 
    while (n--){                           //将起自p的n项依次作为末节点插入
        insertAsLast(p->data);             //实际上就是insertBefore(trailer)
        p = succ;
    }
}

/*remove node*/

template <typename T>       
T List<T>::remove(Posi(T) p){   //删除合法位置p处节点,返回其数值,O(1)
    T e = p->data;              //备份待删除节点数值(假设类型T可直接赋值)
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    _size--;
    return e;                   //返回备份数值
}

/*list dectructor*/

template <typename T>
List<T>::~List(){   
    clear();        //清空列表
    delete header;  //释放header
    delete trailer; //释放trailer
}

template <typename T> int List<T>::clear(){
    int oldSize = _size;
    while(_size>0){
        remove(header->succ);
    }
    return oldSize;
}//O(n)

/*deduplicate*/

template <typename T> int List<T>::deduplicate(){   //剔除无序列表中的重复节点
    if(_size<2) return 0;               //平凡列表自然无重复
    int oldSize = _size;
    Posi(T) p = first();   Rank r = 1;  //p从首节点起

    while( (p=p->succ) != trailer){     //依次直到末节点
        Posi(T) q = find(p->data,r,p);  //r是真前驱的数目
        q? remove(q): r++;              //若存在,删除;不可remove(p)
    }//assert(断言):循环过程中的任意时刻,p的所有pred互不相同

    return oldSize - _size;             //返回列表规模变化量
}//正确性及效率分析的方法与结论,与Vector::deduplicate()相同

/*uniquify*/

template <typename T>
int List<T>::uniquify(){        //成批删除重复元素
    int oldSize = _size;
    ListNodePosi(T) p = first();//各区段起点
    ListNodePosi(T) q;          //起点后继

    while( (q=p->succ) != trailer ){
        if(p->data != q->data) p = q;       //若互异,转向下一区段
        else                   remove(q);   //若相同,删除后者
    }

    return oldSize - _size;
}//O(n)

/*search*/
//在有序列表内节点p的n个真前驱中,找到不大于e的最后者(找到<=e的离e最近的那个)

template <typename T>
Posi(T) List<T>::search(T const & e,int n,Posi(T) p) const {
    while(n--){     //从右向左
        if( ( ( p=p->pred )->data ) <= e) break;
    }

    return p;
}//与无序列表的find没多大差异,最好O(1),最坏O(n),等概率平均时间O(n),正比于区间宽度

//问题在于list的循位置访问(call-by-position,就是得找pred/succ)
//与向量的循秩访问(call-by-rank,就是直接找[i]?(这里英文怎么说))有本质的差别
//RAM模型call-by-rank,找到对应的寄存器,读取数值,O(1)
//图灵机模型call-by-position,纸带长度无限,只能左右移动

//Vector rank
//List   posi

/*selection sort*/
//对列表中起始于位置p的连续n个元素做选择排序,valid(p) && rank(p) + n <= size

tamplate <typename T> void List<T>::selectionSort(Posi(T) p,int n){
    //待排区间(head,tail)
    Posi(T) head = p->pred;
    Posi(T) tail = p;
    for(int i=0; i<n; i++){     //head/tail可能是header/trailer.
        tail = tail->succ;      //(tail到trailer的succ了怎么办? 岂不是null了?)    
        /*改进方法:
        if(tail->succ != NULL){
            tail = tail->succ;
        }
        */
    }

    while(n>1){
        insertBefore(tail,remove( selectMax(head->succ,n) ));//insert要new,remove要delete
        tail = tail->pred;                                   //是通常基本操作的100倍
        n--;                                                 //改进(1):直接修改reference
    }                                                        //改进(2):修改succ/pred
}

/*selectMax*/

template <typename T>
Posi(T) List<T>::selectMax(Posi(T) p, int n){
    Posi(T) max = p;

    for(Posi(T) cur=p;n>1;n--){
        if( !lt((cur = cur->succ)->data,max->data) ) //not less than
            max = cur;                               //painter's algorithm
    }                                                //这里有一个trick, 要用>=,不用>
                                                     //selectMax()中对于多个相等的最大元素，选取其中位置最靠后者
    return max;
}

/*Insertion Sort*/
//对列表中起始于位置p的连续n个元素做插入排序

template<typename T>
void List<T>::insertSort(Posi(T) p,int n){
    for(int r=0;r<n;r++){       //r是已排序的元素个数
        insertAfter( search(p->data,r,p),p->data );     
        p = p->succ;
        remove(p->pred);        //转向下一节点
    }//O(r+1)
}//仅用O(1)辅助空间,就地算法(in-place algorithm)