btree

package
v0.0.0-...-642df0c Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 14, 2024 License: BSD-3-Clause, MIT Imports: 2 Imported by: 0

README

btree

GoDoc

An efficient B-tree implementation in Go.

Features

  • Support for Generics (Go 1.18+).
  • Map and Set types for ordered key-value maps and sets,
  • Fast bulk loading for pre-ordered data using the Load() method.
  • Copy() method with copy-on-write support.
  • Path hinting optimization for operations with nearby keys.

Using

To start using this package, install Go and run:

$ go get github.com/tidwall/btree

B-tree types

This package includes the following types of B-trees:

  • btree.Map: A fast B-tree for storing ordered key value pairs.

  • btree.Set: Like Map, but only for storing keys.

  • btree.BTreeG: A feature-rich B-tree for storing data using a custom comparator. Thread-safe.

  • btree.BTree: Like BTreeG but uses the interface{} type for data. Backwards compatible. Thread-safe.

btree.Map
// Basic
Set(key, value)    // insert or replace an item
Get(key, value)    // get an existing item
Delete(key)        // delete an item
Len()              // return the number of items in the map

// Iteration
Scan(iter)         // scan items in ascending order
Reverse(iter)      // scan items in descending order
Ascend(key, iter)  // scan items in ascending order that are >= to key
Descend(key, iter) // scan items in descending order that are <= to key.
Iter()             // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)       // returns the item at index
DeleteAt(index)    // deletes the item at index

// Bulk-loading
Load(key, value)   // load presorted items into tree
Example
package main

import (
	"fmt"
	"github.com/tidwall/btree"
)

func main() {
	// create a map
	var users btree.Map[string, string]

	// add some users
	users.Set("user:4", "Andrea")
	users.Set("user:6", "Andy")
	users.Set("user:2", "Andy")
	users.Set("user:1", "Jane")
	users.Set("user:5", "Janet")
	users.Set("user:3", "Steve")

	// Iterate over the maps and print each user
	users.Scan(func(key, value string) bool {
		fmt.Printf("%s %s\n", key, value)
		return true
	})
	fmt.Printf("\n")

	// Delete a couple
	users.Delete("user:5")
	users.Delete("user:1")

	// print the map again
	users.Scan(func(key, value string) bool {
		fmt.Printf("%s %s\n", key, value)
		return true
	})
	fmt.Printf("\n")

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:6 Andy
}
btree.Set
// Basic
Insert(key)        // insert an item
Contains(key)      // test if item exists
Delete(key)        // delete an item
Len()              // return the number of items in the set

// Iteration
Scan(iter)         // scan items in ascending order
Reverse(iter)      // scan items in descending order
Ascend(key, iter)  // scan items in ascending order that are >= to key
Descend(key, iter) // scan items in descending order that are <= to key.
Iter()             // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)       // returns the item at index
DeleteAt(index)    // deletes the item at index

// Bulk-loading
Load(key)          // load presorted item into tree
Example
package main

import (
	"fmt"
	"github.com/tidwall/btree"
)

func main() {
	// create a set
	var names btree.Set[string]

	// add some names
	names.Insert("Jane")
	names.Insert("Andrea")
	names.Insert("Steve")
	names.Insert("Andy")
	names.Insert("Janet")
	names.Insert("Andy")

	// Iterate over the maps and print each user
	names.Scan(func(key string) bool {
		fmt.Printf("%s\n", key)
		return true
	})
	fmt.Printf("\n")

	// Delete a couple
	names.Delete("Steve")
	names.Delete("Andy")

	// print the map again
	names.Scan(func(key string) bool {
		fmt.Printf("%s\n", key)
		return true
	})
	fmt.Printf("\n")

	// Output:
	// Andrea
	// Andy
	// Jane
	// Janet
	// Steve
	//
	// Andrea
	// Jane
	// Janet
}
btree.BTreeG
// Basic
Set(item)               // insert or replace an item
Get(item)               // get an existing item
Delete(item)            // delete an item
Len()                   // return the number of items in the btree

// Iteration
Scan(iter)              // scan items in ascending order
Reverse(iter)           // scan items in descending order
Ascend(key, iter)       // scan items in ascending order that are >= to key
Descend(key, iter)      // scan items in descending order that are <= to key.
Iter()                  // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)            // returns the item at index
DeleteAt(index)         // deletes the item at index

// Bulk-loading
Load(item)              // load presorted items into tree

// Path hinting
SetHint(item, *hint)    // insert or replace an existing item
GetHint(item, *hint)    // get an existing item
DeleteHint(item, *hint) // delete an item
AscendHint(key, iter, *hint)
DescendHint(key, iter, *hint)
SeekHint(key, iter, *hint)

// Copy-on-write
Copy()                  // copy the btree
Example
package main

import (
	"fmt"

	"github.com/tidwall/btree"
)

type Item struct {
	Key, Val string
}

// byKeys is a comparison function that compares item keys and returns true
// when a is less than b.
func byKeys(a, b Item) bool {
	return a.Key < b.Key
}

// byVals is a comparison function that compares item values and returns true
// when a is less than b.
func byVals(a, b Item) bool {
	if a.Val < b.Val {
		return true
	}
	if a.Val > b.Val {
		return false
	}
	// Both vals are equal so we should fall though
	// and let the key comparison take over.
	return byKeys(a, b)
}

func main() {
	// Create a tree for keys and a tree for values.
	// The "keys" tree will be sorted on the Keys field.
	// The "values" tree will be sorted on the Values field.
	keys := btree.NewBTreeG[Item](byKeys)
	vals := btree.NewBTreeG[Item](byVals)

	// Create some items.
	users := []Item{
		Item{Key: "user:1", Val: "Jane"},
		Item{Key: "user:2", Val: "Andy"},
		Item{Key: "user:3", Val: "Steve"},
		Item{Key: "user:4", Val: "Andrea"},
		Item{Key: "user:5", Val: "Janet"},
		Item{Key: "user:6", Val: "Andy"},
	}

	// Insert each user into both trees
	for _, user := range users {
		keys.Set(user)
		vals.Set(user)
	}

	// Iterate over each user in the key tree
	keys.Scan(func(item Item) bool {
		fmt.Printf("%s %s\n", item.Key, item.Val)
		return true
	})
	fmt.Printf("\n")

	// Iterate over each user in the val tree
	vals.Scan(func(item Item) bool {
		fmt.Printf("%s %s\n", item.Key, item.Val)
		return true
	})

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:4 Andrea
	// user:2 Andy
	// user:6 Andy
	// user:1 Jane
	// user:5 Janet
	// user:3 Steve
}
btree.BTree
// Basic
Set(item)               // insert or replace an item
Get(item)               // get an existing item
Delete(item)            // delete an item
Len()                   // return the number of items in the btree

// Iteration
Scan(iter)              // scan items in ascending order
Reverse(iter)           // scan items in descending order
Ascend(key, iter)       // scan items in ascending order that are >= to key
Descend(key, iter)      // scan items in descending order that are <= to key.
Iter()                  // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)            // returns the item at index
DeleteAt(index)         // deletes the item at index

// Bulk-loading
Load(item)              // load presorted items into tree

// Path hinting
SetHint(item, *hint)    // insert or replace an existing item
GetHint(item, *hint)    // get an existing item
DeleteHint(item, *hint) // delete an item
AscendHint(key, iter, *hint)
DescendHint(key, iter, *hint)
SeekHint(key, iter, *hint)

// Copy-on-write
Copy()                  // copy the btree
Example
package main

import (
	"fmt"

	"github.com/tidwall/btree"
)

type Item struct {
	Key, Val string
}

// byKeys is a comparison function that compares item keys and returns true
// when a is less than b.
func byKeys(a, b interface{}) bool {
	i1, i2 := a.(*Item), b.(*Item)
	return i1.Key < i2.Key
}

