Thread overview
Exercise at end of Ch. 56 of "Programming in D"
Aug 15, 2022
johntp
Aug 15, 2022
Ali Çehreli
Aug 15, 2022
Ali Çehreli
Aug 15, 2022
johntp
Aug 20, 2022
Paul Backus
Aug 22, 2022
Salih Dincer
Aug 15, 2022
johntp
Aug 20, 2022
Era Scarecrow
August 15, 2022

I'm using DMD64 D Compiler v2.100.0 on linux mint.

I kept getting an assertion error for my solution to the exercises at the end of Chapter 56 of "Programming in D", so I copied the author's solution and got the same thing.

The exercise is the very last one (exercise 3) about overriding

toHash()

for the TriangleArea object. The last couple of assertions fail for me.

assert(area2 in areas);
assert(area[area2] == 1.25;

Is there an errata page for the book? I looked on the book's page and couldn't find it. I can post the entire thing if you want, but I didn't want to clutter the forum until I made sure I didn't overlook something. Thanks in advance.

August 14, 2022
On 8/14/22 18:47, johntp wrote:
> I'm using DMD64 D Compiler v2.100.0 on linux mint.

Same version here.

> I copied the author's
> solution and got the same thing.

Wow! Are people actually working on those? :)

At first, I couldn't even get the code to compile due to const-correctness issues with opCmp. :/ I used the following cast():

  foreach (i, point; points) {
      immutable comparison = (cast()point).opCmp(rhs.points[i]);
      // ...
  }

> Is there an errata page for the book?

No. It is supposed to be corrected as mistakes are discovered. The online version should be the most recent.

The bug was with trying to implement that unnatural "ignore the color" in the comparison logic but then toHash was taking advantage of existing array hashing code, which had no idea of the programmer's requirement:

class Point {
  int x;
  int y;
  Color color;

  // IGNORES COLOR:
  override bool opEquals(Object o) const {
    const rhs = cast(const Point)o;
    return rhs && (x == rhs.x) && (y == rhs.y);
  }

  // ...
}

class TriangularArea {
    // BUG DUE TO WISHFUL THINKING:
    override size_t toHash() const {
      /* Since the 'points' member is an array, we can take
       * advantage of the existing toHash algorithm for
       * array types. */
      return typeid(points).getHash(&points);
    }

    // ...
}

Here is a very inefficient implementation that still relies on existing array hashing functionality but after creating an array that does not contain the color field. I am pretty sure sort(tuples) is needed but at least the example works without it as well:

  override size_t toHash() const {
    auto tuples = points[].map!(p => tuple(cast()p.x, cast()p.y)).array;
    sort(tuples);
    return () @trusted {
      return typeid(tuples).getHash(&tuples);
    }();
  }

Writing it in an efficient way is left as en excercise because the auther is too lazy to learn how to do it. :p

In case it's not clear, toHash() creates a new array which does not contain any color information and then sorts it and then needs to use the @trusted trick because toHash is @safe (apparently).

Ali

August 14, 2022
On 8/14/22 19:23, Ali Çehreli wrote:

>      // BUG DUE TO WISHFUL THINKING:
>      override size_t toHash() const {
>        /* Since the 'points' member is an array, we can take
>         * advantage of the existing toHash algorithm for
>         * array types. */
>        return typeid(points).getHash(&points);

Thinking more about this, I think the above would still work if the Point type had a toHash() function that also ignored the color member. Adding just the following function makes the code work:

class Point {
  int x;
  int y;
  Color color;

  // ...

  override size_t toHash() const {
    return x + y;
  }
}

The book is simply forgetting to show that function. (Otherwise, I never put any code without testing.)

WARNING: Hash functions can be very tricky. I have a strong feeling that adding two integers is not an efficient one.

Ali

August 15, 2022
On Monday, 15 August 2022 at 02:23:34 UTC, Ali Çehreli wrote:
> Wow! Are people actually working on those? :)

Absolutely.  Thanks for the book.  I'm enjoying it.


> At first, I couldn't even get the code to compile due to const-correctness issues with opCmp. :/ I used the following cast():
>
>   foreach (i, point; points) {
>       immutable comparison = (cast()point).opCmp(rhs.points[i]);
>       // ...
>   }
>

For some reason I didn't have this problem.


> The bug was with trying to implement that unnatural "ignore the color" in the comparison logic but then toHash was taking advantage of existing array hashing code, which had no idea of the programmer's requirement:

I thought that was the problem, but wasn't sure.  I wasn't getting the same hash code for area1 and area2.

