[erlang-questions] Ordered set with lower_bound

Paul Mineiro paul-trapexit@REDACTED
Mon Oct 12 20:23:56 CEST 2009


On Mon, 12 Oct 2009, Paul Mineiro wrote:

> On Mon, 12 Oct 2009, Max Lapshin wrote:
>
> > > If by "frame number N" you mean "the Nth object in the ordered set"
> > > then you can use ets:slot for this
> > >
> > > Colm
> >
> > No,no, I was not too clear: I store milliseconds as id of frame and
> > need something like following expression:
> >
> > seek(Time) ->
> >   "SELECT id FROM frames WHERE is_keyframe = 't' AND timestamp <= Time
> > ORDER BY id DESC limit 1"
> >
> > Something like this. Binary tree will be ideal.
>
> If you had an ets ordered_set table with tuple primary key { is_keyframe,
> timestamp } then you could call ets:lookup (Tab, { 't', Time }) to catch
> the '=' case, and then ets:prev (Tab, { 't', Time }) for the '<' case.
> You'd have to confirm the correct is_keyframe in the return value when
> using ets:prev/2.
>
> If this primary key is not convenient, create a second table with entries
> #secondary{ is_keyframe_and_timestamp :: { bool (), number () },
>             original_primary_key :: any () }
> and then do the join yourself.
>
> -- p
>

missed the "ORDER BY id DESC" part, but you can do that by adding id to
the tuple at the end.

another wrinkle, ets uses erlang term order, so for instance if id is
integral and you want to probe with ets:prev/2 you should pick an id whose
type is not actually used but which will cause it to sort above in erlang
term order, e.g., the empty atom will sort higher than any integer.
happily you can skip the ets:lookup/2 call in this case, but you'll have
to verify that is_keyframe and timestamp are correct in the return value
of ets:prev/2.

-- p


More information about the erlang-questions mailing list