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

# prope

```go
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.

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

```go
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
```

</p>
</details>

## Index

- [Variables](<#variables>)
- [type Node](<#type-node>)
  - [func Join[V any](nodes ...*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]) Insert(pos int, value []V) *Node[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) *Node[V]](<#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. 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](<https://github.com/zyedidia/generic/blob/master/prope/prope.go#L48-L53>)

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/prope/prope.go#L183>)

```go
func Join[V any](nodes ...*Node[V]) *Node[V]
```

Join creates a merged version of all of the ropes.

### func [New](<https://github.com/zyedidia/generic/blob/master/prope/prope.go#L58>)

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

### func \(\*Node\[V\]\) [At](<https://github.com/zyedidia/generic/blob/master/prope/prope.go#L88>)

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

At returns the element at the given position.

### func \(\*Node\[V\]\) [Insert](<https://github.com/zyedidia/generic/blob/master/prope/prope.go#L96>)

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

```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/prope/prope.go#L158>)

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

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

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

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

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

### func \(\*Node\[V\]\) [SplitAt](<https://github.com/zyedidia/generic/blob/master/prope/prope.go#L140>)

```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/prope/prope.go#L74>)

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

Value returns the elements of this node concatenated into a slice.



Generated by [gomarkdoc](<https://github.com/princjef/gomarkdoc>)
