Data.IterLinkedList.Internal

A pure linked list with is mutable through iterators.

Exported internals.

Documentation

data LinkedList iter value

The list

Constructors

LinkedList

Fields

• newKey :: iter

  pre-allocated iterator value for the next inserted element

• firstKey :: iter

  iterator to the first element (equals to newKey when `null container`)

• lastKey :: iter

  iterator to the last element (equals to newKey when `null container`)

• container :: LinkedListContainer iter value

Instances

Show value => Show (LinkedList Int value)

Methods

showsPrec :: Int -> LinkedList Int value -> ShowS

show :: LinkedList Int value -> String

showList :: [LinkedList Int value] -> ShowS

Show value => Show (LinkedList Integer value)

Methods

showsPrec :: Int -> LinkedList Integer value -> ShowS

show :: LinkedList Integer value -> String

showList :: [LinkedList Integer value] -> ShowS

class IterLinkedList iter where

Polymorphic operations on the list

Minimal complete definition

null, get, (set | modify), next, prev, empty, singleton, insertBefore, insertAfter, delete, toList

Methods

null :: LinkedList iter value -> Bool

See if this list is an empty list. O(1)

get :: iter -> LinkedList iter value -> Maybe value

Get the element value. O(lg N)

get' :: iter -> LinkedList iter value -> value

Get the element value. Get undefined if not found. O(lg N)

set :: iter -> value -> LinkedList iter value -> LinkedList iter value

Set the element value. Return the original list if the iterator is not in the list O(lg N)

modify :: iter -> (value -> value) -> LinkedList iter value -> LinkedList iter value

Modify the element value. Return the original list if the iterator is not in the list O(lg N)

next :: LinkedList iter value -> iter -> iter

Get the next iterator. If the specified iterator is the last one, or isn't in the list, return the original one. O(lg N)

prev :: LinkedList iter value -> iter -> iter

Get the previous iterator. If the specified iterator is the first one, or isn't in the list, return the original one. O(lg N)

empty :: LinkedList iter value

Get an empty list. O(1)

singleton :: value -> LinkedList iter value

Get a list with exactly one element. O(1)

insertBefore :: iter -> value -> LinkedList iter value -> LinkedList iter value

Insert a new element before the specified iterator. If the list is empty, just insert the new element as the only element. If the specified iterator can't be found, prepend the new element to the whole list. O(lg N)

insertAfter :: iter -> value -> LinkedList iter value -> LinkedList iter value

Insert a new element after the specified iterator. If the list is empty, just insert the new element as the only element. If the specified iterator can't be found, append the new element to the whole list. O(lg N)

delete :: iter -> LinkedList iter value -> LinkedList iter value

Delete the specified element from the list. If there's no such element in the list, return the original list. O(lg N)

fromList :: [value] -> LinkedList iter value

Get a LinkedList from a list O(N)

toList :: LinkedList iter value -> [value]

Get a list from a LinkedList O(N lg N)

Instances

IterLinkedList Int

Methods

null :: LinkedList Int value -> Bool

get :: Int -> LinkedList Int value -> Maybe value

get' :: Int -> LinkedList Int value -> value

set :: Int -> value -> LinkedList Int value -> LinkedList Int value

modify :: Int -> (value -> value) -> LinkedList Int value -> LinkedList Int value

next :: LinkedList Int value -> Int -> Int

prev :: LinkedList Int value -> Int -> Int

empty :: LinkedList Int value

singleton :: value -> LinkedList Int value

insertBefore :: Int -> value -> LinkedList Int value -> LinkedList Int value

insertAfter :: Int -> value -> LinkedList Int value -> LinkedList Int value

delete :: Int -> LinkedList Int value -> LinkedList Int value

fromList :: [value] -> LinkedList Int value

toList :: LinkedList Int value -> [value]

IterLinkedList Integer

Methods

null :: LinkedList Integer value -> Bool

get :: Integer -> LinkedList Integer value -> Maybe value

get' :: Integer -> LinkedList Integer value -> value

set :: Integer -> value -> LinkedList Integer value -> LinkedList Integer value

modify :: Integer -> (value -> value) -> LinkedList Integer value -> LinkedList Integer value

next :: LinkedList Integer value -> Integer -> Integer

prev :: LinkedList Integer value -> Integer -> Integer

empty :: LinkedList Integer value

singleton :: value -> LinkedList Integer value

insertBefore :: Integer -> value -> LinkedList Integer value -> LinkedList Integer value

insertAfter :: Integer -> value -> LinkedList Integer value -> LinkedList Integer value

delete :: Integer -> LinkedList Integer value -> LinkedList Integer value

fromList :: [value] -> LinkedList Integer value

toList :: LinkedList Integer value -> [value]

type family LinkedListContainer iter value

The internal container

Instances

type LinkedListContainer Int value

type LinkedListContainer Int value = IntMap (Int, value, Int)

type LinkedListContainer Integer value

type LinkedListContainer Integer value = Map Integer (Integer, value, Integer)

firstIter :: LinkedList iter value -> iter

Get the first iterator. If the list is empty, you'll still get an unusable one. You can't get the value from the unusable iterator. O(lg N)

lastIter :: LinkedList iter value -> iter

Get the last iterator. If the list is empty, you'll still get an unusable one. You can't get the value from the unusable iterator. O(lg N)