rope

README

rope

import "github.com/zendesk/generic/rope"

Package rope provides an implementation of a rope data structure. A rope provides the same interface as an array, but supports efficient insertion and deletion from the middle of the array. It is implemented as an augmented binary search tree. The rope supports the following operations, where 'n' is the number of elements in the rope:

* Remove: O(lg n).

* Insert: O(lg n).

* Slice: O(lg n + m), where m is the size of the slice.

* At: O(lg n).

A rope will be slower than an array for lookup, but faster for modification, and lookup is still logarithmic, which can be acceptable for many applications, whereas modification of an array is linear time in the worst case, which is often unacceptable.

Example

package main

import (
	"fmt"
	"github.com/zendesk/generic/rope"
)

func main() {
	r := rope.New[byte]([]byte("hello world"))

	fmt.Println(string(r.At(0)))

	r.Remove(6, r.Len())
	r.Insert(6, []byte("rope"))

	fmt.Println(string(r.Value()))
}

Output

h
hello rope

Index

• Variables
• type Node
  • func Join[V any](a, b *Node[V], more ...*Node[V]) *Node[V]
  • func New[V any](b []V) *Node[V]
  • func (n *Node[V]) At(pos int) V
  • func (n *Node[V]) Each(fn func(n *Node[V]))
  • func (n *Node[V]) Insert(pos int, value []V)
  • func (n *Node[V]) Len() int
  • func (n *Node[V]) Rebalance()
  • func (n *Node[V]) Rebuild()
  • func (n *Node[V]) Remove(start, end int)
  • func (n *Node[V]) Slice(start, end int) []V
  • func (n *Node[V]) SplitAt(i int) (*Node[V], *Node[V])
  • func (n *Node[V]) Value() []V

Variables

var (
    // SplitLength is the threshold above which slices will be split into
    // separate nodes.
    SplitLength = 4096 * 4
    // JoinLength is the threshold below which nodes will be merged into
    // slices.
    JoinLength = SplitLength / 2
    // RebalanceRatio is the threshold used to trigger a rebuild during a
    // rebalance operation.
    RebalanceRatio = 1.2
)

type Node

A Node in the rope structure. If the kind is tLeaf, only the value and length are valid, and if the kind is tNode, only length, left, right are valid.

type Node[V any] struct {
    // contains filtered or unexported fields
}

func Join

func Join[V any](a, b *Node[V], more ...*Node[V]) *Node[V]

Join merges all the given ropes together into one rope.

func New

func New[V any](b []V) *Node[V]

New returns a new rope node from the given byte slice. The underlying data is not copied so the user should ensure that it is okay to insert and delete from the input slice.

func (*Node[V]) At

func (n *Node[V]) At(pos int) V

At returns the element at the given position.

func (*Node[V]) Each

func (n *Node[V]) Each(fn func(n *Node[V]))

Each applies the given function to every leaf node in order.

func (*Node[V]) Insert

func (n *Node[V]) Insert(pos int, value []V)

Insert inserts the given value at pos.

func (*Node[V]) Len

func (n *Node[V]) Len() int

Len returns the number of elements stored in the rope.

func (*Node[V]) Rebalance

func (n *Node[V]) Rebalance()

Rebalance finds unbalanced nodes and rebuilds them.

func (*Node[V]) Rebuild

func (n *Node[V]) Rebuild()

Rebuild rebuilds the entire rope structure, resulting in a balanced tree.

func (*Node[V]) Remove

func (n *Node[V]) Remove(start, end int)

Remove deletes the range [start:end) (exclusive bound) from the rope.

func (*Node[V]) Slice

func (n *Node[V]) Slice(start, end int) []V

Slice returns the range of the rope from [start:end). The returned slice is not copied.

func (*Node[V]) SplitAt

func (n *Node[V]) SplitAt(i int) (*Node[V], *Node[V])

SplitAt splits the node at the given index and returns two new ropes corresponding to the left and right portions of the split.

func (*Node[V]) Value

func (n *Node[V]) Value() []V

Value returns the elements of this node concatenated into a slice. May return the underyling slice without copying, so do not modify the returned slice.

