コンテナ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; }