Add to treemap functions that search a key (similar to Floor/Ceiling) and return Iterator

vlkv commented

2022-04-12 11:42:17 +00:00

(Migrated from github.com)

I want to find an element in the tree for O(logN) time and then do a O(1) navigation to the next/prev from there. Similar to c++:

I want to find an element in the tree for O(logN) time and then do a O(1) navigation to the next/prev from there. Similar to c++: - https://en.cppreference.com/w/cpp/container/map/find - https://en.cppreference.com/w/cpp/container/map/lower_bound - https://en.cppreference.com/w/cpp/container/map/upper_bound

👍 1

emirpasic commented

2022-04-12 13:55:36 +00:00

(Migrated from github.com)

This is already possible with the stated requirements, see example below:

package main

import (
	"fmt"
	rbt "github.com/emirpasic/gods/trees/redblacktree"
)

// RedBlackTreeExample to demonstrate basic usage of RedBlackTree
func main() {
	tree := rbt.NewWithIntComparator() // empty(keys are of type int)

	tree.Put(1, "x") // 1->x
	tree.Put(2, "b") // 1->x, 2->b (in order)
	tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
	tree.Put(4, "c") // 1->a, 2->b, 3->c (in order)
	tree.Put(5, "d") // 1->a, 2->b, 3->c, 4->d (in order)
	tree.Put(6, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
	tree.Put(7, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)

	fmt.Println(tree)
	//
	//  RedBlackTree
	//  │           ┌── 7
	//  │       ┌── 6
	//  │   ┌── 5
	//  │   │   └── 4
	//  └── 2
	//       └── 1

	fmt.Println("\nIterating forward from the ceiling node")
	if node, found := tree.Ceiling(3); found {
		it := tree.IteratorAt(node)
		for it.Next() {
			fmt.Print(it.Node(), " ")
		}
	}
	/*
		Iterating forward from the ceiling node
		5 6 7
	*/

	fmt.Println("\nIterating backward from the ceiling node")
	if node, found := tree.Ceiling(3); found {
		it := tree.IteratorAt(node)
		for it.Prev() {
			fmt.Print(it.Node(), " ")
		}
	}
	/*
		Iterating backward from the ceiling node
		2 1
	*/
}

Let me know if this helps or otherwise I'll reopen the question.

This is already possible with the stated requirements, see example below: ```go package main import ( "fmt" rbt "github.com/emirpasic/gods/trees/redblacktree" ) // RedBlackTreeExample to demonstrate basic usage of RedBlackTree func main() { tree := rbt.NewWithIntComparator() // empty(keys are of type int) tree.Put(1, "x") // 1->x tree.Put(2, "b") // 1->x, 2->b (in order) tree.Put(1, "a") // 1->a, 2->b (in order, replacement) tree.Put(4, "c") // 1->a, 2->b, 3->c (in order) tree.Put(5, "d") // 1->a, 2->b, 3->c, 4->d (in order) tree.Put(6, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order) tree.Put(7, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order) fmt.Println(tree) // // RedBlackTree // │ ┌── 7 // │ ┌── 6 // │ ┌── 5 // │ │ └── 4 // └── 2 // └── 1 fmt.Println("\nIterating forward from the ceiling node") if node, found := tree.Ceiling(3); found { it := tree.IteratorAt(node) for it.Next() { fmt.Print(it.Node(), " ") } } /* Iterating forward from the ceiling node 5 6 7 */ fmt.Println("\nIterating backward from the ceiling node") if node, found := tree.Ceiling(3); found { it := tree.IteratorAt(node) for it.Prev() { fmt.Print(it.Node(), " ") } } /* Iterating backward from the ceiling node 2 1 */ } ``` Let me know if this helps or otherwise I'll reopen the question.

vlkv commented

2022-04-12 14:39:06 +00:00

(Migrated from github.com)

Thank you for your response, however, I still have a question: there is no IteratorAt function in the https://github.com/emirpasic/gods/blob/master/maps/treemap/treemap.go The example you provided is about github.com/emirpasic/gods/trees/redblacktree. What is the difference between them? Why not provide IteratorAt to treemap.Map?

Thank you.

Thank you for your response, however, I still have a question: there is no IteratorAt function in the https://github.com/emirpasic/gods/blob/master/maps/treemap/treemap.go The example you provided is about github.com/emirpasic/gods/trees/redblacktree. What is the difference between them? Why not provide IteratorAt to treemap.Map? Thank you.

emirpasic commented

2022-04-12 14:49:10 +00:00

(Migrated from github.com)

@vlkv RedBlackTree is the foundation of the TreeMap anyways, so essentially they are the same. The key difference is that the TreeMap is "branded" as key-value structure and avoids dealing with the internal red-black tree representation of nodes. Do you think you can then simply use the RedBlackTree instead for your case to have this flexibility or should GoDS expose similar IteratorAt functionality?

vlkv commented

2022-04-12 15:32:46 +00:00

(Migrated from github.com)

I looked closely through the public interface that both structures expose and now I see, that the major difference between them probably in that rbt exposes the Node abstraction and treemap - does not.

Do you think you can then simply use the RedBlackTree

Yes, sure.

should GoDS expose similar IteratorAt functionality?

I was expected to see something like c++ std::map or Java's TreeMap and I didn't. But this is simply because of my poor knowlegde of GoDS. Honestly I don't know, this is more of a GoDS philosophy/ideology question, so it's up to you.

Thank you for your help))

I looked closely through the public interface that both structures expose and now I see, that the major difference between them probably in that rbt exposes the Node abstraction and treemap - does not. > Do you think you can then simply use the RedBlackTree Yes, sure. > should GoDS expose similar IteratorAt functionality? I was expected to see something like c++ std::map or Java's TreeMap and I didn't. But this is simply because of my poor knowlegde of GoDS. Honestly I don't know, this is more of a GoDS philosophy/ideology question, so it's up to you. Thank you for your help))

Rows
Columns

Add to treemap functions that search a key (similar to Floor/Ceiling) and return Iterator #193