prope

prope

import "github.com/zyedidia/generic/prope"

Package prope provides an implementation of a persistent rope data structure. It is similar to the base rope data structure, but the changes are saved separately without modifying the original data structure by sharing data between multiple versions. The time complexity of operations stay the same, but they are generally a bit slower:

* 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).

The main difference is in space complexity, as the persistent data structure allows creating a copy with an insertion or removal in O(lg n) space, instead of duplicating the entire rope for each change. This also prevents the O(n) time complexity of cloning the rope to save a version, as this is done inside the operations in a more efficient manner.

Example

package main

import (
	"fmt"

	"github.com/zyedidia/generic/prope"
)

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

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

	r2 := r.Remove(5, r.Len())
	r3 := r2.Insert(5, []byte(" rope"))

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

Output

h
hello world
hello
hello rope

Index

• Variables
• type Node
  • func Join[V any](nodes ...*Node[V]) *Node[V]
  • func New[V any](b []V) *Node[V]
  • func (n *Node[V]) At(pos int) V
  • func (n *Node[V]) Insert(pos int, value []V) *Node[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) *Node[V]
  • 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. Larger values will take make operations take more
    // memory.
    SplitLength = 256
    // 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.5
)

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](nodes ...*Node[V]) *Node[V]

Join creates a merged version of all of the ropes.

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 the slice will not be modified after the rope is created.

func (*Node[V]) At

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

At returns the element at the given position.

func (*Node[V]) Insert

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

Insert returns a new version of the rope with the given value inserted 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. Rebuilded nodes does not share memory with their old versions, so sometimes this operation will take up a lot of memory.

func (*Node[V]) Rebuild

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

Rebuild rebuilds the entire rope structure, resulting in a balanced tree. The rebuilded node does not share memory with its old versions, so this operation will take the same space as creating the node from scratch.

func (*Node[V]) Remove

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

Remove returns a new version of the rope with the elements in the [start:end) range removed.

func (*Node[V]) Slice

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

Slice returns the range of the rope from [start:end).

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.

Generated by gomarkdoc