btree

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Sep 5, 2023 License: MIT Imports: 2 Imported by: 0

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.

Package btree implements a B-Tree, Map, Set It's copied from https://github.com/tidwall/btree

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[T any] struct {
	// contains filtered or unexported fields
}

func NewBTree 

func NewBTree[T cmp.Ordered]() *BTree[T]

New returns a new BTree

func NewBTreeFunc 

func NewBTreeFunc[T any](less func(a, b T) bool) *BTree[T]

func NewBTreeOptions 

func NewBTreeOptions[T any](less func(a, b T) bool, opts Options) *BTree[T]

func (*BTree[T]) Ascend 

func (tr *BTree[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 (*BTree[T]) AscendMut 

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

func (*BTree[T]) Clear 

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

Clear will delete all items.

func (*BTree[T]) Copy 

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

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

func (*BTree[T]) Delete 

func (tr *BTree[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 (*BTree[T]) DeleteAt 

func (tr *BTree[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 (*BTree[T]) DeleteHint 

func (tr *BTree[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 (*BTree[T]) DeleteMax 

func (tr *BTree[T]) DeleteMax() (T, bool)

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

func (*BTree[T]) DeleteMin 

func (tr *BTree[T]) DeleteMin() (T, bool)

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

func (*BTree[T]) Descend 

func (tr *BTree[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 (*BTree[T]) DescendMut 

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

func (*BTree[T]) Get 

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

Get a value for key

func (*BTree[T]) GetAt 

func (tr *BTree[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 (*BTree[T]) GetAtMut 

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

func (*BTree[T]) GetHint 

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

GetHint gets a value for key using a path hint

func (*BTree[T]) GetHintMut 

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

func (*BTree[T]) GetMut 

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

func (*BTree[T]) Height 

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

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

func (*BTree[T]) IsoCopy 

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

func (*BTree[T]) ItemsMut 

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

func (*BTree[T]) Len 

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

Len returns the number of items in the tree

func (*BTree[T]) Load 

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

Load is for bulk loading pre-sorted items

func (*BTree[T]) Max 

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

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

func (*BTree[T]) MaxMut 

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

func (*BTree[T]) Min 

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

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

func (*BTree[T]) MinMut 

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

func (*BTree[T]) ReverseScan 

func (tr *BTree[T]) ReverseScan(iter func(item T) bool)

func (*BTree[T]) ReverseScanMut 

func (tr *BTree[T]) ReverseScanMut(iter func(item T) bool)

func (*BTree[T]) Scan 

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

func (*BTree[T]) ScanMut 

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

func (*BTree[T]) SetHint 

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

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

func (*BTree[T]) Upsert 

func (tr *BTree[T]) Upsert(item T) (T, bool)

Upsert replaces or inserts if the item doesn't exist. It returns the replaced item and whether it's replaced or not.

func (*BTree[T]) Values 

func (tr *BTree[T]) Values() []T

Values returns all the items in order.

func (*BTree[T]) Walk 

func (tr *BTree[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 (*BTree[T]) WalkMut 

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

type Map 

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

func NewMap 

func NewMap[K cmp.Ordered, V any]() *Map[K, V]

NewMap creates a new map.

func NewMapDegree 

func NewMapDegree[K cmp.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]) 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 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
}

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 cmp.Ordered] struct {
	// contains filtered or unexported fields
}

func NewSet 

func NewSet[T cmp.Ordered]() *Set[T]

NewSet creates a new set with degree = 2.

func NewSetDegree 

func NewSetDegree[T cmp.Ordered](degree int) *Set[T]

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]) 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]) DeleteMax 

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

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

func (*Set[K]) DeleteMin 

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

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

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]) Has 

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

Has checks whether a key exists or not.

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]) 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]) 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)

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.