Aritalab:Lecture/Programming/Cpp/LinkedList

ヘッダーファイル　list.hh

#ifndef LIST_HH
#define LIST_HH

class list_node;
typedef list_node* lnode;

class list_node {
private:
  list_node(const list_node&);
  list_node& operator=(const list_node&);
public:
  void* key;
  lnode list_pred;
  lnode list_succ;
  list_node(void* x=0x0) : key(x), list_pred(0), list_succ(0) {}
  ~list_node() {}
};

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() {}

  lnode pop_front();
  void push  (lnode);
  void append(lnode);
  int length() const;

  virtual void* inf(lnode x) { return x->key; }

  int size()   const { return list_size; }
  bool empty() const { return (list_size == 0); }
};

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() { clear(); }
  list(const list& x) { lnode_list::operator=(x); }
  list& operator=(const list& x)
  { lnode_list::operator=(x); return *this; }

  void clear() { lnode_list::clear_all(); }
  
  void push(const T&)
    { lnode v = new list_node(copy_object(x)); push( v ); }
  void pop()
    { lnode x = lnode_list::pop_front(); CLEAR_OBJ(T,x->key); delete x; }
  const T& peek()          const { return inf(list_head); }

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

ソースファイル list.cc

#include "list.hh"

static inline void swap(lnode& x, lnode& y)
{ lnode tmp = x; x = y; y = tmp; }
static inline void swap(GenPtr& x, GenPtr& y)
{ GenPtr tmp = x; x = y; y = tmp; }

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

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;
}

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

void lnode_list::push(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;
}