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);
}

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

On Tuesday, 12 November 2013 at 15:51:53 UTC, bearophile wrote:
> 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

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
Dan

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

On Tuesday, 12 November 2013 at 16:34:30 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?
>
> 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

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
Dan