Re: [rfh] do I need to use something more complex to do this?
Junio C Hamano writes: > I have set of items with two attributes, , 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 . > > 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 , 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 , 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> Note that with the above specification, a possible solution is to show all the items with Y=Unspecified before showing others, but that would not be ideal for the intended use case; pretending Y=U as if Y=max_range is not a usable workaround. This is "I create a stream of items with specified Y in descending order. There are some items with Y=Unspecified and I want to find appropriate places to mix the latter into that stream". Because the desired ordering is not a total order, I need to go to the "pair of priority list" route, I think. > > 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 . 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [rfh] do I need to use something more complex to do this?
On 04/10/2013 04:40 PM, Junio C Hamano wrote: I have set of items with two attributes, , 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 . 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 , 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 , 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 andreas.erics...@op5.se 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. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[rfh] do I need to use something more complex to do this?
I have set of items with two attributes, , 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 . 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 , 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 , 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 . 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
