genarray.h

NMEA protocol for serial GPS communications

#ifndef GENARRAY_H
#define GENARRAY_H
#include <assert.h>
//#include <dlllib.h>

///////////////////////////// General Extensible Arrays ////////////////////////

#define ELEMENTSOF(x) (sizeof(x) / sizeof(x[0]))

////////////////////////// extensible array of simple types
//
// WARNING: these types MUST be copyable safely by doing bitwise copies.
// If not, you will come to great grief. That's why it is an array of
// simple types only! The array grows by the simple act of indexing it at
// a given position.
//
//
class simplelistbase{
public:
	void clear()								{mysize = 0;}
	void zap()								{ delete []mydata; mysize=maxsofar=0;}
	unsigned element_count()const						{ return mysize; }
	void	delete_last_element()						{if(mysize) --mysize; }
protected:
	simplelistbase(unsigned esize);
	~simplelistbase();
	unsigned mysize;
	unsigned maxsofar;
	unsigned ele_size;	// size of an element
	enum{growby = 20};
	char *mydata;
	void operator =(const simplelistbase &);
	simplelistbase(const simplelistbase &);
	void *operator[](unsigned entry)const;
	void *operator[](unsigned entry);
private:
	void initcopy(const simplelistbase &);
};

template <class T>class	simplelist : public simplelistbase{
public:
		simplelist();
		T &operator[](unsigned);
                const T &operator[](unsigned)const;
		void operator +=(T &tr)							{operator[](element_count()) = tr;}
private:
};

template <class T> simplelist<T>::simplelist() : simplelistbase(sizeof(T)){
}

template <class T> T & simplelist<T>::operator[](unsigned i){
	static T dummy;
	void *vp;
	return ((vp = simplelistbase::operator[](i)) == 0) ? dummy : (*(T*)vp);
}

template <class T> const T & simplelist<T>::operator[](unsigned i)const{
	static T dummy;
	void *vp;
	return ((vp = simplelistbase::operator[](i)) == 0) ? dummy : (*(T*)vp);
}

template <class T> class simpleset : simplelist<T>{
public:
	simplelist<T>::element_count;
	simplelist<T>::operator[];

	void operator +=(T &tr);

        int contains(T &tr);
};

template <class T> int simpleset<T>::contains(T &tr){
	for(unsigned u = 0; u < element_count(); u++)
		if(operator[](u) == tr)
			return 1;
        return 0;
}

template <class T> void simpleset<T>::operator +=(T &tr){
	if(!contains(tr))
        	simplelist<T>::operator +=(tr);
}

// Declares generic_ptr_array - an extensible array of ptr-to-void.
// Also, the templated list_of class which holds copies of whatever you
// specify. BEWARE - the fact that list-of deletes its own contents when
// destroyed means that all added entities need virtual destructors. This
// is often forgotten, but results in store leaks (if you are lucky) and
// obscure crashes if not. Since this class is so widely used, it is NOT
// implemented from simplelist (yet), for efficiency reasons


enum sortdirection{up,down};

class generic_ptr_array{
public:
	// Delete this element - if not the last one, shuffle all items
	// down, otherwise just decrement the counter.
	void *delete_this_element(int index);	// zap one entry

	void insert_before_element(int index, void *vp);	// make room

	void push(void *vp){insert_before_element(0, vp);}
	void *pop(){return delete_this_element(0);}

	generic_ptr_array();
	~generic_ptr_array();

	void operator += (void *);

	 // Return the nth pointer.
	 // The user should be careful about this - this is a way of getting
	 // references to things that could be zapped later.
	 // We return a referenc so that things like sorting in place
	 // are easy to implement. On the user's head be it ...
	void * operator [](int index);
	const void *operator[](int index)const;
	void *& element_ref(int index);

	const unsigned element_count()const			{ return slotsused; }

	void operator ~(){	// used to tell me that the slots are empty
		slotsused = 0;	// but I can hang on to the storage
	}
	// Free all storage.
	void zap();

	void delete_last_element(){	// zap the tail item
		if(slotsused > 0)
			elements[--slotsused] = 0;
	}

