# HG changeset patch
# User Jaroslav Hajek <highegg@gmail.com>
# Date 1263542227 -3600
# Node ID e4936c129cbd4d74d508c96127583824f737c42a
# Parent  5aff7f14aa7f92fe58522fa95ecabdbf8913fa2c
optimize sorting of bools

diff --git a/liboctave/Array-b.cc b/liboctave/Array-b.cc
--- a/liboctave/Array-b.cc
+++ b/liboctave/Array-b.cc
@@ -29,8 +29,81 @@
 
 #include "Array.h"
 #include "Array.cc"
+#define INLINE_ASCENDING_SORT
+#define INLINE_DESCENDING_SORT
 #include "oct-sort.cc"
 
+// Specialize bool sorting (aka stable partitioning).
+
+template<bool desc>
+static void do_bool_partition (bool *data, octave_idx_type nel)
+{
+  octave_idx_type k = 0;
+  for (octave_idx_type i = 0; i < nel; i++)
+    if (data[i] == desc)
+      data[k++] = desc;
+  for (octave_idx_type i = k; i < nel; i++)
+    data[i] = ! desc;
+}
+
+template<bool desc>
+static void do_bool_partition (bool *data, octave_idx_type *idx, 
+                               octave_idx_type nel)
+{
+  // FIXME: This is essentially a simple bucket sort.
+  // Can it be efficiently done by std::partition?
+  OCTAVE_LOCAL_BUFFER (octave_idx_type, jdx, nel);
+  octave_idx_type k = 0, l = 0;
+  for (octave_idx_type i = 0; i < nel; i++)
+    {
+      if (data[i] == desc)
+        {
+          data[k] = desc;
+          idx[k++] = idx[i];
+        }
+      else
+        jdx[l++] = idx[i];
+    }
+
+  for (octave_idx_type i = k; i < nel; i++)
+    {
+      data[i] = ! desc;
+      idx[i] = jdx[i-k];
+    }
+}
+
+template <> template <>
+void
+octave_sort<bool>::sort (bool *data, octave_idx_type nel,
+                         std::less<bool>)
+{
+  do_bool_partition<false> (data, nel);
+}
+
+template <> template <>
+void
+octave_sort<bool>::sort (bool *data, octave_idx_type nel,
+                         std::greater<bool>)
+{
+  do_bool_partition<true> (data, nel);
+}
+
+template <> template <>
+void
+octave_sort<bool>::sort (bool *data, octave_idx_type *idx, octave_idx_type nel,
+                         std::less<bool>)
+{
+  do_bool_partition<false> (data, idx, nel);
+}
+
+template <> template <>
+void
+octave_sort<bool>::sort (bool *data, octave_idx_type *idx, octave_idx_type nel,
+                         std::greater<bool>)
+{
+  do_bool_partition<true> (data, idx, nel);
+}
+
 INSTANTIATE_ARRAY_SORT (bool);
 
 INSTANTIATE_ARRAY (bool, OCTAVE_API);
diff --git a/liboctave/ChangeLog b/liboctave/ChangeLog
--- a/liboctave/ChangeLog
+++ b/liboctave/ChangeLog
@@ -1,3 +1,9 @@
+2010-01-15  Jaroslav Hajek  <highegg@gmail.com>
+
+	* Array-b.cc: Inline ascending and descending sort.
+	(do_bool_partition): New helper template function.
+	(octave_sort<bool>::sort): Provide specializations.
+	
 2010-01-14  Jaroslav Hajek  <highegg@gmail.com>
 
 	* Array.cc (Array<T>::insert (const Array<T>&, const