This is an alternative site for discovering Elm packages.
You may be looking for the
official Elm package site
instead.

Fast immutable arrays. The elements in an array must have the same type.

type Array a
= {-
* length : Int = The length of the array.
* startShift : Int = How many bits to shift the index to get the
slot for the first level of the tree.
* tree : Tree a = The actual tree.
* tail : JsArray a = The tail of the array. Inserted into tree when
number of elements is equal to the branching factor. This is an
optimization. It makes operations at the end (push, pop, read, write)
fast.
-}
Array Int Int (Tree a) (JsArray a)

Representation of fast immutable arrays. You can create arrays of integers
(`Array Int`

) or strings (`Array String`

) or any other type of value you can
dream up.

empty : Array a

Return an empty array.

```
length empty == 0
```

initialize : Int -> (Int -> a) -> Array a

Initialize an array. `initialize n f`

creates an array of length `n`

with
the element at index `i`

initialized to the result of `(f i)`

.

```
initialize 4 identity == fromList [0,1,2,3]
initialize 4 (\n -> n*n) == fromList [0,1,4,9]
initialize 4 (always 0) == fromList [0,0,0,0]
```

repeat : Int -> a -> Array a

Creates an array with a given length, filled with a default element.

```
repeat 5 0 == fromList [0,0,0,0,0]
repeat 3 "cat" == fromList ["cat","cat","cat"]
```

Notice that `repeat 3 x`

is the same as `initialize 3 (always x)`

.

fromList : List a -> Array a

Create an array from a `List`

.

isEmpty : Array a -> Bool

Determine if an array is empty.

```
isEmpty empty == True
```

length : Array a -> Int

Return the length of an array.

```
length (fromList [1,2,3]) == 3
```

get : Int -> Array a -> Maybe a

Return `Just`