// byVals is a comparison function that compares item values and returns true
// when a is less than b.
func byVals(a, b interface{}) bool {
	i1, i2 := a.(*Item), b.(*Item)
	if i1.Val < i2.Val {
		return true
	}
	if i1.Val > i2.Val {
		return false
	}
	// Both vals are equal so we should fall though
	// and let the key comparison take over.
	return byKeys(a, b)
}

func main() {
	// Create a tree for keys and a tree for values.
	// The "keys" tree will be sorted on the Keys field.
	// The "values" tree will be sorted on the Values field.
	keys := btree.New(byKeys)
	vals := btree.New(byVals)

	// Create some items.
	users := []*Item{
		&Item{Key: "user:1", Val: "Jane"},
		&Item{Key: "user:2", Val: "Andy"},
		&Item{Key: "user:3", Val: "Steve"},
		&Item{Key: "user:4", Val: "Andrea"},
		&Item{Key: "user:5", Val: "Janet"},
		&Item{Key: "user:6", Val: "Andy"},
	}

	// Insert each user into both trees
	for _, user := range users {
		keys.Set(user)
		vals.Set(user)
	}

	// Iterate over each user in the key tree
	keys.Ascend(nil, func(item interface{}) bool {
		kvi := item.(*Item)
		fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
		return true
	})

	fmt.Printf("\n")
	// Iterate over each user in the val tree
	vals.Ascend(nil, func(item interface{}) bool {
		kvi := item.(*Item)
		fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
		return true
	})

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:4 Andrea
	// user:2 Andy
	// user:6 Andy
	// user:1 Jane
	// user:5 Janet
	// user:3 Steve
}

Performance

See tidwall/btree-benchmark for benchmark numbers.

Contact

Josh Baker @tidwall

License

Source code is available under the MIT License.

Documentation

Overview

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BTree 

type BTree struct {
	// contains filtered or unexported fields
}

func New 

func New(less func(a, b any) bool) *BTree

New returns a new BTree

func NewNonConcurrent deprecated 

func NewNonConcurrent(less func(a, b any) bool) *BTree

NewNonConcurrent returns a new BTree which is not safe for concurrent write operations by multiple goroutines.

This is useful for when you do not need the BTree to manage the locking, but would rather do it yourself.

Deprecated: use NewOptions

func NewOptions 

func NewOptions(less func(a, b any) bool, opts Options) *BTree

NewOptions returns a new BTree

func (*BTree) Ascend 

func (tr *BTree) Ascend(pivot any, iter func(item any) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*BTree) AscendHint 

func (tr *BTree) AscendHint(pivot any, iter func(item any) bool,
	hint *PathHint,
)

func (*BTree) AscendHintMut 

func (tr *BTree) AscendHintMut(pivot any, iter func(item any) bool,
	hint *PathHint,
)

func (*BTree) AscendMut 

func (tr *BTree) AscendMut(pivot any, iter func(item any) bool)

func (*BTree) Clear 

func (tr *BTree) Clear()

Clear will delete all items.

func (*BTree) Copy 

func (tr *BTree) Copy() *BTree

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*BTree) Delete 

func (tr *BTree) Delete(key any) (prev any)

Delete an item for a key. Returns the deleted value or nil if the key was not found.

func (*BTree) DeleteAt 

func (tr *BTree) DeleteAt(index int) any

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTree) DeleteHint 

func (tr *BTree) DeleteHint(key any, hint *PathHint) (prev any)

DeleteHint deletes a value for a key using a path hint Returns the deleted value or nil if the key was not found.

func (*BTree) Descend 

func (tr *BTree) Descend(pivot any, iter func(item any) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*BTree) DescendHint 

func (tr *BTree) DescendHint(pivot any, iter func(item any) bool,
	hint *PathHint,
)

func (*BTree) DescendHintMut 

func (tr *BTree) DescendHintMut(pivot any, iter func(item any) bool,
	hint *PathHint,
)

func (*BTree) DescendMut 

func (tr *BTree) DescendMut(pivot any, iter func(item any) bool)

func (*BTree) Get 

func (tr *BTree) Get(key any) any

Get a value for key. Returns nil if the key was not found.

func (*BTree) GetAt 

