|
|
Array_set -- Array implementation of Set(3C++)
The following code implements most of the functionality class Set and class Setiter as specified in Set(3C++). It has not been fully optimized (for example, to avoid use of the copy constructor in functions returning Array_sets).
#include <assert.h> #include <Block.h> #include <Array_alg.h> #include <stream.h> template <class T> static void compare(ptrdiff_t n,T* p){ assert(n==0 || *p >= *(p-1)); } template <class T> class Array_setiter; template <class T> class Array_set{ friend class Array_setiter<T>; private: Block<T> b; unsigned n; public: void check()const{ /* ** Check the representation invariant: ** ** n<=b.size() ** b is sorted ** b contains no repetitions */ assert(n<=b.size()); generate(compare,&b[0],&b[n]); assert(unique(&b[0],&b[n])==&b[n]); } /* Constructors, destructor */ Array_set():b(10),n(0){ } Array_set(const T& t0):b(10),n(0){ if(set_insert(t0,&b[0],&b[0]))n++; } Array_set(const T& t0,const T& t1):b(10),n(0){ if(set_insert(t0,&b[0],&b[0]))n++; if(set_insert(t1,&b[0],&b[n]))n++; } Array_set(const T& t0,const T& t1,const T& t2) :b(10),n(0){ if(set_insert(t0,&b[0],&b[0]))n++; if(set_insert(t1,&b[0],&b[n]))n++; if(set_insert(t2,&b[0],&b[n]))n++; } Array_set(const T& t0,const T& t1,const T& t2,const T&t3):b(10),n(0){ if(set_insert(t0,&b[0],&b[0]))n++; if(set_insert(t1,&b[0],&b[n]))n++; if(set_insert(t2,&b[0],&b[n]))n++; if(set_insert(t3,&b[0],&b[n]))n++; } Array_set(const Array_set(T)& s):b(s.b),n(s.n){ } ~Array_set(T)(){ } /* Size */ int size()const{ return n; } int size_unique()const{ return size(); } operator const void*()const{ return (n>0 ? this : 0); } /* Assignment */ Array_set<T>& operator=(const Array_set<T>& s){ b = s.b; n = s.n; return *this; } /* Relations */ int operator==(const Array_set<T>& s)const{ return ( n==s.n && mismatch(&b[0], &b[n], &(s.b[0]), &(s.b[s.n]))==0 ); } int operator!=(const Array_set<T>& s)const{ return !(*this==s); } int operator<=(const Array_set<T>& s)const{ int min = n<s.n?n:s.n; Block<T> temp(min); T* p = set_inter(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]),&temp[0]); int result = (p-&temp[0] == n); return result; } int operator<(const Array_set<T>& s)const{ return (*this <= s && n < s.n); } int operator>=(const Array_set<T>& s)const{ return s <= *this; } int operator>(const Array_set<T>& s)const{ return s < *this; } /* Membership */ const T* contains(const T& t)const{ return bin_search(t,&b[0],&b[n]); } unsigned count(const T& t)const{ return bin_search(t,&b[0],&b[n])!=0; } /* Insert and remove */ const T* insert(const T& t,int count=1){ T* result=0; if(count>0){ b.reserve(n); result=set_insert(t,&b[0],&b[n]); if(result)n++; } return result; } unsigned remove(const T& t,int count=1){ unsigned result=0; if(count>0 && set_remove(t,&b[0],&b[n])<&b[n]){ n--; result=1; } return result; } unsigned remove_all(const T& t){ return remove(t,1); } unsigned remove_all(){ unsigned result = n; n = 0; return result; } /* Select an arbitrary element */ const T* select()const{ return random(&b[0],&b[n]); } /* Array_set algebra */ Array_set<T> operator|(const Array_set<T>& s)const{ if(b==s.b)return *this; Array_set<T> result; result.b.reserve(n + s.n ); result.n = set_union(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); return result; } Array_set<T> operator-(const Array_set<T>& s)const{ if(b==s.b)return Array_set<T>(); Array_set<T> result; result.b.reserve(n); result.n = set_diff(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); return result; } Array_set<T> operator&(const Array_set<T>& s)const{ if(b==s.b)return *this; Array_set<T> result; result.b.reserve(n + s.n ); result.n = set_inter(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); return result; } Array_set<T> operator[hyphen](const Array_set<T>& s)const{ if(b==s.b)return Array_set<T>(); Array_set<T> result; result.b.reserve(n + s.n ); result.n = set_sdiff(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); return result; } /* Assignment versions of the above */ Array_set<T> operator|=(const Array_set<T>& s){ Array_set<T> result; result.b.reserve(n + s.n ); result.n = set_union(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); *this = result; return *this; } Array_set<T> operator-=(const Array_set<T>& s){ if(b==s.b)return Array_set<T>(); Array_set<T> result; result.b.reserve(n); result.n = set_diff(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); *this = result; return *this; } Array_set<T> operator&=(const Array_set<T>& s){ if(b==s.b)return *this; Array_set<T> result; result.b.reserve(n + s.n ); result.n = set_inter(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); *this = result; return *this; } Array_set<T> operator[hyphen]=(const Array_set<T>& s){ if(b==s.b)return Array_set<T>(); Array_set<T> result; result.b.reserve(n + s.n ); result.n = set_sdiff(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]), &(result.b[0])) - &(result.b[0]); *this = result; return *this; } }; /* Array_set iterators */ template <class T> class Array_setiter{ const Array_set<T>* sp; unsigned i; public: Array_setiter(const Array_set<T>& s):sp(&s),i(0){ } const T* next(){ if(i<sp->n){ return ((Array_set<T>*)sp)->b+i++; }else{ return 0; } } int next(const T*& t){ if(i<sp->n){ t = ((Array_set<T>*)sp)->b+i++; }else{ t = 0; } return t!=0; } void reset(){ i=0; } }; template <class T> ostream& operator<<(ostream& os,const Array_set<T>& s){ os << "{"; Array_setiter<T> it(s); const T* tp; int first=1; while( tp = it.next() ){ if( first ){ first=0; }else{ os << ','; } os << (T)(*tp); } os << '}'; return os; }