Aritalab:Lecture/Programming/Cpp/LinkedList

Latest revision as of 12:17, 7 October 2010

ヘッダーファイル　list.hh

#ifndef LIST_HH
#define LIST_HH

class list_node;
typedef list_node* lnode;

// list_nodeは実際の値を入れるコンテナ
class list_node {
private:
  list_node(const list_node&);           //外部利用を防ぐためprivate指定
  list_node& operator=(const list_node&);//外部利用を防ぐためprivate指定
public:
  void* key;
  lnode list_pred;
  lnode list_succ;
  list_node(void* x=0x0) : key(x), list_pred(0), list_succ(0) {}
  ~list_node() {}
};

// lnode_listクラスはlist_nodeコンテナをpush/popする。コンテナ中身の型は感知しない。
class lnode_list {
protected:
  lnode list_head;
  lnode list_tail;
  int   list_size;

  lnode_list() : list_head(0), list_tail(0), list_size(0) {}
  lnode_list(const lnode_list&);
  lnode_list& operator=(const lnode_list&);  
  virtual ~lnode_list() {}
  virtual void* copy_key(void*& x) const{} // listクラスで上書きする
  virtual void clear_key(void*& x) const{} // listクラスで上書きする
  virtual lnode pred(lnode e) const { return (e ? e->list_pred : 0); }
  virtual lnode succ(lnode e) const { return (e ? e->list_succ : 0); }

  lnode pop();
  void push  (lnode);
  void append(lnode);
  void clear();

  virtual void* inf(lnode x) { return x->key; }
  int size()   const { return list_size; }
  bool empty() const { return (list_size == 0); }
};

//listクラスはユーザが与える型Tを取り扱う。実際のリスト操作はlnode_listに任せる。
template<class T>
class list: public lnode_list {
private:
  void*  copy_key(void*& x) const { return (void*) new T(x); }
  void  clear_key(void*& x) const { delete x; }
public:
  list()  {}
  ~list() { lnode_list::clear(); }
  list(const list& x) { lnode_list::operator=(x); }
  list& operator=(const list& x)
  { lnode_list::operator=(x); return *this; }
 
  void push(const T&)
    { lnode v = new list_node(copy_object(x)); push(v); }
  void pop()
    { lnode x = lnode_list::pop(); clear_key(x->key); delete x; }
  const T& peek()          const { return inf(list_head); }

  const T& inf(lnode x) const { return (T&)(x->key); } 
}  
#endif

ソースファイル list.cc

#include "list.hh"

lnode_list::lnode_list(const lnode_list& x)
{
  list_head = list_tail =0;
  list_size =0;
  for(lnode i = x.head(); i != 0; i = x.succ(i))
    append(new list_node( copy_key(i->key)));
}

lnode_list& lnode_list::operator=(const lnode_list& x)
{
  if ( &x == this ) return *this;
  clear_all();
  for(lnode i = x.head(); i != 0; i = x.succ(i))
    append( new list_node( copy_key(i->key) ) );
  return *this;
}

void lnode_list::clear()
{
  for(lnode x, y = list_head; x = y, y = succ(y), x != 0;)
    {
      clear_key(x->key);
      delete x;
    }
  list_head = list_tail =0;
  list_size =0;
}

lnode lnode_list::pop()
{
  lnode x = list_head;
  if (x)
    {
      list_head = x->list_succ;
      if (list_head)
	list_head->list_pred =0;
      else
	list_tail =0;
      x->list_succ =0;
      list_size--;
    }
  return x;
}

void lnode_list::push(lnode x)
{
  if (list_size++ > 0)
    list_head->list_pred = x;
  else
    list_tail = x;

  x->list_pred = 0;
  x->list_succ = list_head;  
  list_head = x;
}

void lnode_list::append(lnode x) 
{
  if (list_size++ > 0)
    list_tail->list_succ = x;
  else
    list_head = x;
  
  x->list_pred = list_tail;
  x->list_succ = 0;
  list_tail = x;
}