www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Binary search in structs

reply "FreeSlave" <freeslave93 gmail.com> writes:
I have array of structs sorted by specific field. How can I 
perform binary search using this field as a key?

Currently I ended up with this, but it gives error:

struct S
{
     int i;
     string s;
}

import std.range;

void main(string [] args)
{
     S[] structs = [{1,"hello"}, {2,"world"}, {3, "!"}]; //sorted 
by i

     auto sortedRange = assumeSorted!(function bool(ref const S 
item, int needle) {
         return item.i < needle;
     })(structs);

     sortedRange.trisect(2); //compilation error
}
Apr 05 2015
parent reply "w0rp" <devw0rp gmail.com> writes:
On Sunday, 5 April 2015 at 23:06:27 UTC, FreeSlave wrote:
 I have array of structs sorted by specific field. How can I 
 perform binary search using this field as a key?

 Currently I ended up with this, but it gives error:

 struct S
 {
     int i;
     string s;
 }

 import std.range;

 void main(string [] args)
 {
     S[] structs = [{1,"hello"}, {2,"world"}, {3, "!"}]; 
 //sorted by i

     auto sortedRange = assumeSorted!(function bool(ref const S 
 item, int needle) {
         return item.i < needle;
     })(structs);

     sortedRange.trisect(2); //compilation error
 }
I believe you have to pass trisect a value of S. So S(2, "") would do here, I suppose.
Apr 05 2015
parent reply "FreeSlave" <freeslave93 gmail.com> writes:
On Sunday, 5 April 2015 at 23:15:04 UTC, w0rp wrote:
 On Sunday, 5 April 2015 at 23:06:27 UTC, FreeSlave wrote:
 I have array of structs sorted by specific field. How can I 
 perform binary search using this field as a key?

 Currently I ended up with this, but it gives error:

 struct S
 {
    int i;
    string s;
 }

 import std.range;

 void main(string [] args)
 {
    S[] structs = [{1,"hello"}, {2,"world"}, {3, "!"}]; 
 //sorted by i

    auto sortedRange = assumeSorted!(function bool(ref const S 
 item, int needle) {
        return item.i < needle;
    })(structs);

    sortedRange.trisect(2); //compilation error
 }
I believe you have to pass trisect a value of S. So S(2, "") would do here, I suppose.
Of course I could pass dummy object, but this is ugly solution. I hoped there's some better one.
Apr 05 2015
parent "FreeSlave" <freeslave93 gmail.com> writes:
I think I found solution using opBinaryRight

import std.range;

struct S
{
     int i;
     string s;

     int opCmp(int i) {
         return this.i - i;
     }

     int opCmp(ref const S s) {
         return this.i - s.i;
     }

     int opBinaryRight(string op)(int i) if (op == "<") {
         return i - this.i;
     }
}

void main(string [] args)
{
     S[] structs = [{1,"hello"}, {2,"world"}, {3, "!"}]; //sorted 
by i

     auto sortedRange = assumeSorted(structs);

     auto t = sortedRange.trisect(2);
}
Apr 06 2015