Treeset iterator is broken

[grglcs]

How to reproduce:

import "github.com/emirpasic/gods/sets/treeset"

var tree  *treeset.Set
tree = treeset.NewWith(someComparator)
for _, v := range someItems {
    tree.Add(v)
}
items := tree.Iterator()
for items.Next() {
    // infinite loop!
}

[grglcs]

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

[ghost]

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

[emirpasic]

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...

[ghost]

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

[c3mb0]

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.

[emirpasic]

@c3mb0 thanks for the snippet, constructive, will fix

[hetulbhatt]

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

[emirpasic]

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

[hetulbhatt]

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.

[emirpasic]

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