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

John Hughes <>
Wed Mar 16 20:58:52 CET 2011


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!).


%% gb_tree constructors

gb() ->

compound_gb() ->
        || [Fun|Args] <-
        lists:map(fun tuple_to_list/1,gb_constructors())]

gb_constructors() ->

key() ->

val() ->

orddict() ->

%% Properties

prop_prev2() ->
  T = eval(GB),
  ok == all_prev(lists:reverse(keys(T)), T)

prop_next2() ->
  T = eval(GB),
  ok == all_next(keys(T), T)

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

----- Original Message ----- 
From: "Ulf Wiger" <>
To: "Erlang Questions" <>
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())

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: 

More information about the erlang-questions mailing list