flist v0.2.3 FList View Source
FList a functional list implement using the efficient data structure of fingertree. Any operation in the front and the back is amortized O(1) and the operations involved randomly visiting are O(log n). We complete this work with some reference source files in Haskell from the project of AlgoXY, here we need to show our acknowledging. Now, FList can partly support the protocol of Enumerable and the protocol of Collectable. However, as there still remains a long way to go, the time complexity of these protocals are not assured. Therefore, if you need the assurance now, you’d better use the methods provided below. These methods will be reserved in the future though the protocols are getting better implements in the next version of this module. FList can be inspected in a pretty-looking way, which is shown below:
Examples
iex> [1, 2, 3, 4] |> FList.from_list()
#FList<[1, 2, 3, 4]>You can run mix test first to check whether the implement is working well.
Link to this section Summary
Functions
Concat two FLists
Add a new element to the front.
Examples
Get a new list without the element at the pointed position
Invoked in order to access the value stored under key in the given term term
Generate an FList from the given normal list
Invoked in order to access the value under key and update it at the same time
Get the element at the pointed position from a FList
Get the front element
Get a new list without the back element
Get the back element
Get a new list with the element at the pointed position moved to the front
Generate a FList from the given FTree. If the tree is not provided, a empty list will be generated
Invoked to “pop” the value under key out of the given data structure
Update the value of the element at the pointed position
Get the size of a FList
Return an FList slice
Add a new element to the back
Split a FList at the pointed position
Get a new list without the front elemeny
Turn an FList into a normal list
Pop the front element, and then return a tuple
Pop the back element, and then return a tuple
Link to this section Types
FList.t stands for the FList.
Link to this section Functions
Concat two FLists.
extract_at(t(), non_neg_integer()) :: {any(), t()}
Get a new list without the element at the pointed position.
Invoked in order to access the value stored under key in the given term term.
This function should return {:ok, value} where value is the value under
key if the key exists in the term, or :error if the key does not exist in
the term.
Many of the functions defined in the Access module internally call this
function. This function is also used when the square-brackets access syntax
(structure[key]) is used: the fetch/2 callback implemented by the module
that defines the structure struct is invoked and if it returns {:ok,
value} then value is returned, or if it returns :error then nil is
returned.
See the Map.fetch/2 and Keyword.fetch/2 implementations for examples of
how to implement this callback.
Callback implementation for Access.fetch/2.
Generate an FList from the given normal list.
Invoked in order to access the value under key and update it at the same time.
The implementation of this callback should invoke fun with the value under
key in the passed structure data, or with nil if key is not present in it.
This function must return either {get_value, update_value} or :pop.
If the passed function returns {get_value, update_value},
the return value of this callback should be {get_value, new_data}, where:
get_valueis the retrieved value (which can be operated on before being returned)update_valueis the new value to be stored underkeynew_dataisdataafter updating the value ofkeywithupdate_value.
If the passed function returns :pop, the return value of this callback
must be {value, new_data} where value is the value under key
(or nil if not present) and new_data is data without key.
See the implementations of Map.get_and_update/3 or Keyword.get_and_update/3
for more examples.
Callback implementation for Access.get_and_update/3.
Get the element at the pointed position from a FList.
Get the front element.
Get a new list without the back element.
Get the back element.
move_to_front(t(), non_neg_integer()) :: t()
Get a new list with the element at the pointed position moved to the front.
Generate a FList from the given FTree. If the tree is not provided, a empty list will be generated.
Invoked to “pop” the value under key out of the given data structure.
When key exists in the given structure data, the implementation should
return a {value, new_data} tuple where value is the value that was under
key and new_data is term without key.
When key is not present in the given structure, a tuple {value, data}
should be returned, where value is implementation-defined.
See the implementations for Map.pop/3 or Keyword.pop/3 for more examples.
Callback implementation for Access.pop/2.
Update the value of the element at the pointed position.
Get the size of a FList.
slice(t(), non_neg_integer(), non_neg_integer()) :: t()
Return an FList slice.
Add a new element to the back.
split_at(t(), non_neg_integer()) :: {t(), any(), t()}
Split a FList at the pointed position.
Get a new list without the front elemeny.
Turn an FList into a normal list.
Pop the front element, and then return a tuple.
Pop the back element, and then return a tuple.