DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 
No More Array Errors (Part II) - Array_alg(C++)

Example

Array_set -- Array implementation of Set(C++)

The following code implements most of the functionality class Set and class Setiter as specified in Set(C++). 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;
   }

Previous topic: Conclusion

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005