func (tr *BTree) GetAt(index int) any

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTree) GetAtMut 

func (tr *BTree) GetAtMut(index int) any

func (*BTree) GetHint 

func (tr *BTree) GetHint(key any, hint *PathHint) any

func (*BTree) GetHintMut 

func (tr *BTree) GetHintMut(key any, hint *PathHint) any

func (*BTree) GetMut 

func (tr *BTree) GetMut(key any) any

func (*BTree) Height 

func (tr *BTree) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*BTree) IsoCopy 

func (tr *BTree) IsoCopy() *BTree

func (*BTree) Iter 

func (tr *BTree) Iter() Iter

Iter returns a read-only iterator. The Release method must be called finished with iterator.

func (*BTree) IterMut 

func (tr *BTree) IterMut() Iter

func (*BTree) Len 

func (tr *BTree) Len() int

Len returns the number of items in the tree

func (*BTree) Less 

func (tr *BTree) Less(a, b any) bool

Less is a convenience function that performs a comparison of two items using the same "less" function provided to New.

func (*BTree) Load 

func (tr *BTree) Load(item any) (prev any)

Load is for bulk loading pre-sorted items If the load replaces and existing item then the value for the replaced item is returned.

func (*BTree) Max 

func (tr *BTree) Max() any

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*BTree) MaxMut 

func (tr *BTree) MaxMut() any

func (*BTree) Min 

func (tr *BTree) Min() any

Min returns the minimum item in tree. Returns nil if the tree has no items.

func (*BTree) MinMut 

func (tr *BTree) MinMut() any

func (*BTree) PopMax 

func (tr *BTree) PopMax() any

PopMax removes the maximum item in tree and returns it. Returns nil if the tree has no items.

func (*BTree) PopMin 

func (tr *BTree) PopMin() any

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*BTree) Set 

func (tr *BTree) Set(item any) (prev any)

Set or replace a value for a key Returns the value for the replaced item or nil if the key was not found.

func (*BTree) SetHint 

func (tr *BTree) SetHint(item any, hint *PathHint) (prev any)

SetHint sets or replace a value for a key using a path hint Returns the value for the replaced item or nil if the key was not found.

func (*BTree) Walk 

func (tr *BTree) Walk(iter func(items []any))

Walk iterates over all items in tree, in order. The items param will contain one or more items.

func (*BTree) WalkMut 

func (tr *BTree) WalkMut(iter func(items []any))

type BTreeG 

type BTreeG[T any] struct {
	// contains filtered or unexported fields
}

func NewBTreeG 

func NewBTreeG[T any](less func(a, b T) bool) *BTreeG[T]

New returns a new BTree

func NewBTreeGOptions 

func NewBTreeGOptions[T any](less func(a, b T) bool, opts Options) *BTreeG[T]

func (*BTreeG[T]) Ascend 

func (tr *BTreeG[T]) Ascend(pivot T, iter func(item T) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*BTreeG[T]) AscendHint 

func (tr *BTreeG[T]) AscendHint(pivot T, iter func(item T) bool, hint *PathHint,
)

func (*BTreeG[T]) AscendHintMut 

func (tr *BTreeG[T]) AscendHintMut(pivot T, iter func(item T) bool,
	hint *PathHint,
)

func (*BTreeG[T]) AscendMut 

func (tr *BTreeG[T]) AscendMut(pivot T, iter func(item T) bool)

func (*BTreeG[T]) Clear 

func (tr *BTreeG[T]) Clear()

Clear will delete all items.

func (*BTreeG[T]) Copy 

func (tr *BTreeG[T]) Copy() *BTreeG[T]

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*BTreeG[T]) Delete 

func (tr *BTreeG[T]) Delete(key T) (T, bool)

Delete a value for a key and returns the deleted value. Returns false if there was no value by that key found.

func (*BTreeG[T]) DeleteAt 

func (tr *BTreeG[T]) DeleteAt(index int) (T, bool)

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTreeG[T]) DeleteHint 

func (tr *BTreeG[T]) DeleteHint(key T, hint *PathHint) (T, bool)

