www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Trying to use a template class with ranges

reply mark <mark qtrac.eu> writes:
I am starting on porting Python's difflib's sequence matcher to D.

I want to have a class that will accept two ranges whose elements 
are of the same type and whose elements can be compared for 
equality.

How do I make a class declaration that specifies a (forward) 
range type and an equality-supporting element type?

Here's what doesn't work:

class Diff(T, E) {
	T a; // T should be a forward range of E elements
	T b; // E elements must support == and !=
         // This is a hash key=E element, value=slice of size_t
	size_t[][E] b2j;

	this(T a, T b) {
		this.a = a;
		this.b = b;
		chainB();
	}

	void chainB() {
		foreach (i, element; b)
			b2j[element] ~= i;
		// TODO
	}
}

unittest {
	import std.stdio: writeln;

     writeln("unittest for the diffrange library.");
	auto a = ["Tulips are yellow,", "Violets are blue,",
                   "Agar is sweet,", "As are you."];
	auto b = ["Roses are red,", "Violets are blue,",
                   "Sugar is sweet,", "And so are you."];
	auto diff = Diff(a, b);
}
Feb 06 2020
next sibling parent mark <mark qtrac.eu> writes:
I forgot to mention: I want the class to work with:

Diff(aForwardRange, bForwardRange)
where T = ForwardRange, E = anything that supports ==
A common use case is for two sequences of strings (i.e., lines 
read from two files).

Diff(aString, bString) where
T = char[] or wchar[] or dchar[] E = char or wchar or dchar
Feb 06 2020
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 2/6/20 7:16 AM, mark wrote:

 I am starting on porting Python's difflib's sequence matcher to D.
 
 I want to have a class that will accept two ranges whose elements are of 
 the same type and whose elements can be compared for equality.
 
 How do I make a class declaration that specifies a (forward) range type 
 and an equality-supporting element type?
 
 Here's what doesn't work:
 
 class Diff(T, E) {
      T a; // T should be a forward range of E elements
      T b; // E elements must support == and !=
          // This is a hash key=E element, value=slice of size_t
      size_t[][E] b2j;
 
      this(T a, T b) {
          this.a = a;
          this.b = b;
          chainB();
      }
 
      void chainB() {
          foreach (i, element; b)
              b2j[element] ~= i;
          // TODO
      }
 }
 
 unittest {
      import std.stdio: writeln;
 
      writeln("unittest for the diffrange library.");
      auto a = ["Tulips are yellow,", "Violets are blue,",
                    "Agar is sweet,", "As are you."];
      auto b = ["Roses are red,", "Violets are blue,",
                    "Sugar is sweet,", "And so are you."];
      auto diff = Diff(a, b);
 }
 


1. If one template parameter depends 100% on the other, it doesn't need 
to be a parameter. i.e. I would do:

class Diff(T) {
    alias E = ElementType!T;
    ...
}

2. Class constructors do not support IFTI. You have to explicitly 
instantiate. To use IFTI, you need to create a factory function. i.e. to 
make the code above work, your ctor call should be Diff!(typeof(a)) 
(assuming you take the advice in 1).

But you can instead write a function to use IFTI:

auto makeDiff(T)(T r1, T r2) { return Diff!T(r1, r2); }

...

auto diff = makeDiff(a, b);

3. You should declare constraints signifying what types are valid. i.e.:

class Diff(T) if (
    isForwardRange!T // it's a forward range
    && is(typeof(T.init.front == T.init.front)) // elements are comparable
)

Might be good to put this constraint on the factory function too.

Note: is(typeof(...)) basically checks if the thing inside the typeof 
compiles.

-Steve
Feb 06 2020
parent reply mark <mark qtrac.eu> writes:
On Thursday, 6 February 2020 at 15:21:46 UTC, Steven 
Schveighoffer wrote:
[snip]

 3. You should declare constraints signifying what types are 
 valid. i.e.:

 class Diff(T) if (
    isForwardRange!T // it's a forward range
    && is(typeof(T.init.front == T.init.front)) // elements are 
 comparable
 )

 Might be good to put this constraint on the factory function 
 too.


I don't know how to do that syntactically. I tried the obvious 
and it wouldn't compile.

But even without that it won't compile although it is much closer 
now!

import std.range: ElementType, front, isForwardRange;

class Diff(T) if (
         isForwardRange!T && // T is a range
         is(typeof(T.init.front == T.init.front)) // Elements 
support ==
         ) {
     alias E = ElementType!T;

     T a;
     T b;
     size_t[][E] b2j;

     this(T a, T b) {
         this.a = a;
         this.b = b;
         chainB();
     }

     private final void chainB() {
         foreach (i, element; b)
             b2j[element] ~= i;
         // TODO
     }
}

auto differ(T)(T a, T b) { return Diff!T(a, b); }

unittest {
     import std.array;
     import std.stdio: writeln;

     writeln("unittest for the diffrange library.");
     auto d1 = differ("one two three four".array, "one too tree 
four".array);
     auto a = ["Tulips are yellow,", "Violets are blue,", "Agar is 
sweet,",
               "As are you."];
     auto b = ["Roses are red,", "Violets are blue,", "Sugar is 
sweet,",
               "And so are you."];
     auto d2 = differ(a, b);
}

Here's the error output:

Excluding package.d file from test due to 
https://issues.dlang.org/show_bug.cgi?id=11847
src/package.d(50,35): Error: no property opCall for type 
diffrange.Diff!(dchar[]), did you mean new Diff!(dchar[])?
src/package.d(57,21): Error: template instance 
diffrange.differ!(dchar[]) error instantiating
src/package.d(50,35): Error: no property opCall for type 
diffrange.Diff!(string[]), did you mean new Diff!(string[])?
src/package.d(62,21): Error: template instance 
diffrange.differ!(string[]) error instantiating
/home/mark/opt/bin/ldc2 failed with exit code 1.

Curiously the "Excluding package.d file" message isn't true.
Not that I mind, I just want to be able to get it going.

Thanks!

PS The line numbers don't match because I've deleted some structs 
& enums that are above the class but which aren't used yet.
Feb 06 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 2/6/20 11:05 AM, mark wrote:

 src/package.d(50,35): Error: no property opCall for type 
 diffrange.Diff!(dchar[]), did you mean new Diff!(dchar[])?


Hah, forgot that it's a class. Yes, I DID mean new Diff ;)

-Steve
Feb 06 2020
parent mark <mark qtrac.eu> writes:
On Thursday, 6 February 2020 at 16:29:57 UTC, Steven 
Schveighoffer wrote:

 On 2/6/20 11:05 AM, mark wrote:

 src/package.d(50,35): Error: no property opCall for type 
 diffrange.Diff!(dchar[]), did you mean new Diff!(dchar[])?


 Hah, forgot that it's a class. Yes, I DID mean new Diff ;)

 -Steve


Wow, that's all it needed to compile!

And I've added the extra check you suggested:

auto differ(T)(T a, T b) if (
         isForwardRange!T && // T is a range
         is(typeof(T.init.front == T.init.front)) // Elements 
support ==
         ) {
     return new Diff!T(a, b);
}

Thanks!
Feb 06 2020