[erlang-questions] first, next, prev, last in gb_trees

[John Hughes]

?Nice!

Slight typo: you tested prev twice... your prop_next actually tested prev, 
it's a copy-and-paste of prop_prev without the renaming to next!

I'd suggest testing all the properties at once with 
eqc:module({numtests,1000},gb1). That should work in eqcmini too.

One drawback of your approach is that you only test next and prev on 
gb_trees constructed using empty and enter. Conceivably the other functions 
could create gb_trees with a different structure that you might fail on. 
Here's some code that uses ALL of the constructors to build the test data 
(no bugs found though!).

John

%% gb_tree constructors

gb() ->
    ?SIZED(Size,
    frequency([{1,{call,gb_trees,empty,[]}},
        {1,{call,gb_trees,from_orddict,[orddict()]}},
        {Size,?LAZY(compound_gb())}])).

compound_gb() ->
    ?LETSHRINK([GB],[gb()],
        oneof([{call,gb_trees,Fun,Args++[GB]}
        || [Fun|Args] <-
        lists:map(fun tuple_to_list/1,gb_constructors())]
       ++
    [{call,erlang,element,[3,{call,gb_trees,take_smallest,[GB]}]},
     {call,erlang,element,[3,{call,gb_trees,take_largest,[GB]}]}])).

gb_constructors() ->
    [{balance},
     {delete,key()},
     {delete_any,key()},
     {enter,key(),val()},
     {insert,key(),val()},
     {update,key(),val()}].

key() ->
    nat().

val() ->
    int().

orddict() ->
    ?LET(L,list({key(),val()}),
  orddict:from_list(L)).

%% Properties

prop_prev2() ->
    ?FORALL(GB,eqc_symbolic:well_defined(gb()),
     begin
  T = eval(GB),
  ok == all_prev(lists:reverse(keys(T)), T)
     end).

prop_next2() ->
    ?FORALL(GB,eqc_symbolic:well_defined(gb()),
     begin
  T = eval(GB),
  ok == all_next(keys(T), T)
     end).

keys(T) ->
    [K || {K,_} <- gb_trees:to_list(T)].


----- Original Message ----- 
From: "Ulf Wiger" <ulf.wiger@REDACTED>
To: "Erlang Questions" <erlang-questions@REDACTED>
Sent: Wednesday, March 16, 2011 6:13 PM
Subject: [erlang-questions] first, next, prev, last in gb_trees


When I use ordered_set ets over gb_trees it has more than once been due to 
the fact that you can do wonderful stuff with first, next, prev and last - 
and gb_trees doesn't have them.

I've made a stab at implementing these functions for the gb_trees data 
structure, together with a quickcheck spec to verify that they work as 
expected (you can use eqc mini to run the tests). I think they are 
reasonably efficient, but perhaps someone can think of a way to optimize 
them? Have at it, and pls use the spec to verify that you didn't break them* 
(recalling that an incorrect program can be made arbitrarily fast)

* e.g. eqc:quickcheck(gb1:prop_first())

BR,
Ulf W (hoping the list server won't chop the 150-line attachment)




--------------------------------------------------------------------------------


>
> Ulf Wiger, CTO, Erlang Solutions, Ltd.
> http://erlang-solutions.com
>
>
>
>
>


--------------------------------------------------------------------------------


>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED