コンテナlistの実装:プログラミング原論(ステパノフ)の補助資料

今回はlistのテストを書きました。全ソースコードはプログラミング原論(ステパノフ)のこのページにあります。

#include<cassert>
#include<cstddef>
#include<new>
#include<cstdlib>
#define pointer(T) T*
template<typename I, typename O>
void copy_step(I& f_i, O& f_o) {
  sink(f_o) = source(f_i);
  f_o = successor(f_o);
  f_i = successor(f_i);
}
template<typename I, typename O>
void copy(I f_i, I l_i, O f_o) {
  while(f_i != l_i) copy_step(f_i, f_o);
}
template<typename T>
T successor(const T& x) {
  return x + T(1);
}
template<typename T>
pointer(T) successor(pointer(T) x) {
  return x + ptrdiff_t(1);
}
template<typename T>
T& sink(pointer(T) x) {
  return *x;
}
template<typename T>
const T& source(const T& x) {
  return x;
}
void test_copy_from_int(void) {
  typedef int Z;
  Z a[6];
  Z* l = a;
  copy(Z(0), Z(6), l);
  int i;
  for(i = 0; i < 6; i++)
    assert(a[i] == i);
}
template<typename I, typename U>
I insert(I p, const U& y) {
  construct(sink(p), y);
  p = successor(p);
  return p;
}
template<typename T, typename U>
void construct(T& p, const U& initializer) {
  new (&p) T(initializer);
}
void test_insert(void) {
  typedef int Z;
  Z a[6];
  Z* l = a;
  int i;
  for(i = 0; i < 6; i++)
    l = insert(l, i);
  for(i = 0; i < 6; i++)
    assert(a[i] == i);
}
template<typename T>
struct value_type {
  typedef T type;
};
#define ValueType(T) typename value_type<T>::type
template<typename T>
struct value_type<pointer(T)>{
  typedef T type;
};
template<typename P>
struct insert_iterator{
  P p;
  insert_iterator(const P& p): p(p) {}
  void operator=(const ValueType(P)& x) {
    p = insert(p, x);
  }
};
template<typename T>
insert_iterator<T> successor(const insert_iterator<T>& x) {
  return x;
}
template<typename T>
insert_iterator<T>& sink(insert_iterator<T>& x) {
  return x;
}
void test_insert_iterator(void) {
  typedef int Z;
  Z a[6];
  copy(Z(0), Z(6), insert_iterator<Z*>(a));
  int i;
  for(i = 0; i < 6; i++)
    assert(a[i] == i);
}
template<typename T>
const T& source(pointer(T) x) {
  return *x;
}
template<typename T>
struct distance_type;
#define DistanceType(T) typename distance_type<T>::type
template<typename T>
struct distance_type<pointer(T)> {
  typedef ptrdiff_t type;
};
template<typename P, typename W>
void insert_range(P p, const W& w) {
  copy(begin(w), end(w), insert_iterator<P>(p));
}
template<typename I>
struct counted_range{
  typedef DistanceType(I) N;
  I f;
  N n;
  counted_range(I f, N n): f(f), n(n) {}
};
template<typename I>
I begin(const counted_range<I>& x) {
  return x.f;
}
template<typename I>
I end(const counted_range<I>& x) {
  return x.f + x.n;
}
void test_insert_range(void) {
  typedef int Z;
  Z a[] = {0,1,2,3,4,5};
  Z b[6];
  insert_range(&b[0], counted_range<Z*>(a, sizeof(a)/sizeof(a[0])));
  int i;
  for(i = 0; i < 6; i++)
    assert(b[i] == i);
}
template<typename T>
struct list_node {
  T value;
  pointer(list_node) forward_link; 
  pointer(list_node) backward_link;
};
template<typename T>
struct list_iterator {
  pointer(list_node<T>) p;
  list_iterator():p(NULL) {}
  list_iterator(pointer(list_node<T>) p):p(p) {}
};
template<typename T>
struct value_type< list_iterator<T> > {
  typedef T type;
};
template<typename T>
bool operator!=(const T& x, const T& y) {
  return !(x==y);
}
template<typename T>
bool operator==(const list_iterator<T>& x, const list_iterator<T>& y) {
  return x.p == y.p;
}
template<typename T>
T& sink(list_iterator<T> i) {
  sink(i.p).value;
}
template<typename T>
const T& source(const list_iterator<T> i) {
  return source(i.p).value;
}
template<typename T>
list_iterator<T> successor(const list_iterator<T>& i) {
  return list_iterator<T>(source(i.p).forward_link);
}
template<typename T>
list_iterator<T> predecessor(const list_iterator<T>& i) {
  return list_iterator<T>(source(i.p).backward_link);
}
template<typename I>
struct bidirectional_linker {
  void operator()(I x, I y) {
    sink(x.p).forward_link = y.p;
    sink(y.p).backward_link = x.p;
  }
};
template<typename I>
void set_link_bidirectional(I x, I y) {
  bidirectional_linker<I>()(x, y);
}
template<typename T, typename U>
list_iterator<T> insert(list_iterator<T> j, const U& u) {
  list_iterator<T> i((list_node<T>*)malloc(sizeof(list_node<T>)));
  construct(sink(i), u);
  set_link_bidirectional(predecessor(j), i);
  set_link_bidirectional(i, j);
  return i;
}
template<typename I>
struct iterator_type;
#define IteratorType(I) typename iterator_type<I>::type
template<typename T>
struct list {
  list_iterator<T> dummy;
  list():dummy((list_node<T>*)malloc(sizeof(list_node<T>))){
    set_link_bidirectional(dummy, dummy);
  }
  template<typename W>
  list(const W& w);
  ~list();
};
template<typename T>
struct iterator_type< list<T> > {
  typedef list_iterator<T> type;
};
template<typename T>
IteratorType(list<T>) begin(const list<T>& x) {
  return successor(x.dummy);
}
template<typename T>
IteratorType(list<T>) end(const list<T>& x) {
  return x.dummy;
}
void test_list_insert_range(void) {
  typedef int Z;
  Z a[] = {5,4,3,2,1,0};
  list<Z> la;
  insert_range(begin(la), (counted_range<Z*>(a, sizeof(a)/sizeof(a[0]))));
  list_iterator<Z> f = begin(la);
  list_iterator<Z> l = end(la);
  int i = 0;
  while(f != l) {
    assert(i == source(f));
    f = successor(f);
    i = successor(i);
  }
  assert(6 == i);
}
template<typename T>
void destroy(T& x) {
  x.~T();
}
template<typename T>
void erase(list_iterator<T> i) {
  set_link_bidirectional(predecessor(i), successor(i));
  destroy(sink(i));
  free(i.p);
}
template<typename S>
bool empty(const S& x) {
  return begin(x) == end(x);
}
template<typename T>
void erase_all(list<T>& x) {
  while(!empty(x)) erase(predecessor(end(x)));
}
template<typename T>
list<T>::~list() { 
    erase_all(sink(this));
    free(dummy.p);
}