Generated by gomarkdoc

Documentation

Overview

Package rope provides an implementation of a rope data structure. A rope provides the same interface as an array, but supports efficient insertion and deletion from the middle of the array. It is implemented as an augmented binary search tree. The rope supports the following operations, where 'n' is the number of elements in the rope:

* Remove: O(lg n).

* Insert: O(lg n).

* Slice: O(lg n + m), where m is the size of the slice.

* At: O(lg n).

A rope will be slower than an array for lookup, but faster for modification, and lookup is still logarithmic, which can be acceptable for many applications, whereas modification of an array is linear time in the worst case, which is often unacceptable.

Example

package main

import (
	"fmt"

	"github.com/zendesk/generic/rope"
)

func main() {
	r := rope.New[byte]([]byte("hello world"))

	fmt.Println(string(r.At(0)))

	r.Remove(6, r.Len())
	r.Insert(6, []byte("rope"))

	fmt.Println(string(r.Value()))
}

Output:

h
hello rope

Index

• Variables
• type Node
  • func Join[V any](a, b *Node[V], more ...*Node[V]) *Node[V]
  • func New[V any](b []V) *Node[V]
  • func (n *Node[V]) At(pos int) V
  • func (n *Node[V]) Each(fn func(n *Node[V]))
  • func (n *Node[V]) Insert(pos int, value []V)
  • func (n *Node[V]) Len() int
  • func (n *Node[V]) Rebalance()
  • func (n *Node[V]) Rebuild()
  • func (n *Node[V]) Remove(start, end int)
  • func (n *Node[V]) Slice(start, end int) []V
  • func (n *Node[V]) SplitAt(i int) (*Node[V], *Node[V])
  • func (n *Node[V]) Value() []V

Examples

• Package

Variables

var (
	// SplitLength is the threshold above which slices will be split into
	// separate nodes.
	SplitLength = 4096 * 4
	// JoinLength is the threshold below which nodes will be merged into
	// slices.
	JoinLength = SplitLength / 2
	// RebalanceRatio is the threshold used to trigger a rebuild during a
	// rebalance operation.
	RebalanceRatio = 1.2
)

Types

type Node

type Node[V any] struct {
	// contains filtered or unexported fields
}

A Node in the rope structure. If the kind is tLeaf, only the value and length are valid, and if the kind is tNode, only length, left, right are valid.

func Join

func Join[V any](a, b *Node[V], more ...*Node[V]) *Node[V]

Join merges all the given ropes together into one rope.

func New

func New[V any](b []V) *Node[V]

New returns a new rope node from the given byte slice. The underlying data is not copied so the user should ensure that it is okay to insert and delete from the input slice.

func (*Node[V]) At

func (n *Node[V]) At(pos int) V

At returns the element at the given position.

func (*Node[V]) Each

func (n *Node[V]) Each(fn func(n *Node[V]))

Each applies the given function to every leaf node in order.

func (*Node[V]) Insert

func (n *Node[V]) Insert(pos int, value []V)

Insert inserts the given value at pos.

func (*Node[V]) Len

func (n *Node[V]) Len() int

Len returns the number of elements stored in the rope.

func (*Node[V]) Rebalance

func (n *Node[V]) Rebalance()

Rebalance finds unbalanced nodes and rebuilds them.

func (*Node[V]) Rebuild

func (n *Node[V]) Rebuild()

Rebuild rebuilds the entire rope structure, resulting in a balanced tree.

func (*Node[V]) Remove

func (n *Node[V]) Remove(start, end int)

Remove deletes the range [start:end) (exclusive bound) from the rope.

func (*Node[V]) Slice

func (n *Node[V]) Slice(start, end int) []V

Slice returns the range of the rope from [start:end). The returned slice is not copied.

func (*Node[V]) SplitAt

func (n *Node[V]) SplitAt(i int) (*Node[V], *Node[V])

SplitAt splits the node at the given index and returns two new ropes corresponding to the left and right portions of the split.

func (*Node[V]) Value

func (n *Node[V]) Value() []V

Value returns the elements of this node concatenated into a slice. May return the underyling slice without copying, so do not modify the returned slice.