exqueue v0.1.2 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.fromList()
#FList<[1, 2, 3, 4]>

You can run mix test first to check whether the implement is working well.

Link to this section Summary

Types

t()

FList.t stands for the FList

Functions

concat(a, b)

Concat two FLists

cons(list, x)

Add a new element to the front.

Examples

extractAt(list, x)

Get a new list without the element at the pointed position

fetch(term, key)

Invoked in order to access the value stored under key in the given term term

fromList(originalList)

Generate a FList from the given normal list

get(term, key, default)

Invoked in order to access the value stored under key in the given term term, defaulting to default if not present

getAt(list, x)

Get the element at the pointed position from a FList

get_and_update(term, key, fun)

Invoked in order to access the value under key and update it at the same time

head(list)

Get the front element

init(list)

Get a new list without the back element

last(list)

Get the back element

moveToFront(list, x)

Get a new list with the element at the pointed position moved to the front

new(t \\ :Empty)

Generate a FList from the given FTree. If the tree is not provided, a empty list will be generated

pop(term, key)

Invoked to “pop” the value under key out of the given term

setAt(list, x, ele)

Update the value of the element at the pointed position

size(list)

Get the size of a FList

snoc(list, x)

Add a new element to the back

splitAt(list, x)

Split a FList at the pointed position

tail(list)

Get a new list without the front elemeny

toList(list)

Turn a FList into a normal list

uncons(list)

Pop the front element, and then return a tuple

unsnoc(list)

Pop the back element, and then return a tuple

Link to this section Types

t()

t() :: %FList{tree: FList.FTree.t}

FList.t stands for the FList.

Link to this section Functions

concat(a, b)

concat(t, t) :: t

Concat two FLists.

cons(list, x)

cons(t, any) :: t

Add a new element to the front.

Examples

iex> FList.new() |> FList.cons(0)
#FList<[0]>

extractAt(list, x)

extractAt(t, non_neg_integer) :: {any, t}

Get a new list without the element at the pointed position.

fetch(term, key)

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 it succeeded, or :error if the key does not exist in the structure.

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.

fromList(originalList)

fromList(list) :: t

Generate a FList from the given normal list.

get(term, key, default)

Invoked in order to access the value stored under key in the given term term, defaulting to default if not present.

This function should return the value under the key key in term if there’s such key, otherwise default.

For most data structures, this can be implemented using fetch/2 internally; for example:

def get(structure, key, default) do
  case fetch(structure, key) do
    {:ok, value} -> value
    :error       -> default
  end
end

See the Map.get/3 and Keyword.get/3 implementations for more examples.

Callback implementation for Access.get/3.

getAt(list, x)

getAt(t, non_neg_integer) :: any

Get the element at the pointed position from a FList.

get_and_update(term, key, fun)

Invoked in order to access the value under key and update it at the same time.

The implementation of this callback should invoke the passed function with the value under key key in the passed structure, or nil if the key is not present. This function should return either {value_to_return, new_value} or :pop.

If it returns {value_to_return, new_value}, the return value of this callback should be {value_to_return, new_term} where new_term is term after updating the value of key with new_value.

If it returns :pop, the return value of this callback should be {value, new_term} where value is the value under key or nil if not present, and new_term is term without the key 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.

head(list)

head(t) :: any

Get the front element.

init(list)

init(t) :: t

Get a new list without the back element.

last(list)

last(t) :: any

Get the back element.

moveToFront(list, x)

moveToFront(t, non_neg_integer) :: t

Get a new list with the element at the pointed position moved to the front.

new(t \\ :Empty)

new(FList.FTree.t) :: t

Generate a FList from the given FTree. If the tree is not provided, a empty list will be generated.

pop(term, key)

Invoked to “pop” the value under key out of the given term.

When the key key exists in the given term, the implementation should return a {value, new_term} tuple where value is the value that was under key and new_term is term without key.

When the key key is not present in the given term, a tuple {value, term} 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.

setAt(list, x, ele)

setAt(t, non_neg_integer, any) :: t

Update the value of the element at the pointed position.

size(list)

size(t) :: non_neg_integer

Get the size of a FList.

snoc(list, x)

snoc(t, any) :: t

Add a new element to the back.

splitAt(list, x)

splitAt(t, non_neg_integer) :: {t, any, t}

Split a FList at the pointed position.

tail(list)

tail(t) :: t

Get a new list without the front elemeny.

toList(list)

toList(t) :: list

Turn a FList into a normal list.

uncons(list)

uncons(t) :: {any, t}

Pop the front element, and then return a tuple.

unsnoc(list)

unsnoc(t) :: {t, any}

Pop the back element, and then return a tuple.