[erlang-questions] Ordered set with lower_bound

[Richard O'Keefe]

On Oct 9, 2009, at 1:05 PM, Igor Ribeiro Sucupira wrote:

> Hello.
>
> Indeed, I "have hoped for O (1) after the first O (log N) call".

Just off the top of my head, gb_sets iterators give you O(1)
*amortised* time per call to next/1.  So the
{geq,leq,range}_{reverse_,}iterator functions I sent in my
previous message give you in O(log N) time an iterator which
subsequently gives you O(1) *amortised* time per call.

> But, thinking again at my case, I don't really need the iterator.
> Given a key K, I believe it will be enough to find the smallest key
> that is greater or equals K.

The gb_set data structure, or any balanced tree, can do that in
O(log N) time too.  With the functions in my previous message,

	case gb_sets2:next(gb_sets2:geq_iterator(Set, K))
	  of {M, _} ->
	     M is the smallest element of Set that
              is greater than or equal to K
            ; none ->
	     there is no such M
	end

will do the trick.  You can of course do it more efficiently than that,
but only by writing even more code inside the module.
>
>