From 49ad0b5252190ffbfb4511131af2032f7f341a60 Mon Sep 17 00:00:00 2001
From: Sebastian Geerken <devnull@localhost>
Date: Tue, 5 Mar 2013 00:27:05 +0100
Subject: Implemented iterators for Vector.

---
 lout/container.cc | 17 +++++++++++++----
 lout/container.hh | 14 ++++++++++++++
 2 files changed, 27 insertions(+), 4 deletions(-)

(limited to 'lout')

diff --git a/lout/container.cc b/lout/container.cc
index deeede57..6a55fc2c 100644
--- a/lout/container.cc
+++ b/lout/container.cc
@@ -193,13 +193,22 @@ void Vector::sort()
    qsort(array, numElements, sizeof(Object*), misc::Comparable::compareFun);
 }
 
+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;
+}
 
-/**
- * \bug Not implemented.
- */
 Collection0::AbstractIterator* Vector::createIterator()
 {
-   return NULL;
+   return new VectorIterator(this);
 }
 
 // ------------
diff --git a/lout/container.hh b/lout/container.hh
index f1008e82..10139211 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();
 
-- 
cgit v1.2.3


From 9c98b3c16041ebd41aabbb82e71d424a940a1d47 Mon Sep 17 00:00:00 2001
From: Sebastian Geerken <devnull@localhost>
Date: Tue, 5 Mar 2013 11:34:03 +0100
Subject: Comparable is now subclass of Object (not pseudo-interface anymore).
 The old solution would have made RTTI neccessary to work correctly.

---
 dw/iterator.cc           | 10 +++++-----
 dw/iterator.hh           | 14 +++++++-------
 dw/table.cc              |  2 +-
 dw/table.hh              |  2 +-
 dw/textblock.hh          |  2 +-
 dw/textblock_iterator.cc |  2 +-
 lout/container.cc        |  2 +-
 lout/misc.cc             | 26 --------------------------
 lout/misc.hh             | 29 -----------------------------
 lout/object.cc           | 23 +++++++++++++++++++++++
 lout/object.hh           | 30 ++++++++++++++++++++++++++++--
 test/containers.cc       |  4 ++++
 12 files changed, 72 insertions(+), 74 deletions(-)

(limited to 'lout')

diff --git a/dw/iterator.cc b/dw/iterator.cc
index 5f46cbdb..18d7cd5a 100644
--- a/dw/iterator.cc
+++ b/dw/iterator.cc
@@ -37,7 +37,7 @@ Iterator::Iterator(Widget *widget, Content::Type mask, bool atEnd)
    this->mask = mask;
 }
 
-Iterator::Iterator(Iterator &it): object::Object (), misc::Comparable ()
+Iterator::Iterator(Iterator &it): object::Comparable ()
 {
    widget = it.widget;
    content = it.content;
@@ -205,7 +205,7 @@ object::Object *EmptyIterator::clone ()
    return new EmptyIterator (*this);
 }
 
-int EmptyIterator::compareTo (misc::Comparable *other)
+int EmptyIterator::compareTo (object::Comparable *other)
 {
    EmptyIterator *otherIt = (EmptyIterator*)other;
 
@@ -257,7 +257,7 @@ TextIterator::TextIterator (TextIterator &it): Iterator (it)
    text = it.text;
 }
 
-int TextIterator::compareTo (misc::Comparable *other)
+int TextIterator::compareTo (object::Comparable *other)
 {
    TextIterator *otherIt = (TextIterator*)other;
 
@@ -535,7 +535,7 @@ object::Object *DeepIterator::clone ()
    return it;
 }
 
-int DeepIterator::compareTo (misc::Comparable *other)
+int DeepIterator::compareTo (object::Comparable *other)
 {
    DeepIterator *otherDeepIterator = (DeepIterator*)other;
 
@@ -665,7 +665,7 @@ object::Object *CharIterator::clone()
    return cloned;
 }
 
