digitalmars.D.learn - how use lowerBound with just sorting key, not complete values
- Daniel Davidson (30/30) Nov 12 2013 The following code works for finding the lower bound based on
- bearophile (31/33) Nov 12 2013 You can use a map to perform a projection:
- Daniel Davidson (8/42) Nov 12 2013 Yes, but that is only giving the dates. I want the actual array
- bearophile (28/33) Nov 12 2013 Second try:
- Daniel Davidson (9/43) Nov 12 2013 Well, I think that is it. Thanks, bearophile!
The following code works for finding the lower bound based on needle. But I have to create a needle which I don't want to do. How can I use lowerBound with just the sortKey, date in this case? So I want to do something like the following - but it won't work. Is there a way to search an array I know is ordered by date by only supplying date? assumeSorted!q{ a.date < b.date }(sarr) .lowerBound(Date(2000,2,1)); Thanks Dan ------------------------------------------------------- import std.stdio; import std.range; import std.datetime; import std.algorithm; import std.array; struct S { Date date; string foo; } void main() { auto sarr = [ S(Date(2000,1,1), "x"), S(Date(2000,2,1), "a"), S(Date(2000,3,1), "foo") ]; assert(sort!q{ a.date < b.date }(sarr).array == sarr); auto needle = S(Date(2000,2,1)); writeln(assumeSorted!q{ a.date < b.date }(sarr) .lowerBound(needle)); writeln(sarr); }
Nov 12 2013
Daniel Davidson:Is there a way to search an array I know is ordered by date by only supplying date?You can use a map to perform a projection: import std.stdio, std.range, std.datetime, std.algorithm, std.array; struct S { Date date; string foo; } void main() { auto sarr = [S(Date(2000, 1, 1), "x"), S(Date(2000, 2, 1), "a"), S(Date(2000, 3, 1), "foo")]; assert(sarr.isSorted!q{ a.date < b.date }); auto needle = S(Date(2000, 2, 1)); sarr .assumeSorted!q{ a.date < b.date } .lowerBound(needle) .writeln; sarr.writeln; sarr .map!(s => s.date) .assumeSorted .lowerBound(Date(2000, 2, 1)) .writeln; } Output: [S(2000-Jan-01, "x")] [S(2000-Jan-01, "x"), S(2000-Feb-01, "a"), S(2000-Mar-01, "foo")] [2000-Jan-01] Bye, bearophile
Nov 12 2013
On Tuesday, 12 November 2013 at 15:51:53 UTC, bearophile wrote:Daniel Davidson:Yes, but that is only giving the dates. I want the actual array elements. Suppose S is a large object with lots of extra fields in addition to `string foo`. There should be a way to pull out the lower bound based on a date without creating a needle (S). Maybe lowerBound is not the right function? Thanks DanIs there a way to search an array I know is ordered by date by only supplying date?You can use a map to perform a projection: import std.stdio, std.range, std.datetime, std.algorithm, std.array; struct S { Date date; string foo; } void main() { auto sarr = [S(Date(2000, 1, 1), "x"), S(Date(2000, 2, 1), "a"), S(Date(2000, 3, 1), "foo")]; assert(sarr.isSorted!q{ a.date < b.date }); auto needle = S(Date(2000, 2, 1)); sarr .assumeSorted!q{ a.date < b.date } .lowerBound(needle) .writeln; sarr.writeln; sarr .map!(s => s.date) .assumeSorted .lowerBound(Date(2000, 2, 1)) .writeln; } Output: [S(2000-Jan-01, "x")] [S(2000-Jan-01, "x"), S(2000-Feb-01, "a"), S(2000-Mar-01, "foo")] [2000-Jan-01] Bye, bearophile
Nov 12 2013
Daniel Davidson:Yes, but that is only giving the dates. I want the actual array elements. Suppose S is a large object with lots of extra fields in addition to `string foo`. There should be a way to pull out the lower bound based on a date without creating a needle (S). Maybe lowerBound is not the right function?Second try: import std.stdio, std.range, std.datetime, std.algorithm, std.array, std.typecons; struct S { Date date; string foo; } void main() { auto sarr = [S(Date(2000, 1, 1), "x"), S(Date(2000, 2, 1), "a"), S(Date(2000, 3, 1), "foo")]; assert(sarr.isSorted!q{ a.date < b.date }); sarr.writeln; auto needle = S(Date(2000, 2, 1)); sarr .map!(s => s.date) .zip(sarr.length.iota) .assumeSorted!q{ a[0] < b[0] } .lowerBound(tuple(needle.date, 0)) .map!(p => sarr[p[1]]) .writeln; } Output: [S(2000-Jan-01, "x"), S(2000-Feb-01, "a"), S(2000-Mar-01, "foo")] [S(2000-Jan-01, "x")] Bye, bearophile
Nov 12 2013
On Tuesday, 12 November 2013 at 16:34:30 UTC, bearophile wrote:Daniel Davidson:Well, I think that is it. Thanks, bearophile! Pardon the redirect, but while you are at it, I would appreciate your take on this one (http://forum.dlang.org/post/gofijmqwhfcwgbruzkvz forum.dlang.org). I'm sure you'll improve it and teach me a few things on the way ;-) Thanks DanYes, but that is only giving the dates. I want the actual array elements. Suppose S is a large object with lots of extra fields in addition to `string foo`. There should be a way to pull out the lower bound based on a date without creating a needle (S). Maybe lowerBound is not the right function?Second try: import std.stdio, std.range, std.datetime, std.algorithm, std.array, std.typecons; struct S { Date date; string foo; } void main() { auto sarr = [S(Date(2000, 1, 1), "x"), S(Date(2000, 2, 1), "a"), S(Date(2000, 3, 1), "foo")]; assert(sarr.isSorted!q{ a.date < b.date }); sarr.writeln; auto needle = S(Date(2000, 2, 1)); sarr .map!(s => s.date) .zip(sarr.length.iota) .assumeSorted!q{ a[0] < b[0] } .lowerBound(tuple(needle.date, 0)) .map!(p => sarr[p[1]]) .writeln; } Output: [S(2000-Jan-01, "x"), S(2000-Feb-01, "a"), S(2000-Mar-01, "foo")] [S(2000-Jan-01, "x")] Bye, bearophile
Nov 12 2013