	void *last()const{		// return a pointer to the last item
		return slotsused ? elements[slotsused-1] : 0;
	}


protected:
        // If the members have a comparison operator, we can sort them;
	// as long as a compare function is provided
	void sort(sortdirection d, int (* compare)(const void *, const void *));
private:
	void **elements;
	unsigned slotsallocated, slotsused;
	generic_ptr_array(generic_ptr_array &);	// private - can't initialise
	void operator = (generic_ptr_array &);	// or assign them
};

inline generic_ptr_array::generic_ptr_array(){
	slotsallocated = slotsused = 0;
	elements = 0;
}

inline generic_ptr_array::~generic_ptr_array(){
	delete elements;
}

inline void generic_ptr_array::zap(){
	slotsused = slotsallocated = 0;
	delete elements;
	elements = 0;
}

// Pointer list
template <class TYPE> class list_of_ptr_to : private generic_ptr_array{
public:
	generic_ptr_array::element_count;
	generic_ptr_array::delete_last_element;
	generic_ptr_array::delete_this_element;
	void clear(){
		zap();
	}

	void operator +=(TYPE *p){
		generic_ptr_array::operator +=(p);
		  }

	void push(TYPE *p){
		generic_ptr_array::push(p);
	}

	void insert_before_element(int index, TYPE *p){
		generic_ptr_array::insert_before_element(index, p);
		  }

	TYPE *last_element()const{
		return (TYPE*)generic_ptr_array::last();
	}

	TYPE *pop(){
		return (TYPE*)generic_ptr_array::pop();
	}

	TYPE *  operator [](int i){
		return (TYPE*)generic_ptr_array::operator[](i);
	}

	const TYPE *  operator [](int i)const{
		return (const TYPE*)generic_ptr_array::operator[](i);
	}
};


// The list_of template. Other types of list are also useful, but this will
// do for now
template <class TYPE> class list_of : private generic_ptr_array{
public:
	generic_ptr_array::element_count;

	void operator +=(const TYPE &r);

	void push(TYPE &r){
		generic_ptr_array::push(new TYPE(r));
	}

	void insert_before_element(int index, TYPE &r);

	TYPE &last_element()const{
		return *(TYPE*)generic_ptr_array::last();
	}

	TYPE pop(){
		return *(TYPE*)generic_ptr_array::pop();
	}

	void delete_last_element();
	void delete_this_element(int i);

	void clear();			// delete all elements

	TYPE&  operator [](int i){
		return *(TYPE*)generic_ptr_array::operator[](i);
	}

	const TYPE&  operator [](int i)const{
		return *(const TYPE*)generic_ptr_array::operator[](i);
	}

	list_of<TYPE> & operator=(const list_of<TYPE>&);
	list_of<TYPE> & operator+=(const list_of<TYPE>&);

	virtual ~list_of();
	list_of(const list_of<TYPE>&);
        // Because there is a copy constructor, we have to provide one of these too.
	list_of()						{}
protected:
	generic_ptr_array::sort;
};

template <class TYPE> class sortable_list_of : public list_of<TYPE>{
public:
	// sortable_list_of();
	void sort(sortdirection d = up);
private:
	static int docompare(const void *lhs, const void *rhs);
};

// Here we out-of-line define the functions which generate much code
// for the lists, or those that I feel like making inline anyhow!
template <class TYPE>
int sortable_list_of<TYPE>::docompare(const void *lhs, const void *rhs){
	return *(TYPE *)lhs > *(TYPE *)rhs;
}

template <class TYPE>
inline void sortable_list_of<TYPE>::sort(sortdirection d){
	list_of<TYPE>::sort(d, docompare);
}

// template <class TYPE>
// sortable_list_of<TYPE>::sortable_list_of(){}

// template <class TYPE>
// list_of<TYPE>::list_of(){}

template <class TYPE>
list_of<TYPE> & list_of<TYPE>::operator =(const list_of<TYPE> &csr){
	if(this != &csr){
		clear();
		*this += csr;
	}
	return *this;
}

template <class TYPE>
list_of<TYPE> & list_of<TYPE>::operator +=(const list_of<TYPE> &csr){
	if(this != &csr){
		const unsigned n = csr.element_count();
		for(unsigned u = 0; u < n; u++)
			operator += (csr[u]);
	}
	return *this;
}

