0001 #include <assert.h>
0002 #include "_share/util.h"
0003 #include "UniPrint/print.h"
0004 
0005 template <typename T> class CursorList { //游标式列表
0006 protected:
0007    Rank _size;  Rank _capa; //规模、容量
0008    Rank* _link;  T* _elem; //游标指针、数据区
0009    Rank _data, _free; //数据链表和空闲链表的起点
0010 public:
0011    CursorList(Rank c) { //容量
0012       _link = new Rank[_capa = c]; //游标指针向量
0013       _elem = new T[_capa = c];  memset(_elem, 0, c*sizeof(T)); //数据向量
0014       _data = _capa;  _size = 0; //数据链表初始为空
0015       _free = 0; //空闲链表由所有单元依次串接而成
0016       for (Rank i = 0; i+1 < _capa; i++) _link[i] = i+1;
0017       _link[_capa-1] = _capa;
0018    }
0019    ~CursorList() { delete[] _link;  delete[] _elem; } //释放内部空间
0020    Rank size() const { return _size; } //规模
0021    bool empty() const { return !_size; } //判空
0022    Rank find(const T& e) const { //查找
0023       Rank i = _data; //从数据链表起点出发
0024       while ((_capa != i) && (e != _elem[i])) i = _link[i]; //依次比对
0025       return i;
0026    }
0027    Rank insert(const T& e) { //插入元素
0028       assert(_free < _capa);
0029       if (_size >= _capa) return _capa; //full& insert fails
0030       Rank k = _free;  _free = _link[k];  _elem[k] = e;
0031       _link[k] = _data;  _data = k;
0032       _size++;  return k;
0033    }
0034    Rank remove(Rank k) { //删除秩为k的元素
0035       assert(k < _capa); //此前经查找并确认k合法
0036       if (_data == k) { //若[k]为首节点
0037          _data = _link[k];
0038       } else { //否则
0039          Rank i = _data;  while (k != _link[i]) i = _link[i]; //find i = pred(k)
0040          _link[i] = _link[k];
0041       }
0042       _link[k] = _free;  _free = k;  _elem[k] = 0;
0043       _size--;  return k;
0044    }
0045    void print() {
0046       printf("size = %4d : ", _size);
0047       for (Rank i = _data; _capa != i; i = _link[i])
0048       {  printf("   ");  UniPrint::p(_elem[i]); }
0049       printf("\n");
0050       printf("\tRank: ");  for (Rank i = 0; i < _capa; i++) UniPrint::p(i);  printf("\n");
0051       printf("\tLink: ");  for (Rank i = 0; i < _capa; i++) UniPrint::p(_link[i]);  printf("\n");
0052       printf("\tFree: ");  for (Rank i = _free; i < _capa; i = _link[i]) UniPrint::p(i); printf("\n");
0053       printf("\tData: ");  for (Rank i = _data; i < _capa; i = _link[i]) UniPrint::p(i); printf("\n");
0054       printf("\n\n");
0055    }
0056 };