diff options
| -rw-r--r-- | lout/container.cc | 10 | ||||
| -rw-r--r-- | lout/container.hh | 28 | ||||
| -rw-r--r-- | lout/object.cc | 31 | ||||
| -rw-r--r-- | lout/object.hh | 40 | ||||
| -rw-r--r-- | test/containers.cc | 15 |
5 files changed, 100 insertions, 24 deletions
diff --git a/lout/container.cc b/lout/container.cc index de36a6f7..77f0e710 100644 --- a/lout/container.cc +++ b/lout/container.cc @@ -188,9 +188,10 @@ void Vector::remove(int pos) /** * Sort the elements in the vector. Assumes that all elements are Comparable's. */ -void Vector::sort() +void Vector::sort(Comparator *comparator) { - qsort (array, numElements, sizeof(Object*), Comparable::compareFun); + Comparator::compareFunComparator = comparator; + qsort (array, numElements, sizeof(Object*), Comparator::compareFun); } /** @@ -202,7 +203,7 @@ void Vector::sort() * size of the array. (This is the value which can be used for * insertion; see insertSortet()). */ -int Vector::bsearch(Object *key, bool mustExist) +int Vector::bsearch(Object *key, bool mustExist, Comparator *comparator) { // The case !mustExist is not handled by bsearch(3), so here is a // new implementation. @@ -213,7 +214,7 @@ int Vector::bsearch(Object *key, bool mustExist) while (true) { int index = (low + high) / 2; - int c = ((Comparable*) key)->compareTo ((Comparable*)array[index]); + int c = comparator->compare (key, array[index]); if (c == 0) return index; else { @@ -233,6 +234,7 @@ int Vector::bsearch(Object *key, bool mustExist) /* + Comparator::compareFunComparator = comparator; void *result = ::bsearch (&key, array, numElements, sizeof (Object*), Comparable::compareFun); if (result) diff --git a/lout/container.hh b/lout/container.hh index c87eb10c..70d443f6 100644 --- a/lout/container.hh +++ b/lout/container.hh @@ -137,16 +137,19 @@ public: * 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)); } + inline void insertSorted(object::Object *newElement, + object::Comparator *comparator = + &object::standardComparator) + { insert (newElement, bsearch (newElement, false, comparator)); } 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); + void sort(object::Comparator *comparator = &object::standardComparator); + int bsearch(Object *key, bool mustExist, + object::Comparator *comparator = &object::standardComparator); }; @@ -406,16 +409,23 @@ 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 insertSorted(T *newElement, + object::Comparator *comparator = + &object::standardComparator) + { ((untyped::Vector*)this->base)->insertSorted(newElement, comparator); } 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); } + inline void sort(object::Comparator *comparator = + &object::standardComparator) + { ((untyped::Vector*)this->base)->sort(comparator); } + inline int bsearch(T *key, bool mustExist, + object::Comparator *comparator = + &object::standardComparator) + { return ((untyped::Vector*)this->base)->bsearch(key, mustExist, + comparator); } }; diff --git a/lout/object.cc b/lout/object.cc index 99b5902d..2b87e98b 100644 --- a/lout/object.cc +++ b/lout/object.cc @@ -107,29 +107,44 @@ size_t Object::sizeOf() } // ---------------- -// Comparable +// Comparator // ---------------- +Comparator *Comparator::compareFunComparator = NULL; + /** * \brief This static method may be used as compare function for * qsort(3) and bsearch(3), for an array of Object* (Object*[] or * Object**). + * + * "compareFunComparator" should be set before. + * + * \todo Not reentrant. Consider switching to reentrant variants + * (qsort_r), and compare function with an additional argument. */ -int Comparable::compareFun(const void *p1, const void *p2) +int Comparator::compareFun(const void *p1, const void *p2) { - Comparable *c1 = *(Comparable**)p1; - Comparable *c2 = *(Comparable**)p2; + return compareFunComparator->compare (*(Object**)p1, *(Object**)p2); +} - if (c1 && c2) - return ((c1)->compareTo(c2)); - else if (c1) +// ------------------------ +// StandardComparator +// ------------------------ + +int StandardComparator::compare(Object *o1, Object *o2) +{ + if (o1 && o2) + return ((Comparable*)o1)->compareTo ((Comparable*)o2); + else if (o1) return 1; - else if (c2) + else if (o2) return -1; else return 0; } +StandardComparator standardComparator; + // ------------- // Pointer // ------------- diff --git a/lout/object.hh b/lout/object.hh index fd612863..5a4935c5 100644 --- a/lout/object.hh +++ b/lout/object.hh @@ -42,10 +42,11 @@ class Comparable: public Object { public: /** - * \brief Compare two objects c1 and c2. + * \brief Compare two objects, this and other. * - * 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. + * Return a value < 0, when this is less than other, a value > 0, + * when this is greater than other, or 0, when this and other 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 @@ -55,10 +56,43 @@ public: * care about. */ virtual int compareTo(Comparable *other) = 0; +}; + +/** + * \brief Used for other orders as the one defined by Comparable. + * + * Compared objects must not neccessary be instances of Comparable. + */ +class Comparator: public Object +{ +public: + /** + * \brief Compare two objects o1 and o2. + * + * Return a value < 0, when o1 is less than o2, a value > 0, when o1 + * is greater than o2, or 0, when o1 and o2 are equal. + * + * If o1.equals(o2) (as defined in Object), compare(o1, o2) 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 compare(Object *o1, Object *o2) = 0; + static Comparator *compareFunComparator; static int compareFun(const void *p1, const void *p2); }; +class StandardComparator: public Comparator +{ +public: + int compare(Object *o1, Object *o2); +}; + +extern StandardComparator standardComparator; + /** * \brief An object::Object wrapper for void pointers. */ diff --git a/test/containers.cc b/test/containers.cc index 40b2d8c8..7cbaf2c9 100644 --- a/test/containers.cc +++ b/test/containers.cc @@ -4,6 +4,16 @@ using namespace lout::object; using namespace lout::container::typed; +class ReverseComparator: public Comparator +{ +private: + Comparator *reversed; + +public: + ReverseComparator (Comparator *reversed) { this->reversed = reversed; } + int compare(Object *o1, Object *o2) { return - reversed->compare (o1, o2); } +}; + void testHashSet () { puts ("--- testHashSet ---"); @@ -38,6 +48,8 @@ void testHashTable () void testVector1 () { + ReverseComparator reverse (&standardComparator); + puts ("--- testVector (1) ---"); Vector<String> v (true, 1); @@ -47,6 +59,9 @@ void testVector1 () v.put (new String ("three")); puts (v.toString()); + v.sort (&reverse); + puts (v.toString()); + v.sort (); puts (v.toString()); } |