DeleteHint deletes a value for a key using a path hint and returns the deleted value. Returns false if there was no value by that key found.

func (*BTreeG[T]) Descend 

func (tr *BTreeG[T]) Descend(pivot T, iter func(item T) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*BTreeG[T]) DescendHint 

func (tr *BTreeG[T]) DescendHint(pivot T, iter func(item T) bool,
	hint *PathHint,
)

func (*BTreeG[T]) DescendHintMut 

func (tr *BTreeG[T]) DescendHintMut(pivot T, iter func(item T) bool,
	hint *PathHint,
)

func (*BTreeG[T]) DescendMut 

func (tr *BTreeG[T]) DescendMut(pivot T, iter func(item T) bool)

func (*BTreeG[T]) Get 

func (tr *BTreeG[T]) Get(key T) (T, bool)

Get a value for key

func (*BTreeG[T]) GetAt 

func (tr *BTreeG[T]) GetAt(index int) (T, bool)

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTreeG[T]) GetAtMut 

func (tr *BTreeG[T]) GetAtMut(index int) (T, bool)

func (*BTreeG[T]) GetHint 

func (tr *BTreeG[T]) GetHint(key T, hint *PathHint) (value T, ok bool)

GetHint gets a value for key using a path hint

func (*BTreeG[T]) GetHintMut 

func (tr *BTreeG[T]) GetHintMut(key T, hint *PathHint) (value T, ok bool)

func (*BTreeG[T]) GetMut 

func (tr *BTreeG[T]) GetMut(key T) (T, bool)

func (*BTreeG[T]) Height 

func (tr *BTreeG[T]) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*BTreeG[T]) IsoCopy 

func (tr *BTreeG[T]) IsoCopy() *BTreeG[T]

func (*BTreeG[T]) Items 

func (tr *BTreeG[T]) Items() []T

Items returns all the items in order.

func (*BTreeG[T]) ItemsMut 

func (tr *BTreeG[T]) ItemsMut() []T

func (*BTreeG[T]) Iter 

func (tr *BTreeG[T]) Iter() IterG[T]

Iter returns a read-only iterator. The Release method must be called finished with iterator.

func (*BTreeG[T]) IterMut 

func (tr *BTreeG[T]) IterMut() IterG[T]

func (*BTreeG[T]) Len 

func (tr *BTreeG[T]) Len() int

Len returns the number of items in the tree

func (*BTreeG[T]) Less 

func (tr *BTreeG[T]) Less(a, b T) bool

Less is a convenience function that performs a comparison of two items using the same "less" function provided to New.

func (*BTreeG[T]) Load 

func (tr *BTreeG[T]) Load(item T) (T, bool)

Load is for bulk loading pre-sorted items

func (*BTreeG[T]) Max 

func (tr *BTreeG[T]) Max() (T, bool)

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*BTreeG[T]) MaxMut 

func (tr *BTreeG[T]) MaxMut() (T, bool)

func (*BTreeG[T]) Min 

func (tr *BTreeG[T]) Min() (T, bool)

Min returns the minimum item in tree. Returns nil if the treex has no items.

func (*BTreeG[T]) MinMut 

func (tr *BTreeG[T]) MinMut() (T, bool)

func (*BTreeG[T]) PopMax 

func (tr *BTreeG[T]) PopMax() (T, bool)

PopMax removes the maximum item in tree and returns it. Returns nil if the tree has no items.

func (*BTreeG[T]) PopMin 

func (tr *BTreeG[T]) PopMin() (T, bool)

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*BTreeG[T]) Reverse 

func (tr *BTreeG[T]) Reverse(iter func(item T) bool)

func (*BTreeG[T]) ReverseMut 

func (tr *BTreeG[T]) ReverseMut(iter func(item T) bool)

func (*BTreeG[T]) Scan 

func (tr *BTreeG[T]) Scan(iter func(item T) bool)

func (*BTreeG[T]) ScanMut 

func (tr *BTreeG[T]) ScanMut(iter func(item T) bool)

