Treeset iterator is broken about gods HOT 10 CLOSED

Actually, the problem is, the comparator @c3mb0 used is not consistent. It doesn't return 0 for equivalent objects. Maybe if it was return h2.Y*10 - abs(h2.X) - h1.Y*10 + abs(h1.X), it would work.

from gods.

After investigating the example from @c3mb0 and based on @hetulbhatt comment, the comparator needs to be consistent. I assume the same problem with @grglcs "someComparator" (unfortunately the code is not given to verify).

Essentially if you have a comparator that returns something inconsistent. Otherwise, the nodes can not be ingested in a tree in the order given by the comparator.

package main

import "fmt"

type Test struct {
	Y int
	X int
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func comparator(a, b interface{}) int {
	h1 := a.(*Test)
	h2 := b.(*Test)
	return h2.Y*10 - abs(h2.X) - h1.Y*10 - abs(h1.X)
}

func main() {
	a := &Test{Y: -4, X: -1}
	b := &Test{Y: -3, X: 0}
	c := &Test{Y: -4, X: -1}
	fmt.Println(comparator(a, b)) // -> 9   (ok)
	fmt.Println(comparator(b, a)) // -> -11 (ok)

	fmt.Println(comparator(a, c)) // -> -2 (error - should be 0 to suggest equal)
	fmt.Println(comparator(c, a)) // -> -2 (error - should be 0 to suggest equal)

	fmt.Println(comparator(b, c)) // -11 (ok)
	fmt.Println(comparator(c, b)) // 9 (ok)
}

Basically, the example suggests that a is less than c and that c is less than a

from gods.

This bug breaks everything and makes treeset impossible to use.
Just for instance: tree.Values() falls down with index out of range

from gods.

agreed, this library should definitely be avoided. This is not something anyone should use in production code.

from gods.

Please add full code to reproduce this. There are many tests for the TreeSet, what is "someComparator" and "someItems"?

@Churrodog it's used in a "few" production systems. Not to say that I exclude the possibility of bugs, but the years of maturity and the number of tests outweighs the lack of arguments in your comment. You have no time to file a proper bug report, a reproducible snippet of code, not to mention a fix? In that case...

from gods.

There was a bug filed in april, it was ignored, and now closed. No worries.....

from gods.

None of these comments are constructive. Here's an example to reproduce the problem:

package main

import (
	"fmt"

	"github.com/emirpasic/gods/maps/treebidimap"
	"github.com/emirpasic/gods/utils"
)

type Test struct {
	Y int
	X int
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	tm := treebidimap.NewWith(utils.IntComparator, func(a, b interface{}) int {
		h1 := a.(*Test)
		h2 := b.(*Test)
		return h2.Y*10 - abs(h2.X) - h1.Y*10 - abs(h1.X)
	})
	tm.Put(5, &Test{Y: -4, X: -1})
	tm.Put(3, &Test{Y: -3, X: 0})
	tm.Put(7, &Test{Y: -4, X: -1})
	fmt.Println(tm.Values())
}

Please reopen this issue.

from gods.

@c3mb0 thanks for the snippet, constructive, will fix

from gods.

Is this code still maintained? If yes I can resolve this issue.

from gods.

@hetulbhatt yes it is, feel free to resolve the issue.

from gods.