the problem when Key of the struct is the same

[alihossein]

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]

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

[HuKeping]

FYI:

http://grail.cba.csuohio.edu/~lin/cis506/Chapt9.pdf

Chapter #Duplicate Keys

[alihossein]

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

[HuKeping]

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

[alihossein]

Maybe I should add a clarification to README

yes, I think it is better :+1: