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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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.

E.g. if I have these 6 items (ignore the lines between the items for
now):

            <104,U>--<105,U>--<106,4>
           /
    <101,U>--<100,U>--<102,3>--<104,4>

I would want to pick them up in this order:

    <106,4> <105,U> <104,U> <104,4> <102,3> <101,U> <100,U>

I see how this can easily be done by using a two priority lists,
i.e. one for items with Y=Unspecified that is sorted by X, and the
other for all other items that is sorted by <Y,X>. Peek the top of
both, and pick the top of the former until its X is smaller than the
value of X of the top of the latter, otherwise pick the top of the
latter.  I am wondering if I can use less complex data structure,
like a single ordered sorted array, with a clever comparison
function.

For the curious, the items in the above picture represents commits,
and lines are ancestry chains between them. I am thinking how we can
extend the still_interesting() function with an optional generation
number.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html




[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]