From: MoonWolf Date: 2004-04-22T20:08:39+09:00 Subject: [ruby-dev:23430] Re: Ruby/Bsearch This is a multi-part message in MIME format. --------------040305020705010700030909 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit MoonWolfです。Bsearchを使ったSortedArrayを書いてみました。 パッチを添付します。 Masayoshi Takahashi wrote: > 1) first_by_bsearch とか first_sorted という名前をつける。 > (無難だけど「もっと良い名前」とは思えない。) > > upper_boundary と lower_boundary は元々Arrayにないので、 > そのまま追加してしまっていいのかも。 > > # rangeは使い方を含めてしっくりこないのでパス。 > > 高橋征義 (TAKAHASHI Masayoshi) E-mail: maki@rubycolor.org > 以前、priority queueが標準で欲しいと思ったことがあります。 > メソッド名は上記案を参考にしています。 priority queueがどんなものかは、よくわかりませんが、 SortedArrayではこんなことが出来ます。 irb(main):001:0> a=SortedArray.new {|x,y| x[0]<=>y[0]} => [] irb(main):002:0> a << [5,"a"] => [[5, "a"]] irb(main):003:0> a << [5,"b"] => [[5, "a"], [5, "b"]] irb(main):004:0> a << [1,"x"] => [[1, "x"], [5, "a"], [5, "b"]] irb(main):005:0> a << [1,"y"] => [[1, "x"], [1, "y"], [5, "a"], [5, "b"]] irb(main):006:0> a << [1,"z"] => [[1, "x"], [1, "y"], [1, "z"], [5, "a"], [5, "b"]] irb(main):007:0> a.shift => [1, "x"] irb(main):008:0> a => [[1, "y"], [1, "z"], [5, "a"], [5, "b"]] pushしているArrayの第1要素がpriorityのつもりです。 --------------040305020705010700030909 Content-Type: application/x-gzip; name="sorted.patch.gz" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="sorted.patch.gz" H4sICHelh0AAA3NvcnRlZC5wYXRjaADtHGtz27jxc/wrYN3UQ0WUQ8nO4yzLF8fxdXzjODkn vl6ayXAoCZLo0KTKh2y39X/vLsAHAIKSGOfVOTEzMQUsdhf7BEAAJ/6I3uwRJwyd2+3hRv/+ z8b50Vsydj26Rx5F4fBRmAxuH6X4zflGSOPQpXPXn5AQ/kRu4JPOdmf38cbIHY9JOyHtkP3O eWq329n7g84uOZyFpGtZu8Ta3bOe7HV3SduC5wFH0mq1cuButwDuWHu7z/Z2uxx44/lz0u48 MX8mLfb/8+cb5CfXH3rJiJJGErve9rQhFkUxK9ho/3F4enFMwoE9PEQqJnv9w/ESGvU2Wgtq +fvbIIzpiFX2EF0UO7E7JCcviTuyh1czwKEWmfh34AXDT+xt6HgeNiU/jejY9Sk5PH9vvzz+ 9fDi9J399uSfx6TzBKqxg92fH3fNJ6TF/z7rsG7eYducCmMYfjnhrQ2Ig6HxyXOiqLnRIvDw 7rASYOw/vPDs+B+vX/xmQAuTRHGYDGNyzjrU7HEAqH17/O7iDQdhrU3yzj48Pz98jzAcCirb Bx71SZ9YPaFoFodqkZPcbA+dmSOUgyzduRPaEY0Ng7HZZNQKUf3uu17GUdqGxknokwIcau+Q Ha00fHptpLwDl6lAFImwIi8AUwaQQkIcCJAAwyXJ5gJwx8TA/u8Tq0mg5QPoU+i4ETXghR6G k+MwDEKTNHw6Ae7mlNs1idx/U2IEIX+Jg4AM3EmzkfX1TsZ+QCyytYX8kYesRTBOBUD2+6xn C2kLJFNKVYT6fewHvLVaKcA50zhaQTNT6+Hp6esj+4xzwAWrAxYUzgUrKTDXnKw14JwJ2/Xd 2HU8YBmwTYYmwE/m+P9tpkTXj7Fw2JOU+hDh5CJOKdWqoOcCAiVjkrnjSZaGMgF2mCXaE1Cd b8+MJpM0SR/RgBXLzVvOQrCapiJv6kV0RUSiC9xJnjCwUVJXAYTcWybznsR4NHR8gJhEkgQb Vrdhki3e5S3oczNVusCNpEbZu0saTNkqKCMxRNlBi9389eTPs4tX9hsDCcrCA9qAGOPplIKc mJHa8e2McliBIKLdPDs5BTTIsIRFkERIZ54zpFyACNhTwFS+BZHmXeDdBZ67p6/P/i6xovq6 QH5Vl1/JwQ000malmy8ju7q3H+gdVraF48zd1UhgknIAKFlPKQgIbFzRKxhheBrEAJprUB81 8J8SMkbJzCjig8b3eRGAZREds4OSz82S8Rc8vLx4w1MioOChKO3Pq+NXR2/eZ/2A2qwflSLT ERFkx1FwU1RBV86dGcREjSl5MEqFCtQyoeqD8SCiTjic2l5wTUN7ECT+CIorArMSl8thuVIz IY0SL5agPtHMV1ngDh1/Qu0Bnbh+ubiQDQ/yyKxJrtyRSZLZjIa5HqNrNx5OGfuCqQ8dCMnW nuBfBTE1AGb04L1SQfgMQup86kkUOgKFNFAHg0vbjexPrj+yweNRVB+sj3yoeY6kmv3+7zBG o7rAl3OJ/ORttwTmsx/oVCqvZkcNkizWLkl7yyLQVRLFZEAJjnLpiIC4p8QhDGNDpXcnhOJS WsQHTCB/75O0g2pkr1RVLXUJOlmx+9dO6MMkyGgwSN5F4gcxSSI6WtjXhUbSFc3wy+oYxZmK sSOKccV+1+pzZSdh0uOAq6u91JjSdYi+7CdXAxqSYIyMJ1fUjyNi/G1ExjCA7jQbLAgNtYMk FgVwmCFYSJt0UlAWF5TaVimcXE9hHmwwTK0O2ezzZpJoeLSaC32HuAOIeSvAmTZ5RLr1ZT7n w6Rbl3ojIx3rgAhYBL41gVBTErrWi1Ic48RHp9RjMfO5asdEO6lQJXKdj4/mzX2rxHAmdEC6 lLFMBQqsbrzLsxWS7QJ9g4t0tczFYNeZ69tnrnXKWqesdcpap6wfK2X1v1fOSjWyYtYau2EU /7jJap2T1jlpnZP+EjmJxwwekOssCaW4pPjLcTUP+qVFMGl1k0dOXP2WGZLz1gryXpyLVLaK lfqSGy1LSCVUVdnpTiOVeRPTtLWaDNKKPJKvsnbnrFPJOpWsU8k6lWg7+QOkkiVrND2leT6m VsMuTpYWJZ79frvzV0w1c0wwudSs5ldLNczwv3iuAa8yqZ9NuPj/UPbZYxLAdQ8j5ELJAgF+ SET+EKlJ+LeaXsW+lGKHw4jeGBH1xqC7mF7Jm1OwvCeVIExP2cegLhSauow8N5nJSoLLZrtt dVkhDVVInseqHGKFJYVVFxCIwTjqi18oU0HknyiRAtv6sGRZQN5TZZKuSSRvYXjTpQKU8r2W HURkhbuV8Mq9/R5r5UiXQeej7EKjq/n9vfT0OTri1iJLs15glNHo9fOlht4VXyGqnD38Mby9 tIpYMg4B5quuIX7zEKAzr2pPu6+ZCQajMbdvt/7IdvpwDa4jwVeOBOrabnXiZ9uRo+8eDda5 f5370bLHDtD7K/l8todc0E4fQ/IvfOhO9gqZLPTkWRJN7+fF990WUGhdv+CiXWgpzEEbF77N d0cpMOGzDiCiR2e9/T5fLTnbyWzkxDQVbqpTk1i5jGDWu2NkXSDK3Dg1f/1W3WEA8omNG5PI 23WxQPEQV3KB3NBwySwOkA0jn5UXoQt3N2fBL/+4cKAk9nEQGm7f6rn7iNZttXRLa4Wf3yi2 gRtqmxrNyTHmZpUYYl99wdUS5oJ8G367nZ8LKfrBtgIzHNBjbVxccKgmwxTZw5CicYh8i4eO Vj+eoRxMWnbsJsPtlpTODh7U3puvWcjUbZdnyKstiPV0qQmh6Nk6r/tRbzh11ZD47r/sAcTg xRvfuSOZl6a0fVx/eEQNzymGqq3ovPoSKrNEsditeIK43F/47S8Tui7UKzvZKyM9PjWjPaJ2 m5rCS8nPma60EVZDU0tACP+r0CoLRh24aPi4zE9wiQ8O6tsr90U9vvDBbXU+qnaA5Zfq559q DuTPDqUeykFUcxBJHbXUc5bFfsKjTqicJyk8RuNzvWou1EDvJdF9Mt6NwtpNRluXCo/Ykap3 eJgqPbOJhLPw+f+VIfFEMcq6wzJjV1VfWqzJIDsmmTrRtKfINtf1zsJzQFZx8Ac/ajFBEFcI XJ00CBJVMNn5O2myjzyK5346mUt9LE53wLAodv2ECiJT88dOBY6qRL6zTLqOPyoLdyXpVsq1 I1hq5nT5FznExuvz6tR4GX0BbAX1FGFAr6JulYrSLCfFsm4uzd5yXYJc5ouO5ahKm1f7QW2V gVd+YY3V0EilYr+PHnZSPbD5+ldTBHn0kDC7i6CckiAc0ZDCNBwGonRCwzZb3acjcGDPo8PY DfyIjSj9WxIMLqFkm2wQkuIgDBqvTgD1hjGgjHFS5URQQY4AOfnNmTvbhBySfJTKmhA34mhg KAwj1RFEfdzTEVKPA8HPeErZh00gjq/sKGi73Y6nQMONgIifogKAdodfMLBj7T4zn5HWztPu jrn7jN0vkAqPX05gX9F4GrAP2tmNCI0x0Iypv9nIY35awlIjd8/lWHycOkYFDv47bZ2nXdHx uQWmGIc4KTAaQjVHNZRuMijg2VSCDc3K8aSYa5TbCZxLbRrFKXVOWDm6boKMy9giUL1H48Cv xvvho4Avm2vpsa3Gm/ToGJWeWnRgLKISUOiw47Lapw4dvmagIyWvKuhI1aGzv1/RHSma6EHq 0EEsekry0oAGpKYdgL9rCUk7EbSc1KETVhKSP4LeVz9p9P+lTEnND2VKSrJagVpLcEQcwZu1 eG0LrXEYW6/1ltDawY0ldRr/V2iMKx71u44ZXkCCP4Vh14oINhUMQnqoxw07C2EP8p06Al7p uISo9Fp+ghtkZfzljUWOjL8eAXlrETNflYAMYtbtgbTvSUtABqlLQNrgxf1PJcCqlukAco4T VeNv6NRdMhjoAh0vSqH9hkB5CfTDGrB4Z0UNcNePaBjXaJBeY1KrxZyG0We02KzRJApq9QLB 66BP/GjqjhkFZjd8jYwP93CYHfpGY79/UNT70QwG1jbfPSsA2bZQZds5C+myH5GhsUgE4Xtn JZB8lzTJR7TpbWBENxrlVcpAFKYYJ/yONrxIbXv61a5o4+irb2izlBvarMcZR3hBG3998FS4 nu3J3o611xGuZ7P49Wwp6JLb2R4/tfDuMvzzlE0sNsj5xYv39vGf747Pz7JTBCCo12ya1Kuq Tu9aa+lr5fvY9DDZ7W4V1S/ciZ9cVVYf8Y8U/wPJs4f7aE8AAA== --------------040305020705010700030909--