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

[Ulf Wiger]

Thank you for the bugfix. :)  Happy that the code was sitll correct...

I figured that I would still get a decent spread of different trees, since I built them from variable-length lists of random integers - but of course, your approach is better still.

BR,
Ulf W

On 16 Mar 2011, at 20:58, John Hughes wrote:

> ?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 
> 

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