func (*BTreeG[T]) Set 

func (tr *BTreeG[T]) Set(item T) (T, bool)

Set or replace a value for a key

func (*BTreeG[T]) SetHint 

func (tr *BTreeG[T]) SetHint(item T, hint *PathHint) (prev T, replaced bool)

SetHint sets or replace a value for a key using a path hint

func (*BTreeG[T]) Walk 

func (tr *BTreeG[T]) Walk(iter func(item []T) bool)

Walk iterates over all items in tree, in order. The items param will contain one or more items.

func (*BTreeG[T]) WalkMut 

func (tr *BTreeG[T]) WalkMut(iter func(item []T) bool)

type Generic deprecated 

type Generic[T any] struct {
	*BTreeG[T]
}

Generic BTree

Deprecated: use BTreeG

func NewGeneric deprecated 

func NewGeneric[T any](less func(a, b T) bool) *Generic[T]

NewGeneric returns a generic BTree

Deprecated: use NewBTreeG

func NewGenericOptions deprecated 

func NewGenericOptions[T any](less func(a, b T) bool, opts Options,
) *Generic[T]

NewGenericOptions returns a generic BTree

Deprecated: use NewBTreeGOptions

func (*Generic[T]) Copy 

func (tr *Generic[T]) Copy() *Generic[T]

type Iter 

type Iter struct {
	// contains filtered or unexported fields
}

Iter is an iterator for

func (*Iter) First 

func (iter *Iter) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*Iter) Item 

func (iter *Iter) Item() any

Item returns the current iterator item.

func (*Iter) Last 

func (iter *Iter) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*Iter) Next 

func (iter *Iter) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*Iter) Prev 

func (iter *Iter) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*Iter) Release 

func (iter *Iter) Release()

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*Iter) Seek 

func (iter *Iter) Seek(key any) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

func (*Iter) SeekHint 

func (iter *Iter) SeekHint(key any, hint *PathHint) bool

type IterG 

type IterG[T any] struct {
	// contains filtered or unexported fields
}

Iter represents an iterator

func (*IterG[T]) First 

func (iter *IterG[T]) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*IterG[T]) Item 

func (iter *IterG[T]) Item() T

Item returns the current iterator item.

func (*IterG[T]) Last 

func (iter *IterG[T]) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*IterG[T]) Next 

func (iter *IterG[T]) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*IterG[T]) Prev 

func (iter *IterG[T]) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*IterG[T]) Release 

func (iter *IterG[T]) Release()

Release the iterator.

func (*IterG[T]) Seek 

func (iter *IterG[T]) Seek(key T) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

func (*IterG[T]) SeekHint 

func (iter *IterG[T]) SeekHint(key T, hint *PathHint) bool

type Map 

type Map[K ordered, V any] struct {
	// contains filtered or unexported fields
}

func NewMap 

func NewMap[K ordered, V any](degree int) *Map[K, V]

func (*Map[K, V]) Ascend 

func (tr *Map[K, V]) Ascend(pivot K, iter func(key K, value V) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*Map[K, V]) AscendMut 

func (tr *Map[K, V]) AscendMut(pivot K, iter func(key K, value V) bool)

func (*Map[K, V]) Clear 

func (tr *Map[K, V]) Clear()

Clear will delete all items.

func (*Map[K, V]) Copy 

func (tr *Map[K, V]) Copy() *Map[K, V]

func (*Map[K, V]) Delete 

func (tr *Map[K, V]) Delete(key K) (V, bool)

Delete a value for a key and returns the deleted value. Returns false if there was no value by that key found.

func (*Map[K, V]) DeleteAt 

func (tr *Map[K, V]) DeleteAt(index int) (K, V, bool)

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*Map[K, V]) Descend 

func (tr *Map[K, V]) Descend(pivot K, iter func(key K, value V) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*Map[K, V]) DescendMut 

func (tr *Map[K, V]) DescendMut(pivot K, iter func(key K, value V) bool)

func (*Map[K, V]) Get 

func (tr *Map[K, V]) Get(key K) (V, bool)

