An abstract mergesort function.

5 files changed, 123 insertions, 95 deletions

diff --git a/ChangeLog b/ChangeLog
index 1f06aaf..20c2ecd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2002-11-05  Bruno Haible  <bruno@clisp.org>
+
+	* src/keyword-list.h (mergesort_list): New declarations.
+	* src/keyword-list.cc (Keyword_Comparison): New type.
+	(merge, mergesort_list): New functions, moved here from search.cc.
+	* src/search.h (Search::merge, Search::merge_sort): Remove methods.
+	(Search::_occurrence_sort, Search::_hash_sort): Remove fields.
+	* src/search.cc (Search::merge, Search::merge_sort): Remove methods.
+	(greater_by_occurrence, less_by_hash_value): New functions.
+	(Search::reorder, Search::sort): Use mergesort_list.
+
 2002-11-04  Bruno Haible  <bruno@clisp.org>
 
 	* src/options.h (Options::_asso_iterations): New field.
diff --git a/src/keyword-list.cc b/src/keyword-list.cc
index 8e0983c..4f27117 100644
--- a/src/keyword-list.cc
+++ b/src/keyword-list.cc
@@ -79,6 +79,92 @@ delete_list (Keyword_List *list)
     }
 }
 
+/* Type of a comparison function.  */
+typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2);
+
+/* Merges two sorted lists together to form one sorted list.  */
+static Keyword_List *
+merge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less)
+{
+  Keyword_List *result;
+  Keyword_List **resultp = &result;
+  for (;;)
+    {
+      if (!list1)
+        {
+          *resultp = list2;
+          break;
+        }
+      if (!list2)
+        {
+          *resultp = list1;
+          break;
+        }
+      if (less (list2->first(), list1->first()))
+        {
+          *resultp = list2;
+          resultp = &list2->rest();
+          /* We would have a stable sorting if the next line would read:
+             list2 = *resultp;  */
+          list2 = list1; list1 = *resultp;
+        }
+      else
+        {
+          *resultp = list1;
+          resultp = &list1->rest();
+          list1 = *resultp;
+        }
+    }
+  return result;
+}
+
+/* Sorts a linear list, given a comparison function.
+   Note: This uses a variant of mergesort that is *not* a stable sorting
+   algorithm.  */
+Keyword_List *
+mergesort_list (Keyword_List *list, Keyword_Comparison less)
+{
+  if (list == NULL || list->rest() == NULL)
+    /* List of length 0 or 1.  Nothing to do.  */
+    return list;
+  else
+    {
+      /* Determine a list node in the middle.  */
+      Keyword_List *middle = list;
+      for (Keyword_List *temp = list->rest();;)
+        {
+          temp = temp->rest();
+          if (temp == NULL)
+            break;
+          temp = temp->rest();
+          middle = middle->rest();
+          if (temp == NULL)
+            break;
+        }
+
+      /* Cut the list into two halves.
+         If the list has n elements, the left half has ceiling(n/2) elements
+         and the right half has floor(n/2) elements.  */
+      Keyword_List *right_half = middle->rest();
+      middle->rest() = NULL;
+
+      /* Sort the two halves, then merge them.  */
+      return merge (mergesort_list (list, less),
+                    mergesort_list (right_half, less),
+                    less);
+    }
+}
+
+KeywordExt_List *
+mergesort_list (KeywordExt_List *list,
+                bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2))
+{
+  return
+    static_cast<KeywordExt_List *>
+      (mergesort_list (static_cast<Keyword_List *> (list),
+                       reinterpret_cast<Keyword_Comparison> (less)));
+}
+
 
 #ifndef __OPTIMIZE__
 
diff --git a/src/keyword-list.h b/src/keyword-list.h
index 888eb89..664f7de 100644
--- a/src/keyword-list.h
+++ b/src/keyword-list.h
@@ -64,6 +64,16 @@ extern KeywordExt_List * copy_list (KeywordExt_List *list);
 /* Deletes a linear list, keeping the list elements in memory.  */
 extern void delete_list (Keyword_List *list);
 
+/* Sorts a linear list, given a comparison function.
+   Note: This uses a variant of mergesort that is *not* a stable sorting
+   algorithm.  */
+extern Keyword_List * mergesort_list (Keyword_List *list,
+                                      bool (*less) (Keyword *keyword1,
+                                                    Keyword *keyword2));
+extern KeywordExt_List * mergesort_list (KeywordExt_List *list,
+                                         bool (*less) (KeywordExt *keyword1,
+                                                       KeywordExt *keyword2));
+
 #ifdef __OPTIMIZE__
 
 #define INLINE inline
diff --git a/src/search.cc b/src/search.cc
index 72a61e7..acd913b 100644
--- a/src/search.cc
+++ b/src/search.cc
@@ -152,84 +152,6 @@ Search::prepare ()
     }
 }
 
