HuKeping/rbtree

the problem when Key of the struct is the same

Closed this issue · 5 comments

alihossein commented

thanks for this package .

I think we get into trouble when the key (Expiry) is the same. So only one of the nodes is inserted.

package main

import (
	"fmt"
	"github.com/HuKeping/rbtree"
	"time"
)

type Var struct {
	Expiry time.Time `json:"expiry,omitempty"`
	ID     string    `json:"id",omitempty`
}

// We will order the node by `Time`
func (x Var) Less(than rbtree.Item) bool {
	//return x.Expiry.Before(than.(Var).Expiry)
	return x.Expiry.Before(than.(Var).Expiry) 
}

func main() {
	rbt := rbtree.New()

	ex :=time.Now().Add(time.Second * 10)
	var1 := Var{
		Expiry: ex,
		ID:     "var1",
	}
	var2 := Var{
		Expiry: ex,
		ID:     "var2",
	}
	var3 := Var{
		Expiry: ex,
		ID:     "var2-dup",
	}
	var4 := Var{
		Expiry: ex,
		ID:     "var4",
	}
	var5 := Var{
		Expiry: ex,
		ID:     "var5",
	}

	rbt.Insert(var1)
	rbt.Insert(var2)
	rbt.Insert(var3)
	rbt.Insert(var4)
	rbt.Insert(var5)

	tmp := Var{
		Expiry: var4.Expiry,
		ID:     "This field is not the key factor",
	}

	result:=rbt.Get(tmp)
	fmt.Println("Len is :" , rbt.Len()) // print 1 
	fmt.Println(result)

}

If I changed the condition, all nodes add successfully, but the Get method did not work, and the result is nill!

package main

import (
	"fmt"
	"github.com/HuKeping/rbtree"
	"time"
)

type Var struct {
	Expiry time.Time `json:"expiry,omitempty"`
	ID     string    `json:"id",omitempty`
}

// We will order the node by `Time`
func (x Var) Less(than rbtree.Item) bool {
	//return x.Expiry.Before(than.(Var).Expiry)
	return x.Expiry.Before(than.(Var).Expiry) || x.Expiry.Equal(than.(Var).Expiry)
}

func main() {
	rbt := rbtree.New()

	ex :=time.Now().Add(time.Second * 10)
	var1 := Var{
		Expiry: ex,
		ID:     "var1",
	}
	var2 := Var{
		Expiry: ex,
		ID:     "var2",
	}
	var3 := Var{
		Expiry: ex,
		ID:     "var2-dup",
	}
	var4 := Var{
		Expiry: ex,
		ID:     "var4",
	}
	var5 := Var{
		Expiry: ex,
		ID:     "var5",
	}

	rbt.Insert(var1)
	rbt.Insert(var2)
	rbt.Insert(var3)
	rbt.Insert(var4)
	rbt.Insert(var5)

	tmp := Var{
		Expiry: var4.Expiry,
		ID:     "This field is not the key factor",
	}

	result:=rbt.Get(tmp)
	fmt.Println("Len is :" , rbt.Len()) // print 5
	fmt.Println(result)  // print nil


}
HuKeping commented

@alihossein it's intentional, this implementation does not support duplicate keys, should red-black tree support duplicate keys?

alihossein commented

OK.
So duplicate data is allowed in RBTree but you have ignored it in your implementation. it's true?

HuKeping commented

Not exactly, I think R-B trees are not designed for data structures which support duplicates, but rather sets. So this implementation would not support duplicate keys.

Maybe I should add a clarification to README

  • 👍1
alihossein commented

Maybe I should add a clarification to README

yes, I think it is better 👍