#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