Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Data.IndexedDoublyLinkedList

Description

Synopsis

data DLList s a = DLList {
- values :: !(Vector a)
- llist :: !(MVector s Cell)
}
data Cell = Cell {
- prev :: Maybe Index
- next :: Maybe Index
}
emptyCell :: Cell
data DLListMonad s b a
runDLListMonad :: Vector b -> (forall s. DLListMonad s b a) -> a
type Index = Int
singletons :: (PrimMonad m, s ~ PrimState m) => Vector b -> m (DLList s b)
writeList :: NonEmpty Index -> DLListMonad s b ()
valueAt :: Index -> DLListMonad s b b
getNext :: Index -> DLListMonad s b (Maybe Index)
getPrev :: Index -> DLListMonad s b (Maybe Index)
toListFrom :: Index -> DLListMonad s b (NonEmpty Index)
toListFromR :: Index -> DLListMonad s b (NonEmpty Index)
toListContains :: Index -> DLListMonad s b (NonEmpty Index)
toListFromK :: Index -> Int -> DLListMonad s b (NonEmpty Index)
toListFromRK :: Index -> Int -> DLListMonad s b (NonEmpty Index)
insertAfter :: Index -> Index -> DLListMonad s b ()
insertBefore :: Index -> Index -> DLListMonad s b ()
delete :: Index -> DLListMonad s b (Maybe Index, Maybe Index)
dump :: DLListMonad s a (Vector a, Vector Cell)

Documentation

data DLList s a Source #

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

Constructors

DLList
Fields values :: !(Vector a) llist :: !(MVector s Cell)

Instances

Instances details

Functor (DLList s) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods fmap :: (a -> b) -> DLList s a -> DLList s b # (<$) :: a -> DLList s b -> DLList s a #
MonadReader (DLList s b) (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods ask :: DLListMonad s b (DLList s b) # local :: (DLList s b -> DLList s b) -> DLListMonad s b a -> DLListMonad s b a # reader :: (DLList s b -> a) -> DLListMonad s b a #

data Cell Source #

Cells in the Linked List

Constructors

Cell
Fields prev :: Maybe Index next :: Maybe Index

Instances

Instances details

Eq Cell Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods (==) :: Cell -> Cell -> Bool # (/=) :: Cell -> Cell -> Bool #
Show Cell Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods showsPrec :: Int -> Cell -> ShowS # show :: Cell -> String # showList :: [Cell] -> ShowS #

emptyCell :: Cell Source #

Empty cell with no next or prev cells.

data DLListMonad s b a Source #

Monad in which we can use the IndexedDoublyLinkedList.

Instances

Instances details

Monad (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods (>>=) :: DLListMonad s b a -> (a -> DLListMonad s b b0) -> DLListMonad s b b0 # (>>) :: DLListMonad s b a -> DLListMonad s b b0 -> DLListMonad s b b0 # return :: a -> DLListMonad s b a #
Functor (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods fmap :: (a -> b0) -> DLListMonad s b a -> DLListMonad s b b0 # (<$) :: a -> DLListMonad s b b0 -> DLListMonad s b a #
Applicative (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods pure :: a -> DLListMonad s b a # (<>) :: DLListMonad s b (a -> b0) -> DLListMonad s b a -> DLListMonad s b b0 # liftA2 :: (a -> b0 -> c) -> DLListMonad s b a -> DLListMonad s b b0 -> DLListMonad s b c # (>) :: DLListMonad s b a -> DLListMonad s b b0 -> DLListMonad s b b0 # (<*) :: DLListMonad s b a -> DLListMonad s b b0 -> DLListMonad s b a #
PrimMonad (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Associated Types type PrimState (DLListMonad s b) # Methods primitive :: (State# (PrimState (DLListMonad s b)) -> (# State# (PrimState (DLListMonad s b)), a #)) -> DLListMonad s b a #
MonadReader (DLList s b) (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList Methods ask :: DLListMonad s b (DLList s b) # local :: (DLList s b -> DLList s b) -> DLListMonad s b a -> DLListMonad s b a # reader :: (DLList s b -> a) -> DLListMonad s b a #
type PrimState (DLListMonad s b) Source #
Instance details Defined in Data.IndexedDoublyLinkedList type PrimState (DLListMonad s b) = s

runDLListMonad :: Vector b -> (forall s. DLListMonad s b a) -> a Source #

Runs a DLList Computation, starting with singleton values, crated from the input vector.

type Index = Int Source #

Cell indices. Must be non-negative.

singletons :: (PrimMonad m, s ~ PrimState m) => Vector b -> m (DLList s b) Source #

Constructs a new DoublyLinkedList. Every element is its own singleton list

writeList :: NonEmpty Index -> DLListMonad s b () Source #

Sets the DoublyLinkedList to the given List.

Indices that do not occur in the list are not touched.

valueAt :: Index -> DLListMonad s b b Source #

Gets the value at Index i

getNext :: Index -> DLListMonad s b (Maybe Index) Source #

Next element in the List

getPrev :: Index -> DLListMonad s b (Maybe Index) Source #

Previous Element in the List

toListFrom :: Index -> DLListMonad s b (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 -> DLListMonad s b (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 -> DLListMonad s b (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 -> DLListMonad s b (NonEmpty Index) Source #

Takes the current element and its k next's

toListFromRK :: Index -> Int -> DLListMonad s b (NonEmpty Index) Source #

Takes the current element and its k prev's

insertAfter :: Index -> Index -> DLListMonad s b () Source #

Inserts the second argument after the first one into the linked list

insertBefore :: Index -> Index -> DLListMonad s b () Source #

Inserts the second argument before the first one into the linked list

delete :: Index -> DLListMonad s b (Maybe Index, Maybe Index) Source #

Deletes the element from the linked list. This element thus essentially becomes a singleton list. Returns the pair of indices that now have become neighbours (i.e. the predecessor and successor of j just before we deleted j).

dump :: DLListMonad s a (Vector a, Vector Cell) Source #

For debugging purposes, dump the values and the cells