#ifndef _XLIST_H_
#define _XLIST_H_
#include <stdio>
#include <stdlib>
//==========================================
// リスト型テンプレート
//==========================================
// 連結アイテム・クラス
template <class T> class LIST_ITEM{
public:
T t; // ←アイテム本体
LIST_ITEM *next, *before; // ノード
LIST_ITEM(){ next=before=NULL; } // コンストラクタ
};
//==========================================
// XLIST 拡張リスト
//==========================================
template <class T> class XLIST {
private:
// メンバ変数
LIST_ITEM<T> *head, *tail;
LIST_ITEM<T> *last_use;
int last_use_id;
int item_length;
public :
XLIST(); // コンストラクタ
~XLIST(); // デストラクタ
push(T t); // アイテム追加
push(T t, int n); // アイテム追加
pop(int n=-1); // 第n番目のアイテム削除
val_pop(T t); // tの値と同じアイテムの削除
// ランダムアクセス
LIST_ITEM<T>* get_ptr_abs(int n);
LIST_ITEM<T>* get_ptr_rel(LIST_ITEM<T>* pitem, int n);
virtual LIST_ITEM<T>* get_ptr(int n);
T &operator [](int n);
T &last();
del_all();
init();
set_default(T &t);
size(); // アイテム数を返す
resize(int n);
swap(int n1, int n2){
LIST_ITEM<T> *p
T tmp_t=*get_ptr(n1);
*get_ptr(n1)=*get_ptr(n2);
*get_ptr(n2)=tmp_t;
return 0;
};
roll(int n1, int n2);
};
// コンストラクタ
template <class T> XLIST<T>::XLIST(){ init(); }
// デストラクタ
template <class T> XLIST<T>::~XLIST(){ del_all(); delete head; }
// 初期化
template <class T> XLIST<T>::init(){
head = new LIST_ITEM<T>;
last_use = tail = head;
last_use_id = item_length= 0;
return 0;
}
// アイテム数
template <class T> XLIST<T>::size(){
return item_length;
}
// アイテム数変更
template <class T> XLIST<T>::resize(int n){
if (n<0) n=0;
int i, add_size = n - item_length;
if (!add_size){
return item_length;
}
else if (add_size>0){
T t;
for(i=0;i<add_size;i++) push(t);
return add_size;
}
else if (add_size<0){
add_size=-add_size;
for(i=0;i<add_size;i++) pop();
return -add_size;
}
return item_length;
}
// アクセスエラー時の返り値 設定
template <class T> XLIST<T>::set_default(T &t){ head->t = t; return 0; }
// 全破棄
template <class T> XLIST<T>::del_all(){
int i, del_len=size()+1;
for(i=0;i<del_len;i++) pop();
return 0;
}
// ====== ランダムアクセス =====================================================
// 演算子 []
template <class T> T& XLIST<T>::operator [](int n){
LIST_ITEM<T> *p=get_ptr(n);
return p->t;
}
// 演算子 []
template <class T> T& XLIST<T>::last(){
return tail->t;
}
// 相対パスから
template <class T> LIST_ITEM<T>* XLIST<T>::get_ptr_rel(LIST_ITEM<T>* pitem, int n){
if (n>0){
for(int i=0;i<n;i++) if (pitem->next) pitem=pitem->next;
} else if (n<0){
n=-n;
for(int i=0;i<n;i++) if (pitem->before) pitem=pitem->before;
}
// printf("rel ");
return pitem;
};
// 絶対パスから
template <class T> LIST_ITEM<T>* XLIST<T>::get_ptr_abs(int n){
LIST_ITEM<T> *pitem=head->next;
for(int i=0;i<n;i++) if (pitem->next) pitem=pitem->next;
return pitem;
}
// ランダムアクセス総括関数
template <class T> LIST_ITEM<T>* XLIST<T>::get_ptr(int n){
LIST_ITEM<T> *pitem;
int i = n-last_use_id, len=size();
if (n>=len || n<0) return head;
if (n > abs(i)){
if ((len-n-1) > abs(i)) pitem = get_ptr_rel(last_use, i);
else pitem = get_ptr_rel(tail, n-len+1);
}
else pitem = get_ptr_abs(n); // 先頭からノード検索
if (pitem) { // 最後にアクセスしたアイテム更新
last_use =pitem;
last_use_id =n;
}
return pitem;
}
// アイテム移動 (第n1番目のアイテムを第n2番目に移動)
template <class T> XLIST<T>::roll(int n1, int n2){
if (item_length<=0) return 0; // LISTアイテムなし
LIST_ITEM<T> *bef, *nex, *org, *dst;
if (n1<0 || n1>=item_length) org=tail; // n1 が範囲外なら末尾を削除
else org = get_ptr(n1);
if (n2<0 || n2>=item_length) dst=tail; // n2 が範囲外なら末尾を削除
else dst = get_ptr(n2);
if (!org || !dst || org==head || dst==head || org==dst) return 0;
// ターゲット・アイテムを一時リストからはずす
bef=org->before;
nex=org->next;
if (bef) bef->next=nex;
if (nex) nex->before=bef;
// 一時リストからはずしていたターゲット・アイテムを目的位置にセット
bef=dst->before; bef->next=org; // ■-□-□ ■の設定
dst->before=org; // □-□-■ ■の設定
org->next=dst; // □-■-□ ■の設定
org->before=bef; // □-■-□ ■の設定
tail = last_use =get_ptr_abs(item_length);
last_use_id =item_length-1;
return item_length;
}
// アイテム追加
template <class T> XLIST<T>::push(T t){
LIST_ITEM<T> *old_tail=tail; // 更新前の末尾ポインタ保持
tail->next = new LIST_ITEM<T>; // 末尾アイテムのnextに新リスト作成
tail=tail->next; // 新リストにtailポインタを合わせる
tail->t = t; // 新リストにアイテム代入
tail->before=old_tail;
item_length++;
return item_length;
};
// アイテム追加 (挿入型)
template <class T> XLIST<T>::push(T t, int n){
if (n>=item_length) return push(t);
if (n<=0) n=0;
LIST_ITEM<T> *bef_pitem, *nex_pitem, *pitem;
bef_pitem=get_ptr(n-1); // 挿入先の前ポインタ取得(確実に存在)
nex_pitem=bef_pitem->next; // 挿入先の次ポインタ保持(NULLのときもあり)
pitem = new LIST_ITEM<T>; // 末尾アイテムのnextに新リスト作成
pitem->t = t; // 新リストにアイテム代入
pitem->before=bef_pitem;
pitem->next=nex_pitem;
bef_pitem->next = pitem;
if (nex_pitem) nex_pitem->before = pitem;
item_length++;
last_use =pitem;
last_use_id =n;
return item_length;
};
// アイテム削除 (第n番目のアイテム削除)
template <class T> XLIST<T>::pop(int n){
if (item_length<=0) return 0; // LISTアイテムなし
LIST_ITEM<T> *del, *bef, *nex;
if (n<0 || n>=item_length) del=tail; // n が範囲外なら末尾を削除
else del = get_ptr(n);
if (del==head) return 0;
bef = del->before; // 削除アイテムの前のノードGET
nex = del->next; // 削除アイテムの次のノードGET
bef->next=nex; // 前のノードは確実に存在するのでじかに更新
if (nex) {
nex->before=bef; // 削除アイテムが末尾なときnexはNULLなので回避
}
else tail=bef;
delete del;
item_length--;
last_use =bef; // 最後にアクセスしたアイテム更新（前のノードに代入）
last_use_id =n-1;
return item_length;
}
// tの値と同じアイテムの削除
template <class T> XLIST<T>::val_pop(T t){
LIST_ITEM<T> *p;
for(int i=0;i<item_length;i++){
p=get_ptr(i);
if (p->t==t) {
pop(i);
return 1;
}
}
return 0;
};
#endif // _XLIST_H_
|