void test_list_erase(void) {
  typedef int Z;
  Z a[] = {5,4,3,2,1,0};
  list<Z> la;
  insert_range(begin(la), (counted_range<Z*>(a, sizeof(a)/sizeof(a[0]))));
  erase(begin(la));
  erase(begin(la));
  list_iterator<Z> f = begin(la);
  list_iterator<Z> l = end(la);
  int i = 2;
  while(f != l) {
    assert(i == source(f));
    f = successor(f);
    i = successor(i);
  }
  assert(6 == i);
}
template<typename T>
struct underlying_type {
  typedef T type;
};
#define UnderlyingType(T) typename underlying_type<T>::type
template<typename T>
UnderlyingType(T)& underlying_ref(T& x) {
  return reinterpret_cast<UnderlyingType(T)&>(x);
}
template<typename T>
void swap(T& x, T& y) {
  UnderlyingType(T) tmp = underlying_ref(x);
  underlying_ref(x) = underlying_ref(y);
  underlying_ref(y) = tmp;
}
template<typename S>
struct after{
  typedef IteratorType(S) I;
  pointer(S) s;
  I i;
  after(S& s, I i): s(&s), i(i) {}
};
template<typename T>
struct value_type< list<T> > {
  typedef T type;
};
template<typename S>
struct value_type< after<S> > {
  typedef ValueType(S) type;
};
template<typename S>
IteratorType(S) current(after<S>& x) {
  return x.i;
}
template<typename T>
T& deref(pointer(T) x) {
  return *x;
}
template<typename S>
S& base(after<S>& x) {
  return deref(x.s);
}
template<typename S, typename U>
after<S> insert(after<S>& x, const U& u) {
  return after<S>(base(x), insert(successor(current(x)), u));
}
template<typename T>
void construct(T& p) {
  new (&p) T();
}
template<typename T>
struct underlying_type< list<T> >{
  typedef list_iterator<T> type;
};
template<typename S, typename W>
void dynamic_sequence_construction(S& s, const W& w) {
  construct(s);
  S tmp;
  insert_range(after<S>(tmp, end(tmp)), w);
  swap(s, tmp);
}
template<typename T>
template<typename W>
list<T>::list(const W& w) {
    dynamic_sequence_construction(sink(this), w);
}
void test_list_construct(void) {
  typedef int Z;
  Z a[] = {0,1,2,3,4,5};
  list<Z> la(counted_range<Z*>(a, sizeof(a)/sizeof(a[0])));
  list_iterator<Z> f = begin(la);
  list_iterator<Z> l = end(la);
  int i = 0;
  while(f != l) {
    assert(i == source(i));
    f = successor(f);
    i = successor(i);
  }
  assert(6 == i);
}
int main(void) {
  test_copy_from_int();
  test_insert();
  test_insert_iterator();
  test_insert_range();
  test_list_insert_range();
  test_list_erase();
  test_list_construct();
  return 0;
}