<!-- Code generated by gomarkdoc. DO NOT EDIT -->

# rope

```go
import "github.com/zyedidia/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.

<details><summary>Example</summary>
<p>

```go
package main

import (
	"fmt"

	"github.com/zyedidia/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
```

</p>
</details>

## Index

- [Variables](<#variables>)
- [type Node](<#type-node>)
  - [func Join[V any](a, b *Node[V], more ...*Node[V]) *Node[V]](<#func-join>)
  - [func New[V any](b []V) *Node[V]](<#func-new>)
  - [func (n *Node[V]) At(pos int) V](<#func-nodev-at>)
  - [func (n *Node[V]) Each(fn func(n *Node[V]))](<#func-nodev-each>)
  - [func (n *Node[V]) Insert(pos int, value []V)](<#func-nodev-insert>)
  - [func (n *Node[V]) Len() int](<#func-nodev-len>)
  - [func (n *Node[V]) Rebalance()](<#func-nodev-rebalance>)
  - [func (n *Node[V]) Rebuild()](<#func-nodev-rebuild>)
  - [func (n *Node[V]) Remove(start, end int)](<#func-nodev-remove>)
  - [func (n *Node[V]) Slice(start, end int) []V](<#func-nodev-slice>)
  - [func (n *Node[V]) SplitAt(i int) (*Node[V], *Node[V])](<#func-nodev-splitat>)
  - [func (n *Node[V]) Value() []V](<#func-nodev-value>)


## Variables

```go
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](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L45-L50>)

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.

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

### func [Join](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L222>)

```go
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](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L55>)

```go
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](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L185>)

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

At returns the element at the given position.

### func \(\*Node\[V\]\) [Each](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L257>)

```go
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](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L131>)

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

Insert inserts the given value at pos.

### func \(\*Node\[V\]\) [Len](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L66>)

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

Len returns the number of elements stored in the rope.

### func \(\*Node\[V\]\) [Rebalance](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L242>)

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

Rebalance finds unbalanced nodes and rebuilds them.

### func \(\*Node\[V\]\) [Rebuild](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L231>)

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

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

### func \(\*Node\[V\]\) [Remove](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L106>)

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

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

### func \(\*Node\[V\]\) [Slice](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L151>)

```go
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](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L192>)

```go
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](<https://github.com/zyedidia/generic/blob/master/rope/rope.go#L95>)

```go
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](<https://github.com/princjef/gomarkdoc>)
