[erlang-questions] Ordered set with lower_bound

[Paul Mineiro]

On Mon, 12 Oct 2009, Paul Mineiro wrote:

> 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

Another thought: if the frames are being added in temporal order, you
could leverage the min-stack trick.

http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1

-- p