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