btree

package module
v1.7.0 Latest Latest
Warning

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

 Go to latest Published: Sep 6, 2023 License: MIT Imports: 2 Imported by: 201

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 added in v0.6.0 

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 added in v1.5.0 

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 added in v1.7.0 

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

func (*BTree) AscendHintMut added in v1.7.0 

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

func (*BTree) AscendMut added in v1.6.0 

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

func (*BTree) Clear added in v1.4.3 

func (tr *BTree) Clear()

Clear will delete all items.

func (*BTree) Copy added in v0.4.0 

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 added in v0.5.0 

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 added in v0.2.0 

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 added in v1.7.0 

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

func (*BTree) DescendHintMut added in v1.7.0 

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

func (*BTree) DescendMut added in v1.6.0 

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 added in v0.5.0 

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 added in v1.6.0 

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

func (*BTree) GetHint added in v0.2.0 

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

func (*BTree) GetHintMut added in v1.6.0 

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

func (*BTree) GetMut added in v1.6.0 

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

func (*BTree) Height added in v0.2.0 

func (tr *BTree) Height() int

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

func (*BTree) IsoCopy added in v1.6.0 

func (tr *BTree) IsoCopy() *BTree

func (*BTree) Iter added in v1.1.0 

func (tr *BTree) Iter() Iter

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

func (*BTree) IterMut added in v1.6.0 

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 added in v0.2.1 

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 added in v0.2.0 

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 added in v1.6.0 

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 added in v1.6.0 

func (tr *BTree) MinMut() any

func (*BTree) PopMax added in v0.2.0 

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 added in v0.2.0 

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 added in v0.2.0 

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 added in v0.2.0 

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 added in v0.2.0 

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 added in v1.6.0 

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

type BTreeG added in v1.4.1 

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

func NewBTreeG added in v1.4.1 

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

New returns a new BTree

func NewBTreeGOptions added in v1.4.1 

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

func (*BTreeG[T]) Ascend added in v1.4.1 

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 added in v1.7.0 

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

func (*BTreeG[T]) AscendHintMut added in v1.7.0 

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

func (*BTreeG[T]) AscendMut added in v1.6.0 

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

func (*BTreeG[T]) Clear added in v1.4.3 

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

Clear will delete all items.

func (*BTreeG[T]) Copy added in v1.4.1 

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 added in v1.4.1 

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 added in v1.4.1 

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 added in v1.4.1 

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 added in v1.4.1 

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 added in v1.7.0 

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

func (*BTreeG[T]) DescendHintMut added in v1.7.0 

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

func (*BTreeG[T]) DescendMut added in v1.6.0 

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

func (*BTreeG[T]) Get added in v1.4.1 

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

Get a value for key

func (*BTreeG[T]) GetAt added in v1.4.1 

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 added in v1.6.0 

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

func (*BTreeG[T]) GetHint added in v1.4.1 

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 added in v1.6.0 

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

func (*BTreeG[T]) GetMut added in v1.6.0 

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

func (*BTreeG[T]) Height added in v1.4.1 

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

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

func (*BTreeG[T]) IsoCopy added in v1.6.0 

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

func (*BTreeG[T]) Items added in v1.4.1 

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

Items returns all the items in order.

func (*BTreeG[T]) ItemsMut added in v1.6.0 

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

func (*BTreeG[T]) Iter added in v1.4.1 

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 added in v1.6.0 

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

func (*BTreeG[T]) Len added in v1.4.1 

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

Len returns the number of items in the tree

func (*BTreeG[T]) Less added in v1.4.1 

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 added in v1.4.1 

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

Load is for bulk loading pre-sorted items

func (*BTreeG[T]) Max added in v1.4.1 

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 added in v1.6.0 

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

func (*BTreeG[T]) Min added in v1.4.1 

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 added in v1.6.0 

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

func (*BTreeG[T]) PopMax added in v1.4.1 

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 added in v1.4.1 

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 added in v1.4.1 

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

func (*BTreeG[T]) ReverseMut added in v1.6.0 

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

func (*BTreeG[T]) Scan added in v1.4.1 

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

func (*BTreeG[T]) ScanMut added in v1.6.0 

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

func (*BTreeG[T]) Set added in v1.4.1 

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

Set or replace a value for a key

func (*BTreeG[T]) SetHint added in v1.4.1 

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 added in v1.4.1 

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 added in v1.6.0 

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

type Generic deprecated added in v1.2.0 

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

Generic BTree

Deprecated: use BTreeG

func NewGeneric deprecated added in v1.2.0 

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

NewGeneric returns a generic BTree

Deprecated: use NewBTreeG

func NewGenericOptions deprecated added in v1.2.0 

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 added in v1.2.0 

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

