Subject: Re: [rfh] do I need to use something more complex to do this?

From: Andreas Ericsson <[email-masked]>
Date: Wed, 10 Apr 2013 17:23:21 +0200

On 04/10/2013 04:40 PM, Junio C Hamano wrote:
> I have set of items with two attributes, <X,Y>, and would like to
> keep them in some data structure in such a way that it is efficient
> to (1) add a new item to the data structure, and (2) pick an item in
> a specific order. There can be multiple items that share the same
> value for X, or Y, or both X and Y, and it does not matter in what
> order items comes out among those that share the same <X,Y>.
>
> The type of X is totally ordered. The type of Y also usually is, but
> Y can take a special value U(nspecified).
>
> Now on to the "specific" order I want to pick an item.  I'd like to
> take the item with the largest value of Y in general, and tiebreaking
> on the value of X which also I prefer to take from larger to smaller.
>
> But with a twist.
>
> When I am picking an item <X=n,Y=m>, there should be no item
> remaining in the data store with a value of Y that is smaller than m
> (duplicates are allowed, so there can still be items with Y=m), and
> also when I am picking <X=n,Y=m>, there should be no item with
> Y=Unspecified that has a value of X that is equal or smaller than n.
>

So X is primary sort and Y is secondary, except Y=Undefined trumps all
other values for Y, but never trumps X as primary sort.

Can't you just have U be the largest unsigned integer value of the
type you choose? For this particular application, I doubt there's any
risk of the defined numbers catching up with it.

I might have missed something though. This seems a bit too trivial for
you to ask for help.

-- 
Andreas Ericsson                   [email-masked]
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.