Rewrite ts to use a list of lists and change its API.

We want to get rid of maps because they're a bit too new for some
distributions. Replacing the arrays with lists is not necessary and
arguably not even the right move -- they're about twice as costly RAM
wise and the CPU cost for accesses are O(n). This cleans up the
implementation though so let's keep it as a reference implementation.

Changes to ht include poping potential placeholders in parent layer
before adding and swapping IR -> RI all over, for consistency.

1 files changed, 70 insertions, 61 deletions

diff --git a/src/ts.erl b/src/ts.erl
index e60a114..cf71ff5 100644
--- a/src/ts.erl
+++ b/src/ts.erl
@@ -7,78 +7,87 @@
 -module(ts).
 -include_lib("eunit/include/eunit.hrl").
 -export_type([tree_store/0]).
--export([new/0, store/3, append/3, truncate/2, retrieve/2, retrieve_hash/2, delete/2]).
+-export([new/0, add/3, delete/2, retrieve/2, count/2]).
 
-%% FIXME: swap IR -> RI for consistency with ht
-
-%% FIXME: Keep the arrays in an array instead of in a map? Or maybe an
-%% array of binaries? Hashes do have fixed lenght.
--record(tree_store, {arrays :: map()}). % Map of arrays, indexed by layer.
+%% FIXME: Keep the entries in binaries instead of lists? Hashes do
+%% have fixed lenght.
+-record(tree_store, {layers :: list()}). % orddict of lists, keyed on layer.
 -type tree_store() :: #tree_store{}.
 
+%%%%%%%%%%%%%%%%%%%%
+%% Public.
 new() ->
-    #tree_store{arrays = #{}}.
+    #tree_store{layers = orddict:new()}.
 
--spec store(tree_store(), tuple(), binary()) -> tree_store().
-store(S = #tree_store{arrays = Arrays}, {I, R}, Hash) ->
-    {A, NewArrays} = get_array(R, Arrays),
-    Index = case I of
-                append -> array:size(A);
-                N -> N
-            end,
-    S#tree_store{arrays = maps:put(R, array:set(Index, Hash, A), NewArrays)}.
+-spec add(tree_store(), non_neg_integer(), binary()) -> tree_store().
+add(S = #tree_store{layers = Layers}, Layer, Entry) ->
+    {NewLayers, List} = layer(Layers, rw, Layer),
+    NewList = [Entry | List],
+    S#tree_store{layers = orddict:store(Layer, NewList, NewLayers)}.
 
--spec retrieve(tree_store(), tuple()) -> {tuple(), binary()}.
-retrieve(#tree_store{arrays = Arrays}, {I, R}) ->
-    {{I, R},
-     case maps:get(R, Arrays, undefined) of
-         undefined -> undefined;
-         A -> array:get(I, A)
-     end}.
+-spec delete(tree_store(), non_neg_integer()) -> tree_store().
+delete(S = #tree_store{layers = Layers}, Layer) ->
+    List = layer(Layers, ro, Layer),
+    [_ | NewList] = List,
+    S#tree_store{layers = orddict:store(Layer, NewList, Layers)}.
 
--spec retrieve_hash(tree_store(), tuple()) -> binary().
-retrieve_hash(S, IR) ->
-    element(2, retrieve(S, IR)).
-
--spec delete(tree_store(), tuple()) -> tree_store().
-delete(S, {I, R}) ->
-    {A, NewArrays} = get_array(R, S#tree_store.arrays),
-    Index = case I of
-                last -> array:size(A) - 1;
-                N -> N
-            end,
-    S#tree_store{arrays = maps:put(R,
-                                   array:reset(Index, A),
-                                   NewArrays)}.
-append(S, R, Hash) ->
-    store(S, {append, R}, Hash).
+-spec retrieve(tree_store(), tuple()) -> binary() | undefined.
+retrieve(#tree_store{layers = Layers}, {Layer, Index}) ->
+    List = layer(Layers, ro, Layer),
+    Len = length(List),
+    case Index < Len of
+        true -> lists:nth(Len - Index, List);
+        false -> undefined
+    end.
 
-truncate(S, R) ->
-    delete(S, {last, R}).
+-spec count(tree_store(), non_neg_integer()) -> non_neg_integer().
+count(#tree_store{layers = Layers}, Layer) ->
+    length(layer(Layers, ro, Layer)).
 
-%% Private
-get_array(Layer, Arrays) ->
-    case maps:is_key(Layer, Arrays) of
-        true -> {maps:get(Layer, Arrays), Arrays} ;
-        false ->
-            NewArray = array:new(),
-            {NewArray, maps:put(Layer, NewArray, Arrays)}
+%%%%%%%%%%%%%%%%%%%%
+%% Private.
+-spec layer(list(), rw | ro, non_neg_integer()) -> list() | {list(), list()}.
+layer(Layers, Access, Layer) ->
+    case Access of
+        rw ->
+            case orddict:find(Layer, Layers) of
+                error -> {orddict:store(Layer, [], Layers), []};
+                {ok, List} -> {Layers, List}
+            end;
+        ro ->
+            case orddict:find(Layer, Layers) of
+                error -> [];
+                {ok, List} -> List
+            end
     end.
 
 %%%%%%%%%%%%%%%%%%%%
 %% Testing ts.
--define(TEST_VECTOR, {{{0,0}, <<00>>},
-                      {{0,1}, <<01>>},
-                      {{1,0}, <<10>>}}).
-store_test_() ->
-    T = ?TEST_VECTOR,
+add_retrieve_test_() ->
+    S = new(),
+    S0 = add(S, 0, <<00>>),
+    S1 = add(S0, 0, <<01>>),
+    S2 = add(S1, 1, <<10>>),
+    [?_assertEqual(2, count(S2, 0)),
+     ?_assertEqual(1, count(S2, 1)),
+     ?_assertEqual(<<10>>, retrieve(S2, {1,0})),
+     ?_assertEqual(<<00>>, retrieve(S2, {0,0})),
+     ?_assertEqual(<<01>>, retrieve(S2, {0,1})),
+     ?_assertEqual(<<00>>, retrieve(S2, {0,0})),
+     ?_assertEqual(undefined, retrieve(S2, {3,0})),
+     ?_assertEqual(undefined, retrieve(S1, {1,0}))].
+
+delete_test_() ->
     S = new(),
-    S0 = store(S, {0,0}, <<00>>),
-    S1 = store(S0, {0,1}, <<01>>),
-    S2 = store(S1, {1,0}, <<10>>),
-    [?_assertEqual(retrieve(S2, {1,0}), element(3, T)),
-     ?_assertEqual(retrieve(S2, {0,1}), element(2, T)),
-     ?_assertEqual(retrieve(S2, {0,0}), element(1, T)),
-     ?_assertEqual(retrieve_hash(S2, {3,0}), undefined),
-     ?_assertEqual(retrieve_hash(S1, {1,0}), undefined)
-    ].
+    S0 = add(S, 0, <<00>>),
+    S1 = add(S0, 0, <<01>>),
+    S2 = add(S1, 1, <<10>>),
+    S3 = delete(S2, 0),
+    S4 = add(S3, 0, <<99>>),
+    [?_assertEqual(2, count(S2, 0)),
+     ?_assertEqual(1, count(S3, 0)),
+     ?_assertEqual(2, count(S4, 0)),
+     ?_assertEqual(retrieve(S2, {0,1}), <<01>>),
+     ?_assertEqual(retrieve(S3, {0,1}), undefined),
+     ?_assertEqual(retrieve(S3, {0,0}), <<00>>),
+     ?_assertEqual(retrieve(S4, {0,1}), <<99>>)].