ordered_tree

An ordered unbalanced tree.

Ordering of items is maintained as new items are inserted into the tree. Sort of a replacement for an ordered list. Worst case performance for insertion is O(n).

Types

Comparator

</>

Comparator function to resolve the order of items. Must return Lt if the first argument is before the second, Gt if the opposite, or Eq if they are equal.

pub type Comparator(a) =
  fn(a, a) -> Order

OrderedTree

opaque </>

pub opaque type OrderedTree(a)

WalkOrder

</>

Item ordering for when walking through a tree.

pub type WalkOrder {
  Asc
  Desc
}

Constructors

```
Asc
```
```
Desc
```

Functions

fold

</>

pub fn fold(
  over tree: OrderedTree(a),
  from initial: b,
  order order: WalkOrder,
  with fun: fn(b, a) -> b,
) -> b

Fold over the elements in the tree in the given order.

insert

</>

pub fn insert(tree: OrderedTree(a), item: a) -> OrderedTree(a)

Insert a new item into the tree.

length

</>

pub fn length(tree: OrderedTree(a)) -> Int

Get the amount of items in the tree.

This operation runs in O(n) time.

new

</>

pub fn new(comparator: fn(a, a) -> Order) -> OrderedTree(a)

Create a new, empty tree, with the given comparator.

to_list

</>

pub fn to_list(tree: OrderedTree(a), order: WalkOrder) -> List(a)

Get the tree as a list in the given list order.