From: Julian S. <js...@ac...> - 2007-12-08 18:30:57
|
> Yes. The relation established by the comparison function has to be > transitive. This is not the case here. Therefore the function should not be > used. > > I've shown how this affects the AVL tree in theory and implementation. This > also fits one fact that Tom gives: There have to be additional additions > and deletions to the tree till the values are not found. Below is a test program which compares comparison functions through exhaustive testing. It shows immediately that the slow (reference) and fast versions produce different results. We can fix Memcheck by falling back to the reference version, but I'd like to see if there is a way to get the correct behaviour without the extra conditionals. J #include <stdio.h> typedef signed char Char; typedef unsigned char UChar; Char cmp_slow_signed ( Char x, Char y ) { if (x < y) return -1; if (x > y) return 1; return 0; } Char cmp_fast_signed ( Char x, Char y ) { Char diff = x - y; return diff; } void run_test_signed ( char* testname, Char(*cmp1)(Char,Char), Char(*cmp2)(Char,Char) ) { unsigned int x, y; printf("\n%s: start\n", testname); for (x = 0; x < 256; x++) { for (y = 0; y < 256; y++) { Char r1 = cmp1( (Char)x, (Char)y ); Char r2 = cmp2( (Char)x, (Char)y ); if (r1 < 0 && r2 < 0) continue; if (r1 > 0 && r2 > 0) continue; if (r1 == 0 && r2 == 0) continue; printf("%s: difference at %x %x\n\n", testname, x, y); return; } } printf("%s: success\n\n", testname); } int main ( void ) { run_test_signed( "cmp_fast_signed", cmp_slow_signed, cmp_fast_signed ); return 0; } |