CLL (cll v0.2.0)
This module can be used to represent a data structure with similar behavior as circular Doubly-Linked-List.
"But wait, aren't all Lists in Erlang Linked Lists?" Well yes, but they are immutable, which makes things like removing elements while iterating through the list very slow. Also, getting consistent CLL-like behaviour from normal Lists is not easy when dealing with problems such as polygon math around the beginning and end of the list.
Internally, it uses a Zipper data structure (https://en.wikipedia.org/wiki/Zipper_(data_structure)) to keep the items before and after the current item in a way that optimizes for moving forward and backward in the list. Because the next and previous item are always the first items in the surrounding lists, those operations are substantially faster than tracking a cursor in a standar List an fetching its neighbors.
A list can be created by passing a List to the init/2 function along with
an boolean defining if the resulting Doubly-Linked-List is circular or not.
Once created, you can traverse through the list one or more steps at a time.
examples
Examples
iex> [1, 2, 3, 4, 5]
...> |> CLL.init()
...> |> CLL.value()
1
iex> [1, 2, 3, 4, 5]
...> |> CLL.init()
...> |> CLL.next()
...> |> CLL.value()
2
iex> [1, 2, 3, 4, 5]
...> |> CLL.init()
...> |> CLL.prev()
...> |> CLL.prev(3)
...> |> CLL.next(2)
...> |> CLL.value()
4You can also modify the list by inserting, replacing, or removing the current element. Finally, if desired, you can convert the CLL back into a List.
examples-1
Examples
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(2)
...> |> CLL.remove()
...> |> CLL.to_list()
[1, 2, 4, 5]
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.prev(2)
...> |> CLL.replace(:foo)
...> |> CLL.to_list()
[1, 2, 3, :foo, 5]
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(3)
...> |> CLL.insert(3.5)
...> |> CLL.insert(3.75)
...> |> CLL.to_list()
[1, 2, 3, 3.5, 3.75, 4, 5]To help with use cases where iterating through the list once is useful, CLL keeps track of the "start" of the list so that you can determine when a list has been fully traversed. A list can also be reset to the initial start position at any time.
examples-2
Examples
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(3)
...> |> CLL.prev(2)
...> |> CLL.next()
...> |> CLL.offset()
2
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(5)
...> |> CLL.done?()
true
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(4)
...> |> CLL.reset()
...> |> CLL.value()
1Link to this section Summary
Functions
In the case that you are stepping through the list, the function returns true when all of the elements of the list have been visited once and only once.
Returns true if the CLL is empty, false otherwise.
Initializes a CLL with the contents of the given list and sets the
Inserts an element prior to the pointer position such that inserting an element does not change the value at the pointer position.
Returns the number of elements in the CLL.
Moves the root of the list to the next element in the CLL.
Preforms the next/1 action a number of times.
Returns the offset of the CLL pointer from the first element of the original list.
Moves the root of the list to the previous element in the CLL.
Preforms the prev/1 action a number of times.
Removes the element at the pointer from the list. The pointer will point to the element after the removed one.
Replaces the element at the pointer positing with the given value. The pointer remains in the same place.
Resets the pointer to point to the first element of the original list.
Returns a list of the elements in the CLL. The order of elements will match the original list the CLL was created from.
Returns the value at the given offset from the root. If offset is not given, the value at root is returned.
Link to this section Types
cll()
value()
@type value() :: any()
Link to this section Functions
done?(arg1)
In the case that you are stepping through the list, the function returns true when all of the elements of the list have been visited once and only once.
examples
Examples
iex> CLL.init([1, 2, 3])
...> |> CLL.next()
...> |> CLL.next()
...> |> CLL.next()
...> |> CLL.done?()
true
iex> CLL.init([1, 2, 3])
...> |> CLL.next()
...> |> CLL.next()
...> |> CLL.next()
...> |> CLL.next()
...> |> CLL.done?()
falseempty?(arg1)
Returns true if the CLL is empty, false otherwise.
examples
Examples
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.empty?()
false
iex> CLL.init([])
...> |> CLL.empty?()
trueinit(list)
Initializes a CLL with the contents of the given list and sets the
insert(arg, value)
Inserts an element prior to the pointer position such that inserting an element does not change the value at the pointer position.
examples
Examples
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(2)
...> |> CLL.value()
3
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(2)
...> |> CLL.insert(9)
...> |> CLL.value()
3len(arg)
@spec len(cll()) :: non_neg_integer()
Returns the number of elements in the CLL.
examples
Examples
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.len()
5 next(arg)
Moves the root of the list to the next element in the CLL.
next(state, offset)
Preforms the next/1 action a number of times.
offset(arg)
@spec offset(cll()) :: non_neg_integer()
Returns the offset of the CLL pointer from the first element of the original list.
prev(arg)
Moves the root of the list to the previous element in the CLL.
prev(state, offset)
Preforms the prev/1 action a number of times.
remove(arg)
Removes the element at the pointer from the list. The pointer will point to the element after the removed one.
replace(arg, value)
Replaces the element at the pointer positing with the given value. The pointer remains in the same place.
examples
Examples
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(2)
...> |> CLL.replace(9)
...> |> CLL.value()
9
iex> CLL.init([1, 2, 3, 4, 5])
...> |> CLL.next(2)
...> |> CLL.insert(9)
...> |> CLL.value()
3reset(state)
Resets the pointer to point to the first element of the original list.
examples
Examples
iex> CLL.init([1, 2, 3])
...> |> CLL.next(2)
...> |> CLL.reset()
...> |> CLL.value()
1to_list(arg)
Returns a list of the elements in the CLL. The order of elements will match the original list the CLL was created from.
examples
Examples
iex> CLL.init([1,2,3])
...> |> CLL.next(2)
...> |> CLL.prev()
...> |> CLL.to_list()
[1, 2, 3]value(state, offset \\ 0)
Returns the value at the given offset from the root. If offset is not given, the value at root is returned.