diff options
Diffstat (limited to 'omegalib/omega_lib')
30 files changed, 3301 insertions, 6 deletions
diff --git a/omegalib/omega_lib/CMakeLists.txt b/omegalib/omega_lib/CMakeLists.txt index 84ee384..84f84f6 100644 --- a/omegalib/omega_lib/CMakeLists.txt +++ b/omegalib/omega_lib/CMakeLists.txt @@ -1,6 +1,6 @@ set(BASIC_SRC - ${OMEGAROOT}/basic/src/ConstString.cc - ${OMEGAROOT}/basic/src/Link.cc + src/basic/ConstString.cc + src/basic/Link.cc ) set(OC_SRC diff --git a/omegalib/omega_lib/include/basic/Bag.c b/omegalib/omega_lib/include/basic/Bag.c new file mode 100644 index 0000000..c3084c1 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Bag.c @@ -0,0 +1,329 @@ +/**************************************************************** + * * + * Collection constructors, desctructors, assignments * + * * + ****************************************************************/ + +#include <assert.h> + +namespace omega { + +template<class T> Bag<T>::Bag() { + contents = new List_Element <T>; + contents->tail = 0; + } +template<class T> Bag<T>::~Bag() { + delete contents; + } + +template<class T> Ordered_Bag<T>::Ordered_Bag() {} + +template<class T> Set<T>::Set() {} + +template<class T> Bag<T>::Bag(const Bag<T> &L) { + contents = new List_Element<T>(*L.contents); + } + +template<class T> Bag<T> & Bag<T>::operator=(const Bag<T> &L) { + if (this != &L) { + delete contents; + contents = new List_Element<T>(*L.contents); + } + return *this; + } + + + +template<class T> Set<T>::Set(T e) { + assert(this->contents); + this->contents->tail = new List_Element<T>(e, 0); + } + + +/**************************************************************** + * * + * Misc. simple Collection operations * + * * + ****************************************************************/ + +template<class T> bool Bag<T>::empty() const { + return contents->tail == 0; + } + +template<class T> Iterator<T> *Bag<T>::new_iterator() + { + return new List_Element_Iterator<T>(contents->tail); + } + + +template<class T> void Bag<T>::clear() { + if (contents->tail) delete contents->tail; + contents->tail = 0; + } + +template<class T> int Bag<T>::size() const { + int i = 0; + List_Element<T> * p = contents->tail; + while (p) { + p = p->tail; + i++; + }; + return i; + } + + +/**************************************************************** + * * + * Collection/Element operations (e.g. insert, contains) * + * * + ****************************************************************/ + +template<class T> void Bag<T>::remove(T e) { + List_Element<T> * p = contents; + while (p->tail && p->tail->head != e) p = p->tail; + if (p->tail && p->tail->head == e) { + List_Element<T> * q = p->tail; + p->tail = q->tail; + q->tail = 0; + delete q; + } + } + +template<class T> T Bag<T>::extract() { + List_Element<T> * p = contents->tail; + T e = p->head; + contents->tail = p->tail; + p->tail = 0; + delete p; + return e; + } + + +template<class T> void Bag<T>::insert(T e) { + List_Element<T> * q = new List_Element<T>(e,contents->tail); + contents->tail = q; + } + +template<class T> void Ordered_Bag<T>::insert(T e) { + List_Element<T> * p = this->contents; + while (p->tail && p->tail->head < e) p = p->tail; + if (!p->tail || p->tail->head != e) { + List_Element<T> * q = new List_Element<T>(e,p->tail); + p->tail = q; + } + } + + +template<class T> bool Bag<T>::contains(T e) const { + List_Element<T> * p = contents; + while (p->tail && p->tail->head != e) p = p->tail; + return (p->tail && p->tail->head == e); + } + +template<class T> bool Ordered_Bag<T>::contains(T e) const { + List_Element<T> * p = this->contents; + while (p->tail && p->tail->head < e) p = p->tail; + return (p->tail && p->tail->head == e); + } + + +template<class T> bool Set<T>::contains (const Set<T>& b) const { + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents; + do { + /* consume matched elements in p and q */ + p = p->tail; + q = q->tail; + if (!q) return 1; /* no more elements to match */ + if (!p) return 0; /* nothing left in p to match with */ + if (q->head < p->head) { + /* nothing smaller than + p->head left in p, so q->head + can't be matched */ + return 0; + }; + while (p && p->head < q->head) { + /* toss away some elements from p */ + p = p->tail; + } + if (!p || q->head < p->head) return 0; + } while (q); + + return 1; + } + + + +/**************************************************************** + * * + * Collection/Collection operations (e.g. |=) * + * * + ****************************************************************/ + +template<class T> void Bag<T>::operator |= (const Bag<T> & b) { + assert(this != &b); + List_Element<T> * q = b.contents->tail; + + while (q) { + List_Element<T> * r = new List_Element<T>(q->head,contents->tail); + contents->tail = r; + q = q->tail; + } + } + +template<class T> void Ordered_Bag<T>::operator |= (const Ordered_Bag<T> & b) { + if (this == &b) return; + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents->tail; + + while (q) { + while (p->tail && p->tail->head < q->head) p = p->tail; + List_Element<T> * r = new List_Element<T>(q->head,p->tail); + p->tail = r; + q = q->tail; + } + } + +template<class T> void Ordered_Bag<T>::operator |= (const Bag<T> & b) { + Ordered_Bag<T> tmp; + for (List_Element<T> *p = b.contents; p; p=p->tail) { + tmp.insert(p->head); + } + *this |= tmp; +} + +template<class T> void Set<T>::operator |= (const Set<T> & b) { + if (this == &b) return; + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents->tail; + + while (q) { + while (p->tail && p->tail->head < q->head) p = p->tail; + if (!p->tail || p->tail->head != q->head) { + List_Element<T> * r = new List_Element<T>(q->head,p->tail); + p->tail = r; + } + q = q->tail; + } + } + +template<class T> void Set<T>::operator |= (const Ordered_Bag<T> & b) { + Set<T> tmp; + for (List_Element<T> *p = b.contents; p; p=p->tail) { + tmp.insert(p->head); + } + *this |= tmp; +} + +template<class T> void Set<T>::operator |= (const Bag<T> & b) { + Set<T> tmp; + for (List_Element<T> *p = b.contents; p; p=p->tail) { + tmp.insert(p->head); + } + *this |= tmp; +} + + + +// delete items also in b +template<class T> void Set<T>::operator -= (const Set<T> & b) { + if (this == &b) { + this->clear(); + return; + } + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents->tail; + + while (q) { + while (p->tail && p->tail->head < q->head) p = p->tail; + if (p->tail && p->tail->head == q->head) { + List_Element<T> * r = p->tail; + p->tail = r->tail; + r->tail = 0; + delete r; + } + q = q->tail; + } + } + + +// delete items not in b +template<class T> void Set<T>::operator &= (const Set<T> & b) + { + if (this == &b) return; + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents->tail; + + while (q) { + while (p->tail && p->tail->head < q->head) { + List_Element<T> * r = p->tail; + p->tail = r->tail; + r->tail = 0; + delete r; + }; + if (p->tail && p->tail->head == q->head) { + /* allow p->tail->head into the result */ + p = p->tail; + } + /* q->head has matched anything it is going to match */ + q = q->tail; + } + if (p->tail) { + delete p->tail; + p->tail = 0; + }; + + } + + +template<class T> bool Set<T>::operator & (const Set<T>& b) const { + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents; + do { + p = p->tail; + q = q->tail; + while (p && q && p->head != q->head) { + while (p && p->head < q->head) p = p->tail; + while (p && q && q->head < p->head) q = q->tail; + }; + if (p && q && p->head == q->head) return 1; + } while (p && q); + + return 0; + } + + +template<class T> bool Ordered_Bag<T>::operator == (const Ordered_Bag<T>& b) const { + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents; + while (1) { + p = p->tail; + q = q->tail; + if (!p && !q) return 1; + if (!p || !q) return 0; + if (p->head != q->head) return 0; + }; + + } + +template<class T> bool Ordered_Bag<T>::operator != (const Ordered_Bag<T>& b) const { + return !(*this == b); + } + +template<class T> bool Ordered_Bag<T>::operator < (const Ordered_Bag<T>& b) const { + List_Element<T> * p = this->contents; + List_Element<T> * q = b.contents; + while (1) { + p = p->tail; + q = q->tail; + if (!p && !q) return 0; + if (!p) return 1; + if (!q) return 0; + if (p->head < q->head) return 1; + if (q->head < p->head) return 0; + }; + + return 1; + } + +} // namespace diff --git a/omegalib/omega_lib/include/basic/Bag.h b/omegalib/omega_lib/include/basic/Bag.h new file mode 100644 index 0000000..42285d0 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Bag.h @@ -0,0 +1,78 @@ +#if ! defined _Bag_h +#define _Bag_h 1 + +#include <stdio.h> +#include <basic/Iterator.h> +#include <basic/Collection.h> +#include <basic/Link.h> + +namespace omega { + +template<class T> class Bag : public Collection<T> { +public: +virtual ~Bag(); + Bag(); + Bag(const Bag<T>&); + Bag & operator=(const Bag<T>&); +virtual void operator |= (const Bag<T> & b); // add elements in b + Iterator<T> *new_iterator(); + bool empty() const; + void remove(T); +virtual void insert(T); + void clear(); +virtual bool contains(T) const; + int size() const; + T extract(); +// protected: breaks g++ 261 + List_Element<T>* contents; +}; + + +template<class T> class Ordered_Bag : public Bag<T> { +public: + Ordered_Bag(); +// virtual ~Ordered_Bag(); + Ordered_Bag(const Ordered_Bag<T>& B) : Bag<T>(B) {} + void insert(T); +virtual void operator |= (const Ordered_Bag<T> & b); // add elements in b + void operator |= (const Bag<T> & b); + bool contains(T) const; + bool operator == (const Ordered_Bag<T>&) const; + bool operator != (const Ordered_Bag<T>&) const; + bool operator < (const Ordered_Bag<T>&) const; +}; + +template <class T> class Set : public Ordered_Bag <T> { +public: + Set(); +// virtual ~Set(); + Set(T); + Set(const Set<T>& S) : Ordered_Bag<T>(S) {} + + bool contains (const Set<T>& b) const; + bool contains (T t) const { return Ordered_Bag<T>::contains(t); } + // the above makes "standard" C++ happy + +virtual void operator |= (const Set<T> & b); // add elements in b + void operator |= (const Ordered_Bag<T> & b); + void operator |= (const Bag<T> & b); + + void operator -= (const Set<T> & b); // delete items also in b + void operator &= (const Set<T> & b); // delete items not in b + bool operator & (const Set<T> &) const; // check for elements in common +}; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/Bag.c> +#endif + +#define instantiate_Bag(T) template class Bag<T>; \ + instantiate_List_Element(T); +#define instantiate_Ordered_Bag(T) template class Ordered_Bag<T>; \ + instantiate_Bag(T) +#define instantiate_Set(T) template class Set<T>; \ + instantiate_Ordered_Bag(T) + +#endif diff --git a/omegalib/omega_lib/include/basic/BoolSet.h b/omegalib/omega_lib/include/basic/BoolSet.h new file mode 100755 index 0000000..dc9ef83 --- /dev/null +++ b/omegalib/omega_lib/include/basic/BoolSet.h @@ -0,0 +1,637 @@ +/***************************************************************************** + Copyright (C) 2009-2011 Chun Chen + All Rights Reserved. + + Purpose: + BoolSet class, used as a set of integers from 0..n-1 where n is a very + small integer. + + Notes: + Set operands of binary operations can be of different sizes, missing + elements are treated as false. + + History: + 03/30/09 Created by Chun Chen. + 03/26/11 iterator added, -chun +*****************************************************************************/ + +#ifndef _BOOLSET_H +#define _BOOLSET_H + +#include <vector> +#include <iostream> +#include <assert.h> +#include <stdexcept> +#include <iterator> + +namespace omega { + +template<typename T = unsigned int> +class BoolSet { +protected: + unsigned int size_; + std::vector<T> set_; + +public: + BoolSet(unsigned int size = 0); + ~BoolSet() {} + + void set(unsigned int); + void unset(unsigned int); + void set_all(); + void unset_all(); + bool get(unsigned int) const; + unsigned int size() const {return size_;} + unsigned int num_elem() const; + bool imply(const BoolSet<T> &) const; + bool empty() const; + void dump() const; + + BoolSet<T> &operator|=(const BoolSet<T> &); + BoolSet<T> &operator&=(const BoolSet<T> &); + BoolSet<T> &operator-=(const BoolSet<T> &); + + template<typename TT> friend BoolSet<TT> operator|(const BoolSet<TT> &, const BoolSet<TT> &); // union + template<typename TT> friend BoolSet<TT> operator&(const BoolSet<TT> &, const BoolSet<TT> &); // intersection + template<typename TT> friend BoolSet<TT> operator-(const BoolSet<TT> &, const BoolSet<TT> &); // difference + template<typename TT> friend BoolSet<TT> operator~(const BoolSet<TT> &); // complement + template<typename TT> friend bool operator==(const BoolSet<TT> &, const BoolSet<TT> &); + template<typename TT> friend bool operator!=(const BoolSet<TT> &, const BoolSet<TT> &); + template<typename TT> friend std::ostream& operator<<(std::ostream &, const BoolSet<TT> &); + template<typename TT> friend bool operator<(const BoolSet<TT> &, const BoolSet<TT> &); + +// iterator related +public: + class iterator; + class const_iterator; + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; +}; + + +template<typename T> +BoolSet<T>::BoolSet(unsigned int size) { + assert(size >= 0); + size_ = size; + unsigned int n = size / (sizeof(T)*8); + unsigned int r = size % (sizeof(T)*8); + if (r != 0) + n++; + set_ = std::vector<T>(n, static_cast<T>(0)); +} + + +template<typename T> +void BoolSet<T>::set(unsigned int i) { + assert(i < size_ && i >= 0); + unsigned int n = i / (sizeof(T)*8); + unsigned int r = i % (sizeof(T)*8); + + T t = static_cast<T>(1) << r; + set_[n] |= t; +} + + +template<typename T> +void BoolSet<T>::unset(unsigned int i) { + assert(i < size_ && i >= 0); + unsigned int n = i / (sizeof(T)*8); + unsigned int r = i % (sizeof(T)*8); + + T t = static_cast<T>(1) << r; + t = ~t; + set_[n] &= t; +} + + +template<typename T> +void BoolSet<T>::set_all() { + unsigned int r = size_ % (sizeof(T)*8); + if (r == 0) { + for (unsigned int i = 0; i < set_.size(); i++) + set_[i] = ~static_cast<T>(0); + } + else { + for (unsigned int i = 0; i < set_.size()-1; i++) + set_[i] = ~static_cast<T>(0); + set_[set_.size()-1] = static_cast<T>(0); + T t = static_cast<T>(1); + for (unsigned int i = 0; i < r; i++) { + set_[set_.size()-1] |= t; + t = t<<1; + } + } +} + + +template<typename T> +void BoolSet<T>::unset_all() { + for (unsigned int i = 0; i < set_.size(); i++) + set_[i] = static_cast<T>(0); +} + + +template<typename T> +bool BoolSet<T>::get(unsigned int i) const { + assert(i < size_ && i >= 0); + unsigned int n = i / (sizeof(T)*8); + unsigned int r = i % (sizeof(T)*8); + + T t = static_cast<T>(1) << r; + t = set_[n] & t; + if (t) + return true; + else + return false; +} + + +template<typename T> +unsigned int BoolSet<T>::num_elem() const { + unsigned int n = size_; + unsigned int c = 0; + unsigned int p = 0; + while (n != 0) { + unsigned int m; + if (n >= sizeof(T)*8) { + m = sizeof(T)*8; + n -= sizeof(T)*8; + } + else { + m = n; + n = 0; + } + + T v = set_[p++]; + if (v != static_cast<T>(0)) { + for (unsigned int i = 0; i < m; i++) { + if (v & static_cast<T>(1)) + c++; + v >>= 1; + } + } + } + + return c; +} + + +template<typename T> +bool BoolSet<T>::imply(const BoolSet<T> &b) const { + if (size_ >= b.size_) { + for (unsigned int i = 0; i < b.set_.size(); i++) + if ((set_[i] & b.set_[i]) != b.set_[i]) + return false; + } + else { + for (unsigned int i = 0; i < set_.size(); i++) + if ((set_[i] & b.set_[i]) != b.set_[i]) + return false; + for (unsigned int i = set_.size(); i < b.set_.size(); i++) + if (b.set_[i] != static_cast<T>(0)) + return false; + } + + return true; +} + + +template<typename T> +bool BoolSet<T>::empty() const { + for (int i = 0; i < set_.size(); i++) + if (set_[i] != static_cast<T>(0)) + return false; + + return true; +} + + +template<typename T> +void BoolSet<T>::dump() const { + int j = 1; + for (unsigned int i = 0; i < size(); i++) { + if (get(i)) + std::cout << '1'; + else + std::cout << '0'; + if (j%10 == 0 && i != size() - 1) { + std::cout << ' '; + j = 1; + } + else + j++; + } + std::cout << std::endl; + std::cout.flush(); +} + + +template<typename T> +BoolSet<T> operator|(const BoolSet<T> &a, const BoolSet<T> &b) { + if (a.size_ >= b.size_) { + BoolSet<T> c = a; + for (unsigned int i = 0; i < b.set_.size(); i++) + c.set_[i] |= b.set_[i]; + return c; + } + else { + BoolSet<T> c = b; + for (unsigned int i = 0; i < a.set_.size(); i++) + c.set_[i] |= a.set_[i]; + return c; + } +} + + +template<typename T> +BoolSet<T> operator&(const BoolSet<T> &a, const BoolSet<T> &b) { + if (a.size_ >= b.size_) { + BoolSet<T> c = a; + for (unsigned int i = 0; i < b.set_.size(); i++) + c.set_[i] &= b.set_[i]; + for (unsigned int i = b.set_.size(); i < a.set_.size(); i++) + c.set_[i] = static_cast<T>(0); + return c; + } + else { + BoolSet<T> c = b; + for (unsigned int i = 0; i < a.set_.size(); i++) + c.set_[i] &= a.set_[i]; + for (unsigned int i = a.set_.size(); i < b.set_.size(); i++) + c.set_[i] = static_cast<T>(0); + return c; + } +} + + +template<typename T> +BoolSet<T> operator-(const BoolSet<T> &a, const BoolSet<T> &b) { + BoolSet<T> c(a.size_); + + int sz = a.set_.size(); + if (sz > b.set_.size()) + sz = b.set_.size(); + for (int i = 0; i < sz; i++) + c.set_[i] = a.set_[i] ^ (a.set_[i] & b.set_[i]); + for (int i = sz; i < a.set_.size(); i++) + c.set_[i] = a.set_[i]; + + return c; +} + + +template<typename T> +BoolSet<T> operator~(const BoolSet<T> &b) { + unsigned int r = b.size_ % (sizeof(T)*8); + BoolSet<T> a(b.size_); + for (unsigned int i = 0; i < b.set_.size(); i++) + a.set_[i] = ~b.set_[i]; + + if (r != 0) { + T t = static_cast<T>(1); + for (unsigned int i = 1; i < r; i++) + t = (t << 1) | static_cast<T>(1); + a.set_[a.set_.size()-1] &= t; + } + return a; +} + + +template<typename T> +bool operator==(const BoolSet<T> &a, const BoolSet<T> &b) { + return (a.size_ == b.size_) && (a.set_ == b.set_); +} + + +template<typename T> +bool operator!=(const BoolSet<T> &a, const BoolSet<T> &b) { + return !(a == b); +} + + + +template<typename T> +BoolSet<T> & BoolSet<T>::operator|=(const BoolSet<T> &b) { + *this = *this | b; + return *this; +} + + +template<typename T> +BoolSet<T> & BoolSet<T>::operator&=(const BoolSet<T> &b) { + *this = *this & b; + return *this; +} + + +template<typename T> +BoolSet<T> & BoolSet<T>::operator-=(const BoolSet<T> &b) { + *this = *this - b; + return *this; +} + + +template<typename T> +std::ostream& operator<<(std::ostream &os, const BoolSet<T> &b) { + os << '{'; + for (typename BoolSet<T>::const_iterator i = b.begin(); i != b.end(); i++) { + os << *i; + if (i+1 != b.end()) + os << ','; + } + os << '}'; + + return os; +} + + +template<typename T> +bool operator<(const BoolSet<T> &a, const BoolSet<T> &b) { + unsigned int t1, t2; + t1 = a.num_elem(); + t2 = b.num_elem(); + if (t1 < t2) + return true; + else if (t1 > t2) + return false; + else { + t1 = a.size(); + t2 = b.size(); + if (t1 < t2) + return true; + else if (t1 > t2) + return false; + else + for (unsigned int i = 0; i < a.set_.size(); i++) + if (a.set_[i] < b.set_[i]) + return true; + } + return false; +} + + +// +// iterator for BoolSet +// + +template<typename T> +typename BoolSet<T>::iterator BoolSet<T>::begin() { + typename BoolSet<T>::iterator it(this, 0); + if (size_ == 0) + return it; + else if (set_[0] & static_cast<T>(1)) + return it; + else + return ++it; +} + + +template<typename T> +typename BoolSet<T>::iterator BoolSet<T>::end() { + return typename BoolSet<T>::iterator(this, size_); +} + + +template<typename T> +typename BoolSet<T>::const_iterator BoolSet<T>::begin() const { + typename BoolSet<T>::const_iterator it(this, 0); + if (size_ == 0) + return it; + else if (set_[0] & static_cast<T>(1)) + return it; + else + return ++it; +} + + +template<typename T> +typename BoolSet<T>::const_iterator BoolSet<T>::end() const { + return typename BoolSet<T>::const_iterator(this, size_); +} + + +template<typename T> +class BoolSet<T>::iterator: public std::iterator<std::forward_iterator_tag, T> { +protected: + BoolSet<T> *s_; + unsigned int pos_; + +protected: + iterator(BoolSet<T> *s, unsigned int pos) { s_ = s; pos_ = pos; } + +public: + ~iterator() {} + + typename BoolSet<T>::iterator &operator++(); + typename BoolSet<T>::iterator operator++(int); + typename BoolSet<T>::iterator operator+(int) const; + unsigned int operator*() const; + bool operator==(const BoolSet<T>::iterator &) const; + bool operator!=(const BoolSet<T>::iterator &) const; + operator typename BoolSet<T>::const_iterator(); + + friend class BoolSet<T>; +}; + + +template<typename T> +typename BoolSet<T>::iterator &BoolSet<T>::iterator::operator++() { + assert(pos_ < s_->size_); + + pos_++; + unsigned int n = pos_ / (sizeof(T)*8); + unsigned int r = pos_ % (sizeof(T)*8); + while (pos_ < s_->size_) { + if (s_->set_[n] == static_cast<T>(0)) { + pos_ += sizeof(T)*8-r; + n++; + r = 0; + if (pos_ >= s_->size_) + break; + } + + if (r == 0) { + while (pos_ < s_->size_) { + if (s_->set_[n] == static_cast<T>(0)) { + pos_ += sizeof(T)*8; + n++; + } + else + break; + } + if (pos_ >= s_->size_) + break; + } + + for (unsigned int i = r; i < sizeof(T)*8; i++) + if (s_->set_[n] & static_cast<T>(1) << i) { + pos_ = pos_+i-r; + return *this; + } + + pos_ += sizeof(T)*8-r; + n++; + r = 0; + } + + pos_ = s_->size_; + return *this; +} + + +template<typename T> +typename BoolSet<T>::iterator BoolSet<T>::iterator::operator++(int) { + typename BoolSet<T>::iterator it(*this); + ++(*this); + return it; +} + + +template<typename T> +typename BoolSet<T>::iterator BoolSet<T>::iterator::operator+(int n) const { + assert(n >= 0); + typename BoolSet<T>::iterator it(*this); + while (n > 0) { + ++it; + --n; + } + return it; +} + + +template<typename T> +unsigned int BoolSet<T>::iterator::operator*() const { + assert(pos_ < s_->size_); + return pos_; +} + + +template<typename T> +bool BoolSet<T>::iterator::operator==(const BoolSet<T>::iterator &other) const { + return s_ == other.s_ && pos_ == other.pos_; +} + + +template<typename T> +bool BoolSet<T>::iterator::operator!=(const BoolSet<T>::iterator &other) const { + return !((*this) == other); +} + + +template<typename T> +BoolSet<T>::iterator::operator typename BoolSet<T>::const_iterator() { + return BoolSet<T>::const_iterator(s_, pos_); +} + + +template<typename T> +class BoolSet<T>::const_iterator: public std::iterator<std::forward_iterator_tag, T> { +protected: + const BoolSet<T> *s_; + unsigned int pos_; + +protected: + const_iterator(const BoolSet<T> *s, unsigned int pos) { s_ = s; pos_ = pos; } + +public: + ~const_iterator() {} + + typename BoolSet<T>::const_iterator &operator++(); + typename BoolSet<T>::const_iterator operator++(int); + typename BoolSet<T>::const_iterator operator+(int) const; + unsigned int operator*() const; + bool operator==(const BoolSet<T>::const_iterator &) const; + bool operator!=(const BoolSet<T>::const_iterator &) const; + + friend class BoolSet<T>; +}; + + +template<typename T> +typename BoolSet<T>::const_iterator &BoolSet<T>::const_iterator::operator++() { + assert(pos_ < s_->size_); + + pos_++; + unsigned int n = pos_ / (sizeof(T)*8); + unsigned int r = pos_ % (sizeof(T)*8); + while (pos_ < s_->size_) { + if (s_->set_[n] == static_cast<T>(0)) { + pos_ += sizeof(T)*8-r; + n++; + r = 0; + if (pos_ >= s_->size_) + break; + } + + if (r == 0) { + while (pos_ < s_->size_) { + if (s_->set_[n] == static_cast<T>(0)) { + pos_ += sizeof(T)*8; + n++; + } + else + break; + } + if (pos_ >= s_->size_) + break; + } + + for (unsigned int i = r; i < sizeof(T)*8; i++) + if (s_->set_[n] & static_cast<T>(1) << i) { + pos_ = pos_+i-r; + return *this; + } + + pos_ += sizeof(T)*8-r; + n++; + r = 0; + } + + pos_ = s_->size_; + return *this; +} + + +template<typename T> +typename BoolSet<T>::const_iterator BoolSet<T>::const_iterator::operator++(int) { + typename BoolSet<T>::const_iterator it(*this); + ++(*this); + return it; +} + + +template<typename T> +typename BoolSet<T>::const_iterator BoolSet<T>::const_iterator::operator+(int n) const { + assert(n >= 0); + typename BoolSet<T>::const_iterator it(*this); + while (n > 0) { + ++it; + --n; + } + return it; +} + + +template<typename T> +unsigned int BoolSet<T>::const_iterator::operator*() const { + assert(pos_ < s_->size_); + return pos_; +} + + +template<typename T> +bool BoolSet<T>::const_iterator::operator==(const BoolSet<T>::const_iterator &other) const { + return s_ == other.s_ && pos_ == other.pos_; +} + + +template<typename T> +bool BoolSet<T>::const_iterator::operator!=(const BoolSet<T>::const_iterator &other) const { + return !((*this) == other); +} + +} + +#endif diff --git a/omegalib/omega_lib/include/basic/Collection.h b/omegalib/omega_lib/include/basic/Collection.h new file mode 100644 index 0000000..c7e4eef --- /dev/null +++ b/omegalib/omega_lib/include/basic/Collection.h @@ -0,0 +1,47 @@ +#if !defined Already_Included_Collection +#define Already_Included_Collection + +namespace omega { + +template<class T> class Iterator; +template<class T> class Any_Iterator; + + +/* + * protocol for any kind of collection + */ + +template<class T> class Collection { +public: + virtual Iterator<T> *new_iterator() = 0; + virtual Any_Iterator<T> any_iterator() { return Any_Iterator<T>(new_iterator()); } + + virtual int size() const = 0; +}; + + +/* + * protocol for collections whose elements are ordered + * by the way they are entered into the collection, and + * whose elements can be accessed by "index" + * + * note that the implementation need not be a linked list + */ + +template<class T> class Sequence : public Collection<T> { +public: + virtual const T &operator[](int) const = 0; + virtual T &operator[](int) = 0; + + virtual int index(const T &) const = 0; // Y in X --> X[X.index(Y)] == Y +}; + +} // namespace + +#define instantiate_Collection(T) template class Collection<T>; \ + instantiate_Any_Iterator(T) +#define instantiate_Sequence(T) template class Sequence<T>; \ + instantiate_Collection(T) + +#endif + diff --git a/omegalib/omega_lib/include/basic/Collections.h b/omegalib/omega_lib/include/basic/Collections.h new file mode 100644 index 0000000..1e68031 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Collections.h @@ -0,0 +1,12 @@ +#if !defined Already_Included_Collections +#define Already_Included_Collections + +#include <stdio.h> +#include <basic/Collection.h> +#include <basic/Iterator.h> +#include <basic/List.h> +#include <basic/Bag.h> +#include <basic/Map.h> + +#endif + diff --git a/omegalib/omega_lib/include/basic/ConstString.h b/omegalib/omega_lib/include/basic/ConstString.h new file mode 100644 index 0000000..5149e55 --- /dev/null +++ b/omegalib/omega_lib/include/basic/ConstString.h @@ -0,0 +1,58 @@ +#if ! defined _Const_String_h +#define _Const_String_h 1 + +#include <string> + +namespace omega { + +// should be inside Const_String, but I can't get it to +// compile the hashTable when it is: hashTable can't be +// global, but if it and its size are static to Const_String, +// the compiler still doesn't seem to like the definition, +// or the declaration either for that matter. + +class ConstStringRep { +public: + const char *name; + int count; + ConstStringRep *nextInBucket; + ConstStringRep(const char *t); +}; + +class Const_String { +private: + ConstStringRep *rep; + void buildRep(const char *t); + +public: + Const_String(); + Const_String(const char* t); + Const_String(const std::string &s); + Const_String(const Const_String & t) {rep = t.rep;} + + operator int() const; + int null() const; + + operator const char*() const; + operator std::string() const; + int operator++(int); + int operator++(); + int operator--(int); + int operator--(); + friend int operator==(const Const_String &x, const Const_String &y); + friend int operator!=(const Const_String &x, const Const_String &y); + friend int operator<(const Const_String &x, const Const_String &y); + friend int operator >(const Const_String &x, const Const_String &y); + +}; + +#if defined SCREWED_UP_CASTING_RULES +static int operator==(const Const_String &x, const char *y) +{ return x == (Const_String) y; } +static int operator!=(const Const_String &x, const char *y) +{ return x != (Const_String) y; } +#endif + +} // namespace + +#endif diff --git a/omegalib/omega_lib/include/basic/Dynamic_Array.c b/omegalib/omega_lib/include/basic/Dynamic_Array.c new file mode 100644 index 0000000..0300fd8 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Dynamic_Array.c @@ -0,0 +1,219 @@ +#include <assert.h> +#include <basic/Dynamic_Array.h> + +namespace omega { + +template<class T, int d> void Dynamic_Array<T,d>::do_constr() + { +// #if ! defined SHUT_UP_ABOUT_STATEMENT_WITH_NO_EFFECT_IN_DYNAMIC_ARRAY_CREATION +// assert(d > 0); +// #endif + bounds = 0; + elements = 0; + partial = false; + } + + +template<class T> void Dynamic_Array1<T>::do_construct(int d0) + { + this->bounds = new int[1]; + this->bounds[0] = d0; + this->elements = new T [d0]; + this->partial = false; + } + +template<class T> void Dynamic_Array2<T>::do_construct(int d0, int d1) + { + this->bounds = new int[2]; + this->bounds[0] = d0; + this->bounds[1] = d1; + this->elements = new T [d0 * d1]; + this->partial = false; + } + +template<class T> void Dynamic_Array3<T>::do_construct(int d0,int d1,int d2) + { + this->bounds = new int[3]; + this->bounds[0] = d0; + this->bounds[1] = d1; + this->bounds[2] = d2; + this->elements = new T [d0 * d1 * d2]; + this->partial = false; + } + +template<class T> void Dynamic_Array4<T>::do_construct(int d0,int d1,int d2,int d3) + { + this->bounds = new int[4]; + this->bounds[0] = d0; + this->bounds[1] = d1; + this->bounds[2] = d2; + this->bounds[3] = d3; + this->elements = new T [d0 * d1 * d2 * d3]; + this->partial = false; + } + +template<class T, int d> Dynamic_Array<T,d>::Dynamic_Array() + { + do_constr(); + } + +template<class T> Dynamic_Array1<T>::Dynamic_Array1(const char *) + { + this->do_constr(); + } + +template<class T> Dynamic_Array2<T>::Dynamic_Array2(const char *,const char *) + { + this->do_constr(); + } + +template<class T> Dynamic_Array3<T>::Dynamic_Array3(const char *,const char *,const char *) + { + this->do_constr(); + } + +template<class T> Dynamic_Array4<T>::Dynamic_Array4(const char *,const char *,const char *,const char *) + { + this->do_constr(); + } + +template<class T> Dynamic_Array1<T>::Dynamic_Array1(int d0) + { + do_construct(d0); + } + +template<class T> Dynamic_Array2<T>::Dynamic_Array2(int d0, int d1) + { + do_construct(d0, d1); + } + +template<class T> Dynamic_Array3<T>::Dynamic_Array3(int d0,int d1,int d2) + { + do_construct(d0, d1, d2); + } + +template<class T> Dynamic_Array4<T>::Dynamic_Array4(int d0,int d1,int d2,int d3) + { + do_construct(d0, d1, d2, d3); + } + + +template<class T, int d> void Dynamic_Array<T,d>::do_destruct() + { + if (! partial) + { + delete [] bounds; + delete [] elements; + } + } + + +template<class T, int d> Dynamic_Array<T,d>::~Dynamic_Array() + { + do_destruct(); + } + + +template<class T> void Dynamic_Array1<T>::resize(int d0) + { + assert(!this->partial); + this->do_destruct(); + if (d0 == 0) + this->do_constr(); + else + do_construct(d0); + } + +template<class T> void Dynamic_Array2<T>::resize(int d0, int d1) + { + assert(!this->partial); + this->do_destruct(); + if (d0 == 0 && d1 == 0) + this->do_constr(); + else + do_construct(d0, d1); + } + +template<class T> void Dynamic_Array3<T>::resize(int d0, int d1, int d2) + { + assert(!this->partial); + this->do_destruct(); + if (d0 == 0 && d1 == 0 && d2 == 0) + this->do_constr(); + else + do_construct(d0, d1, d2); + } + +template<class T> void Dynamic_Array4<T>::resize(int d0, int d1, int d2, int d3) + { + assert(!this->partial); + this->do_destruct(); + if (d0 == 0 && d1 == 0 && d2 == 0 && d3 == 0) + this->do_constr(); + else + do_construct(d0, d1, d2, d3); + } + + +template<class T> T& Dynamic_Array1<T>::operator[](int d0) + { +#if !defined (NDEBUG) + assert(this->elements != 0 && "Trying to dereference undefined array"); + assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds"); +#endif + + return this->elements[d0]; + } + +template<class T> Dynamic_Array1<T> Dynamic_Array2<T>::operator[](int d0) + { +#if !defined (NDEBUG) + assert(this->elements != 0 && "Trying to dereference undefined array"); + assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds"); +#endif + + Dynamic_Array1<T> result; + result.bounds = this->bounds+1; + result.elements = this->elements + this->bounds[1] * d0; + result.partial = true; + return result; + } + +template<class T> Dynamic_Array2<T> Dynamic_Array3<T>::operator[](int d0) + { +#if !defined (NDEBUG) + assert(this->elements != 0 && "Trying to dereference undefined array"); + assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds"); +#endif + Dynamic_Array2<T> result; + result.bounds = this->bounds+1; + result.elements = this->elements + this->bounds[1] * this->bounds[2] * d0; + result.partial = true; + return result; + } + +template<class T> Dynamic_Array3<T> Dynamic_Array4<T>::operator[](int d0) + { +#if !defined (NDEBUG) + assert(this->elements != 0 && "Trying to dereference undefined array"); + assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds"); +#endif + + Dynamic_Array3<T> result; + result.bounds = this->bounds+1; + result.elements = this->elements + this->bounds[1] * this->bounds[2] * this->bounds[3] * d0; + result.partial = true; + return result; + } + + +template<class T, int d> + Dynamic_Array<T,d>::Dynamic_Array(Dynamic_Array<T,d> &D) + { + assert(D.elements != 0 && "Trying to copy an undefined array"); + partial = true; + bounds = D.bounds; + elements = D.elements; + } + +} // namespace diff --git a/omegalib/omega_lib/include/basic/Dynamic_Array.h b/omegalib/omega_lib/include/basic/Dynamic_Array.h new file mode 100644 index 0000000..c0bdf12 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Dynamic_Array.h @@ -0,0 +1,103 @@ +#ifndef Already_Included_Dynamic_Array +#define Already_Included_Dynamic_Array + +namespace omega { + +template <class T> class Dynamic_Array2; +template <class T> class Dynamic_Array3; +template <class T> class Dynamic_Array4; + +template <class T, int d> class Dynamic_Array + { + public: + Dynamic_Array(Dynamic_Array<T,d> &D); + ~Dynamic_Array(); + + protected: + Dynamic_Array(); + bool partial; + int *bounds; + T *elements; + + void do_constr(); + void do_destruct(); + }; + + +template <class T> class Dynamic_Array1 : public Dynamic_Array<T,1> + { + public: + Dynamic_Array1(const char *s0 = 0); + Dynamic_Array1(int d0); + void resize(int d0); + T& operator[](int d); + + friend class Dynamic_Array2<T>; + + private: + void do_construct(int d0); + }; + + +template <class T> class Dynamic_Array2 : public Dynamic_Array<T,2> + { + public: + Dynamic_Array2(const char *s0 = 0, const char *s1 = 0); + Dynamic_Array2(int d0, int d1); + void resize(int d0, int d1); + Dynamic_Array1<T> operator[](int d); + + friend class Dynamic_Array3<T>; + + private: + void do_construct(int d0, int d1); + }; + + +template <class T> class Dynamic_Array3 : public Dynamic_Array<T,3> + { + public: + Dynamic_Array3(const char *s0 = 0, const char *s1 = 0, const char *s2 = 0); + Dynamic_Array3(int d0, int d1, int d2); + void resize(int d0, int d1, int d2); + Dynamic_Array2<T> operator[](int d); + + friend class Dynamic_Array4<T>; + + private: + void do_construct(int d0, int d1, int d2); + }; + +template <class T> class Dynamic_Array4 : public Dynamic_Array<T,4> + { + public: + Dynamic_Array4(const char *s0 = 0, const char *s1 = 0, const char *s2 = 0, const char *s3 = 0); + Dynamic_Array4(int d0, int d1, int d2, int d3); + void resize(int d0, int d1, int d2, int d3); + Dynamic_Array3<T> operator[](int d); + + private: + void do_construct(int d0, int d1, int d2, int d3); + }; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/Dynamic_Array.c> +#endif + +#define instantiate_Dynamic_Array1(T) template class Dynamic_Array1<T>; \ + template class Dynamic_Array<T,1>; + +#define instantiate_Dynamic_Array2(T) template class Dynamic_Array2<T>; \ + template class Dynamic_Array<T,2>; \ + instantiate_Dynamic_Array1(T); + +#define instantiate_Dynamic_Array3(T) template class Dynamic_Array3<T>; \ + template class Dynamic_Array<T,3>; \ + instantiate_Dynamic_Array2(T); + +#define instantiate_Dynamic_Array4(T) template class Dynamic_Array4<T>; \ + template class Dynamic_Array<T,4>; \ + instantiate_Dynamic_Array3(T); +#endif diff --git a/omegalib/omega_lib/include/basic/Iterator.h b/omegalib/omega_lib/include/basic/Iterator.h new file mode 100644 index 0000000..8975d9e --- /dev/null +++ b/omegalib/omega_lib/include/basic/Iterator.h @@ -0,0 +1,131 @@ +/* + * Base classes for iterators, generators + * + * These don't really work yet for constant collections. + * I'm not sure how to make that happen. + */ + +#if ! defined _Iterator_h +#define _Iterator_h 1 + +#include <basic/Collection.h> + +namespace omega { + +#define foreach(x,T,S,A) do {for (omega::Any_Iterator<T> __P_##x = (S).any_iterator();__P_##x;__P_##x++) {T & x = *__P_##x; A;}} while (0) + +#define foreachSeparated(x,T,S,A,B) do {for (omega::Any_Iterator<T> __P_##x = (S).any_iterator();__P_##x;) {T & x = *__P_##x; A; __P_##x++; if (__P_##x) B;}} while (0) + +/* + * Abstract base class Iterator<type> + * Supports two styles of iteration: + * + * for ( ... initialize i (typically i = collection) ... ; i ; i++ ) + * operate_on(*i) + * + * or + * + * for ( ... initialize i ... ; i.live() ; i.next() ) + * operate_on(i.curr()) + * + * >>> IF THE COLLECTION IS CHANGED, THE ITERATOR IS NO LONGER VALID <<< + * + * For collections that are not "Sequence"s, the order in + * which the elements are returned may not be consistent. + */ + +template<class T> class Iterator { +public: + virtual const T & operator*() const = 0; + virtual T & operator*() = 0; + + virtual void operator++(int) = 0; + virtual void operator++() = 0; + + virtual bool live() const = 0; + operator bool() const { return live(); } + + const T & curr() const { return *(*this); } + T & curr() { return *(*this); } + void next() { (*this)++; } + + virtual Iterator<T> *new_copy() const = 0; + virtual ~Iterator() {} +}; + + +// A generator is like an iterator but it gives out values, +// which may or may not exist in some writable collection + +template<class T> class Generator { +public: + virtual T operator*() const = 0; + + virtual void operator++(int) = 0; + virtual void operator++() = 0; + + virtual int live() const = 0; + operator int() const { return live(); } + + const T curr() const { return *(*this); } + T curr() { return *(*this); } + void next() { (*this)++; } +}; + + + +// Delegate to any kind of iterator (on the heap) +// If created via a reference, become a copy of the iterator +// If created via a pointer, manipulate that pointer and free *p when this dies +// +// Mostly useful for Collection::iterator +// Iterator::Iterator(Collection) + + +template<class T> class Any_Iterator : public Iterator<T> { +public: + Any_Iterator(Collection<T> &c); + Any_Iterator(const Iterator<T> &i); // copy of i + + virtual ~Any_Iterator() { delete me; } + + Any_Iterator<T> &operator=(const Any_Iterator<T> &rhs) + { delete me; me = rhs.me->new_copy(); return *this; } + + const T & operator*() const { return *(*me); } + T & operator*() { return *(*me); } + void operator++(int) { (*me)++; } + void operator++() { ++(*me); } + bool live() const { return (*me).live(); } + + Iterator<T> *new_copy() const { return new Any_Iterator<T>((*me).new_copy()); } + +private: + Any_Iterator(Iterator<T> *p) // take over *p, *p MUST BE ON THE HEAP + { me = p; } + friend class Collection<T>; +#if 0 + // Couldn't make this work with g++258 + friend Any_Iterator<T> Collection<T>::any_iterator(); +#endif + Iterator<T> *me; +}; + +template <class T> inline Any_Iterator<T>::Any_Iterator(Collection<T> &c) + { + me = c.new_iterator(); + } + +template <class T> inline Any_Iterator<T>::Any_Iterator(const Iterator<T> &i) + { + me = i.new_copy(); + } + +} // namespace + +#define instantiate_Iterator(T) template class Iterator<T>; +#define instantiate_Generator(T) template class Generator<T>; +#define instantiate_Any_Iterator(T) template class Any_Iterator<T>; \ + instantiate_Iterator(T) + +#endif diff --git a/omegalib/omega_lib/include/basic/Link.h b/omegalib/omega_lib/include/basic/Link.h new file mode 100644 index 0000000..ede7a2b --- /dev/null +++ b/omegalib/omega_lib/include/basic/Link.h @@ -0,0 +1,98 @@ +#if ! defined _Link_h +#define _Link_h 1 + +#include <basic/Iterator.h> +#include <stddef.h> + +namespace omega { + +// By default, if ndebug is not set, do not do free list + +#if ! defined ListElementFreeList +#if ! defined NDEBUG || defined ASSERTIONS_ANYWAY +#define ListElementFreeList 0 +#else +#define ListElementFreeList 1 +#endif +#endif + +/* + List_Element: one item in a list and the pointer to the next. + Each such object should be pointed to by either exactly one + other List_Element or by some other pointer(s), exactly one + of which will delete the List_Element. + ListElements should ONLY be allocated on the heap. + */ + +#if ListElementFreeList + // g++ 2.5.8 does not allow static data in template classes, so... + extern void *kludgy_List_Element_new(size_t size); + extern void kludgy_List_Element_delete(void *ptr, size_t size); +#endif + +template <class T> class List_Element { +public: +#if ListElementFreeList + void *operator new(size_t size) + { + return kludgy_List_Element_new(size); + } + void operator delete(void *ptr, size_t size) + { + kludgy_List_Element_delete(ptr, size); + } +#endif + + T head; + List_Element<T> *tail; + + List_Element() { + tail = 0; + } + List_Element(T h, List_Element<T> * t) { + head = h; + tail = t; + } + List_Element(const List_Element<T> & L) { + head = L.head; + if (L.tail) tail = new List_Element<T>(*L.tail); + else tail = 0; + } + List_Element & operator=(const List_Element<T> &L) { + if (this != &L) { + head = L.head; + if (tail) delete tail; + if (L.tail) tail = new List_Element<T>(*L.tail); + else tail = 0; + } + return *this; + } + virtual ~List_Element() { // virtual ensures 2nd arg of delete is right + delete tail; + } +}; + + + +template<class T> class List_Element_Iterator : public Iterator<T> { +public: + List_Element_Iterator(List_Element<T>* j) { i = j; } + virtual const T & operator*() const { return i->head; } + virtual T & operator*() { return i->head; } + virtual void operator++(int) { i = i->tail; } + virtual void operator++() { i = i->tail; } + virtual bool live() const { return i != 0; } + Iterator<T> * new_copy() const { return new List_Element_Iterator<T>(i);} + +protected: + List_Element<T> *i; +}; + +} // namespace + +#define instantiate_Only_List_Element(T) template class List_Element<T>; \ + template class List_Element_Iterator<T>; +#define instantiate_List_Element(T) instantiate_Only_List_Element(T)\ + instantiate_Collection(T) + +#endif diff --git a/omegalib/omega_lib/include/basic/List.c b/omegalib/omega_lib/include/basic/List.c new file mode 100644 index 0000000..f05e0de --- /dev/null +++ b/omegalib/omega_lib/include/basic/List.c @@ -0,0 +1,149 @@ +#include <assert.h> + +namespace omega { + +template<class T> List_Iterator<T>::List_Iterator(List<T> &l) +: List_Element_Iterator<T>(l.contents) {} + +template<class T> List_Iterator<T>::List_Iterator(const List<T> &l) +: List_Element_Iterator<T>(l.contents) {} + +template<class T> List_Iterator<T>::List_Iterator() +: List_Element_Iterator<T>(0) {} + +template<class T> Iterator<T> *List<T>::new_iterator() +{ + return new List_Iterator<T>(*this); +} + +template<class T> const T &List<T>::operator[](int i) const +{ + assert(i > 0 && "Subscript out of bounds"); + List_Iterator<T> p(*this); + + while(--i > 0 && p) + p++; + + if (p) + return *p; + else + return *((T *)0); +} + +template<class T> T &List<T>::operator[](int i) +{ + assert(i > 0 && "Subscript out of bounds"); + List_Iterator<T> p(*this); + + while(--i > 0 && p) + p++; + + if (p) + return *p; + else + return *((T *)0); +} + +template<class T> int List<T>::index(const T &item) const +{ + List_Iterator<T> p(*this); + int i = 1; + + while(p && *p != item) + { + p++; + i++; + } + + if (p) + return i; + else + return 0; +} + +template<class T> int List<T>::size() const + { + int i = 0; + List_Element<T> * p = contents; + while (p) + { + p = p->tail; + i++; + } + return i; + } + +template<class T> T &List<T>::front() const + { + return contents->head; + } + +template<class T> T List<T>::remove_front() + { + List_Element<T> *frunt = contents; + contents = contents->tail; + T fruntT = frunt->head; + frunt->tail = 0; + delete frunt; + return fruntT; + } + +template<class T> void List<T>::prepend(const T &item) + { + contents = new List_Element<T>(item, contents); + } + + +template<class T> void List<T>::append(const T &item) + { + *(end()) = new List_Element<T>(item, 0); + } + +template<class T> void List<T>::ins_after(List_Iterator<T> i, + const T &item) + { +#if ! defined NDEBUG + for (List_Element<T> *e = contents; e != &(i.element()); e=e->tail) + { + assert(e); + } +#endif + i.element().tail = new List_Element<T>(item, i.element().tail); + } + +template<class T> void List<T>::del_front() + { + List_Element<T> *e = contents; + contents = contents->tail; + e->tail = 0; + delete e; + } + +template<class T> void List<T>::del_after(List_Iterator<T> i) + { +#if ! defined NDEBUG + for (List_Element<T> *e0 = contents; e0 != &(i.element()); e0=e0->tail) + { + assert(e0); + } +#endif + List_Element<T> *e = i.element().tail; + i.element().tail = e->tail; + e->tail = 0; + delete e; + } + +template<class T> void List<T>::clear() + { + delete contents; + contents = 0; + } + +template<class T> void List<T>::join(List<T> &consumed) + { + List_Element<T> *e = consumed.contents; + consumed.contents = 0; + *(end()) = e; + } + +} // namespace diff --git a/omegalib/omega_lib/include/basic/List.h b/omegalib/omega_lib/include/basic/List.h new file mode 100644 index 0000000..c6fc062 --- /dev/null +++ b/omegalib/omega_lib/include/basic/List.h @@ -0,0 +1,95 @@ +#if ! defined _List_h +#define _List_h 1 + +/* + * Linked lists with an interface like a bit of libg++'s SLList class + */ + + +#if 0 +#include <basic/assert.h> /* List requires assert which needs Exit which */ +#endif /* needs List! just include assert in List.c */ +#include <stdio.h> // for NULL +#include <basic/Iterator.h> +#include <basic/Collection.h> +#include <basic/Link.h> + +namespace omega { + +template<class T> class List_Iterator; + +// +// indexing of Lists starts at 1, index == 0 means not there +// + +template<class T> class List : public Sequence<T> { +public: + List(const List<T> &l) + { contents = l.contents ? new List_Element<T>(*l.contents) : 0; } + List() { contents = 0; } + virtual ~List() { delete contents; } + + Iterator<T> *new_iterator(); + const T &operator[](int) const; + T &operator[](int); + + int index(const T &) const; + + int size() const; + int length() const { return size(); } + bool empty() const { return size() == 0; } + + T &front() const; + +// insertion/deletion on a list invalidates any iterators +// that are on/after the element added/removed + + T remove_front(); + + void prepend(const T &item); + void append(const T &item); + void ins_after(List_Iterator<T> i, const T &item); + + void del_front(); + void del_after(List_Iterator<T> i); + void clear(); + + void join(List<T> &consumed); + +private: + friend class List_Iterator<T>; + List_Element<T> **end() + { + List_Element<T> **e = &contents; + while (*e) + e = &((*e)->tail); + return e; + } + + List_Element<T> *contents; +}; + + +template<class T> class List_Iterator : public List_Element_Iterator<T> { +public: + List_Iterator(List<T> &l); + List_Iterator(const List<T> &l); + List_Iterator(); +private: + List_Element<T> &element() { return *List_Element_Iterator<T>::i; } ; + friend class List<T>; +}; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/List.c> +#endif + +#define instantiate_List(T) template class List<T>; \ + template class List_Iterator<T>; \ + instantiate_Only_List_Element(T) \ + instantiate_Sequence(T) + + +#endif diff --git a/omegalib/omega_lib/include/basic/Map.c b/omegalib/omega_lib/include/basic/Map.c new file mode 100644 index 0000000..69cc3f7 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Map.c @@ -0,0 +1,63 @@ +namespace omega { + +template<class K, class V> MapElement<K,V>:: MapElement(const MapElement<K,V>& M) { + if (M.tail) tail = new MapElement<K,V>(*M.tail); + else tail = 0; + k = M.k; + v = M.v; + } + +template<class K, class V> MapElement<K,V> & + MapElement<K,V>:: operator=(const MapElement<K,V>& M) { + if (this != &M) { + if (tail) delete tail; + if (M.tail) tail = new MapElement<K,V>(*M.tail); + else tail = 0; + k = M.k; + v = M.v; + } + return *this; + } + + + + +#if ! defined linux +template <class K, class V> Map <K,V>::Map(const V &default_value) +#else +template <class K, class V> Map <K,V>::Map(V default_value) +#endif + : _default_value(default_value) + { + contents = 0; + } + +template <class K, class V> Map <K,V>::~Map() + { + delete contents; + } + +template <class K, class V> V Map<K,V>::operator()(K k) const { + MapElement <K,V> * P = contents; + while (P) { + if (P->k == k) return P->v; + P = P->tail; + }; + return _default_value; + } + +template <class K, class V> V & Map<K,V>::operator[](K k) { + MapElement <K,V> * P = contents; + while (P) { + if (P->k == k) return P->v; + P = P->tail; + }; + P = new MapElement <K,V>; + P->k = k; + P->v = _default_value; + P->tail = contents; + contents = P; + return P->v; + } + +} // namespace diff --git a/omegalib/omega_lib/include/basic/Map.h b/omegalib/omega_lib/include/basic/Map.h new file mode 100644 index 0000000..f94a10c --- /dev/null +++ b/omegalib/omega_lib/include/basic/Map.h @@ -0,0 +1,68 @@ +#if ! defined _Map_h +#define _Map_h 1 + +#include <basic/Link.h> +#include <stdio.h> // for NULL + +namespace omega { + +#define foreach_map(k,K,v,V,M,A) {for (omega::MapElementIterator<K,V> __M_##k = (M).iterator();__M_##k;__M_##k++) {K & k = *__M_##k; V & v = __M_##k.value(); A;}} + +template <class K, class V> class MapElement { +public: + K k; + V v; + MapElement<K,V> *tail; + MapElement(const MapElement<K,V>&); + MapElement() {} + MapElement & operator=(const MapElement<K,V>&); + ~MapElement() { delete tail; } +}; + +template<class K, class V> class MapElementIterator { +public: + MapElementIterator(MapElement<K,V>* j) { i = j;} + virtual const K & operator*() const { return i->k; } + virtual K & operator*() { return i->k;} + virtual const V & value() const { return i->v; } + virtual V & value() { return i->v; } + virtual void operator++(int) { i = i->tail; } + virtual void operator++() { i = i->tail; } + virtual bool live() const { return i != NULL; } + operator bool() const { return live(); } +protected: +MapElement<K,V> *i; +}; + +template <class K, class V> class Map { +public: +#if ! defined linux + Map(const V &default_value); +#else + // work around for '386 g++ on Linux + Map(V default_value); +#endif + ~Map(); + MapElementIterator<K,V> iterator() + {return MapElementIterator<K,V>(contents);} + int empty() const {return contents == NULL;} + V operator()(K) const; + V& operator[](K); +private: + MapElement<K,V> * contents; + V _default_value; +}; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/Map.c> +#endif + +#define instantiate_Map(T1,T2) template class Map<T1,T2>; \ + template class MapElement<T1,T2>; \ + template class MapElementIterator<T1,T2>; +#define instantiate_MapElement(T1,T2) instantiate_Map(T1,T2) +#define instantiate_MapElementIterator(T1,T2) instantiate_Map(T1,T2) + +#endif diff --git a/omegalib/omega_lib/include/basic/Section.c b/omegalib/omega_lib/include/basic/Section.c new file mode 100644 index 0000000..754e002 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Section.c @@ -0,0 +1,79 @@ +#include <assert.h> + +namespace omega { + +template <class T> Section<T>::Section(Sequence<T> *s, int start, int length) + { + assert(s->size() >= start-1 + length); + it = s; + _start = start; + _length = length; + } + +template <class T> Iterator<T> *Section<T>::new_iterator() + { + return new Section_Iterator<T>(*this); + } + +template <class T> const T &Section<T>::operator[](int i) const + { + assert(1 <= i && i <= size()); + return (*it)[i+(_start-1)]; + } + +template <class T> T &Section<T>::operator[](int i) + { + assert(1 <= i && i <= size()); + return (*it)[i+(_start-1)]; + } + +template <class T> int Section<T>::index(const T &var) const + { + int i; + for (i=1; i<=size(); i++) + if ((*this)[i] == var) + return i; + return 0; + } + +template <class T> int Section<T>::size() const + { + return _length; + } + + +template <class T> Section_Iterator<T>::Section_Iterator(Section<T> &sec) + { + it = sec.it->new_iterator(); + for (int i = 1; i < sec._start; i++) + (*it)++; + remaining = sec.size(); + } + + +template <class T> Section_Iterator<T>::Section_Iterator(const Section_Iterator<T> &si) : it(si.it), remaining(si.remaining) {} + + +template <class T> void Section_Iterator<T>::operator++() + { this->operator++(0); } + +template <class T> void Section_Iterator<T>::operator++(int) + { + if (remaining > 0) + { + (*it)++; + remaining--; + } + } + +template <class T> bool Section_Iterator<T>::live() const + { + return (remaining > 0); + } + +template <class T> Iterator<T> *Section_Iterator<T>::new_copy() const + { + return new Section_Iterator<T>(*this); + } + +} // namespace diff --git a/omegalib/omega_lib/include/basic/Section.h b/omegalib/omega_lib/include/basic/Section.h new file mode 100644 index 0000000..60821d1 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Section.h @@ -0,0 +1,63 @@ +#if ! defined _Section_h +#define _Section_h 1 +/* + Section of an existing collection viewed as a collection + */ + +#include <basic/Collection.h> + +namespace omega { + +template<class T> class Section_Iterator; + +template <class T> class Section : public Sequence<T> { +public: + Section(Sequence<T> *, int start, int length); + + Iterator<T> *new_iterator(); + + const T &operator[](int) const; + T &operator[](int); + + int index(const T &) const; + int size() const; + + friend class Section_Iterator<T>; + +private: + Sequence<T> *it; + int _start, _length; +}; + +template <class T> class Section_Iterator : public Iterator<T> { +public: + Section_Iterator(Section<T> &sec); + virtual ~Section_Iterator() { delete it; } + + const T & operator*() const { return *(*it); } + T & operator*() { return *(*it); } + + void operator++(int); + void operator++(); + + bool live() const; + Iterator<T> *new_copy() const; + +private: + Section_Iterator(const Section_Iterator<T> &si); + Iterator<T> *it; + int remaining; +}; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/Section.c> +#endif + +#define instantiate_Section(T) template class Section<T>; \ + template class Section_Iterator<T>; \ + instantiate_Sequence(T) +#define instantiate_Section_Iterator(T) instantiate_Section(T) + +#endif diff --git a/omegalib/omega_lib/include/basic/SimpleList.c b/omegalib/omega_lib/include/basic/SimpleList.c new file mode 100644 index 0000000..da7de9b --- /dev/null +++ b/omegalib/omega_lib/include/basic/SimpleList.c @@ -0,0 +1,105 @@ +namespace omega { + +template<class T> Simple_List_Iterator<T>::Simple_List_Iterator(Simple_List<T> &l) +: List_Element_Iterator<T>(l.contents) {} + +template<class T> Simple_List_Iterator<T>::Simple_List_Iterator(const Simple_List<T> &l) +: List_Element_Iterator<T>(l.contents) {} + +template<class T> Simple_List_Iterator<T>::Simple_List_Iterator() +: List_Element_Iterator<T>(0) {} + +template<class T> Iterator<T> *Simple_List<T>::new_iterator() +{ + return new Simple_List_Iterator<T>(*this); +} + +template<class T> const T &Simple_List<T>::operator[](int i) const +{ + Simple_List_Iterator<T> p(*this); + + while(--i > 0 && p) + p++; + + if (p) + return *p; + else + return *((T *)0); +} + +template<class T> T &Simple_List<T>::operator[](int i) +{ + Simple_List_Iterator<T> p(*this); + + while(--i > 0 && p) + p++; + + if (p) + return *p; + else + return *((T *)0); +} + + +template<class T> int Simple_List<T>::size() const + { + int i = 0; + List_Element<T> * p = contents; + while (p) + { + p = p->tail; + i++; + } + return i; + } + +template<class T> T &Simple_List<T>::front() const + { + return contents->head; + } + +template<class T> T Simple_List<T>::remove_front() + { + List_Element<T> *frunt = contents; + contents = contents->tail; + T fruntT = frunt->head; + frunt->tail = 0; + delete frunt; + return fruntT; + } + +template<class T> void Simple_List<T>::prepend(const T &item) + { + contents = new List_Element<T>(item, contents); + } + + +template<class T> void Simple_List<T>::append(const T &item) + { + *(end()) = new List_Element<T>(item, 0); + } + + +template<class T> void Simple_List<T>::del_front() + { + List_Element<T> *e = contents; + contents = contents->tail; + e->tail = 0; + delete e; + } + + +template<class T> void Simple_List<T>::clear() + { + delete contents; + contents = 0; + } + +template<class T> void Simple_List<T>::join(Simple_List<T> &consumed) + { + List_Element<T> *e = consumed.contents; + consumed.contents = 0; + *(end()) = e; + } + +} // namespace diff --git a/omegalib/omega_lib/include/basic/SimpleList.h b/omegalib/omega_lib/include/basic/SimpleList.h new file mode 100644 index 0000000..a08b307 --- /dev/null +++ b/omegalib/omega_lib/include/basic/SimpleList.h @@ -0,0 +1,93 @@ +#if ! defined _Simple_List_h +#define _Simple_List_h 1 + +/* + * Linked lists with an interface like a bit of libg++'s SLSimple_List class + */ + +#include <assert.h> +#include <basic/Iterator.h> +#include <basic/Collection.h> +#include <basic/Link.h> + +namespace omega { + +#define Simple_List Omega_Simple_List +#define Simple_List_Iterator Omega_Simple_List_Iterator + +template<class T> class Simple_List_Iterator; + +// A TEMPORARY HACK - ERROR IF YOU TRY TO USE "INDEX" - FERD + +template<class T> class Simple_List : public Sequence<T> { +public: + Simple_List(const Simple_List<T> &l) + { contents = l.contents ? new List_Element<T>(*l.contents) : 0; } + Simple_List() { contents = 0; } + virtual ~Simple_List() { delete contents; } + + Iterator<T> *new_iterator(); + const T &operator[](int) const; + T &operator[](int); + + + int size() const; + int length() const { return size(); } + int empty() const { return size() == 0; } + + T &front() const; + +// insertion/deletion on a list invalidates any iterators +// that are on/after the element added/removed + + T remove_front(); + + void prepend(const T &item); + void append(const T &item); + + void del_front(); + void clear(); + + void join(Simple_List<T> &consumed); + + int index(const T &) const { + assert(0&&"ILLEGAL SimpleList operation\n"); + return -1; + } + +private: + friend class Simple_List_Iterator<T>; + List_Element<T> **end() + { + List_Element<T> **e = &contents; + while (*e) + e = &((*e)->tail); + return e; + } + + List_Element<T> *contents; +}; + + +template<class T> class Simple_List_Iterator : public List_Element_Iterator<T> { +public: + Simple_List_Iterator(Simple_List<T> &l); + Simple_List_Iterator(const Simple_List<T> &l); + Simple_List_Iterator(); +private: + List_Element<T> &element() { return *this->i; } ; + friend class Simple_List<T>; +}; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/SimpleList.c> +#endif + +#define instantiate_Simple_List(T) template class Simple_List<T>; \ + template class Simple_List_Iterator<T>; \ + instantiate_Only_List_Element(T) \ + instantiate_Sequence(T) + +#endif diff --git a/omegalib/omega_lib/include/basic/Tuple.c b/omegalib/omega_lib/include/basic/Tuple.c new file mode 100644 index 0000000..ce99e82 --- /dev/null +++ b/omegalib/omega_lib/include/basic/Tuple.c @@ -0,0 +1,254 @@ +/* class Tuple */ + +// THESE FIRST TWO REALLY SHOULD BE INLINE BUT IT BREAKS CFRONT: + +namespace omega { + +template<class T> T &Tuple<T>::operator[](int index) + { + assert(1 <= index && index <= sz); return data[index-1]; + } + +template<class T> const T &Tuple<T>::operator[](int index) const + { + assert(1 <= index && index <= sz); return data[index-1]; + } + + +template<class T> Tuple<T>::~Tuple() + { + if (data) + delete [] data; + } + +template<class T> Tuple<T>::Tuple() : sz(0), alloc_sz(0), + prealloc_min(20),prealloc_pad(5), data(0) +{ + // nothing needs be done + } + +template<class T> Tuple<T>::Tuple(int size) : sz(size), + prealloc_min(20),prealloc_pad(5) +{ + if (sz > 0) + { + alloc_sz = prealloc_size(sz); + data = new T[alloc_sz]; + assert(alloc_sz >= sz); + //Need some handling for out of memory. + assert (data!=0); + } + else { + alloc_sz = 0; + data = 0; + } +} + + +template<class T> Tuple<T>::Tuple(const Tuple<T>& t) + : sz(t.sz), alloc_sz(t.alloc_sz), prealloc_min(20),prealloc_pad(5) +{ + if (sz > 0) { + data = new T[alloc_sz]; + assert (data!=0); + assert (alloc_sz >= sz); + for (int i=0; i<sz; i++) + data[i] = t.data[i]; + } else { + data = 0; + alloc_sz = 0; // THis might not be 0 if it was a "clear"ed Tuple +// assert(alloc_sz == 0); + } +} + + +template<class T> Tuple<T>& Tuple<T>::operator=(const Tuple<T>& t) +{ + if (this != &t) { // Delete this + if (data) + delete [] data; + sz = t.sz; + alloc_sz = t.alloc_sz; + assert(alloc_sz >= sz); + if (sz > 0) { // Copy old + data = new T[alloc_sz]; + assert (data!=0); + for (int i=0; i<sz; i++) + data[i] = t.data[i]; + } else { + data=0; + alloc_sz = 0; // THis might not be 0 if it was a "clear"ed Tuple +// assert(alloc_sz == 0); + } + } + return *this; +} + + +template<class T> void Tuple<T>::reallocate(const int req_size) +{ + if (alloc_sz >= req_size) { // if (sz >= req_size), does this. + sz = req_size; + return; + } + alloc_sz = prealloc_size(req_size); + T* tmp_data = new T[alloc_sz]; + for(int i=0;i<sz;i++) + tmp_data[i] = data[i]; + delete [] data; + data = tmp_data; + sz = req_size; + assert(alloc_sz >= req_size); +} + +template<class T> void Tuple<T>::delete_last() +{ +assert(sz > 0); +sz --; +} + +template<class T> void Tuple<T>::append(const T &v) +{ + // Check if reallocation is necessary. + if (sz == 0) { // Empty Tuple + assert(alloc_sz >= 0); // May be nonzero for cleared tuple + + if(alloc_sz == 0) { // If it's > 1 no allocation is necessary + alloc_sz = prealloc_size(1); + data = new T[alloc_sz]; + } + assert (alloc_sz > 0 && data != 0); + } else { + if(sz == alloc_sz) { // Requires new allocation + alloc_sz = realloc_size(alloc_sz); + T * data_tmp = new T[alloc_sz]; + assert (data_tmp!=0); + assert (alloc_sz > sz); + for (int i=0; i<sz; i++) + data_tmp[i] = data[i]; + delete [] data; + data=data_tmp; + } // Otherwise big enough, no reallocation necessary + } + // Make assignment + assert(alloc_sz >= sz); + data[sz++] = v; +} + +template<class T> void Tuple<T>::append(const Tuple<T>& t) { + int old_sz = sz; + reallocate(t.size()+size()); + assert(alloc_sz >= sz); + for(int i=0; i<t.sz; i++) + data[i+old_sz] = t.data[i]; +} + +template<class T> void Tuple<T>::join(Tuple<T>& t) { + int old_sz = sz; + reallocate(t.size()+size()); + assert(alloc_sz >= sz); + for(int i=0; i<t.sz; i++) + data[i+old_sz] = t.data[i]; + t.clear(); +} + +template<class T> void Tuple<T>::clear() { if (sz) delete [] data; data = 0; alloc_sz = 0; sz = 0; } + +template<class T> int Tuple<T>::empty() const { return (sz == 0); } + +template<class T> Iterator<T> *Tuple<T>::new_iterator() +{ + return new Tuple_Iterator<T>(*this); +} + +template<class T> int Tuple<T>::index(const T & var) const +/* returns index or 0 if var isn't in the tuple */ +{ + int i; + for (i=0; i<sz; i++) + if (data[i]== var) + return i+1; + return 0; +} + +template<class T> bool Tuple<T>::operator == (const Tuple<T>& b) const +{ + int i; + if (sz != b.size()) return false; + for (i=0; i<sz; i++) + if (!(data[i] == b[i+1])) return false; + return true; +} + +/* class Tuple_Iterator */ + +template<class T> Tuple_Iterator<T>::Tuple_Iterator(const Tuple<T> &tpl) : +current(tpl.data), lastptr(tpl.data+tpl.sz-1), firstptr(tpl.data), sz(tpl.sz) +{ +} + +template<class T> Tuple_Iterator<T>::Tuple_Iterator(T * cr, T *frst, T * lst, + int insz) + : current(cr), lastptr(lst), firstptr(frst), sz(insz) +{ +} + +template<class T> const T & Tuple_Iterator<T>::operator*() const +{ + assert (current<=lastptr && current>=firstptr); + return *current; +} + +template<class T> T & Tuple_Iterator<T>::operator*() +{ + assert (current<=lastptr && current >=firstptr); + return *current; +} + +template<class T> void Tuple_Iterator<T>::operator++(int) +{ + current++; +} + +template<class T> void Tuple_Iterator<T>::operator++() +{ + current++; +} + +template<class T> void Tuple_Iterator<T>::operator--(int) +{ + current--; +} + +template<class T> void Tuple_Iterator<T>::operator--() +{ + current--; +} + +template<class T> void Tuple_Iterator<T>::set_to_last() +{ + current = lastptr; +} + +template<class T> void Tuple_Iterator<T>::set_to_first() +{ + current = firstptr; +} + +template<class T> void Tuple_Iterator<T>::set_position(const int req_pos) +{ + assert(req_pos <= sz && 1 <= req_pos); + current = firstptr + (req_pos - 1); +} + + +template<class T> bool Tuple_Iterator<T>::live() const +{ + return (current !=0 && current<=lastptr && current >= firstptr); +} + +template<class T> Iterator<T> *Tuple_Iterator<T>::new_copy() const { + return new Tuple_Iterator<T>(current, firstptr, lastptr, sz); +} + +} // namespace diff --git a/omegalib/omega_lib/include/basic/Tuple.h b/omegalib/omega_lib/include/basic/Tuple.h new file mode 100644 index 0000000..28e83bd --- /dev/null +++ b/omegalib/omega_lib/include/basic/Tuple.h @@ -0,0 +1,90 @@ +#if !defined _Already_defined_tuple +#define _Already_defined_tuple + +#include <stdio.h> + +#include <basic/Collection.h> +#include <basic/Iterator.h> +#include <basic/util.h> + +namespace omega { + +template<class T> class Tuple_Iterator; + +// TUPLES ARE INDEXED STARTING AT 1 +// index\(i\) == 0 MEANS i IS NOT IN THE TUPLE + +template <class T> class Tuple : public Sequence<T> { +public: + Tuple(); + Tuple(int size); + Tuple (const Tuple<T>& tpl); + virtual ~Tuple(); + Tuple<T>& operator=(const Tuple<T>& tpl); + int size() const { return sz; } + int length() const { return sz; } + bool operator==(const Tuple<T> &b) const; + void reallocate(const int); + void delete_last(); + void append(const Tuple<T> &v); + void append(const T &v); + void join(Tuple<T> &v); + void clear(); + int empty() const; + + Iterator<T> *new_iterator(); + + virtual T &operator[](int index); + virtual const T &operator[](int index) const; + + int index(const T &) const; + + friend class Tuple_Iterator<T>; + +private: + int prealloc_size(const int req_size) + { return max(req_size+prealloc_pad,prealloc_min); } + int realloc_size(const int oldsize) { return 2*oldsize; } + + + int sz, alloc_sz; // Number of elements, size of allocated array + int prealloc_min,prealloc_pad; // These should be static, but that + // causes portability prob. for initialization + +protected: + T * data; +}; + +template <class T> class Tuple_Iterator : public Iterator <T> { +public: + Tuple_Iterator(const Tuple<T> &tpl); + const T & operator*() const; + T & operator*(); + void set_position(const int req_pos); + void operator++(int); + void operator++(); + void operator--(int); + void operator--(); + void set_to_last(); + void set_to_first(); +// void set_position(const int req_pos); Don't do this, compiler bug + bool live() const; + Iterator<T> *new_copy() const; + +private: + Tuple_Iterator(T * cr, T * frst, T *lst, int insz); + T * current, * lastptr, *firstptr; + int sz; +}; + +} // namespace + +#if ! defined DONT_INCLUDE_TEMPLATE_CODE +#include <basic/Tuple.c> +#endif + +#define instantiate_Tuple(T) template class Tuple<T>; \ + template class Tuple_Iterator<T>; \ + instantiate_Sequence(T) + +#endif diff --git a/omegalib/omega_lib/include/basic/boolset-test.cc b/omegalib/omega_lib/include/basic/boolset-test.cc new file mode 100755 index 0000000..5b68220 --- /dev/null +++ b/omegalib/omega_lib/include/basic/boolset-test.cc @@ -0,0 +1,72 @@ +#include "boolset.h" +#include <iostream> + +using namespace omega; + +void foo(const BoolSet<> &B) { + for (BoolSet<>::const_iterator i = B.begin(); i != B.end(); i++) + std::cout << *i << ' '; + std::cout << std::endl; +} + +int main() { + BoolSet<> A(13); + + A.set(2); + std::cout << A << std::endl; + + A.set_all(); + std::cout << A << std::endl; + + A.unset_all(); + std::cout << A << std::endl; + + A.set(2); + A.set(4); + + BoolSet<> B(13); + B.set(2); + + std::cout << "A: " << A << std::endl; + std::cout << "B: " << B << std::endl; + + std::cout << A.imply(B) << std::endl; + std::cout << B.imply(A) << std::endl; + + B.set(10); + std::cout << (A|B) << std::endl; + std::cout << (A&B) << std::endl; + + BoolSet<> C(3); + C.set(0); + std::cout << (A|C) << std::endl; + std::cout << ~(A|C) << std::endl; + + B = BoolSet<>(23); + std::cout << "test iterator\n"; + B.set(12); + B.set(11); + B.set(0); + std::cout << B << std::endl; + for (BoolSet<>::const_iterator i = B.begin(); i != B.end(); i++) { + std::cout << *i << ' '; + if (*i == 11) + B.unset(*i); + } + std::cout << std::endl; + std::cout << B << std::endl; + std::cout << std::endl; + foo(B); + + std::cout << ~BoolSet<>(5) << std::endl; + + std::cout << "------\n"; + B.dump(); + std::cout << std::endl << *(B.begin()+1) << std::endl; + + for (BoolSet<>::iterator i = B.begin(); i != B.end(); i++) + for (BoolSet<>::iterator j = i; j != B.end(); j++) + if (j == i) + std::cout << "ehh-"; + +} diff --git a/omegalib/omega_lib/include/basic/omega_error.h b/omegalib/omega_lib/include/basic/omega_error.h new file mode 100644 index 0000000..e342efb --- /dev/null +++ b/omegalib/omega_lib/include/basic/omega_error.h @@ -0,0 +1,14 @@ +#ifndef OMEGA_ERROR_H +#define OMEGA_ERROR_H + +namespace omega { + +struct presburger_error: public std::runtime_error { + presburger_error(const std::string &msg): std::runtime_error("presburger error: " + msg) {} +}; + + + +} +#endif + diff --git a/omegalib/omega_lib/include/basic/util.h b/omegalib/omega_lib/include/basic/util.h new file mode 100644 index 0000000..4e807cd --- /dev/null +++ b/omegalib/omega_lib/include/basic/util.h @@ -0,0 +1,263 @@ +#if ! defined Already_Included_Util +#define Already_Included_Util + +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include <string> +#include <sstream> +#include <stdexcept> + +namespace omega { + +#define LONG_LONG_COEF 1 + +#if LONG_LONG_COEF +#if defined BOGUS_LONG_DOUBLE_COEF +typedef long double coef_t; // type of coefficients +#define coef_fmt "%llf" +#define posInfinity (1e+24) +#define negInfinity (-1e+24) +#else +#ifdef WIN32 +typedef _int64 coef_t; // type of coefficients +#else +typedef long long coef_t; +#endif +#define coef_fmt "%lld" +#define posInfinity (0x7ffffffffffffffLL) +#define negInfinity (-0x7ffffffffffffffLL) +#endif +#else +typedef int coef_t; // type of coefficients +#define coef_fmt "%d" +#define posInfinity (0x7ffffff) +#define negInfinity (-0x7ffffff) +#endif + + +template<typename T> inline const T& max(const T &x, const T &y) { + if (x >= y) return x; else return y; +} + + +template<typename T> inline const T& max(const T &x, const T &y, const T &z) { + return max(x, max(y, z)); +} + +template<typename T> inline const T& min(const T &x, const T &y) { + if (x <= y) return x; else return y; +} + +template<typename T> inline const T& min(const T &x, const T &y, const T &z) { + return min(x, min(y, z)); +} + +template<class T> inline void set_max(T &m, const T &x) { + if (m < x) m = x; +} + +template<class T> inline void set_min(T &m, const T &x) { + if (m > x) m = x; +} + +/* template<class T> inline void swap(T &i, T &j) { */ +/* T tmp; */ +/* tmp = i; */ +/* i = j; */ +/* j = tmp; */ +/* } */ + +/* template<class T> inline T copy(const T &t) { return t; } */ + + +/* inline coef_t check_pos_mul(coef_t x, coef_t y) { */ +/* if (y >= 48051280 && y < posInfinity) */ +/* fprintf(stderr, "%d %d\n", x, y); */ +/* /\* #if !defined NDEBUG *\/ */ +/* /\* if (x != 0) *\/ */ +/* /\* assert(((MAXINT)/4) / x > y); *\/ */ +/* /\* #elif defined STILL_CHECK_MULT *\/ */ +/* /\* if (x != 0 && !(((MAXINT)/4) / x > y)) { *\/ */ +/* /\* assert(0&&"Integer overflow during multiplication (util.h)"); *\/ */ +/* /\* } *\/ */ +/* /\* #endif *\/ */ +/* #if !defined NDEBUG */ +/* if (x != 0 && y != 0) */ +/* assert(x*y > 0); */ +/* #elif defined STILL_CHECK_MULT */ +/* if (x != 0 && y != 0 && x*y < 0) */ +/* assert(0&&"Integer overflow during multiplication (util.h)"); */ +/* #endif */ +/* return x * y; */ +/* } */ + + +/* inline int */ +/* check_pos_mul(int x, int y) { */ +/* #if !defined NDEBUG */ +/* if (x != 0) */ +/* assert(((posInfinity)/4) / x > y); */ +/* #elif defined STILL_CHECK_MULT */ +/* if (x != 0 && !(((posInfinity)/4) / x > y)) { */ +/* assert(0&&"Integer overflow during multiplication (util.h)"); */ +/* } */ +/* #endif */ +/* return x * y; */ +/* } */ + +/* inline LONGLONG */ +/* check_pos_mul(LONGLONG x, LONGLONG y) { */ +/* #if !defined NDEBUG */ +/* if (x != 0) */ +/* assert(((posInfinity)/4) / x > y); */ +/* #elif defined STILL_CHECK_MULT */ +/* if (x != 0 && !(((posInfinity)/4) / x > y)) { */ +/* assert(0&&"Integer overflow during multiplication (util.h)"); */ +/* } */ +/* #endif */ +/* return x * y; */ +/* } */ + +/* inline LONGLONG abs(LONGLONG c) { return (c>=0?c:(-c)); } */ + +template<typename T> inline T check_mul(const T &x, const T &y) { +#if defined NDEBUG && ! defined STILL_CHECK_MULT + return x*y; +#else + if (x == 0 || y == 0) + return 0; + + T z = x*y; + int sign_x = (x>0)?1:-1; + int sign_y = (y>0)?1:-1; + int sign_z = (z>0)?1:-1; + + if (sign_x * sign_y != sign_z) + throw std::overflow_error("coefficient multiply overflow"); + + return z; + + /* if (x > 0) { */ + /* if (y > 0) { */ + /* assert(x*y > 0); */ + /* } */ + /* else */ + /* assert(x*y < 0); */ + /* } */ + /* else { */ + /* if (y > 0) */ + /* assert(x*y < 0); */ + /* else */ + /* assert(x*y > 0); */ + /* } */ + /* return x*y; */ +#endif +} + +template<typename T> inline T abs(const T &v) { + return (v >= static_cast<T>(0))?v:-v; +} + +template<class T> inline T int_div(const T &a, const T &b) { + T result; + assert(b > 0); + if (a>0) result = a/b; + else result = -((-a+b-1)/b); + return result; +} + +template<class T> inline T int_mod(const T &a, const T &b) { + return a-b*int_div(a,b); +} + +template<class T> inline T int_mod_hat(const T &a, const T &b) { + T r; + assert(b > 0); + r = a-b*int_div(a,b); + if (r > -(r-b)) r -= b; + return r; +} + +template<typename T> inline T gcd(T b, T a) {/* First argument is non-negative */ + assert(a >= 0); + assert(b >= 0); + if (b == 1) + return (1); + while (b != 0) { + T t = b; + b = a % b; + a = t; + } + return (a); +} + +template<typename T> inline T lcm(T b, T a) { /* First argument is non-negative */ + assert(a >= 0); + assert(b >= 0); + return check_mul(a/gcd(a,b), b); +} + +template<typename T> T square_root(const T &n, T precision = 1) { + T guess = 1; + + while (true) { + T next_guess = 0.5*(guess+n/guess); + if (abs(next_guess-guess) <= precision) + return next_guess; + else + guess = next_guess; + } +} + +template<typename T> T factor(const T &n) { + assert(n >= 0); + if (n == 1) return 1; + + static int prime[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113}; + + if (n <= 113*113) { + for (int i = 0; i < 30; i++) + if (n % static_cast<T>(prime[i]) == 0) + return static_cast<T>(prime[i]); + + return n; + } + + T i = 1; + T k = 2; + T x = static_cast<T>(rand())%n; + T y = x; + while(i < square_root<float>(n, 1)) { + i++; + x = (x*x-1) % n; + T d = gcd(abs(y-x), n); + if(d != 1 && d != n) + return factor(d); + if(i == k) { + y = x; + k *= 2; + } + } + return n; +} + +/* #define implies(A,B) (A==(A&B)) */ + +template<typename T> std::string to_string(const T &t) { + std::ostringstream ss; + ss << t; + return ss.str(); +} + +template<typename T> T from_string(const std::string &s) { + std::istringstream ss(s); + ss.exceptions(std::ios::failbit); + T t; + ss >> t; + return t; +} + +} // namespace + +#endif diff --git a/omegalib/omega_lib/src/basic/ConstString.cc b/omegalib/omega_lib/src/basic/ConstString.cc new file mode 100644 index 0000000..7d2ec1e --- /dev/null +++ b/omegalib/omega_lib/src/basic/ConstString.cc @@ -0,0 +1,134 @@ +#include <basic/ConstString.h> +#include <stdlib.h> +#include <stdio.h> +#include <assert.h> +#include <string> +#include <string.h> + +/* static const int CS_HashTable_Size = 1000; */ +/* static ConstStringRep *hashTable[CS_HashTable_Size] = {0}; */ + +namespace omega { + +const int CS_HashTable_Size = 1000; +class CS_HashTable { +public: + ConstStringRep *p[CS_HashTable_Size]; + CS_HashTable(); + ~CS_HashTable(); +}; + +namespace { + CS_HashTable hashTable; +} + +CS_HashTable::CS_HashTable() { + for (int i = 0; i < CS_HashTable_Size; i++) + p[i] = NULL; + } + +CS_HashTable::~CS_HashTable() { + for (int i = 0; i < CS_HashTable_Size; i++) { + ConstStringRep *t = p[i]; + while (t != NULL) { + ConstStringRep *tt = t->nextInBucket; + delete []t->name; + delete t; + t = tt; + } + } +} + +Const_String::Const_String() { + rep = 0; +} + +void Const_String::buildRep(const char* t) { + int hash = 0; + const char *s = t; + while (*s != '\0') + hash = hash*33 + *s++; + int hashBucket = hash % CS_HashTable_Size; + if (hashBucket < 0) hashBucket += CS_HashTable_Size; + assert(0 <= hashBucket && hashBucket < CS_HashTable_Size); + ConstStringRep **q = &(hashTable.p[hashBucket]); + ConstStringRep *p = *q; + while (p != 0) { + if (strcmp(p->name,t) == 0) break; + q = &p->nextInBucket; + p = *q; + } + if (p!= 0) rep = p; + else { + rep = new ConstStringRep(t); + *q = rep; + } +} + +Const_String::Const_String(const char * t) { + buildRep(t); +} + +Const_String::Const_String(const std::string &s) { + buildRep(s.c_str()); +} + +Const_String::operator const char*() const { + if (!rep) return 0; + return rep->name; +} + +Const_String::operator std::string() const { + if (!rep) return std::string(""); + return std::string(rep->name); +} + +int Const_String::operator++(int) { + return rep->count++; +} + +int Const_String::operator++() { + return ++rep->count; +} + +int Const_String:: operator--(int) { + return rep->count--; +} + +int Const_String:: operator--() { + return --rep->count; +} + +int operator ==(const Const_String &x, const Const_String &y) { + return x.rep == y.rep; +} + +int operator !=(const Const_String &x, const Const_String &y) { + return x.rep != y.rep; +} + +int operator <(const Const_String &x, const Const_String &y) { + return (strcmp(x.rep->name,y.rep->name) < 0); +} + +int operator >(const Const_String &x, const Const_String &y) { + return (strcmp(x.rep->name,y.rep->name) > 0); +} + +Const_String:: operator int() const { + return rep != 0; +} + +int Const_String::null() const { + return rep == 0; +} + +ConstStringRep:: ConstStringRep(const char *t) { + count = 0; + nextInBucket = 0; + char *s = new char[1+strlen(t)]; + strcpy(s,t); + name = s; +} + +} // namespace diff --git a/omegalib/omega_lib/src/basic/Link.cc b/omegalib/omega_lib/src/basic/Link.cc new file mode 100644 index 0000000..50b9441 --- /dev/null +++ b/omegalib/omega_lib/src/basic/Link.cc @@ -0,0 +1,41 @@ +#include <basic/Link.h> + +namespace omega { + +#if ListElementFreeList + static List_Element<void*> *_kludgy_List_Element_free_list_pointer; +// we rely on the fact that that is initialized to 0 before any +// constructor-based initialization that could call List_Element::new. + + void *kludgy_List_Element_new(size_t size) + { + void *mem; + if (size == sizeof(List_Element<void*>) && + _kludgy_List_Element_free_list_pointer) + { + List_Element<void*> *it = _kludgy_List_Element_free_list_pointer; + _kludgy_List_Element_free_list_pointer = it->tail; + mem = it; + } + else + mem = ::operator new(size); + + return mem; + } + + void kludgy_List_Element_delete(void *ptr, size_t size) + { + if (ptr) + if (size == sizeof(List_Element<void*>)) + { + List_Element<void*> *it = (List_Element<void*> *) ptr; + it->tail = _kludgy_List_Element_free_list_pointer; + _kludgy_List_Element_free_list_pointer = it; + } + else + ::operator delete(ptr); + } + +#endif + +} // namespace diff --git a/omegalib/omega_lib/src/hull_simple.cc b/omegalib/omega_lib/src/hull_simple.cc index 93d8ad3..62dcb26 100755 --- a/omegalib/omega_lib/src/hull_simple.cc +++ b/omegalib/omega_lib/src/hull_simple.cc @@ -14,7 +14,7 @@ #include <assert.h> #include <omega.h> -#include <basic/boolset.h> +#include <basic/BoolSet.h> #include <vector> #include <list> #include <set> diff --git a/omegalib/omega_lib/src/omega_core/oc_exp_kill.cc b/omegalib/omega_lib/src/omega_core/oc_exp_kill.cc index bf3ba19..fdb2718 100644 --- a/omegalib/omega_lib/src/omega_core/oc_exp_kill.cc +++ b/omegalib/omega_lib/src/omega_core/oc_exp_kill.cc @@ -13,7 +13,7 @@ *****************************************************************************/ #include <omega/omega_core/oc_i.h> -#include <basic/boolset.h> +#include <basic/BoolSet.h> #include <vector> namespace omega { diff --git a/omegalib/omega_lib/src/omega_core/oc_quick_kill.cc b/omegalib/omega_lib/src/omega_core/oc_quick_kill.cc index e49aee7..1b988d4 100644 --- a/omegalib/omega_lib/src/omega_core/oc_quick_kill.cc +++ b/omegalib/omega_lib/src/omega_core/oc_quick_kill.cc @@ -15,7 +15,7 @@ #include <omega/omega_core/oc_i.h> #include <vector> #include <algorithm> -#include <basic/boolset.h> +#include <basic/BoolSet.h> namespace omega { diff --git a/omegalib/omega_lib/src/omega_core/oc_simple.cc b/omegalib/omega_lib/src/omega_core/oc_simple.cc index ebbf407..0e492db 100644 --- a/omegalib/omega_lib/src/omega_core/oc_simple.cc +++ b/omegalib/omega_lib/src/omega_core/oc_simple.cc @@ -15,7 +15,7 @@ *****************************************************************************/ #include <omega/omega_core/oc_i.h> -#include <basic/boolset.h> +#include <basic/BoolSet.h> #include <algorithm> #include <vector> |