type Iter added in v1.1.0 

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

Iter is an iterator for

func (*Iter) First added in v1.1.0 

func (iter *Iter) First() bool

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

func (*Iter) Item added in v1.1.0 

func (iter *Iter) Item() any

Item returns the current iterator item.

func (*Iter) Last added in v1.1.0 

func (iter *Iter) Last() bool

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

func (*Iter) Next added in v1.1.0 

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 added in v1.1.0 

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 added in v1.1.0 

func (iter *Iter) Release()

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

func (*Iter) Seek added in v1.1.0 

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 added in v1.7.0 

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

type IterG added in v1.6.0 

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

Iter represents an iterator

func (*IterG[T]) First added in v1.6.0 

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 added in v1.6.0 

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

Item returns the current iterator item.

func (*IterG[T]) Last added in v1.6.0 

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 added in v1.6.0 

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 added in v1.6.0 

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 added in v1.6.0 

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

Release the iterator.

func (*IterG[T]) Seek added in v1.6.0 

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 added in v1.7.0 

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

type Map added in v1.2.0 

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

func NewMap added in v1.5.0 

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

func (*Map[K, V]) Ascend added in v1.2.0 

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 added in v1.6.0 

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

func (*Map[K, V]) Clear added in v1.4.3 

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

Clear will delete all items.

func (*Map[K, V]) Copy added in v1.3.0 

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

func (*Map[K, V]) Delete added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.6.0 

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

func (*Map[K, V]) Get added in v1.2.0 

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

Get a value for key.

func (*Map[K, V]) GetAt added in v1.2.0 

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 added in v1.6.0 

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

func (*Map[K, V]) GetMut added in v1.6.0 

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 added in v1.2.0 

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 added in v1.6.0 

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

func (*Map[K, V]) Iter added in v1.2.0 

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

Iter returns a read-only iterator.

func (*Map[K, V]) IterMut added in v1.6.0 

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

func (*Map[K, V]) KeyValues added in v1.2.0 

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

KeyValues returns all the keys and values in order.

func (*Map[K, V]) KeyValuesMut added in v1.6.0 

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

func (*Map[K, V]) Keys added in v1.2.0 

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

Keys returns all the keys in order.

func (*Map[K, V]) Len added in v1.2.0 

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

Len returns the number of items in the tree

func (*Map[K, V]) Load added in v1.2.0 

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 added in v1.2.0 

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 added in v1.6.0 

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

func (*Map[K, V]) Min added in v1.2.0 

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 added in v1.6.0 

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

func (*Map[K, V]) PopMax added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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

func (*Map[K, V]) ReverseMut added in v1.6.0 

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

func (*Map[K, V]) Scan added in v1.2.0 

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

func (*Map[K, V]) ScanMut added in v1.6.0 

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

func (*Map[K, V]) Set added in v1.2.0 

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 added in v1.2.0 

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

Values returns all the values in order.

func (*Map[K, V]) ValuesMut added in v1.6.0 

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

type MapIter added in v1.2.0 

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

MapIter represents an iterator for btree.Map

func (*MapIter[K, V]) First added in v1.2.0 

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 added in v1.2.0 

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

Key returns the current iterator item key.

func (*MapIter[K, V]) Last added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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

Value returns the current iterator item value.

type Options added in v1.2.0 

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 added in v0.2.2 

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 added in v1.2.0 

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

func (*Set[K]) Ascend added in v1.2.0 

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 added in v1.4.3 

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

Clear will delete all items.

func (*Set[K]) Contains added in v1.2.0 

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

Get a value for key

func (*Set[K]) Copy added in v1.3.0 

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

Copy

func (*Set[K]) Delete added in v1.2.0 

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

Delete an item

func (*Set[K]) DeleteAt added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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

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

func (*Set[K]) Insert added in v1.2.0 

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

Insert an item

func (*Set[K]) IsoCopy added in v1.6.0 

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

func (*Set[K]) Iter added in v1.2.0 

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

Iter returns a read-only iterator.

func (*Set[K]) Keys added in v1.3.0 

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

Keys returns all the keys in order.

func (*Set[K]) Len added in v1.2.0 

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

Len returns the number of items in the tree

func (*Set[K]) Load added in v1.2.0 

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

Load is for bulk loading pre-sorted items

func (*Set[K]) Max added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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

func (*Set[K]) Scan added in v1.2.0 

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

type SetIter added in v1.2.0 

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

SetIter represents an iterator for btree.Set

func (*SetIter[K]) First added in v1.2.0 

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 added in v1.2.0 

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

Key returns the current iterator item key.

func (*SetIter[K]) Last added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

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.