Get a value for key.

func (*Map[K, V]) GetAt 

func (tr *Map[K, V]) GetAt(index int) (K, V, bool)

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*Map[K, V]) GetAtMut 

func (tr *Map[K, V]) GetAtMut(index int) (K, V, bool)

func (*Map[K, V]) GetMut 

func (tr *Map[K, V]) GetMut(key K) (V, bool)

GetMut gets a value for key. If needed, this may perform a copy the resulting value before returning.

Mut methods are only useful when all of the following are true:

  • The interior data of the value requires changes.
  • The value is a pointer type.
  • The BTree has been copied using `Copy()` or `IsoCopy()`.
  • The value itself has a `Copy()` or `IsoCopy()` method.

Mut methods may modify the tree structure and should have the same considerations as other mutable operations like Set, Delete, Clear, etc.

func (*Map[K, V]) Height 

func (tr *Map[K, V]) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*Map[K, V]) IsoCopy 

func (tr *Map[K, V]) IsoCopy() *Map[K, V]

func (*Map[K, V]) Iter 

func (tr *Map[K, V]) Iter() MapIter[K, V]

Iter returns a read-only iterator.

func (*Map[K, V]) IterMut 

func (tr *Map[K, V]) IterMut() MapIter[K, V]

func (*Map[K, V]) KeyValues 

func (tr *Map[K, V]) KeyValues() ([]K, []V)

KeyValues returns all the keys and values in order.

func (*Map[K, V]) KeyValuesMut 

func (tr *Map[K, V]) KeyValuesMut() ([]K, []V)

func (*Map[K, V]) Keys 

func (tr *Map[K, V]) Keys() []K

Keys returns all the keys in order.

func (*Map[K, V]) Len 

func (tr *Map[K, V]) Len() int

Len returns the number of items in the tree

func (*Map[K, V]) Load 

func (tr *Map[K, V]) Load(key K, value V) (V, bool)

Load is for bulk loading pre-sorted items

func (*Map[K, V]) Max 

func (tr *Map[K, V]) Max() (K, V, bool)

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*Map[K, V]) MaxMut 

func (tr *Map[K, V]) MaxMut() (K, V, bool)

func (*Map[K, V]) Min 

func (tr *Map[K, V]) Min() (K, V, bool)

Min returns the minimum item in tree. Returns nil if the treex has no items.

func (*Map[K, V]) MinMut 

func (tr *Map[K, V]) MinMut() (K, V, bool)

func (*Map[K, V]) PopMax 

func (tr *Map[K, V]) PopMax() (K, V, bool)

PopMax removes the maximum item in tree and returns it. Returns nil if the tree has no items.

func (*Map[K, V]) PopMin 

func (tr *Map[K, V]) PopMin() (K, V, bool)

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Map[K, V]) Reverse 

func (tr *Map[K, V]) Reverse(iter func(key K, value V) bool)

func (*Map[K, V]) ReverseMut 

func (tr *Map[K, V]) ReverseMut(iter func(key K, value V) bool)

func (*Map[K, V]) Scan 

func (tr *Map[K, V]) Scan(iter func(key K, value V) bool)

func (*Map[K, V]) ScanMut 

func (tr *Map[K, V]) ScanMut(iter func(key K, value V) bool)

func (*Map[K, V]) Set 

func (tr *Map[K, V]) Set(key K, value V) (V, bool)

Set or replace a value for a key

func (*Map[K, V]) Values 

func (tr *Map[K, V]) Values() []V

Values returns all the values in order.

func (*Map[K, V]) ValuesMut 

func (tr *Map[K, V]) ValuesMut() []V

type MapIter 

type MapIter[K ordered, V any] struct {
	// contains filtered or unexported fields
}

MapIter represents an iterator for btree.Map

func (*MapIter[K, V]) First 

func (iter *MapIter[K, V]) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*MapIter[K, V]) Key 

func (iter *MapIter[K, V]) Key() K

Key returns the current iterator item key.

func (*MapIter[K, V]) Last 

func (iter *MapIter[K, V]) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*MapIter[K, V]) Next 

