diff options
| author | Evgeniy Khramtsov <xramtsov@gmail.com> | 2009-07-22 10:49:06 +0400 |
|---|---|---|
| committer | Evgeniy Khramtsov <xramtsov@gmail.com> | 2009-07-22 10:49:06 +0400 |
| commit | bd73b01083b62e9336f978ee13c94ec5284e8bfa (patch) | |
| tree | 71b70ee673588bf5d20df085cc3ce5687abc9269 | |
| parent | c735577ca7b46b3755a4c15556265ebdd73d8874 (diff) | |
treap backport from svn trunk
SVN Revision: 2384
| -rw-r--r-- | src/treap.erl | 11 |
1 files changed, 10 insertions, 1 deletions
diff --git a/src/treap.erl b/src/treap.erl index ab5c4d33f..360f543de 100644 --- a/src/treap.erl +++ b/src/treap.erl @@ -32,7 +32,8 @@ delete_root/1, get_root/1, lookup/2, - is_empty/1]). + is_empty/1, + fold/3]). empty() -> nil. @@ -105,6 +106,8 @@ delete(Key, Tree) -> HashKey = {erlang:phash2(Key), Key}, delete1(HashKey, Tree). +delete1(_HashKey, nil) -> + nil; delete1(HashKey, {HashKey1, Priority1, Value1, Left, Right} = Tree) -> if HashKey < HashKey1 -> @@ -162,3 +165,9 @@ lookup1({HashKey1, Priority1, Value1, Left, Right}, HashKey) -> {ok, Priority1, Value1} end. +fold(_F, Acc, nil) -> + Acc; +fold(F, Acc, {{_Hash, Key}, Priority, Value, Left, Right}) -> + Acc1 = F({Key, Priority, Value}, Acc), + Acc2 = fold(F, Acc1, Left), + fold(F, Acc2, Right). |