-int CharIterator::compareTo(misc::Comparable *other)
+int CharIterator::compareTo(object::Comparable *other)
 {
    CharIterator *otherIt = (CharIterator*)other;
    int c = it->compareTo(otherIt->it);
diff --git a/dw/iterator.hh b/dw/iterator.hh
index c5cfd72b..d086721c 100644
--- a/dw/iterator.hh
+++ b/dw/iterator.hh
@@ -16,7 +16,7 @@ namespace core {
  *
  * \sa dw::core::Widget::iterator
  */
-class Iterator: public lout::object::Object, public lout::misc::Comparable
+class Iterator: public lout::object::Comparable
 {
 protected:
    Iterator(Widget *widget, Content::Type mask, bool atEnd);
@@ -101,7 +101,7 @@ public:
    EmptyIterator (Widget *widget, Content::Type mask, bool atEnd);
 
    lout::object::Object *clone();
-   int compareTo(lout::misc::Comparable *other);
+   int compareTo(lout::object::Comparable *other);
    bool next ();
    bool prev ();
    void highlight (int start, int end, HighlightLayer layer);
@@ -126,7 +126,7 @@ public:
    TextIterator (Widget *widget, Content::Type mask, bool atEnd,
                  const char *text);
 
-   int compareTo(lout::misc::Comparable *other);
+   int compareTo(lout::object::Comparable *other);
 
    bool next ();
    bool prev ();
@@ -142,7 +142,7 @@ public:
  * iterators do not have the limitation, that iteration is only done within
  * a widget, instead, child widgets are iterated through recursively.
  */
-class DeepIterator: public lout::object::Object, public lout::misc::Comparable
+class DeepIterator: public lout::object::Comparable
 {
 private:
    class Stack: public lout::container::typed::Vector<Iterator>
@@ -183,7 +183,7 @@ public:
    bool next ();
    bool prev ();
    inline DeepIterator *cloneDeepIterator() { return (DeepIterator*)clone(); }
-   int compareTo(lout::misc::Comparable *other);
+   int compareTo(lout::object::Comparable *other);
 
    /**
     * \brief Highlight a part of the current content.
@@ -216,7 +216,7 @@ public:
                          start, end, hpos, vpos); }
 };
 
-class CharIterator: public lout::object::Object, public lout::misc::Comparable
+class CharIterator: public lout::object::Comparable
 {
 public:
    // START and END must not clash with any char value
@@ -234,7 +234,7 @@ public:
    ~CharIterator ();
 
    lout::object::Object *clone();
-   int compareTo(lout::misc::Comparable *other);
+   int compareTo(lout::object::Comparable *other);
 
    bool next ();
    bool prev ();
diff --git a/dw/table.cc b/dw/table.cc
index 39cfee73..defc4259 100644
--- a/dw/table.cc
+++ b/dw/table.cc
@@ -1114,7 +1114,7 @@ object::Object *Table::TableIterator::clone()
    return new TableIterator ((Table*)getWidget(), getMask(), index);
 }
 
-int Table::TableIterator::compareTo(misc::Comparable *other)
+int Table::TableIterator::compareTo(object::Comparable *other)
 {
    return index - ((TableIterator*)other)->index;
 }
diff --git a/dw/table.hh b/dw/table.hh
index 7bcc6c1b..b8feb835 100644
--- a/dw/table.hh
+++ b/dw/table.hh
@@ -344,7 +344,7 @@ private:
       TableIterator (Table *table, core::Content::Type mask, int index);
 
       lout::object::Object *clone();
-      int compareTo(lout::misc::Comparable *other);
+      int compareTo(lout::object::Comparable *other);
 
       bool next ();
       bool prev ();
diff --git a/dw/textblock.hh b/dw/textblock.hh
index e1957740..90185cd2 100644
--- a/dw/textblock.hh
+++ b/dw/textblock.hh
@@ -376,7 +376,7 @@ protected:
                          int index);
 
       lout::object::Object *clone();
-      int compareTo(lout::misc::Comparable *other);
+      int compareTo(lout::object::Comparable *other);
 
       bool next ();
       bool prev ();
diff --git a/dw/textblock_iterator.cc b/dw/textblock_iterator.cc
index c6aaab57..22f43fb6 100644
--- a/dw/textblock_iterator.cc
+++ b/dw/textblock_iterator.cc
@@ -57,7 +57,7 @@ object::Object *Textblock::TextblockIterator::clone()
    return new TextblockIterator ((Textblock*)getWidget(), getMask(), index);
 }
 
-int Textblock::TextblockIterator::compareTo(misc::Comparable *other)
+int Textblock::TextblockIterator::compareTo(object::Comparable *other)
 {
    return index - ((TextblockIterator*)other)->index;
 }
diff --git a/lout/container.cc b/lout/container.cc
index 6a55fc2c..9e71ba77 100644
--- a/lout/container.cc
+++ b/lout/container.cc
@@ -190,7 +190,7 @@ void Vector::remove(int pos)
  */
 void Vector::sort()
 {
-   qsort(array, numElements, sizeof(Object*), misc::Comparable::compareFun);
+   qsort(array, numElements, sizeof(Object*), Comparable::compareFun);
 }
 
 Object *Vector::VectorIterator::getNext()
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
@@ -64,35 +64,6 @@ inline int AsciiStrcasecmp(const char *s1, const char *s2)
    return ret;
 }
 
-/**
- * \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..059564c0 100644
--- a/lout/object.cc
+++ b/lout/object.cc
@@ -106,6 +106,29 @@ size_t Object::sizeOf()
    return sizeof(Object*);
 }
 
+// ----------------
+//    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;
+}
+
 // -------------
 //    Pointer
 // -------------
diff --git a/lout/object.hh b/lout/object.hh
index 9df69987..fd612863 100644
--- a/lout/object.hh
+++ b/lout/object.hh
@@ -33,6 +33,32 @@ public:
    virtual size_t sizeOf();
 };
 
+/**
+ * \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.
  */
@@ -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;
diff --git a/test/containers.cc b/test/containers.cc
index 059125ac..adb58317 100644
--- a/test/containers.cc
+++ b/test/containers.cc
@@ -47,6 +47,10 @@ void testVector ()
    v.put (new String ("three"));
 
    puts (v.toString());
+
+   v.sort ();
+
+   puts (v.toString());
 }
 
 int main (int argc, char *argv[])
-- 
cgit v1.2.3


From 3a713f19f22a049c4237fa96d12400409e3ccb51 Mon Sep 17 00:00:00 2001
From: Sebastian Geerken <devnull@localhost>
Date: Tue, 5 Mar 2013 11:40:18 +0100
Subject: Comment.

---
 lout/object.cc | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

(limited to 'lout')

diff --git a/lout/object.cc b/lout/object.cc
index 059564c0..99b5902d 100644
--- a/lout/object.cc
+++ b/lout/object.cc
@@ -111,8 +111,9 @@ size_t Object::sizeOf()
 // ----------------
 
 /**
- * \brief This static method may be used as compare function for qsort(3), for
- *    an array of Object* (Object*[] or Object**).
+ * \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)
 {
-- 
cgit v1.2.3


From e844f4119a6a5b144b18af4bcc841c816f575159 Mon Sep 17 00:00:00 2001
From: Sebastian Geerken <devnull@localhost>
Date: Tue, 5 Mar 2013 14:24:33 +0100
Subject: Vector::bsearch and insertSorted.

---
 lout/container.cc  | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
 lout/container.hh  | 15 +++++++++++++++
 test/containers.cc | 28 +++++++++++++++++++++++++++-
 3 files changed, 90 insertions(+), 2 deletions(-)

(limited to 'lout')

diff --git a/lout/container.cc b/lout/container.cc
index 9e71ba77..5e5eda73 100644
--- a/lout/container.cc
+++ b/lout/container.cc
@@ -190,7 +190,54 @@ void Vector::remove(int pos)
  */
 void Vector::sort()
 {
-   qsort(array, numElements, sizeof(Object*), Comparable::compareFun);
+   qsort (array, numElements, sizeof(Object*), Comparable::compareFun);
+}
+
+/**
+ * \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()
diff --git a/lout/container.hh b/lout/container.hh
index 10139211..c87eb10c 100644
--- a/lout/container.hh
+++ b/lout/container.hh
@@ -130,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);
 };
 
 
@@ -395,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/test/containers.cc b/test/containers.cc
index adb58317..d8107bdf 100644
--- a/test/containers.cc
+++ b/test/containers.cc
@@ -45,12 +45,38 @@ void testVector ()
    v.put (new String ("one"));
    v.put (new String ("two"));
    v.put (new String ("three"));
-
    puts (v.toString());
 
    v.sort ();
+   puts (v.toString());
+
+   v.insertSorted (new String ("five"));
+   puts (v.toString());
 
+   v.insertSorted (new String ("six"));
    puts (v.toString());
+
+   v.insertSorted (new String ("four"));
+   puts (v.toString());
+
+   for (int b = 0; b < 2; b++) {
+      bool mustExist = b;
+      printf ("mustExist = %s\n", mustExist ? "true" : "false");
+   
+      String k ("alpha");
+      printf ("   '%s' -> %d\n", k.chars(), v.bsearch (&k, mustExist));
+      
+      for (Iterator<String> it = v.iterator(); it.hasNext(); ) {
+         String *k1 = it.getNext();
+         printf ("   '%s' -> %d\n", k1->chars(), v.bsearch (k1, mustExist));
+         
+         char buf[64];
+         strcpy (buf, k1->chars());
+         strcat (buf, "-var");
+         String k2 (buf);
+         printf ("   '%s' -> %d\n", k2.chars(), v.bsearch (&k2, mustExist));
+      }
+   }
 }
 
 int main (int argc, char *argv[])
-- 
cgit v1.2.3