the element at the index or `Nothing`` if the index is out of
range.

```
get 0 (fromList [0,1,2]) == Just 0
get 2 (fromList [0,1,2]) == Just 2
get 5 (fromList [0,1,2]) == Nothing
get -1 (fromList [0,1,2]) == Nothing
```

set : Int -> a -> Array a -> Array a

Set the element at a particular index. Returns an updated array. If the index is out of range, the array is unaltered.

```
set 1 7 (fromList [1,2,3]) == fromList [1,7,3]
```

push : a -> Array a -> Array a

Push an element onto the end of an array.

```
push 3 (fromList [1,2]) == fromList [1,2,3]
```

append : Array a -> Array a -> Array a

Append two arrays to a new one.

```
append (repeat 2 42) (repeat 3 81) == fromList [42,42,81,81,81]
```

slice : Int -> Int -> Array a -> Array a

Get a sub-section of an array: `(slice start end array)`

. The `start`

is a
zero-based index where we will start our slice. The `end`

is a zero-based index
that indicates the end of the slice. The slice extracts up to but not including
`end`

.

```
slice 0 3 (fromList [0,1,2,3,4]) == fromList [0,1,2]
slice 1 4 (fromList [0,1,2,3,4]) == fromList [1,2,3]
```

Both the `start`

and `end`

indexes can be negative, indicating an offset from
the end of the array.

```
slice 1 -1 (fromList [0,1,2,3,4]) == fromList [1,2,3]
slice -2 5 (fromList [0,1,2,3,4]) == fromList [3,4]
```

This makes it pretty easy to `pop`

the last element off of an array:
`slice 0 -1 array`

toList : Array a -> List a

Create a list of elements from an array.

```
toList (fromList [3,5,8]) == [3,5,8]
```

toIndexedList : Array a -> List ( Int, a )

Create an indexed list from an array. Each element of the array will be paired with its index.

```
toIndexedList (fromList ["cat","dog"]) == [(0,"cat"), (1,"dog")]
```

foldl : (a -> b -> b) -> b -> Array a -> b

Reduce an array from the left. Read `foldl`

as fold from the left.

```
foldl (::) [] (fromList [1,2,3]) == [3,2,1]
```

foldr : (a -> b -> b) -> b -> Array a -> b

Reduce an array from the right. Read `foldr`

as fold from the right.

```
foldr (+) 0 (repeat 3 5) == 15
```

filter : (a -> Bool) -> Array a -> Array a

Keep only elements that satisfy the predicate.

```
filter isEven (fromList [1,2,3]) == (fromList [2])
```

map : (a -> b) -> Array a -> Array b

Apply a function on every element in an array.

```
map sqrt (fromList [1,4,9]) == fromList [1,2,3]
```

indexedMap : (Int -> a -> b) -> Array a -> Array b

Apply a function on every element with its index as first argument.

```
indexedMap (*) (fromList [5,5,5]) == fromList [0,5,10]
```

toString : Array a -> String

Return the array represented as a string.

```
(toString <| Array.fromList [1,2,3]) == "Array [1,2,3]"
```

```
module Array.Hamt
exposing
( Array
, empty
, isEmpty
, length
, initialize
, repeat
, fromList
, get
, set
, push
, toList
, toIndexedList
, foldr
, foldl
, filter
, map
, indexedMap
, append
, slice
, toString
)
{-| Fast immutable arrays. The elements in an array must have the same type.
# Arrays
@docs Array
# Creation
@docs empty, initialize, repeat, fromList
# Query
@docs isEmpty, length, get
# Manipulate
@docs set, push, append, slice
# Lists
@docs toList, toIndexedList
# Transform
@docs foldl, foldr, filter, map, indexedMap
# Display
@docs toString
-}
import Bitwise
import Array.JsArray as JsArray exposing (JsArray)
{-| The array in this module is implemented as a tree with a high branching
factor (number of elements at each level). In comparision, the `Dict` has
a branching factor of 2 (left or right).
The higher the branching factor, the more elements are stored at each level.
This makes writes slower (more to copy per level), but reads faster
(fewer traversals). In practice, 32 is a good compromise.
The branching factor has to be a power of two (8, 16, 32, 64...). This is
because we use the index to tell us which path to take when navigating the
tree, and we do this by dividing it into several smaller numbers (see
`shiftStep` documentation). By dividing the index into smaller numbers, we
will always get a range which is a power of two (2 bits gives 0-3, 3 gives
0-7, 4 gives 0-15...).
-}
branchFactor : Int
branchFactor =
32
{-| A number is made up of several bits. For bitwise operations in javascript,
numbers are treated as 32-bits integers. The number 1 is represented by 31
zeros, and a one. The important thing to take from this, is that a 32-bit
integer has enough information to represent several smaller numbers.
For a branching factor of 32, a 32-bit index has enough information to store 6
different numbers in the range of 0-31 (5 bits), and one number in the range of
0-3 (2 bits). This means that the tree of an array can have, at most, a depth
of 7.
An index essentially functions as a map. To figure out which branch to take at
any given level of the tree, we need to shift (or move) the correct amount of
bits so that those bits are at the front. We can then perform a bitwise and to
read which of the 32 branches to take.
The `shiftStep` specifices how many bits are required to represent the branching
factor.
-}
shiftStep : Int
shiftStep =
logBase 2 (toFloat branchFactor)
|> ceiling
{-| A mask which, when used in a bitwise and, reads the first `shiftStep` bits
in a number as a number of its own.
-}
bitMask : Int
bitMask =
Bitwise.shiftRightZfBy (32 - shiftStep) 0xFFFFFFFF
{-| Representation of fast immutable arrays. You can create arrays of integers
(`Array Int`) or strings (`Array String`) or any other type of value you can
dream up.
-}
type Array a
= {-
* length : Int = The length of the array.
* startShift : Int = How many bits to shift the index to get the
slot for the first level of the tree.
* tree : Tree a = The actual tree.
* tail : JsArray a = The tail of the array. Inserted into tree when
number of elements is equal to the branching factor. This is an
optimization. It makes operations at the end (push, pop, read, write)
fast.
-}
Array Int Int (Tree a) (JsArray a)
{-| Each level in the tree is represented by a `JsArray` of `Node`s.
A `Node` can either be a subtree (the next level of the tree) or, if
we're at the bottom, a `JsArray` of values (also known as a leaf).
-}
type Node a
= SubTree (Tree a)
| Leaf (JsArray a)
type alias Tree a =
JsArray (Node a)
{-| Return an empty array.
length empty == 0
-}
empty : Array a
empty =
{-
`startShift` is only used when there is at least one `Node` in the
`tree`. The minimal value is therefore equal to the `shiftStep`.
-}
Array 0 shiftStep JsArray.empty JsArray.empty
{-| Determine if an array is empty.
isEmpty empty == True
-}
isEmpty : Array a -> Bool
isEmpty (Array length _ _ _) =
length == 0
{-| Return the length of an array.
length (fromList [1,2,3]) == 3
-}
length : Array a -> Int
length (Array length _ _ _) =
length
{-| Initialize an array. `initialize n f` creates an array of length `n` with
the element at index `i` initialized to the result of `(f i)`.
initialize 4 identity == fromList [0,1,2,3]
initialize 4 (\n -> n*n) == fromList [0,1,4,9]
initialize 4 (always 0) == fromList [0,0,0,0]
-}
initialize : Int -> (Int -> a) -> Array a
initialize length fn =
if length <= 0 then
empty
else
let
tailLen =
rem length branchFactor
tail =
JsArray.initialize tailLen (length - tailLen) fn
initialFromIndex =
length - tailLen - branchFactor
in
initializeHelp fn initialFromIndex length [] tail
initializeHelp : (Int -> a) -> Int -> Int -> List (Node a) -> JsArray a -> Array a
initializeHelp fn fromIndex length nodeList tail =
if fromIndex < 0 then
builderToArray False
{ tail = tail
, nodeList = nodeList
, nodeListSize = length // branchFactor
}
else
let
leaf =
Leaf <| JsArray.initialize branchFactor fromIndex fn
in
initializeHelp
fn
(fromIndex - branchFactor)
length
(leaf :: nodeList)
tail
{-| Creates an array with a given length, filled with a default element.
repeat 5 0 == fromList [0,0,0,0,0]
repeat 3 "cat" == fromList ["cat","cat","cat"]
Notice that `repeat 3 x` is the same as `initialize 3 (always x)`.
-}
repeat : Int -> a -> Array a
repeat n e =
initialize n (\_ -> e)
{-| Create an array from a `List`.
-}
fromList : List a -> Array a
fromList ls =
case ls of
[] ->
empty
_ ->
fromListHelp ls [] 0
fromListHelp : List a -> List (Node a) -> Int -> Array a
fromListHelp list nodeList nodeListSize =
let
( jsArray, remainingItems ) =
JsArray.initializeFromList branchFactor list
in
if JsArray.length jsArray < branchFactor then
builderToArray True
{ tail = jsArray
, nodeList = nodeList
, nodeListSize = nodeListSize
}
else
fromListHelp
remainingItems
((Leaf jsArray) :: nodeList)
(nodeListSize + 1)
{-| Return the array represented as a string.
(toString <| Array.fromList [1,2,3]) == "Array [1,2,3]"
-}
toString : Array a -> String
toString array =
let
content =
array
|> map Basics.toString
|> toList
|> String.join ","
in
"Array [" ++ content ++ "]"
{-| Return `Just` the element at the index or `Nothing`` if the index is out of
range.
get 0 (fromList [0,1,2]) == Just 0
get 2 (fromList [0,1,2]) == Just 2
get 5 (fromList [0,1,2]) == Nothing
get -1 (fromList [0,1,2]) == Nothing
-}
get : Int -> Array a -> Maybe a
get idx (Array length startShift tree tail) =
if idx < 0 || idx >= length then
Nothing
else if idx >= tailIndex length then
Just <| JsArray.unsafeGet (Bitwise.and bitMask idx) tail
else
Just <| getHelp startShift idx tree
getHelp : Int -> Int -> Tree a -> a
getHelp shift idx tree =
let
pos =
Bitwise.and bitMask <| Bitwise.shiftRightZfBy shift idx
in
case JsArray.unsafeGet pos tree of
SubTree subTree ->
getHelp (shift - shiftStep) idx subTree
Leaf values ->
JsArray.unsafeGet (Bitwise.and bitMask idx) values
{-| Given an array length, return the index of the first element in the tail.
Commonly used to check if a given index references something in the tail.
-}
tailIndex : Int -> Int
tailIndex len =
len
|> Bitwise.shiftRightZfBy 5
|> Bitwise.shiftLeftBy 5
{-| Set the element at a particular index. Returns an updated array.
If the index is out of range, the array is unaltered.
set 1 7 (fromList [1,2,3]) == fromList [1,7,3]
-}
set : Int -> a -> Array a -> Array a
set idx val ((Array length startShift tree tail) as arr) =
if idx < 0 || idx >= length then
arr
else if idx >= tailIndex length then
Array length startShift tree <|
JsArray.unsafeSet (Bitwise.and bitMask idx) val tail
else
Array
length
startShift
(setHelp startShift idx val tree)
tail
setHelp : Int -> Int -> a -> Tree a -> Tree a
setHelp shift idx val tree =
let
pos =
Bitwise.and bitMask <| Bitwise.shiftRightZfBy shift idx
in
case JsArray.unsafeGet pos tree of
SubTree subTree ->
let
newSub =
setHelp (shift - shiftStep) idx val subTree
in
JsArray.unsafeSet pos (SubTree newSub) tree
Leaf values ->
let
newLeaf =
JsArray.unsafeSet (Bitwise.and bitMask idx) val values
in
JsArray.unsafeSet pos (Leaf newLeaf) tree
{-| Push an element onto the end of an array.
push 3 (fromList [1,2]) == fromList [1,2,3]
-}
push : a -> Array a -> Array a
push a ((Array _ _ _ tail) as arr) =
unsafeReplaceTail (JsArray.push a tail) arr
{-| Replaces the tail of an array. If the length of the tail equals the
`branchFactor`, it is inserted into the tree, and the tail cleared.
WARNING: For performance reasons, this function does not check if the new tail
has a length equal to or beneath the `branchFactor`. Make sure this is the case
before using this function.
-}
unsafeReplaceTail : JsArray a -> Array a -> Array a
unsafeReplaceTail newTail (Array length startShift tree tail) =
let
originalTailLen =
JsArray.length tail
newTailLen =
JsArray.length newTail
newArrayLen =
length + (newTailLen - originalTailLen)
in
if newTailLen == branchFactor then
let
overflow =
Bitwise.shiftRightZfBy shiftStep newArrayLen > Bitwise.shiftLeftBy startShift 1
in
if overflow then
let
newShift =
startShift + shiftStep
newTree =
JsArray.singleton (SubTree tree)
|> insertTailInTree newShift length newTail
in
Array
newArrayLen
newShift
newTree
JsArray.empty
else
Array
newArrayLen
startShift
(insertTailInTree startShift length newTail tree)
JsArray.empty
else
Array
newArrayLen
startShift
tree
newTail
insertTailInTree : Int -> Int -> JsArray a -> Tree a -> Tree a
insertTailInTree shift idx tail tree =
let
pos =
Bitwise.and bitMask <| Bitwise.shiftRightZfBy shift idx
in
if pos >= JsArray.length tree then
if shift == 5 then
JsArray.push (Leaf tail) tree
else
let
newSub =
JsArray.empty
|> insertTailInTree (shift - shiftStep) idx tail
|> SubTree
in
JsArray.push newSub tree
else
let
val =
JsArray.unsafeGet pos tree
in
case val of
SubTree subTree ->
let
newSub =
subTree
|> insertTailInTree (shift - shiftStep) idx tail
|> SubTree
in
JsArray.unsafeSet pos newSub tree
Leaf _ ->
let
newSub =
JsArray.singleton val
|> insertTailInTree (shift - shiftStep) idx tail
|> SubTree
in
JsArray.unsafeSet pos newSub tree
{-| Create a list of elements from an array.
toList (fromList [3,5,8]) == [3,5,8]
-}
toList : Array a -> List a
toList arr =
foldr (::) [] arr
{-| Create an indexed list from an array. Each element of the array will be
paired with its index.
toIndexedList (fromList ["cat","dog"]) == [(0,"cat"), (1,"dog")]
-}
toIndexedList : Array a -> List ( Int, a )
toIndexedList ((Array length _ _ _) as arr) =
let
helper n ( idx, ls ) =
( idx - 1, ( idx, n ) :: ls )
in
foldr helper ( length - 1, [] ) arr
|> Tuple.second
{-| Reduce an array from the right. Read `foldr` as fold from the right.
foldr (+) 0 (repeat 3 5) == 15
-}
foldr : (a -> b -> b) -> b -> Array a -> b
foldr f init (Array _ _ tree tail) =
let
helper i acc =
case i of
SubTree subTree ->
JsArray.foldr helper acc subTree
Leaf values ->
JsArray.foldr f acc values
acc =
JsArray.foldr f init tail
in
JsArray.foldr helper acc tree
{-| Reduce an array from the left. Read `foldl` as fold from the left.
foldl (::) [] (fromList [1,2,3]) == [3,2,1]
-}
foldl : (a -> b -> b) -> b -> Array a -> b
foldl f init (Array _ _ tree tail) =
let
helper i acc =
case i of
SubTree subTree ->
JsArray.foldl helper acc subTree
Leaf values ->
JsArray.foldl f acc values
acc =
JsArray.foldl helper init tree
in
JsArray.foldl f acc tail
{-| Keep only elements that satisfy the predicate.
filter isEven (fromList [1,2,3]) == (fromList [2])
-}
filter : (a -> Bool) -> Array a -> Array a
filter f arr =
let
helper n acc =
if f n then
n :: acc
else
acc
in
foldr helper [] arr
|> fromList
{-| Apply a function on every element in an array.
map sqrt (fromList [1,4,9]) == fromList [1,2,3]
-}
map : (a -> b) -> Array a -> Array b
map f (Array length startShift tree tail) =
let
helper i =
case i of
SubTree subTree ->
SubTree <| JsArray.map helper subTree
Leaf values ->
Leaf <| JsArray.map f values
in
Array
length
startShift
(JsArray.map helper tree)
(JsArray.map f tail)
{-| Apply a function on every element with its index as first argument.
indexedMap (*) (fromList [5,5,5]) == fromList [0,5,10]
-}
indexedMap : (Int -> a -> b) -> Array a -> Array b
indexedMap f ((Array length _ tree tail) as arr) =
let
helper node builder =
case node of
SubTree subTree ->
JsArray.foldl helper builder subTree
Leaf leaf ->
let
offset =
builder.nodeListSize * branchFactor
mappedLeaf =
Leaf <| JsArray.indexedMap f offset leaf
in
{ tail = builder.tail
, nodeList = mappedLeaf :: builder.nodeList
, nodeListSize = builder.nodeListSize + 1
}
initialBuilder =
{ tail = JsArray.indexedMap f (tailIndex length) tail
, nodeList = []
, nodeListSize = 0
}
in
JsArray.foldl helper initialBuilder tree
|> builderToArray True
{-| Append two arrays to a new one.
append (repeat 2 42) (repeat 3 81) == fromList [42,42,81,81,81]
-}
append : Array a -> Array a -> Array a
append ((Array _ _ _ aTail) as a) (Array bLen _ bTree bTail) =
-- The magic number 4 has been found with benchmarks
if bLen <= (branchFactor * 4) then
let
foldHelper node arr =
case node of
SubTree tree ->
JsArray.foldl foldHelper arr tree
Leaf leaf ->
appendHelpTree leaf arr
in
JsArray.foldl foldHelper a bTree
|> appendHelpTree bTail
else
let
builder =
builderFromArray a
foldHelper node builder =
case node of
SubTree tree ->
JsArray.foldl foldHelper builder tree
Leaf leaf ->
appendHelpBuilder leaf builder
in
JsArray.foldl foldHelper builder bTree
|> appendHelpBuilder bTail
|> builderToArray True
appendHelpTree : JsArray a -> Array a -> Array a
appendHelpTree toAppend ((Array length shiftStep tree tail) as arr) =
let
appended =
JsArray.appendN branchFactor tail toAppend
itemsToAppend =
JsArray.length toAppend
notAppended =
branchFactor - (JsArray.length tail) - itemsToAppend
newArray =
unsafeReplaceTail appended arr
in
if notAppended < 0 then
let
nextTail =
JsArray.slice notAppended itemsToAppend toAppend
in
unsafeReplaceTail nextTail newArray
else
newArray
appendHelpBuilder : JsArray a -> Builder a -> Builder a
appendHelpBuilder tail builder =
let
appended =
JsArray.appendN branchFactor builder.tail tail
tailLen =
JsArray.length tail
notAppended =
branchFactor - (JsArray.length builder.tail) - tailLen
in
if notAppended < 0 then
{ tail = JsArray.slice notAppended tailLen tail
, nodeList = (Leaf appended) :: builder.nodeList
, nodeListSize = builder.nodeListSize + 1
}
else if notAppended == 0 then
{ tail = JsArray.empty
, nodeList = (Leaf appended) :: builder.nodeList
, nodeListSize = builder.nodeListSize + 1
}
else
{ tail = appended
, nodeList = builder.nodeList
, nodeListSize = builder.nodeListSize
}
{-| Get a sub-section of an array: `(slice start end array)`. The `start` is a
zero-based index where we will start our slice. The `end` is a zero-based index
that indicates the end of the slice. The slice extracts up to but not including
`end`.
slice 0 3 (fromList [0,1,2,3,4]) == fromList [0,1,2]
slice 1 4 (fromList [0,1,2,3,4]) == fromList [1,2,3]
Both the `start` and `end` indexes can be negative, indicating an offset from
the end of the array.
slice 1 -1 (fromList [0,1,2,3,4]) == fromList [1,2,3]
slice -2 5 (fromList [0,1,2,3,4]) == fromList [3,4]
This makes it pretty easy to `pop` the last element off of an array:
`slice 0 -1 array`
-}
slice : Int -> Int -> Array a -> Array a
slice from to arr =
let
correctFrom =
translateIndex from arr
correctTo =
translateIndex to arr
in
if correctFrom > correctTo then
empty
else
arr
|> sliceRight correctTo
|> sliceLeft correctFrom
{-| Given a relative array index, convert it into an absolute one.
translateIndex -1 someArray == someArray.length - 1
translateIndex -10 someArray == someArray.length - 10
translateIndex 5 someArray == 5
-}
translateIndex : Int -> Array a -> Int
translateIndex idx (Array length _ _ _) =
let
posIndex =
if idx < 0 then
length + idx
else
idx
in
if posIndex < 0 then
0
else if posIndex > length then
length
else
posIndex
{-| This function slices the tree from the right.
First, two things are tested:
1. If the array does not need slicing, return the original array.
2. If the array can be sliced by only slicing the tail, slice the tail.
Otherwise, we do the following:
1. Find the new tail in the tree, promote it to the root tail position and
slice it.
2. Slice every sub tree.
3. Promote subTrees until the tree has the correct height.
-}
sliceRight : Int -> Array a -> Array a
sliceRight end ((Array length startShift tree tail) as arr) =
if end == length then
arr
else if end >= tailIndex length then
Array end startShift tree <|
JsArray.slice 0 (Bitwise.and bitMask end) tail
else
let
endIdx =
tailIndex end
depth =
(endIdx - 1)
|> max 1
|> toFloat
|> logBase (toFloat branchFactor)
|> floor
newShift =
max 5 <| depth * shiftStep
in
Array
end
newShift
(tree
|> sliceTree startShift endIdx
|> hoistTree startShift newShift
)
(fetchNewTail startShift end endIdx tree)
{-| Slice and return the `Leaf` node after what is to be the last node
in the sliced tree.
-}
fetchNewTail : Int -> Int -> Int -> Tree a -> JsArray a
fetchNewTail shift end treeEnd tree =
let
pos =
Bitwise.and bitMask <| Bitwise.shiftRightZfBy shift treeEnd
in
case JsArray.unsafeGet pos tree of
SubTree sub ->
fetchNewTail (shift - shiftStep) end treeEnd sub
Leaf values ->
JsArray.slice 0 (Bitwise.and bitMask end) values
{-| Shorten the root `Node` of the tree so it is long enough to contain
the `Node` indicated by `endIdx`. Then recursively perform the same operation
to the last node of each `SubTree`.
-}
sliceTree : Int -> Int -> Tree a -> Tree a
sliceTree shift endIdx tree =
let
lastPos =
Bitwise.and bitMask <| Bitwise.shiftRightZfBy shift endIdx
in
case JsArray.unsafeGet lastPos tree of
SubTree sub ->
let
newSub =
sliceTree (shift - shiftStep) endIdx sub
in
if JsArray.length newSub == 0 then
-- The sub is empty, slice it away
JsArray.slice 0 lastPos tree
else
tree
|> JsArray.slice 0 (lastPos + 1)
|> JsArray.unsafeSet lastPos (SubTree newSub)
-- This is supposed to be the new tail. Fetched by `fetchNewTail`.
-- Slice up to, but not including, this point.
Leaf _ ->
JsArray.slice 0 lastPos tree
{-| The tree is supposed to be of a certain depth. Since slicing removes
elements, it could be that the tree should have a smaller depth
than it had originally. This function shortens the height if it is necessary
to do so.
-}
hoistTree : Int -> Int -> Tree a -> Tree a
hoistTree oldShift newShift tree =
if oldShift <= newShift || JsArray.length tree == 0 then
tree
else
case JsArray.unsafeGet 0 tree of
SubTree sub ->
hoistTree (oldShift - shiftStep) newShift sub
Leaf _ ->
tree
{-| This function slices the tree from the left. Such an operation will change
the index of every element after the slice. Which means that we will have to
rebuild the array.
First, two things are tested:
1. If the array does not need slicing, return the original array.
2. If the slice removes every element but those in the tail, slice the tail and
set the tree to the empty array.
Otherwise, we do the following:
1. Add every leaf node in the tree to a list.
2. Drop the nodes which are supposed to be sliced away.
3. Slice the head node of the list, which represents the start of the new array.
4. Create a builder with the tail set as the node from the previous step.
5. Append the remaining nodes into this builder, and create the array.
-}
sliceLeft : Int -> Array a -> Array a
sliceLeft from ((Array length _ tree tail) as arr) =
if from == 0 then
arr
else if from >= tailIndex length then
Array (length - from) shiftStep JsArray.empty <|
JsArray.slice (from - tailIndex length) (JsArray.length tail) tail
else
let
helper node acc =
case node of
SubTree subTree ->
JsArray.foldr helper acc subTree
Leaf leaf ->
leaf :: acc
leafNodes =
JsArray.foldr helper [ tail ] tree
skipNodes =
from // branchFactor
nodesToInsert =
List.drop skipNodes leafNodes
in
case nodesToInsert of
[] ->
empty
head :: rest ->
let
firstSlice =
from - (skipNodes * branchFactor)
initialBuilder =
{ tail =
JsArray.slice
firstSlice
(JsArray.length head)
head
, nodeList = []
, nodeListSize = 0
}
in
List.foldl appendHelpBuilder initialBuilder rest
|> builderToArray True
{-| A builder contains all information necessary to build an array. Adding
information to the builder is fast. A builder is therefore a suitable
intermediary for constructing arrays.
-}
type alias Builder a =
{ tail : JsArray a
, nodeList : List (Node a)
, nodeListSize : Int
}
{-| The empty builder.
-}
emptyBuilder : Builder a
emptyBuilder =
{ tail = JsArray.empty
, nodeList = []
, nodeListSize = 0
}
{-| Converts an array to a builder.
-}
builderFromArray : Array a -> Builder a
builderFromArray (Array length _ tree tail) =
let
helper node acc =
case node of
SubTree tree ->
JsArray.foldl helper acc tree
Leaf _ ->
node :: acc
in
{ tail = tail
, nodeList = JsArray.foldl helper [] tree
, nodeListSize = length // branchFactor
}
{-| Construct an array with the information in a given builder.
Due to the nature of `List` the list of nodes in a builder will often
be in reverse order (that is, the first leaf of the array is the last
node in the node list). This function therefore allows the caller to
specify if the node list should be reversed before building the array.
-}
builderToArray : Bool -> Builder a -> Array a
builderToArray reverseNodeList builder =
if builder.nodeListSize == 0 then
Array
(JsArray.length builder.tail)
shiftStep
JsArray.empty
builder.tail
else
let
treeLen =
builder.nodeListSize * branchFactor
depth =
(treeLen - 1)
|> toFloat
|> logBase (toFloat branchFactor)
|> floor
correctNodeList =
if reverseNodeList then
List.reverse builder.nodeList
else
builder.nodeList
tree =
treeFromBuilder correctNodeList builder.nodeListSize
in
Array
(JsArray.length builder.tail + treeLen)
(max 5 <| depth * shiftStep)
tree
builder.tail
{-| Takes a list of leaves and an `Int` specifying how many leaves there are,
and builds a tree structure to be used in an `Array`.
-}
treeFromBuilder : List (Node a) -> Int -> Tree a
treeFromBuilder nodeList nodeListSize =
let
newNodeSize =
((toFloat nodeListSize) / (toFloat branchFactor))
|> ceiling
in
if newNodeSize == 1 then
JsArray.initializeFromList branchFactor nodeList
|> Tuple.first
else
treeFromBuilder
(compressNodes nodeList [])
newNodeSize
{-| Takes a list of nodes and return a list of `SubTree`s containing those
nodes.
-}
compressNodes : List (Node a) -> List (Node a) -> List (Node a)
compressNodes nodes acc =
let
( node, remainingNodes ) =
JsArray.initializeFromList branchFactor nodes
newAcc =
(SubTree node) :: acc
in
case remainingNodes of
[] ->
List.reverse newAcc
_ ->
compressNodes remainingNodes newAcc
```