Copyright	(c) CindyLinz 2016
License	MIT
Maintainer	cindylinz@gmail.com
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Data.IterLinkedList.Internal

Description

A pure linked list with is mutable through iterators.

Exported internals.

Synopsis

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)