SortedArraySet#find does not behave properly if equality and sort fields are different.

[jramoyo]

In the example below, elements in the set are identified as unique if the name fields are equal. Subsequently, they are sorted by the instrument field.

It is expected for SortedArraySet#find to return the correct indexes corresponding to the names. However, starting index 2, find() returns -1.

It appears that the equals() function is not getting called for all iterations (see log output below).

This works if both equals() and compare() functions are referring to the same fields.

var SortedArraySet = require('collections/sorted-array-set'),
    set   = new SortedArraySet([],
        function (a, b ) {
            console.log(a.name + ' equals ' + b.name + ' : ' + (a.name === b.name));
            return a.name === b.name;
        },
        function (a, b) {
            if      (a.instrument > b.instrument) { return  1; }
            else if (a.instrument < b.instrument) { return -1; }
            else                                  { return  0; }
        });

describe('set', function () {
    it('finds an element from the collection', function () {
        set.push({ name: 'John',   instrument: 'rhythm' });
        set.push({ name: 'Paul',   instrument: 'bass' });
        set.push({ name: 'George', instrument: 'lead' });
        set.push({ name: 'Ringo',  instrument: 'drum kit' });

        expect(set.find({ name: 'Paul'   })).toBe(0);
        expect(set.find({ name: 'Ringo'  })).toBe(1);
        expect(set.find({ name: 'George' })).toBe(2);
        expect(set.find({ name: 'John'   })).toBe(3);
    });
});

Output

LOG LOG: 'Paul equals Paul : true'
LOG LOG: 'Paul equals Paul : true'
LOG LOG: 'Ringo equals Paul : false'
LOG LOG: 'Ringo equals Ringo : true'
LOG LOG: 'George equals Paul : false'
LOG LOG: 'George equals Ringo : false'
LOG LOG: 'John equals Paul : false'
LOG LOG: 'John equals Ringo : false'

set
    ✗ finds an element from the collection
    Expected -1 to be 2.
    Error: Expected -1 to be 2.
        at null.<anonymous> (/tmp/2e18f5dfdaf9e610854903b5e4d05e71bee0ebac.browserify:46805:46 <- sortedArraySet.spec.js:22:0)

    Expected -1 to be 3.
    Error: Expected -1 to be 3.
        at null.<anonymous> (/tmp/2e18f5dfdaf9e610854903b5e4d05e71bee0ebac.browserify:46806:46 <- sortedArraySet.spec.js:23:0)

[kriskowal]

I should clarify in the documents that all of these collections require compare, equals, and hash methods to be in agreement.

[jramoyo]

I understand equals and hash should be the same, but why should compare affect these two?

Would you be able to suggest a work-around?

[kriskowal]

With a map, hash finds the general area, and equals distinguishes a value from others that have the same hash. With a sorted set, compare finds the general area, and equals finds the exact position relative to other values that are either equal or incomparable.

[kriskowal]

A sorted set does not lend itself well to indexing by one property and searching by another. You might consider keeping two sorted sets, one indexed by name, and the other by instrument.

[jramoyo]

Fair enough, thanks for the explanation.

[vanakema]

I'm not a fan of commenting on dead issues... but this is a serious problem. The implementation doesn't work as documented. If it's required for the compare callback to ALSO do all the checks that equals does, because of the way it was implemented, then it needs to be documented.

[kriskowal]

I'm not a fan of commenting on dead issues... but this is a serious problem. The implementation doesn't work as documented. If it's required for the compare callback to ALSO do all the checks that equals does, because of the way it was implemented, then it needs to be documented.

I agree. Can you spare some time to propose a change?

I’m not entirely sure whether I’m still a maintainer here, but I can offer a review and inquire.

[hthetiot]

Cc @cdebost

[vanakema]

I'm not a fan of commenting on dead issues... but this is a serious problem. The implementation doesn't work as documented. If it's required for the compare callback to ALSO do all the checks that equals does, because of the way it was implemented, then it needs to be documented.

I agree. Can you spare some time to propose a change?

I’m not entirely sure whether I’m still a maintainer here, but I can offer a review and inquire.

I'll try to look at the underlying code soon, but I have a feeling that changing the implementation will dramatically reduce performance, since I'm guessing it first sorts everything, and then does deduplication in array order, requiring duplicates to be ordered next to each other in the underlying array, at least for initialization. Updating of documentation might be the quick route to somewhat solving this problem.

[kriskowal]

Yes, I believe documenting the invariants more thoroughly is the right way to go. Are you familiar with the companion documentation site http://www.collectionsjs.com/?

On Wed, Jun 17, 2020 at 9:46 AM Mark V notifications@github.com wrote:

I'm not a fan of commenting on dead issues... but this is a serious problem. The implementation doesn't work as documented. If it's required for the compare callback to ALSO do all the checks that equals does, because of the way it was implemented, then it needs to be documented.

I agree. Can you spare some time to propose a change?

I’m not entirely sure whether I’m still a maintainer here, but I can offer a review and inquire.

I'll try to look at the underlying code soon, but I have a feeling that changing the implementation will dramatically reduce performance, since I'm guessing it first sorts everything, and then does deduplication in array order, requiring duplicates to be ordered next to each other in the underlying array, at least for initialization. Updating of documentation might be the quick route to somewhat solving this problem.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/montagejs/collections/issues/93#issuecomment-645489266, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAOXBWF5PMTTNH5EWXR4FTRXDXMXANCNFSM4AS3HE2A .

[vanakema]

Yeah

[vanakema]

Ok found the docs repo. I'll try and open an PR soon.