Persistent Vector v0.1.4 PersistentVector View Source
PersistentVector is an array-like collection of values indexed by contiguous 0-based integer index
and optimized for growing/shrinking at the end.
PersistentVector optimizes the following operations:
- Get element count
- Lookup element by index
- Update element by index
- Adding new element to the end
- Removing element from the end
- Enumeration
Get count operation is O(1), most others are O(log32(N)).
PersistentVector is implemented as a trie with 32-way branching at each level and uses structural sharing for updates.
All ideas are borrowed directly from Clojure, yet the implementation (and all the bugs) are my own.
Supported protocols
PersistentVector implements the following protocols/behaviors:
Usage example
iex> v = new(1..3)
#PersistentVector<count: 3, [1, 2, 3]>
iex> get(v, 0)
1
iex> v[1]
2
iex> set(v, 1, :two)
#PersistentVector<count: 3, [1, :two, 3]>
iex> v # but v remains unchanged
#PersistentVector<count: 3, [1, 2, 3]>
iex> append(v, 4)
#PersistentVector<count: 4, [1, 2, 3, 4]>
iex> remove_last(v)
#PersistentVector<count: 2, [1, 2]>Efficiency
Creating big vectors is OK both CPU-wise and memory-wise.
For a 100_000-element vector the trie depths is 4
(because log32(100_000) = 3.3), leading to fast lookup in 4 hops:
iex> big = new(100_000..0)
iex> big[70_000]
30_000Update is also fast and efficient as it needs to build only 4 new trie nodes.
Apart from that big1 and big2 share majority of the elements, leading to efficient memory usage:
iex> big1 = new(100_000..0)
iex> big2 = set(big1, 70_000, "thirty thousand")
iex> big2[70_000]
"thirty thousand"Link to this section Summary
Functions
Appends new_value to the end of v
Returns element count in v
Returns empty PersistentVector, same as new/0
Returns true if v is empty and false otherwise
Returns value of element in v at 0-based index
Returns value of element in v at 0-based index or default if index >= count(v)
Returns last element in v, or raises ArgumentError if v is empty
Returns last element in v, or default if v is empty
Creates new empty PersistentVector, same as empty/0
Returns PersistentVector with elements from enumerable
Removes last element from v or raises ArgumentError if v is empty
Returns updated v with element at 0-based index set to new_value
Converts PersistentVector v to List
Link to this section Types
Integer >= 0 for indexing elements.
t() :: %PersistentVector{count: index, root: tuple, shift: shift, tail: tuple}
The PersistentVector itself.
Stored values.
Link to this section Functions
Appends new_value to the end of v.
Examples:
iex> v = append(empty(), 1)
#PersistentVector<count: 1, [1]>
iex> append(v, 2)
#PersistentVector<count: 2, [1, 2]>Returns element count in v.
Returns empty PersistentVector, same as new/0.
Returns true if v is empty and false otherwise.
Returns value of element in v at 0-based index.
Index must be an integer and satisfy condition 0 <= index < count(v) or ArgumentError will be raised.
Note that since PersistentVector implements Access behavior, a shorter syntax v[i] can be used.
See also: get/3
Examples:
iex> v = new([:a, :b, :c])
#PersistentVector<count: 3, [:a, :b, :c]>
iex> get(v, 0)
:a
iex> v[1]
:b
iex> get(v, 10)
** (ArgumentError) Attempt to get index 10 for vector of size 3
iex> v[10]
nilReturns value of element in v at 0-based index or default if index >= count(v).
Index must be an integer and satisfy condition 0 <= index or ArgumentError will be raised.
See also: get/2
Examples:
iex> v = new([:a, :b, :c])
#PersistentVector<count: 3, [:a, :b, :c]>
iex> get(v, 0, :not_found)
:a
iex> get(v, 10, :not_found)
:not_found
iex> get(v, :bad_index, :not_found)
** (ArgumentError) Attempt to get index :bad_index for vector of size 3Returns last element in v, or raises ArgumentError if v is empty.
See also: last/2
Examples:
iex> v = new(1..3)
iex> last(v)
3
iex> last(empty())
** (ArgumentError) last/1 called for empty vectorReturns last element in v, or default if v is empty.
See also: last/1
Examples:
iex> v = new(1..3)
iex> last(v, nil)
3
iex> last(empty(), nil)
nil
iex> last(empty(), 0)
0Creates new empty PersistentVector, same as empty/0.
Returns PersistentVector with elements from enumerable.
Removes last element from v or raises ArgumentError if v is empty.
Examples:
iex> v = new(1..3)
#PersistentVector<count: 3, [1, 2, 3]>
iex> remove_last(v)
#PersistentVector<count: 2, [1, 2]>
iex> remove_last(empty())
** (ArgumentError) Cannot remove_last from empty vectorReturns updated v with element at 0-based index set to new_value.
Index must be an integer and satisfy condition 0 <= index <= count(v) or ArgumentError will be raised.
Note that setting index equal to count(v) is allowed and behaves as append/2.
Examples:
iex> v = new([:a, :b, :c])
#PersistentVector<count: 3, [:a, :b, :c]>
iex> get(v, 1)
:b
iex> set(v, 1, :new_value)
#PersistentVector<count: 3, [:a, :new_value, :c]>
iex> set(v, 3, :append)
#PersistentVector<count: 4, [:a, :b, :c, :append]>
iex> set(v, 10, :wrong_index)
** (ArgumentError) Attempt to set index 10 for vector of size 3Converts PersistentVector v to List.
This function is more efficient than Enum.into/2(v, []) call
because it builds the list in correct order right away and
does not require :lists.reverse/1 call at the end.
Examples:
iex> to_list(new(1..3))
[1, 2, 3]
iex> to_list(empty())
[]