diff options
Diffstat (limited to 'src/AMRPlus/flexset.h')
| -rw-r--r-- | src/AMRPlus/flexset.h | 209 |
1 files changed, 209 insertions, 0 deletions
diff --git a/src/AMRPlus/flexset.h b/src/AMRPlus/flexset.h new file mode 100644 index 0000000..d2e486d --- /dev/null +++ b/src/AMRPlus/flexset.h @@ -0,0 +1,209 @@ +#ifndef FLEX_SET_H +#define FLEX_SET_H +#include "flexarrays.h" + +/* + * A flexset is a set datastructure. Fast insertion/deletion (O(logN)), + * and basic set operations (union, difference, etc...). This set is + * not completely generalized - you must either use native (non-pointer) + * types, or use a class with operators < and == implemented + * (i.e: inline int operator<(const X&) const{...};) This is what allows + * log time access, and linear time set operations. + * Routines: + * Constructor/Destructor/copy constructor... + * + * Information: + * int getSize() - returns size of set. + * int find(X& x) - return position of x, or -1 if x isn't in the set + * int contains(X& x) - boolean version of above + * int contains(flexset &s) - returns 1 if s is a subset + * + * Manipulation: + * insert(X& x) - add x to the set. If x is already in the set + * (technically, x==e for some e in the set) nothing happens. + * remove(X& x) - remove x (only if x is inside, of course); + * X& [int idx] - access element by index. Index will change with insertion + * buldSubset(flexset<X> &x, int (* test)(X& y)) - creates a subset consisting + * of all elements in the set for which 'test' returns true. + * + * Operations: + * [all of form: set<oper>(X& A, X& B, X& result){ result= A <oper> B}] + * setunion(A=AUB, or C=AUB), setintersection, setdifference, setsymmetricdifference + * setdifferences (returns A-B and B-A in one go) + * NOTE: The result of intersection or difference will consist only + * of items taken from A. (Important if you are comparing sets with + * similar keys and dissimilar data + */ + +/* +class flexset; +template <class X> setiter{ + public: + setiter(flexset *nset){itsset=nset; idx=(nset->empty())?-1:0;} + + operator++(){idx++; if (idx>itsset->getSize()-1) idx=-1;} + operator--(){idx--; if (idx<0) idx=-1;} + int ok(){return idx!=-1;} + + X &operator*(){if (idx==-1) return itsset[0]; return itsset[idx];} + + private: + flexset *itsset; + int idx; +} +*/ + + +template <class X> +class flexset : protected flexarray<X>{ + public: + flexset(): flexarray<X>(){}; + flexset(const flexset<X> &src): flexarray<X>(src){}; + ~flexset(){}; + //by all accounts, this should inherit flexarray operator= + + int getSize() const{return flexarray<X>::getSize();} + int findpos(const X &elt, int start=0, int end=-1) const{ + if (start<0) start=0; + if (end==-1) end=getLength()-1; + + int a=start, b=end, e; + if (empty()) return 0; + if (elt<(*this)(a)) return a; + if (elt==(*this)(a)) return a; //don't depend on <= being implemented + if (elt==(*this)(b)) return b; + if (!(elt<(*this)(b))) return b+1; //given above line, equiv to elt>data[b] + + if ((a+b)&1) e=(a+b+1)/2; //e odd + else e=(a+b)/2; + while ((b-a>1)){ + if (elt==(*this)(e)) return e; + + if (elt<(*this)(e)) b=e; + else a=e; + if ((a+b)&1) e=(a+b+1)/2; //e odd + else e=(a+b)/2; + } + if (elt<(*this)(e)) return e; + if (elt==(*this)(e)) return e; + else return e+1; + + } +//If elt is in the set, return its index, otherwise return -1 + int find(const X &elt, int start=0, int end=-1) const{ + if (empty()) return -1; + int result=findpos(elt, start, end); + if (result<getSize() && elt==*getDataConst(result)) return result; + return -1; + } + + int contains(const X &elt) const{return (find(elt)!=-1);} + + int contains(const flexset<X> &iset) const{ + if (iset.empty()) return 1; //Empty set is in everything! + int a=find(iset(0)); + if (a<0)return 0; + for (int ii=1;ii<iset.getSize();ii++){ + if ((a=find(iset(ii), a))<0) return 0; + } + + return 1; + } + + + + void clear(){ + flexarray<X>::clear(); + } + + int empty() const {return flexarray<X>::empty();} + + void buildSubset(flexset<X> &A, int (* test)(const X&)){ + A.clear(); + for (int ii=0;ii<getSize();ii++) + if (test((*this)[ii])) A.append((*this)[ii]); + } + + + +//Insert elt into the set. If elt is already in, do nothing + void insert(const X &elt){ + int pos=findpos(elt); + if (pos<getSize()) + if (elt==*getData(pos)) return; + insertElement(elt, pos); + }; + + void remove(const X &elt){ + if (empty()) return; + int pos=findpos(elt); + if (pos<getSize()) + if (elt==*getData(pos)) removeElements(pos, 1); + } + + //Indexed removal preserves set ordering, and it's O(1), + //so it is safe to include + void indexremove(int idx){ + if (empty()||idx<0||idx>=getSize()) return; + removeElements(idx, 1); + } + + void append(const X &elt){ + if (empty()) { + insertElement(elt, 0); + return; + } + X *tmp=&(*this)[getSize()-1]; + if ((*tmp)<elt) insertElement(elt, -1); + else if (!((*tmp)==elt)) cout<<"BAD APPEND!"<<endl; + } + void prepend(const X &elt){ + if (empty()) { + insertElement(elt, 0); + return; + } + X *tmp=&(*this)[getSize()-1]; + if (elt<(*tmp)) insertElement(elt, 0); + else if (!((*tmp)==elt)) cout<<"BAD PREPEND!"<<endl; + } + + X &operator[](int idx) const{return *getData(idx);} + const X &operator()(int idx)const {return *getDataConst(idx);} + +friend +void setunion(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); +friend +void setintersection(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); +friend +void setsymmetricdifference(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); +friend +void setdifference(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); +friend +void setdifferences(const flexset<X> &A, const flexset<X> &B,flexset<X> &AMB,flexset<X> &BMA); +friend +void setconvert(flexset<X> &A, const flexset<X> &B); +}; + +template <class X> +void setunion(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); + + +template <class X> +void setunion(flexset<X> &A, const flexset<X> &B); + +template <class X> +void setintersection(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); + + +template <class X> +void setsymmetricdifference(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); + +template <class X> +void setdifference(const flexset<X> &A, const flexset<X> &B,flexset<X> &result); + +template <class X> +void setdifferences(const flexset<X> &A, const flexset<X> &B,flexset<X> &AMB,flexset<X> &BMA); + +template <class X> +void setconvert(flexset<X> &A, const flexset<X> &B); +#endif |