| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.IndexedDoublyLinkedList.Bare
Description
Synopsis
- newtype IDLList s = IDLList {}
- data Cell = Cell {}
- emptyCell :: Cell
- data IDLListMonad s a
- runIDLListMonad :: Int -> (forall s. IDLListMonad s a) -> a
- type Index = Int
- singletons :: (PrimMonad m, s ~ PrimState m) => Int -> m (IDLList s)
- writeList :: NonEmpty Index -> IDLListMonad s ()
- getNext :: Index -> IDLListMonad s (Maybe Index)
- getPrev :: Index -> IDLListMonad s (Maybe Index)
- toListFrom :: Index -> IDLListMonad s (NonEmpty Index)
- toListFromR :: Index -> IDLListMonad s (NonEmpty Index)
- toListContains :: Index -> IDLListMonad s (NonEmpty Index)
- toListFromK :: Index -> Int -> IDLListMonad s (NonEmpty Index)
- toListFromRK :: Index -> Int -> IDLListMonad s (NonEmpty Index)
- insertAfter :: Index -> Index -> IDLListMonad s ()
- insertBefore :: Index -> Index -> IDLListMonad s ()
- delete :: Index -> IDLListMonad s ()
- dump :: IDLListMonad s (Vector Cell)
Documentation
Doubly linked list implemented by a mutable vector. So actually this data type can represent a collection of Linked Lists that can efficiently be concatenated and split.
Supports O(1) indexing, and O(1) insertions, deletions
Instances
| MonadReader (IDLList s) (IDLListMonad s) Source # | |
Defined in Data.IndexedDoublyLinkedList.Bare Methods ask :: IDLListMonad s (IDLList s) # local :: (IDLList s -> IDLList s) -> IDLListMonad s a -> IDLListMonad s a # reader :: (IDLList s -> a) -> IDLListMonad s a # | |
Cells in the Linked List
data IDLListMonad s a Source #
Monad in which we can use the IndexedDoublyLinkedList.
Instances
runIDLListMonad :: Int -> (forall s. IDLListMonad s a) -> a Source #
Runs a DLList Computation, starting with n singleton values
singletons :: (PrimMonad m, s ~ PrimState m) => Int -> m (IDLList s) Source #
Constructs a new DoublyLinkedList, of size at most n
writeList :: NonEmpty Index -> IDLListMonad s () Source #
Sets the DoublyLinkedList to the given List.
Indices that do not occur in the list are not touched.
toListFrom :: Index -> IDLListMonad s (NonEmpty Index) Source #
Computes a maximal length list starting from the Given index
running time: \(O(k)\), where \(k\) is the length of the output list
toListFromR :: Index -> IDLListMonad s (NonEmpty Index) Source #
Computes a maximal length list by walking backwards in the DoublyLinkedList, starting from the Given index
running time: \(O(k)\), where \(k\) is the length of the output list
toListContains :: Index -> IDLListMonad s (NonEmpty Index) Source #
Computes a maximal length list that contains the element i.
running time: \(O(k)\), where \(k\) is the length of the output list
toListFromK :: Index -> Int -> IDLListMonad s (NonEmpty Index) Source #
Takes the current element and its k next's
toListFromRK :: Index -> Int -> IDLListMonad s (NonEmpty Index) Source #
Takes the current element and its k prev's
insertAfter :: Index -> Index -> IDLListMonad s () Source #
Inserts the second argument after the first one into the linked list
insertBefore :: Index -> Index -> IDLListMonad s () Source #
Inserts the second argument before the first one into the linked list
delete :: Index -> IDLListMonad s () Source #
Deletes the element from the linked list. This element thus essentially becomes a singleton list.