{"thread":{"id":"33459","subject":"[rfh] do I need to use something more complex to do this?","startedAt":"2013-04-10T14:40:18Z","lastAt":"2013-04-10T18:19:57Z","messageCount":3,"participants":["Junio C Hamano","Andreas Ericsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"213776","messageId":"7vk3oao3e5.fsf@alter.siamese.dyndns.org","threadId":"33459","inReplyTo":null,"subject":"[rfh] do I need to use something more complex to do this?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-10T14:40:18Z","receivedAt":"2013-04-10T14:40:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I have set of items with two attributes, , and would like to\nkeep them in some data structure in such a way that it is efficient\nto (1) add a new item to the data structure, and (2) pick an item in\na specific order. There can be multiple items that share the same\nvalue for X, or Y, or both X and Y, and it does not matter in what\norder items comes out among those that share the same .\n\nThe type of X is totally ordered. The type of Y also usually is, but\nY can take a special value U(nspecified).\n\nNow on to the \"specific\" order I want to pick an item. I'd like to\ntake the item with the largest value of Y in general, and tiebreaking\non the value of X which also I prefer to take from larger to smaller.\n\nBut with a twist.\n\nWhen I am picking an item , there should be no item\nremaining in the data store with a value of Y that is smaller than m\n(duplicates are allowed, so there can still be items with Y=m), and\nalso when I am picking , there should be no item with\nY=Unspecified that has a value of X that is equal or smaller than n.\n\nE.g. if I have these 6 items (ignore the lines between the items for\nnow):\n\n <104,U>--<105,U>--<106,4>\n /\n <101,U>--<100,U>--<102,3>--<104,4>\n\nI would want to pick them up in this order:\n\n <106,4> <105,U> <104,U> <104,4> <102,3> <101,U> <100,U>\n\nI see how this can easily be done by using a two priority lists,\ni.e. one for items with Y=Unspecified that is sorted by X, and the\nother for all other items that is sorted by . Peek the top of\nboth, and pick the top of the former until its X is smaller than the\nvalue of X of the top of the latter, otherwise pick the top of the\nlatter. I am wondering if I can use less complex data structure,\nlike a single ordered sorted array, with a clever comparison\nfunction.\n\nFor the curious, the items in the above picture represents commits,\nand lines are ancestry chains between them. I am thinking how we can\nextend the still_interesting() function with an optional generation\nnumber.\n"},{"id":"213779","messageId":"516583E9.9030200@op5.se","threadId":"33459","inReplyTo":"7vk3oao3e5.fsf@alter.siamese.dyndns.org","subject":"Re: [rfh] do I need to use something more complex to do this?","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2013-04-10T15:23:21Z","receivedAt":"2013-04-10T15:23:21Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 04/10/2013 04:40 PM, Junio C Hamano wrote:\n> I have set of items with two attributes, , and would like to\n> keep them in some data structure in such a way that it is efficient\n> to (1) add a new item to the data structure, and (2) pick an item in\n> a specific order. There can be multiple items that share the same\n> value for X, or Y, or both X and Y, and it does not matter in what\n> order items comes out among those that share the same .\n>\n> The type of X is totally ordered. The type of Y also usually is, but\n> Y can take a special value U(nspecified).\n>\n> Now on to the \"specific\" order I want to pick an item. I'd like to\n> take the item with the largest value of Y in general, and tiebreaking\n> on the value of X which also I prefer to take from larger to smaller.\n>\n> But with a twist.\n>\n> When I am picking an item , there should be no item\n> remaining in the data store with a value of Y that is smaller than m\n> (duplicates are allowed, so there can still be items with Y=m), and\n> also when I am picking , there should be no item with\n> Y=Unspecified that has a value of X that is equal or smaller than n.\n>\n\nSo X is primary sort and Y is secondary, except Y=Undefined trumps all\nother values for Y, but never trumps X as primary sort.\n\nCan't you just have U be the largest unsigned integer value of the\ntype you choose? For this particular application, I doubt there's any\nrisk of the defined numbers catching up with it.\n\nI might have missed something though. This seems a bit too trivial for\nyou to ask for help.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"213795","messageId":"7vr4iimenm.fsf@alter.siamese.dyndns.org","threadId":"33459","inReplyTo":"7vk3oao3e5.fsf@alter.siamese.dyndns.org","subject":"Re: [rfh] do I need to use something more complex to do this?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-10T18:19:57Z","receivedAt":"2013-04-10T18:19:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I have set of items with two attributes, , and would like to\n> keep them in some data structure in such a way that it is efficient\n> to (1) add a new item to the data structure, and (2) pick an item in\n> a specific order. There can be multiple items that share the same\n> value for X, or Y, or both X and Y, and it does not matter in what\n> order items comes out among those that share the same .\n>\n> The type of X is totally ordered. The type of Y also usually is, but\n> Y can take a special value U(nspecified).\n>\n> Now on to the \"specific\" order I want to pick an item. I'd like to\n> take the item with the largest value of Y in general, and tiebreaking\n> on the value of X which also I prefer to take from larger to smaller.\n>\n> But with a twist.\n>\n> When I am picking an item , there should be no item\n> remaining in the data store with a value of Y that is smaller than m\n> (duplicates are allowed, so there can still be items with Y=m), and\n> also when I am picking , there should be no item with\n> Y=Unspecified that has a value of X that is equal or smaller than n.\n>\n> E.g. if I have these 6 items (ignore the lines between the items for\n> now):\n>\n> <104,U>--<105,U>--<106,4>\n> /\n> <101,U>--<100,U>--<102,3>--<104,4>\n>\n> I would want to pick them up in this order:\n>\n> <106,4> <105,U> <104,U> <104,4> <102,3> <101,U> <100,U>\n\nNote that with the above specification, a possible solution is to\nshow all the items with Y=Unspecified before showing others, but\nthat would not be ideal for the intended use case; pretending Y=U as\nif Y=max_range is not a usable workaround.\n\nThis is \"I create a stream of items with specified Y in descending\norder. There are some items with Y=Unspecified and I want to find\nappropriate places to mix the latter into that stream\".\n\nBecause the desired ordering is not a total order, I need to go\nto the \"pair of priority list\" route, I think.\n>\n> I see how this can easily be done by using a two priority lists,\n> i.e. one for items with Y=Unspecified that is sorted by X, and the\n> other for all other items that is sorted by . Peek the top of\n> both, and pick the top of the former until its X is smaller than the\n> value of X of the top of the latter, otherwise pick the top of the\n> latter. I am wondering if I can use less complex data structure,\n> like a single ordered sorted array, with a clever comparison\n> function.\n>\n> For the curious, the items in the above picture represents commits,\n> and lines are ancestry chains between them. I am thinking how we can\n> extend the still_interesting() function with an optional generation\n> number.\n"}]}