template <class TYPE>
void list_of<TYPE>::clear(){
	unsigned u = element_count();
	while(u--){
		// u now decremented
		delete_this_element(u);
	}
	generic_ptr_array::zap();
}

template <class TYPE>
list_of<TYPE>::~list_of(){clear();}

template <class TYPE>
list_of<TYPE>::list_of(const list_of<TYPE>&lor){
	unsigned lorec = lor.element_count();
	for(unsigned i = 0; i < lorec; i++)
		*this += lor[i];
}

template <class TYPE>
void list_of<TYPE>::operator+=(const TYPE &r){
	generic_ptr_array::operator+=(new TYPE(r));
}

template <class TYPE>
void list_of<TYPE>::insert_before_element(int index, TYPE &r){
	generic_ptr_array::insert_before_element(index, new TYPE(r));
}

template <class TYPE>
inline void list_of<TYPE>::delete_last_element(){
	delete_this_element(element_count()-1);
}

template <class TYPE>
void list_of<TYPE>::delete_this_element(int i){
	TYPE *tp = (TYPE *) generic_ptr_array::delete_this_element(i);
	if(tp) delete tp;
}

// Map (associative array) of copyable objects, where the keys have
// a defined == operator
template <class KEY, class VALUE> class mapiter;
template <class KEY, class VALUE> class map{
public:
	// Let's not have these as inline functions
	map();
	~map();
	// could also specify the copy constructor and assignment ops
	// as non-inline-defaults, but they are rarely used. We'll take
	// the hit of having the compiler generate them (it will quite
	// likely also do them out-of-line


	// isvalidkey: returns true or false as appropriate
	int	isvalidkey(const KEY &ckr)const;

	// If there is an entry with this key, there won't be after this!
        void	remove_entry(const KEY &ckr);

	// Using an invalid key results in creation of a VALUE object
	// via its default constructor and addition of said object
        // and key to the array
	VALUE&	operator[](const KEY &ckr);

	// The const version of operator[] cannot add an item if
	// the key is invalid. THAT IS A RUN-TIME ERROR, be warned
	const VALUE& operator[](const KEY &ckr)const;

        unsigned element_count()const				{ return keys.element_count();}

        // empty both arrays
        void clear();
private:
	list_of<KEY>	keys;
	list_of<VALUE>	values;
        friend mapiter<KEY, VALUE>;

	// pos returns the internal index of an element in the key
	// list, or 0xFFFF if not found. This limits the number of
        // elements to 0xfffe - not thought a big problem
        unsigned int pos(const KEY &ckr)const;
};

template<class KEY, class VALUE> class mapiter{
public:
	mapiter()					: mp(0){}
	mapiter(const map<KEY, VALUE> &mr)		: index(0), mp(&mr){}

	operator int()const				{ return mp && index < mp->keys.element_count();}
	void operator++()				{ index++;}
	void operator++(int)				{ index++;}

	mapiter&operator =(const map<KEY, VALUE>&mr)	{ index = 0; mp = &mr; return *this;}

	// Since this is really just an index, we permit
	void setindex(unsigned i)			{ index = i; }

	// You are in BIG TROUBLE if you call these and the iterator
	// is invalid - believe me!
	const KEY & key()				{ return mp->keys[index];}
	const VALUE & value()				{ return mp->values[index];}
private:
	unsigned index;
        const map<KEY, VALUE> *mp;
};

template<class KEY, class VALUE>map<KEY, VALUE>::map(){}
template<class KEY, class VALUE>map<KEY, VALUE>::~map(){}

template<class KEY, class VALUE>
void map<KEY, VALUE>::clear(){
	keys.clear();
	values.clear();
}

template<class KEY, class VALUE>
unsigned int map<KEY, VALUE>::pos(const KEY &ckr)const{
	unsigned const neles = keys.element_count();
	for(unsigned int ui = 0; ui < neles; ui++){
		if(keys[ui] == ckr)
			return ui;
        }
        return 0xffff;
}

template<class KEY, class VALUE>
int map<KEY, VALUE>::isvalidkey(const KEY &ckr)const{
	if(pos(ckr) != 0xffff)
		return 1;
        return 0;
}

