www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - how use lowerBound with just sorting key, not complete values

reply "Daniel Davidson" <nospam spam.com> writes:
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
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
parent reply "Daniel Davidson" <nospam spam.com> writes:
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
Nov 12 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
parent "Daniel Davidson" <nospam spam.com> writes:
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
Nov 12 2013