-/* ----------------------- Sorting the Keyword list ------------------------ */
-
-/* Merges two sorted lists together to form one sorted list.
-   The sorting criterion depends on which of _occurrence_sort and _hash_sort
-   is set to true.  This is a kludge, but permits nice sharing of almost
-   identical code without incurring the overhead of a function call for
-   every comparison.  */
-
-KeywordExt_List *
-Search::merge (KeywordExt_List *list1, KeywordExt_List *list2) const
-{
-  KeywordExt_List *result;
-  KeywordExt_List **resultp = &result;
-  for (;;)
-    {
-      if (!list1)
-        {
-          *resultp = list2;
-          break;
-        }
-      if (!list2)
-        {
-          *resultp = list1;
-          break;
-        }
-      if ((_occurrence_sort
-           && list1->first()->_occurrence < list2->first()->_occurrence)
-          || (_hash_sort
-              && list1->first()->_hash_value > list2->first()->_hash_value))
-        {
-          *resultp = list2;
-          resultp = &list2->rest(); list2 = list1; list1 = *resultp;
-        }
-      else
-        {
-          *resultp = list1;
-          resultp = &list1->rest(); list1 = *resultp;
-        }
-    }
-  return result;
-}
-
-/* Sorts a list using the recursive merge sort algorithm.
-   The sorting criterion depends on which of _occurrence_sort and _hash_sort
-   is set to true.  */
-
-KeywordExt_List *
-Search::merge_sort (KeywordExt_List *head) const
-{
-  if (!head || !head->rest())
-    /* List of length 0 or 1.  Nothing to do.  */
-    return head;
-  else
-    {
-      /* Determine a list node in the middle.  */
-      KeywordExt_List *middle = head;
-      for (KeywordExt_List *temp = head->rest();;)
-        {
-          temp = temp->rest();
-          if (temp == NULL)
-            break;
-          temp = temp->rest();
-          middle = middle->rest();
-          if (temp == NULL)
-            break;
-        }
-
-      /* Cut the list into two halves.
-         If the list has n elements, the left half has ceiling(n/2) elements
-         and the right half has floor(n/2) elements.  */
-      KeywordExt_List *right_half = middle->rest();
-      middle->rest() = NULL;
-
-      /* Sort the two halves, then merge them.  */
-      return merge (merge_sort (head), merge_sort (right_half));
-    }
-}
-
 /* ---------------- Reordering the Keyword list (optional) ----------------- */
 
 /* Computes the sum of occurrences of the _selchars of a keyword.
@@ -251,6 +173,13 @@ Search::compute_occurrence (KeywordExt *ptr) const
   return value;
 }
 
+/* Comparison function for sorting by decreasing _occurrence valuation.  */
+static bool
+greater_by_occurrence (KeywordExt *keyword1, KeywordExt *keyword2)
+{
+  return keyword1->_occurrence > keyword2->_occurrence;
+}
+
 /* Auxiliary function for reorder():
    Sets all alphabet characters as undetermined.  */
 
@@ -308,9 +237,7 @@ Search::reorder ()
     }
 
   /* Sort the list by decreasing _occurrence valuation.  */
-  _hash_sort = false;
-  _occurrence_sort = true;
-  _head = merge_sort (_head);
+  _head = mergesort_list (_head, greater_by_occurrence);
 
   /* Reorder the list to maximize the efficiency of the search.  */
 
@@ -716,14 +643,19 @@ Search::find_asso_values ()
 
 /* ------------------------------------------------------------------------- */
 
+/* Comparison function for sorting by increasing _hash_value.  */
+static bool
+less_by_hash_value (KeywordExt *keyword1, KeywordExt *keyword2)
+{
+  return keyword1->_hash_value < keyword2->_hash_value;
+}
+
 /* Sorts the keyword list by hash value.  */
 
 void
 Search::sort ()
 {
-  _hash_sort = true;
-  _occurrence_sort = false;
-  _head = merge_sort (_head);
+  _head = mergesort_list (_head, less_by_hash_value);
 }
 
 void
diff --git a/src/search.h b/src/search.h
index f058a4d..7e1f781 100644
--- a/src/search.h
+++ b/src/search.h
@@ -38,11 +38,6 @@ public:
 private:
   void                  prepare ();
 
-  /* Merges two sorted lists together to form one sorted list.  */
-  KeywordExt_List *     merge (KeywordExt_List *list1, KeywordExt_List *list2) const;
-  /* Sorts a list using the recursive merge sort algorithm.  */
-  KeywordExt_List *     merge_sort (KeywordExt_List *head) const;
-
   /* Computes the sum of occurrences of the _selchars of a keyword.  */
   int                   compute_occurrence (KeywordExt *ptr) const;
 
@@ -120,12 +115,6 @@ private:
   /* Length of _head list.  Number of keywords, not counting duplicates.  */
   int                   _list_len;
 
-  /* Choice of sorting criterion during Search::merge_sort.  */
-  /* True if sorting by occurrence.  */
-  bool                  _occurrence_sort;
-  /* True if sorting by hash value.  */
-  bool                  _hash_sort;
-
   /* Vector used during Search::reorder().  */
   bool * const          _determined;