Your solution worked. I guess it is a little unnatural to ignore the color.  I tried overriding the toHash() of Point, but I don't know enough D to get it to work.  I wonder if that could be a solution.

Thanks so much for the reply.
August 15, 2022
On Monday, 15 August 2022 at 02:59:59 UTC, Ali Çehreli wrote:
> On 8/14/22 19:23, Ali Çehreli wrote:

> class Point {
>   int x;
>   int y;
>   Color color;
>
>   // ...
>
>   override size_t toHash() const {
>     return x + y;


I just saw this second reply.  Might not be good if you have Point(1,2) and Point(2,1) because they would hash the same.
August 20, 2022

On Monday, 15 August 2022 at 03:19:43 UTC, johntp wrote:

>

Your solution worked. I guess it is a little unnatural to ignore the color. I tried overriding the toHash() of Point, but I don't know enough D to get it to work. I wonder if that could be a solution.

Depends on what you're trying to do. Metadata unrelated to the value of the object i would ignore and not be part of hashing or comparisons. I've also done things for strings that held information like what original position in the array the data was (for visually sorting testing) and could yield me information while not interfering with the object/data in question.

Though x+y as a hash seems terrible. I'd probably do ((x+1000)**2)+y (assuming x and y are both going to be generally small ensuring the hash for location is unique. Then point(2,1) and point(1,2) have different hashes. But I'm not familiar with the exercise in question.

August 20, 2022
On Monday, 15 August 2022 at 02:59:59 UTC, Ali Çehreli wrote:
> class Point {
>   int x;
>   int y;
>   Color color;
>
>   // ...
>
>   override size_t toHash() const {
>     return x + y;
>   }
> }
>
> The book is simply forgetting to show that function. (Otherwise, I never put any code without testing.)
>
> WARNING: Hash functions can be very tricky. I have a strong feeling that adding two integers is not an efficient one.

Fortunately there is no need to invent our own hash function here, because we can use the generic hashOf [1] from druntime:

    override size_t toHash() const {
        return hashOf(y, hashOf(x));
    }

The second argument is optional, and is used when you want to "accumulate" a single hash value from multiple input values.

[1] https://druntime.dpldocs.info/object.hashOf.1.html
August 22, 2022

On Saturday, 20 August 2022 at 21:26:25 UTC, Paul Backus wrote:

>

Fortunately there is no need to invent our own hash function here, because we can use the generic hashOf [1] from druntime:

override size_t toHash() const {
    return hashOf(y, hashOf(x));
}

The second argument is optional, and is used when you want to "accumulate" a single hash value from multiple input values.

[1] https://druntime.dpldocs.info/object.hashOf.1.html

It's very simple and beautiful, thanks!

I know, off-topic but valuable info; we can gain a nice auto-constructor template*:

enum defaultClassConstructor = q{
  this(typeof(this.tupleof) params) {
    static foreach (i; 0..this.tupleof.length)
      this.tupleof[i] = params[i];
  }
};

struct Color {
  ubyte r, g, b, a;
}

class Point {
  Color c;
  int x, y;
  bool h;

  mixin(defaultClassConstructor);
}

unittest
{
  Color foo = { r : 0x30,
                g : 0xd5,
                b : 0xc8
  };

  auto bar = new Point(foo, 320, 240, true);

  assert(bar.h);
  assert(bar.x == 320);
  assert(bar.y == 240);
  assert(bar.c.a == 0);
  assert(bar.c.r == 48);
  assert(bar.c.g == 213);
  assert(bar.c.b == 200);
}

(*) I learned on this forum (from Steven Schweighoffer, I think):

Or so this is also very good:

void main()
{
  auto colorWithAlpha = vec4i(100, 150, 200, 300);
       colorWithAlpha.r = 120;
  assert(colorWithAlpha.r == 120);
  assert(colorWithAlpha.g == 150);
  assert(colorWithAlpha.b == 200);
  assert(colorWithAlpha.a == 300);

  auto point3D = vec3i(100, 200, 300);
       point3D.z /= 2;
  assert(point3D.x == 100);
  assert(point3D.y == 200);
  assert(point3D.z == 150);

  auto point2D = vec2i(100, 200);
       point2D.y = point3D.z;
  assert(point2D.x == 100);
  assert(point2D.y == 150);
}

template vec2(T) { alias Vector!(T, 2) vec2; }
alias vec2!int    vec2i;
alias vec2!float  vec2f;
alias vec2!double vec2d;

template vec3(T) { alias Vector!(T, 3) vec3; }
alias vec3!int    vec3i;
alias vec3!float  vec3f;
alias vec3!double vec3d;

template vec4(T) { alias Vector!(T, 4) vec4; }
alias vec4!int    vec4i;
alias vec4!float  vec4f;
alias vec4!double vec4d;

enum isVector(T) = is(T : Vector!A, A...);

struct Vector(T, int N)
{
  static assert(N >= 1);
  import std.conv,
         std.format,
         std.traits;

  union
  {
    T[N] v;
    struct
    {
      static if(N >= 1)
      {
        T x; alias x r;
      }
      static if(N >= 2)
      {
        T y; alias y g;
      }
      static if(N >= 3)
      {
        T z; alias z b;
      }
      static if(N >= 4)
      {
        T w; alias w a;
      }
    }
  }

  this(Args...)(Args args)
  {
    static if (args.length == 1)
    {// Construct a Vector from a single value.
      opAssign!(Args[0])(args[0]);
    }
    else
    { // validate the total argument count across scalars and vectors
      template argCount(T...)
      {
        static if(T.length == 0)
          enum argCount = 0; // done recursing
        else static if(isVector!(T[0]))
          enum argCount = T[0]._N + argCount!(T[1..$]);
        else
          enum argCount = 1 + argCount!(T[1..$]);
        }

        static assert(argCount!Args <= N, "Too many arguments in vector constructor");

        int index = 0;
        foreach(arg; args)
        {
          static if(isAssignable!(T, typeof(arg)))
          {
            v[index] = arg;
            index++; // has to be on its own line (DMD 2.068)
          }
          else static if (isVector!(typeof(arg)) && isAssignable!(T, arg._T))
          {
            mixin(generateLoopCode!("v[index + @] = arg[@];", arg._N)());
            index += arg._N;
          }
          else static assert(false, "Unrecognized argument in Vector constructor");
        }
        assert(index == N, "Bad arguments in Vector constructor");
      }
  }

  /// Assign a Vector with a static array type.
  ref Vector opAssign(U)(U arr)
  if ((isStaticArray!(U) && isAssignable!(T, typeof(arr[0])) && (arr.length == N)))
  {
    mixin(generateLoopCode!("v[@] = arr[@];", N)());
    return this;
  }

  /// Assign with a dynamic array.
  /// Size is checked in debug-mode.
  ref Vector opAssign(U)(U arr)
  if (isDynamicArray!(U) && isAssignable!(T, typeof(arr[0])))
  {
    assert(arr.length == N);
    mixin(generateLoopCode!("v[@] = arr[@];", N)());
    return this;
  }

  /// Assign from a samey Vector.
  ref Vector opAssign(U)(U u)
  if (is(U : Vector))
  {
    v[] = u.v[];
    return this;
  }

  /// Assign from other vectors types (same size, compatible type).
  ref Vector opAssign(U)(U x)
  if(isVector!U && isAssignable!(T, U._T)
                && (!is(U: Vector))
                && (U._N == _N)
     ) {
    mixin(generateLoopCode!("v[@] = x.v[@];", N)());
    return this;
  }

  /// Returns: a pointer to content.
  inout(T)* ptr() inout @property
  {
    return v.ptr;
  }

  /// Converts to a pretty string.
  string toString() const nothrow
  {
    try
      return format("%s", v);
    catch (Exception e)
      assert(false); // should not happen since format is right
  }

  private
  {
    enum _N = N;
    alias T _T;

    // define types that can be converted to this, but are not the same type
    template isConvertible(T)
    {
      enum bool isConvertible =
         (!is(T : Vector)) &&
           is(typeof( { T x_Detect;
                        Vector v = x_Detect;
                      }()
                    )
             );
    }

    static
    string generateLoopCode(string str, int N)()
    {
      import std.string;
      string result;
      for(int i; i < N; ++i)
      {
        string index = ctIntToString(i);
        // replace all @ by indices
        result ~= str.replace("@", index);
      }
      return result;
    }

    // Speed-up CTFE conversions
    static
    string ctIntToString(int n)
    {
      static
      immutable string[16] table = ["0", "1", "2",
                                    "3", "4", "5",
                                    "6", "7", "8",
                                    "9"];
      if (n < 10) return table[n];
      else return n.to!string;
    }
  } // private
}

A big thank you to Ali, Steve and Paul for this information I've gained. Again thank you to the others whose names I cannot mention.

Disclaimer: The Vector structure above is not my own code, I couldn't find its source. But it can belong to the following repositories:

Thank you all...

SDB@79