diff options
Diffstat (limited to 'lout')
| -rw-r--r-- | lout/container.cc | 64 | ||||
| -rw-r--r-- | lout/container.hh | 29 | ||||
| -rw-r--r-- | lout/misc.cc | 26 | ||||
| -rw-r--r-- | lout/misc.hh | 29 | ||||
| -rw-r--r-- | lout/object.cc | 24 | ||||
| -rw-r--r-- | lout/object.hh | 30 |
6 files changed, 141 insertions, 61 deletions
diff --git a/lout/container.cc b/lout/container.cc index deeede57..5e5eda73 100644 --- a/lout/container.cc +++ b/lout/container.cc @@ -190,16 +190,72 @@ void Vector::remove(int pos) */ void Vector::sort() { - qsort(array, numElements, sizeof(Object*), misc::Comparable::compareFun); + qsort (array, numElements, sizeof(Object*), Comparable::compareFun); } - /** - * \bug Not implemented. + * \brief Use binary search to find an element in a sorted vector. + * + * If "mustExist" is true, only exact matches are found; otherwise, -1 + * is returned. If it is false, the position of the next greater + * element is returned, or, if the key is the greatest element, the + * size of the array. (This is the value which can be used for + * insertion; see insertSortet()). */ +int Vector::bsearch(Object *key, bool mustExist) +{ + // The case !mustExist is not handled by bsearch(3), so here is a + // new implementation. + + int high = numElements - 1, low = 0; + + while (true) { + int index = (low + high) / 2; + int c = ((Comparable*) key)->compareTo ((Comparable*)array[index]); + if (c == 0) + return index; + else { + if (low >= high) { + if (mustExist) + return -1; + else + return c > 0 ? index + 1 : index; + } + + if (c < 0) + high = index - 1; + else + low = index + 1; + } + } + + + /* + void *result = ::bsearch (&key, array, numElements, sizeof (Object*), + Comparable::compareFun); + if (result) + return (Object**)result - array; + else + return -1; + */ +} + +Object *Vector::VectorIterator::getNext() +{ + if (index < vector->numElements - 1) + index++; + + return index < vector->numElements ? vector->array[index] : NULL; +} + +bool Vector::VectorIterator::hasNext() +{ + return index < vector->numElements - 1; +} + Collection0::AbstractIterator* Vector::createIterator() { - return NULL; + return new VectorIterator(this); } // ------------ diff --git a/lout/container.hh b/lout/container.hh index f1008e82..c87eb10c 100644 --- a/lout/container.hh +++ b/lout/container.hh @@ -102,11 +102,25 @@ public: */ class Vector: public Collection { + friend class VectorIterator; + private: object::Object **array; int numAlloc, numElements; bool ownerOfObjects; + class VectorIterator: public AbstractIterator + { + private: + Vector *vector; + int index; + + public: + VectorIterator(Vector *vector) { this->vector = vector; index = -1; } + bool hasNext(); + Object *getNext(); + }; + protected: AbstractIterator* createIterator(); @@ -116,12 +130,23 @@ public: void put(object::Object *newElement, int newPos = -1); void insert(object::Object *newElement, int pos); + + /** + * \brief Insert into an already sorted vector. + * + * Notice that insertion is not very efficient, unless the position + * is rather at the end. + */ + inline void insertSorted(object::Object *newElement) + { insert (newElement, bsearch (newElement, false)); } + void remove(int pos); inline object::Object *get(int pos) { return (pos >= 0 && pos < numElements) ? array[pos] : NULL; } inline int size() { return numElements; } void clear(); void sort(); + int bsearch(Object *key, bool mustExist); }; @@ -381,12 +406,16 @@ public: { ((untyped::Vector*)this->base)->put(newElement, newPos); } inline void insert(T *newElement, int pos) { ((untyped::Vector*)this->base)->insert(newElement, pos); } + inline void insertSorted(T *newElement) + { ((untyped::Vector*)this->base)->insertSorted(newElement); } inline void remove(int pos) { ((untyped::Vector*)this->base)->remove(pos); } inline T *get(int pos) { return (T*)((untyped::Vector*)this->base)->get(pos); } inline int size() { return ((untyped::Vector*)this->base)->size(); } inline void clear() { ((untyped::Vector*)this->base)->clear(); } inline void sort() { ((untyped::Vector*)this->base)->sort(); } + inline int bsearch(T *key, bool mustExist) + { return ((untyped::Vector*)this->base)->bsearch(key, mustExist); } }; diff --git a/lout/misc.cc b/lout/misc.cc index f45a3450..d4db609e 100644 --- a/lout/misc.cc +++ b/lout/misc.cc @@ -37,32 +37,6 @@ void init (int argc, char *argv[]) prgName = strdup (argv[0]); } -// ---------------- -// Comparable -// ---------------- - -Comparable::~Comparable() -{ -} - -/** - * \brief This static method may be used as compare function for qsort(3), for - * an array of Object* (Object*[] or Object**). - */ -int Comparable::compareFun(const void *p1, const void *p2) -{ - Comparable **c1 = (Comparable**)p1; - Comparable **c2 = (Comparable**)p2; - if (c1 && c2) - return ((*c1)->compareTo(*c2)); - else if (c1) - return 1; - else if (c2) - return -1; - else - return 0; -} - // ------------------ // StringBuffer diff --git a/lout/misc.hh b/lout/misc.hh index b0c0b2f8..cff8e05b 100644 --- a/lout/misc.hh +++ b/lout/misc.hh @@ -65,35 +65,6 @@ inline int AsciiStrcasecmp(const char *s1, const char *s2) } /** - * \brief Instances of a sub class of this interface may be compared (less, - * greater). - * - * Used for sorting etc. - */ -class Comparable -{ -public: - virtual ~Comparable(); - - /** - * \brief Compare two objects c1 and c2. - * - * return a value < 0, when c1 is less than c2, a value > 0, when c1 - * is greater than c2, or 0, when c1 and c2 are equal. - * - * If also object::Object is implemented, and if c1.equals(c2), - * c1.compareTo(c2) must be 0, but, unlike you may expect, - * the reversed is not necessarily true. This method returns 0, if, - * according to the rules for sorting, there is no difference, but there - * may still be differences (not relevant for sorting), which "equals" will - * care about. - */ - virtual int compareTo(Comparable *other) = 0; - - static int compareFun(const void *p1, const void *p2); -}; - -/** * \brief Simple (simpler than container::untyped::Vector and * container::typed::Vector) template based vector. */ diff --git a/lout/object.cc b/lout/object.cc index 85a908b9..99b5902d 100644 --- a/lout/object.cc +++ b/lout/object.cc @@ -106,6 +106,30 @@ size_t Object::sizeOf() return sizeof(Object*); } +// ---------------- +// Comparable +// ---------------- + +/** + * \brief This static method may be used as compare function for + * qsort(3) and bsearch(3), for an array of Object* (Object*[] or + * Object**). + */ +int Comparable::compareFun(const void *p1, const void *p2) +{ + Comparable *c1 = *(Comparable**)p1; + Comparable *c2 = *(Comparable**)p2; + + if (c1 && c2) + return ((c1)->compareTo(c2)); + else if (c1) + return 1; + else if (c2) + return -1; + else + return 0; +} + // ------------- // Pointer // ------------- diff --git a/lout/object.hh b/lout/object.hh index 9df69987..fd612863 100644 --- a/lout/object.hh +++ b/lout/object.hh @@ -34,6 +34,32 @@ public: }; /** + * \brief Instances of a sub class of may be compared (less, greater). + * + * Used for sorting etc. + */ +class Comparable: public Object +{ +public: + /** + * \brief Compare two objects c1 and c2. + * + * Return a value < 0, when c1 is less than c2, a value > 0, when c1 + * is greater than c2, or 0, when c1 and c2 are equal. + * + * If c1.equals(c2) (as defined in Object), c1.compareTo(c2) must + * be 0, but, unlike you may expect, the reversed is not + * necessarily true. This method returns 0, if, according to the + * rules for sorting, there is no difference, but there may still + * be differences (not relevant for sorting), which "equals" will + * care about. + */ + virtual int compareTo(Comparable *other) = 0; + + static int compareFun(const void *p1, const void *p2); +}; + +/** * \brief An object::Object wrapper for void pointers. */ class Pointer: public Object @@ -63,7 +89,7 @@ public: /** * \brief An object::Object wrapper for int's. */ -class Integer: public Object, misc::Comparable +class Integer: public Comparable { int value; @@ -82,7 +108,7 @@ public: * * As opposed to object::String, the char array is not copied. */ -class ConstString: public Object, misc::Comparable +class ConstString: public Comparable { protected: const char *str; |