func (iter *MapIter[K, V]) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*MapIter[K, V]) Prev 

func (iter *MapIter[K, V]) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*MapIter[K, V]) Seek 

func (iter *MapIter[K, V]) Seek(key K) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

func (*MapIter[K, V]) Value 

func (iter *MapIter[K, V]) Value() V

Value returns the current iterator item value.

type Options 

type Options struct {
	// Degree is used to define how many items and children each internal node
	// can contain before it must branch. For example, a degree of 2 will
	// create a 2-3-4 tree, where each node may contains 1-3 items and
	// 2-4 children. See https://en.wikipedia.org/wiki/2–3–4_tree.
	// Default is 32
	Degree int
	// NoLocks will disable locking. Otherwide a sync.RWMutex is used to
	// ensure all operations are safe across multiple goroutines.
	NoLocks bool
}

Options for passing to New when creating a new BTree.

type PathHint 

type PathHint struct {
	// contains filtered or unexported fields
}

PathHint is a utility type used with the *Hint() functions. Hints provide faster operations for clustered keys.

type Set 

type Set[K ordered] struct {
	// contains filtered or unexported fields
}

func (*Set[K]) Ascend 

func (tr *Set[K]) Ascend(pivot K, iter func(key K) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*Set[K]) Clear 

func (tr *Set[K]) Clear()

Clear will delete all items.

func (*Set[K]) Contains 

func (tr *Set[K]) Contains(key K) bool

Get a value for key

func (*Set[K]) Copy 

func (tr *Set[K]) Copy() *Set[K]

Copy

func (*Set[K]) Delete 

func (tr *Set[K]) Delete(key K)

Delete an item

func (*Set[K]) DeleteAt 

func (tr *Set[K]) DeleteAt(index int) (K, bool)

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*Set[K]) Descend 

func (tr *Set[K]) Descend(pivot K, iter func(key K) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*Set[K]) GetAt 

func (tr *Set[K]) GetAt(index int) (K, bool)

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*Set[K]) Height 

func (tr *Set[K]) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*Set[K]) Insert 

func (tr *Set[K]) Insert(key K)

Insert an item

func (*Set[K]) IsoCopy 

func (tr *Set[K]) IsoCopy() *Set[K]

func (*Set[K]) Iter 

func (tr *Set[K]) Iter() SetIter[K]

Iter returns a read-only iterator.

func (*Set[K]) Keys 

func (tr *Set[K]) Keys() []K

Keys returns all the keys in order.

func (*Set[K]) Len 

func (tr *Set[K]) Len() int

Len returns the number of items in the tree

func (*Set[K]) Load 

func (tr *Set[K]) Load(key K)

Load is for bulk loading pre-sorted items

func (*Set[K]) Max 

func (tr *Set[K]) Max() (K, bool)

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*Set[K]) Min 

func (tr *Set[K]) Min() (K, bool)

Min returns the minimum item in tree. Returns nil if the treex has no items.

func (*Set[K]) PopMax 

func (tr *Set[K]) PopMax() (K, bool)

PopMax removes the maximum item in tree and returns it. Returns nil if the tree has no items.

func (*Set[K]) PopMin 

func (tr *Set[K]) PopMin() (K, bool)

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Set[K]) Reverse 

func (tr *Set[K]) Reverse(iter func(key K) bool)

func (*Set[K]) Scan 

func (tr *Set[K]) Scan(iter func(key K) bool)

type SetIter 

type SetIter[K ordered] struct {
	// contains filtered or unexported fields
}

SetIter represents an iterator for btree.Set

func (*SetIter[K]) First 

func (iter *SetIter[K]) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*SetIter[K]) Key 

func (iter *SetIter[K]) Key() K

Key returns the current iterator item key.

func (*SetIter[K]) Last 

func (iter *SetIter[K]) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*SetIter[K]) Next 

func (iter *SetIter[K]) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*SetIter[K]) Prev 

func (iter *SetIter[K]) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*SetIter[K]) Seek 

func (iter *SetIter[K]) Seek(key K) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.