stathat中的treap包重叠？

According to this link stathat uses overlapping with their treap:

GoLLRB is great and there's no reason you should switch. We thought the idea behind treaps was an elegant solution to our problem, so we implemented it. We liked the interface that GoLLRB provided, so we mimicked it in our implementation.

One thing we added to the treap package is to allow you to iterate using an overlap function, so you can get all the keys in [3,9), for example. We use this a lot, often with a struct as the key.

Patrick

I am playing with the following code and have no idea how to continue:

package main

import(
    "reflect"
    "fmt"
    "github.com/stathat/treap"
)

func IntLess(p, q interface{}) bool {
        return p.(int) < q.(int)
}

func BucketOverlap(a, b interface{}) bool {
    return false
}

func main() {
    tree := treap.NewOverlapTree(IntLess, BucketOverlap)
    tree.Insert(5, "a")
    tree.Insert(7, "b")
    tree.Insert(2, "c")
    tree.Insert(1, "d")

    for v := range tree.IterateOverlap([]int{2,5}) {
        fmt.Printf("val: %v
", v)
    }
}

let's say I want to get keys in range [2,5] => [c,a]

I have found a solution using GoLLRB:

package main

import (
    "fmt"
    "github.com/petar/GoLLRB/llrb"
)

type Item struct {
    key     int
    value   string
}

func lessInt(a, b interface{}) bool {
    aa := a.(*Item)
    bb := b.(*Item)
    return aa.key < bb.key
}

func main() {
    tree := llrb.New(lessInt)
    tree.ReplaceOrInsert(&Item{5, "a"})
    tree.ReplaceOrInsert(&Item{7, "b"})
    tree.ReplaceOrInsert(&Item{2, "c"})
    tree.ReplaceOrInsert(&Item{1, "d"})
    //tree.DeleteMin()

    c := tree.IterRangeInclusive(&Item{key: 2}, &Item{key: 5})
    for item := <-c; item != nil; item = <-c {
        i := item.(*Item)
        fmt.Printf("%s
", i.value)
    }
}

Still I am wondering if this is also possible using stathat's treap.

The first place I'd start would be the tests for the stathat treap code: https://github.com/stathat/treap/blob/master/treap_test.go#L164

It seems that what you're doing is trying to pass a slice of keys when it is expecting a single one. You are also trying to do vector operations (i.e. range overlap) on a value that is scalar (i.e. int).

Maybe I am misunderstanding the point of the overlap, but my understanding is that the use for it is as an interval tree:

key1 := []int{1, 3}
key2 := []int{2, 4}
key3 := []int{5, 6}

These are intervals (low and high). key1 overlaps key2, and vice-versa. Neither overlap key3. In this case, the overlap would be useful (i.e. IterateOverlap([]int{2,3}) would give me key1 and key2, whereas IterateOverlap([]int{3,5}) would return all).

I'm not sure how you'd iterate over these entries. Maybe this:

for i := 2; i <= 5; i++ {
  fmt.Printf("val: %v
", tree.Get(i))
}

Again, I've not used this implementation, so forgive me if I'm barking up the wrong tree.