Treeset iterator is broken

grglcs commented

2019-04-15 12:17:22 +00:00

(Migrated from github.com)

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!
}

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 commented

2019-04-15 12:24:11 +00:00

(Migrated from github.com)

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

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

ghost commented

2019-11-07 21:12:34 +00:00

(Migrated from github.com)

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

emirpasic commented

2019-11-07 22:56:07 +00:00

(Migrated from github.com)

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

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 commented

2019-11-07 23:22:13 +00:00

(Migrated from github.com)

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

c3mb0 commented

2019-11-07 23:46:55 +00:00

(Migrated from github.com)

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.

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 commented

2019-11-08 00:41:23 +00:00

(Migrated from github.com)

@c3mb0 thanks for the snippet, constructive, will fix

hetulbhatt commented

2020-09-27 14:58:42 +00:00

(Migrated from github.com)

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

emirpasic commented

2020-10-08 18:39:58 +00:00

(Migrated from github.com)

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

hetulbhatt commented

2020-10-13 09:52:43 +00:00

(Migrated from github.com)

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.

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.

👍 1

emirpasic commented

2022-04-07 10:14:03 +00:00

(Migrated from github.com)

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

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

👍 1

Rows
Columns

Treeset iterator is broken #110