diff options
author | jsdelfino <jsdelfino@13f79535-47bb-0310-9956-ffa450edef68> | 2013-01-03 07:41:02 +0000 |
---|---|---|
committer | jsdelfino <jsdelfino@13f79535-47bb-0310-9956-ffa450edef68> | 2013-01-03 07:41:02 +0000 |
commit | 157ca678dee75e7881a0198425d0c8328f0bee04 (patch) | |
tree | 3c63c23b4948b2ee923c0b2027fbb5ac525a1b85 /sca-cpp/trunk/kernel/tree.hpp | |
parent | 36adc76235fb0a38e7042bc751f988b71627e2a0 (diff) |
Improve handling of nested lists, trees, null and floating point values.
git-svn-id: http://svn.us.apache.org/repos/asf/tuscany@1428191 13f79535-47bb-0310-9956-ffa450edef68
Diffstat (limited to 'sca-cpp/trunk/kernel/tree.hpp')
-rw-r--r-- | sca-cpp/trunk/kernel/tree.hpp | 168 |
1 files changed, 143 insertions, 25 deletions
diff --git a/sca-cpp/trunk/kernel/tree.hpp b/sca-cpp/trunk/kernel/tree.hpp index 44af09fa64..d350879ce7 100644 --- a/sca-cpp/trunk/kernel/tree.hpp +++ b/sca-cpp/trunk/kernel/tree.hpp @@ -31,54 +31,172 @@ #include "function.hpp" #include "list.hpp" #include "monad.hpp" -#include "value.hpp" namespace tuscany { /** - * Make a tree from a leaf and two branches. + * Delete assocs matching a path of keys in a tree of assocs. + * The path can be a complete or partial path to an assoc. + * Requires T to support isList, isAssoc, and cast to list<T>. */ -template<typename T> inline const list<T> mktree(const T& e, const list<T>& left, const list<T>& right) { +template<typename T> inline const list<T> treeDelAssoc(const list<T>& k, const list<T>& l) noexcept { + if (isNil(k) || isNil(l)) + return l; + const list<T> lv = l; + + // If list is an assoc and matches, skip it + if (isAssoc(lv)) { + if (car<T>(lv) == car(k) && isNil(cdr(k))) + return list<T>(); + } + + // If list element is not an assoc, lookup children and rest of the list + const T a = car(lv); + if (!isAssoc(a)) { + if (!isList(a)) + return cons<T>(a, treeDelAssoc<T>(k, cdr(lv))); + const list<T> da = treeDelAssoc<T>(k, a); + return isNil(da)? treeDelAssoc<T>(k, cdr(lv)) : cons<T>(da, treeDelAssoc<T>(k, cdr(lv))); + } + + // If we found a match, skip it and lookup children and rest of the list + if (car<T>(a) == car(k)) { + if (isNil(cdr(k))) + return treeDelAssoc<T>(k, cdr(lv)); + return cons<T>(cons<T>(car<T>(a), treeDelAssoc<T>(cdr(k), cdr<T>(a))), treeDelAssoc<T>(k, cdr(lv))); + } + + // No match, lookup children and rest of the list + if (isNil(cdr<T>(a))) + return cons<T>(a, treeDelAssoc<T>(k, cdr(lv))); + if (!isList(cadr<T>(a))) + return cons<T>(cons<T>(car<T>(a), cons<T>(cadr<T>(a), treeDelAssoc<T>(k, cddr<T>(a)))), treeDelAssoc<T>(k, cdr(lv))); + const list<T> da = treeDelAssoc<T>(k, cadr<T>(a)); + if (isNil(da)) + return cons<T>(cons<T>(car<T>(a), treeDelAssoc<T>(k, cddr<T>(a))), treeDelAssoc<T>(k, cdr(lv))); + return cons<T>(cons<T>(car<T>(a), cons<T>(da, treeDelAssoc<T>(k, cddr<T>(a)))), treeDelAssoc<T>(k, cdr(lv))); +} + +/** + * Substitute assocs matching a path of keys in a tree of assocs. + * The path can be a complete or partial path to an assoc. + * Requires T to support isList, isAssoc, and cast to list<T>. + */ +template<typename T> inline const list<T> treeSubstAssoc(const list<T>& k, const list<T>& n, const list<T>& lv) noexcept { + if (isNil(k) || isNil(lv)) + return lv; + + // If list is an assoc and matches, substitute it + if (isAssoc(lv)) { + if (car<T>(lv) == car(k) && isNil(cdr(k))) + return n; + } + + // If list element is not an assoc, lookup children and rest of the list + const T a = car(lv); + if (!isAssoc(a)) { + if (!isList(a)) + return cons<T>(a, treeSubstAssoc<T>(k, n, cdr(lv))); + return cons<T>(treeSubstAssoc<T>(k, n, a), treeSubstAssoc<T>(k, n, cdr(lv))); + } + + // If we found a match, substitute it and lookup children and rest of the list + if (car<T>(a) == car(k)) { + if (isNil(cdr(k))) + return cons<T>(n, treeSubstAssoc<T>(k, n, cdr(lv))); + return cons<T>(cons<T>(car<T>(a), treeSubstAssoc<T>(cdr(k), n, cdr<T>(a))), treeSubstAssoc<T>(k, n, cdr(lv))); + } + + // No match, lookup children and rest of the list + if (isNil(cdr<T>(a))) + return cons<T>(a, treeSubstAssoc<T>(k, n, cdr(lv))); + if (!isList(cadr<T>(a))) + return cons<T>(cons<T>(car<T>(a), cons<T>(cadr<T>(a), treeSubstAssoc<T>(k, n, cddr<T>(a)))), treeSubstAssoc<T>(k, n, cdr(lv))); + return cons<T>(cons<T>(car<T>(a), cons<T>(treeSubstAssoc<T>(k, n, cadr<T>(a)), treeSubstAssoc<T>(k, n, cddr<T>(a)))), treeSubstAssoc<T>(k, n, cdr(lv))); +} + +/** + * Select assocs matching a path of keys in a tree of assocs. + * The path can be a complete or partial path to an assoc. + * Requires T to support isList, isAssoc, and cast to list<T>. + */ +template<typename T> inline const list<T> treeSelectAssoc(const list<T>& k, const list<T>& lv) noexcept { + if (isNil(k) || isNil(lv)) + return list<T>(); + + // If list is an assoc and matches, select it + if (isAssoc(lv)) { + if (car<T>(lv) == car(k) && isNil(cdr(k))) + return mklist<T>(lv); + } + + // If list element is not an assoc, lookup children and rest of the list + const T a = car(lv); + if (!isAssoc(a)) { + if (!isList(a)) + return treeSelectAssoc<T>(k, cdr(lv)); + return append<T>(treeSelectAssoc<T>(k, a), treeSelectAssoc<T>(k, cdr(lv))); + } + + // If we found a match, select it and lookup children and rest of the list + if (car<T>(a) == car(k)) { + if (isNil(cdr(k))) + return cons<T>(a, treeSelectAssoc<T>(k, cdr(lv))); + return append<T>(treeSelectAssoc<T>(cdr(k), cdr<T>(a)), treeSelectAssoc<T>(k, cdr(lv))); + } + + // No match, lookup children and rest of the list + if (isNil(cdr<T>(a))) + return treeSelectAssoc<T>(k, cdr(lv)); + if (!isList(cadr<T>(a))) + return append<T>(treeSelectAssoc<T>(k, cddr<T>(a)), treeSelectAssoc<T>(k, cdr(lv))); + return append<T>(append<T>(treeSelectAssoc<T>(k, cadr<T>(a)), treeSelectAssoc<T>(k, cddr<T>(a))), treeSelectAssoc<T>(k, cdr(lv))); +} + +/** + * Make a rooted binary tree from a leaf and two branches. + */ +template<typename T> inline const list<T> mkrbtree(const T& e, const list<T>& left, const list<T>& right) { return mklist<T>(e, left, right); } /** - * Find a leaf with the given key in a tree. + * Find a leaf with the given key in a rooted binary tree. */ -template<typename T> inline const list<T> assoctree(const T& k, const list<T>& tree) { +template<typename T> inline const list<T> rbtreeAssoc(const T& k, const list<T>& tree) { if (isNil(tree)) return tree; if (k == car<T>(car(tree))) return car(tree); if (k < car<T>(car(tree))) - return assoctree<T>(k, cadr(tree)); - return assoctree<T>(k, caddr(tree)); + return rbtreeAssoc<T>(k, cadr(tree)); + return rbtreeAssoc<T>(k, caddr(tree)); } /** - * Construct a new tree from a leaf and a tree. + * Construct a new rooted binary tree from a leaf and a tree. */ -template<typename T> inline const list<T> constree(const T& e, const list<T>& tree) { +template<typename T> inline const list<T> rbtreeCons(const T& e, const list<T>& tree) { if (isNil(tree)) - return mktree(e, list<T>(), list<T>()); + return mkrbtree(e, list<T>(), list<T>()); if (e == car(tree)) return tree; if (e < car(tree)) - return mktree<T>(car(tree), constree<T>(e, cadr(tree)), caddr(tree)); - return mktree<T>(car(tree), cadr(tree), constree<T>(e, caddr(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))); } /** - * Make a tree from an unordered list of leaves. + * Make a rooted binary tree from an unordered list of leaves. */ -template<typename T> inline const list<T> mktree(const list<T>& l) { +template<typename T> inline const list<T> mkrbtree(const list<T>& l) { if (isNil(l)) return l; - return constree(car(l), mktree(cdr(l))); + return rbtreeCons(car(l), mkrbtree(cdr(l))); } /** - * Convert a tree to an ordered list of leaves. + * Convert a rooted binary tree to an ordered list of leaves. */ template<typename T> inline const list<T> flatten(const list<T>& tree) { if (isNil(tree)) @@ -87,28 +205,28 @@ template<typename T> inline const list<T> flatten(const list<T>& tree) { } /** - * Sort a list. + * Sort a list, using a rooted binary tree. */ template<typename T> inline const list<T> sort(const list<T>& l) { - return flatten(mktree(l)); + return flatten(mkrbtree(l)); } /** - * Make a balanced tree from an ordered list of leaves. + * Make a balanced rooted binary tree from an ordered list of leaves. */ -template<typename T> inline const list<T> btreeHelper(const list<T>& elements, const size_t n) { +template<typename T> inline const list<T> brbtreeHelper(const list<T>& elements, const size_t n) { if (n == 0) return cons<T>(list<T>(), elements); const size_t leftSize = (n - 1) / 2; { - const list<T> leftResult = btreeHelper<T>(elements, leftSize); { + const list<T> leftResult = brbtreeHelper<T>(elements, leftSize); { const list<T> leftTree = car(leftResult); const list<T> nonLeftElements = cdr(leftResult); const size_t rightSize = n - (leftSize + 1); { const T thisEntry = car(nonLeftElements); - const list<T> rightResult = btreeHelper<T>(cdr(nonLeftElements), rightSize); { + const list<T> rightResult = brbtreeHelper<T>(cdr(nonLeftElements), rightSize); { const list<T> rightTree = car(rightResult); const list<T> remainingElements = cdr(rightResult); { - return cons<T>(mktree<T>(thisEntry, leftTree, rightTree), remainingElements); + return cons<T>(mkrbtree<T>(thisEntry, leftTree, rightTree), remainingElements); } } } @@ -116,8 +234,8 @@ template<typename T> inline const list<T> btreeHelper(const list<T>& elements, c } } -template<typename T> inline const list<T> mkbtree(const list<T>& elements) { - return car(btreeHelper<T>(elements, length(elements))); +template<typename T> inline const list<T> mkbrbtree(const list<T>& elements) { + return car(brbtreeHelper<T>(elements, length(elements))); } } |