template<class KEY, class VALUE>
void map<KEY, VALUE>::remove_entry(const KEY &ckr){
	unsigned const vpos = pos(ckr);
	if(vpos == 0xffff)
		return;
	values.delete_this_element(vpos);
        keys.delete_this_element(vpos);
}

template<class KEY, class VALUE>
VALUE& map<KEY, VALUE>::operator[](const KEY &ckr){
	unsigned int ui = pos(ckr);
	if(ui != 0xffff)
		return values[ui];
	// Not found - create and add an item
        VALUE v;
	values += v;
	keys += ckr;
	return values[values.element_count()-1];
}

template<class KEY, class VALUE>
const VALUE& map<KEY, VALUE>::operator[](const KEY &ckr)const{
	unsigned int ui = pos(ckr);

	// The slightly odd order of this code avoids having to do
	// wierd stuff when we handle the bad-key case
	if(ui == 0xffff)
		// Violated precondition: the key value was NOT preset
		assert("map::operator[](...)const - key not present" == 0);
	return values[ui];
}


#ifdef USELINKEDLISTS
////////////////////////////////////////////// Linked Lists /////////////////////////////////////////////
class linked_list_vpbase{
public:
	unsigned element_count()const{
		return neles;
        }

	linked_list_vpbase();
	~linked_list_vpbase(){
		clear();
	};
	void operator +=(void *vp);

	const void *operator[](unsigned u)const;
	void *operator[](unsigned u){
		return (void *)(((const linked_list_vpbase *)this)->operator[](u));
	}

	void *last_element(){
		return listhead.backp->item;
	}
	void clear();
	void insert_before_element(unsigned idx, void *vp);
	void delete_this_element(unsigned idx);

	struct list_bucket{
		list_bucket *forwp, *backp;
                void *item;
	};
protected:
	list_bucket listhead;
	unsigned neles;
	const list_bucket *locate_ele(unsigned u)const;

	// These things are not copyable
	void operator =(linked_list_vpbase &);
        linked_list_vpbase(const linked_list_vpbase&);

};

template <class TYPE> class linked_list_of : private linked_list_vpbase{
public:
	linked_list_vpbase::element_count;

	void operator +=(const TYPE &r);


	void insert_before_element(int index, TYPE &r);

	const TYPE &last_element()const{
		return *(TYPE*)linked_list_vpbase::last_element();
	}

	void delete_last_element();
	void delete_this_element(int i);

	void clear();			// delete all elements

	TYPE&  operator [](int i){
		return *(TYPE*)linked_list_vpbase::operator[](i);
	}

	const TYPE&  operator [](int i)const{
		return *(const TYPE*)linked_list_vpbase::operator[](i);
	}

	linked_list_of<TYPE> & operator=(const linked_list_of<TYPE>&);
	linked_list_of<TYPE> & operator+=(const linked_list_of<TYPE>&);

	virtual ~linked_list_of();
	linked_list_of(const linked_list_of<TYPE>&);
        // Because there is a copy constructor, we have to provide one of these too.
	linked_list_of()						{}
protected:
	friend class linked_list_iterator<TYPE>;
};

template <class TYPE>class linked_list_iterator{
public:
	linked_list_iterator()				{ p = 0;}
	linked_list_iterator(const linked_list_of<TYPE>&r)	{ p = &r; forwp = r.listhead.forwp;}
	operator int()					{return p != 0
								&& forwp != &(p->listhead);}
	void operator++()				{forwp = forwp->forwp;}
	void operator--()				{forwp = forwp->backp;}
        const TYPE &value()					{return *(const TYPE*)(forwp->item);}
private:
	const linked_list_of<TYPE> *p;
	linked_list_vpbase::list_bucket *forwp;
};


template <class TYPE>
void linked_list_of<TYPE>::operator +=(const TYPE &r){
	linked_list_vpbase::operator +=(new TYPE(r));
}

template <class TYPE>
linked_list_of<TYPE>::~linked_list_of(){
	linked_list_iterator<TYPE> li(*this);
	while(li){
		delete (TYPE *)&li.value();
		++li;
	}
}

template <class TYPE>
linked_list_of<TYPE>::linked_list_of(const linked_list_of<TYPE> &r){
	linked_list_iterator<TYPE> li(r);
	while(li){
		operator += (li.value());
		++li;
	}
}
#endif


#endif