From 7905926c413e843d9497948cb824059f2c017f6a Mon Sep 17 00:00:00 2001
From: jsdelfino <jsdelfino@13f79535-47bb-0310-9956-ffa450edef68>
Date: Mon, 26 Aug 2013 03:04:23 +0000
Subject: Support sorting database search results by rank, and add a rank
 attribute to ATOM entries.

git-svn-id: http://svn.us.apache.org/repos/asf/tuscany@1517412 13f79535-47bb-0310-9956-ffa450edef68
---
 sca-cpp/trunk/kernel/tree.hpp | 30 +++++++++++++++++++++---------
 1 file changed, 21 insertions(+), 9 deletions(-)

(limited to 'sca-cpp/trunk/kernel/tree.hpp')

diff --git a/sca-cpp/trunk/kernel/tree.hpp b/sca-cpp/trunk/kernel/tree.hpp
index a5d0e3d5b0..77f2f1ea54 100644
--- a/sca-cpp/trunk/kernel/tree.hpp
+++ b/sca-cpp/trunk/kernel/tree.hpp
@@ -173,26 +173,38 @@ template<typename T> inline const list<T> rbtreeAssoc(const T& k, const list<T>&
     return rbtreeAssoc<T>(k, caddr(tree));
 }
 
+/**
+ * Default function used to compare two values while building a rooted binary tree.
+ */
+template<typename T> inline const int rbtreeComp(const T& a, const T& b) {
+    if (a == b)
+        return 0;
+    if (a < b)
+        return -1;
+    return 1;
+}
+
 /**
  * Construct a new rooted binary tree from a leaf and a tree.
  */
-template<typename T> inline const list<T> rbtreeCons(const T& e, const list<T>& tree) {
+template<typename T> inline const list<T> rbtreeCons(const T& e, const list<T>& tree, const lambda<int(const T&, const T&)>& comp = rbtreeComp<T>) {
     if (isNull(tree))
         return mkrbtree(e, list<T>(), list<T>());
-    if (e == car(tree))
+    const int c = comp(e, car(tree));
+    if (c == 0)
         return tree;
-    if (e < car(tree))
-        return mkrbtree<T>(car(tree), rbtreeCons<T>(e, cadr(tree)), caddr(tree));
-    return mkrbtree<T>(car(tree), cadr(tree), rbtreeCons<T>(e, caddr(tree)));
+    if (c == -1)
+        return mkrbtree<T>(car(tree), rbtreeCons<T>(e, cadr(tree), comp), caddr(tree));
+    return mkrbtree<T>(car(tree), cadr(tree), rbtreeCons<T>(e, caddr(tree), comp));
 }
 
 /**
  * Make a rooted binary tree from an unordered list of leaves.
  */
-template<typename T> inline const list<T> mkrbtree(const list<T>& l) {
+template<typename T> inline const list<T> mkrbtree(const list<T>& l, const lambda<int(const T&, const T&)>& comp = rbtreeComp<T>) {
     if (isNull(l))
         return l;
-    return rbtreeCons(car(l), mkrbtree(cdr(l)));
+    return rbtreeCons(car(l), mkrbtree(cdr(l), comp), comp);
 }
 
 /**
@@ -207,8 +219,8 @@ template<typename T> inline const list<T> flatten(const list<T>& tree) {
 /**
  * Sort a list, using a rooted binary tree.
  */
-template<typename T> inline const list<T> sort(const list<T>& l) {
-    return flatten(mkrbtree(l));
+template<typename T> inline const list<T> sort(const list<T>& l,  const lambda<int(const T&, const T&)>& comp = rbtreeComp<T>) {
+    return flatten(mkrbtree(l, comp));
 }
 
 /**
-- 
cgit v1.2.3