www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - comparison operators

reply Kevin Bealer <kevinbealer gmail.com> writes:
Here is another strategy for comparisons which I think satisfies several
currently unusual criteria.  It's based on the idea of "Schwartz sorting". 
I'll give the pseudo code first:

class Object {
    byte[] schwartzKey()
    {
        throw new UnimplementedMethodException("schwartzKey");
    }
    size_t getHash()
    {
        return Object.standardHash(schwartzKey());
    }
    int opEquals(Object other) // could return bool
    {
        return opCmp(other);
    }
    int opCmp(Object other)
    {
        return schwartzKey() < other.schwartzKey();
    }
};

(Note: I've left the constness off all these methods to hopefully simplify the
discussion.)

The schwartzKey method returns a key whose comparison produces the desired
ordering for this type.  If you have an ASCII string and want locale "C"
ordering, this could be as simple
as casting that string to a byte array.  If you only want to order objects for
the sake of hash
tables, it could just be a "slice" of what would otherwise be the 4 byte cached
"hash" value
of the fields.  The name comes from the idea of the Schwartzian transform used
for sorting:
http://en.wikipedia.org/wiki/Schwartzian_transform.  (But please suggest a
better one!  Maybe opComparisonKey().)

In the above design, if you define the "schwartzKey" method, you already have
reasonable, correct, and consistent definitions for opCmp, opEquals, and
getHash.

On the other hand, if you just want field-wise comparisons, you can just
redefine opCmp.  If you only want to allow equality comparisons, just define
opEquals.  You can also just make the object hashable without defining any of
the other functions.

And if you define nothing, the comparisons above will just throw an exception.

ALSO: this solves the "Fundametal OO Problem" that objects of different types
are not comparable (as described in Joshua Bloch's Effective Java).  The
problem is: depending
on which class you have on the left side, its impossible to write comparison
operators
that respect the class of both objects. 

class A {
  int opCmp(Object o) {
    //compares "this" to o -- but doesn't know about "n"
  }
};

class B : A {
  int n;
  int opCmp(Object o) {
     //compares "this" to o -- but doesn't know classes derived
     // from B at some later time.
  }
};

Since the author of A doesn't know about B, its normally impossible to write
comparators
for A that produce correct and consistent results for both A < B and B < A.

But with the schwartzKey method, both comparisons work properly, since A will
see the
value of "n" in B's schwartzKey.

class A {
  // int opCmp(); -- not defined, default is fine
  byte[] schwartzKey(Object o)
};

class B : A {
  int n;
  // int opCmp(); -- not defined, default is fine
  byte[] schwartzKey(Object o)
  {
       return super.schwartzKey() ~ cast(ubyte[]) toString(n);
  }
};

But you can still safely override each of these various other methods as long
as you
know that your class is not going to be someone else's base class.

The best part is -- this whole feature is just a library change -- nothing in
the language
itself has to change at all, just some mostly compatible changes to Object.

If you want backward compatibility, you need to catch the "unimplemented method"
exception in each of these methods and do something slightly different for
methods
that currently have non-throwing definitions.  (I think I prefer the throwing
definitions,
but I'm not picky about that part of it.)

Kevin

(P.S. Use the Schwartz!)
Apr 16 2008
next sibling parent Kevin Bealer <kevinbealer gmail.com> writes:
Kevin Bealer Wrote:

     int opCmp(Object other)
     {
         return schwartzKey() < other.schwartzKey();
     }

Oops -- this is obviously too simple, maybe: if (schwartzKey() < other.schwartzKey()) return -1; if (schwartzKey() > other.schwartzKey()) return 1; return 0; Kevin
Apr 16 2008
prev sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Kevin Bealer" <kevinbealer gmail.com> wrote in message 
news:fu5e33$969$1 digitalmars.com...

 (P.S. Use the Schwartz!)

Crap! You beat me to it.
Apr 16 2008