-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A pure linked list which is mutable through iterators.
--   
--   It's iternally implemented by <a>Data.IntMap.Strict.IntMap</a> or
--   <a>Data.Map.Strict.Map</a> <a>Integer</a>, using <a>Int</a> or
--   <a>Integer</a> as the iterator type respectly. Most of the operations
--   cost <tt>O(lg N)</tt>.
--   
--   Each newly inserted element will consume a unique number and never
--   reuse old numbers. Choose <a>Int</a> one if you're sure that there're
--   no more than <a>Int</a> space times of insertions, or choose
--   <a>Integer</a> one otherwise.
@package linked-list-with-iterator
@version 0.1.1.0


-- | A pure linked list with is mutable through iterators.
--   
--   Exported internals.
module Data.IterLinkedList.Internal

-- | The list
data LinkedList iter value
LinkedList :: iter -> iter -> iter -> LinkedListContainer iter value -> LinkedList iter value

-- | pre-allocated iterator value for the next inserted element
[newKey] :: LinkedList iter value -> iter

-- | iterator to the first element (equals to <a>newKey</a> when `null
--   container`)
[firstKey] :: LinkedList iter value -> iter

-- | iterator to the last element (equals to <a>newKey</a> when `null
--   container`)
[lastKey] :: LinkedList iter value -> iter
[container] :: LinkedList iter value -> LinkedListContainer iter value

-- | Polymorphic operations on the list
class IterLinkedList iter where get' iter list = case get iter list of { Just value -> value Nothing -> undefined } set iter value list = modify iter (const value) list modify iter f list = case get iter list of { Just value -> set iter (f value) list Nothing -> list } fromList [] = empty fromList (a : as) = go (singleton a) as where go list (a : as) = go (insertAfter (lastIter list) a list) as go list _ = list

-- | See if this list is an empty list. <tt>O(1)</tt>
null :: IterLinkedList iter => LinkedList iter value -> Bool

-- | Get the element value. <tt>O(lg N)</tt>
get :: IterLinkedList iter => iter -> LinkedList iter value -> Maybe value

-- | Get the element value. Get undefined if not found. <tt>O(lg N)</tt>
get' :: IterLinkedList iter => iter -> LinkedList iter value -> value

-- | Set the element value. Return the original list if the iterator is not
--   in the list <tt>O(lg N)</tt>
set :: IterLinkedList iter => iter -> value -> LinkedList iter value -> LinkedList iter value

-- | Modify the element value. Return the original list if the iterator is
--   not in the list <tt>O(lg N)</tt>
modify :: IterLinkedList iter => iter -> (value -> value) -> LinkedList iter value -> LinkedList iter value

-- | Get the next iterator. If the specified iterator is the last one, or
--   isn't in the list, return the original one. <tt>O(lg N)</tt>
next :: IterLinkedList iter => 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. <tt>O(lg N)</tt>
prev :: IterLinkedList iter => LinkedList iter value -> iter -> iter

-- | Get an empty list. <tt>O(1)</tt>
empty :: IterLinkedList iter => LinkedList iter value

-- | Get a list with exactly one element. <tt>O(1)</tt>
singleton :: IterLinkedList 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. <tt>O(lg N)</tt>
insertBefore :: IterLinkedList iter => 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. <tt>O(lg N)</tt>
insertAfter :: IterLinkedList iter => iter -> value -> 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. <tt>O(lg N)</tt>
delete :: IterLinkedList iter => iter -> LinkedList iter value -> LinkedList iter value

-- | Get a LinkedList from a list <tt>O(N)</tt>
fromList :: IterLinkedList iter => [value] -> LinkedList iter value

-- | Get a list from a LinkedList <tt>O(N lg N)</tt>
toList :: IterLinkedList iter => LinkedList iter value -> [value]

-- | The internal container

-- | 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.
--   <tt>O(lg N)</tt>
firstIter :: 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.
--   <tt>O(lg N)</tt>
lastIter :: LinkedList iter value -> iter
instance GHC.Show.Show value => GHC.Show.Show (Data.IterLinkedList.Internal.LinkedList GHC.Types.Int value)
instance GHC.Show.Show value => GHC.Show.Show (Data.IterLinkedList.Internal.LinkedList GHC.Integer.Type.Integer value)
instance Data.IterLinkedList.Internal.IterLinkedList GHC.Types.Int
instance Data.IterLinkedList.Internal.IterLinkedList GHC.Integer.Type.Integer


-- | A pure linked list with is mutable through iterators.
--   
--   It's iternally implemented by <a>IntMap</a> or <a>Map</a>
--   <a>Integer</a>, using <a>Int</a> or <a>Integer</a> as the iterator
--   type respectly. Most of the operations cost <tt>O(lg N)</tt>. Each
--   newly inserted element will consume a unique number and never reuse
--   old numbers. Choose <a>Int</a> one if you're sure that there're no
--   more than <a>Int</a> space times of insertions, or choose
--   <a>Integer</a> one otherwise.
module Data.IterLinkedList

-- | Polymorphic operations on the list
class IterLinkedList iter where get' iter list = case get iter list of { Just value -> value Nothing -> undefined } set iter value list = modify iter (const value) list modify iter f list = case get iter list of { Just value -> set iter (f value) list Nothing -> list } fromList [] = empty fromList (a : as) = go (singleton a) as where go list (a : as) = go (insertAfter (lastIter list) a list) as go list _ = list

-- | See if this list is an empty list. <tt>O(1)</tt>
null :: IterLinkedList iter => LinkedList iter value -> Bool

-- | Get the element value. <tt>O(lg N)</tt>
get :: IterLinkedList iter => iter -> LinkedList iter value -> Maybe value

-- | Get the element value. Get undefined if not found. <tt>O(lg N)</tt>
get' :: IterLinkedList iter => iter -> LinkedList iter value -> value

-- | Set the element value. Return the original list if the iterator is not
--   in the list <tt>O(lg N)</tt>
set :: IterLinkedList iter => iter -> value -> LinkedList iter value -> LinkedList iter value

-- | Modify the element value. Return the original list if the iterator is
--   not in the list <tt>O(lg N)</tt>
modify :: IterLinkedList iter => iter -> (value -> value) -> LinkedList iter value -> LinkedList iter value

-- | Get the next iterator. If the specified iterator is the last one, or
--   isn't in the list, return the original one. <tt>O(lg N)</tt>
next :: IterLinkedList iter => 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. <tt>O(lg N)</tt>
prev :: IterLinkedList iter => LinkedList iter value -> iter -> iter

-- | Get an empty list. <tt>O(1)</tt>
empty :: IterLinkedList iter => LinkedList iter value

-- | Get a list with exactly one element. <tt>O(1)</tt>
singleton :: IterLinkedList 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. <tt>O(lg N)</tt>
insertBefore :: IterLinkedList iter => 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. <tt>O(lg N)</tt>
insertAfter :: IterLinkedList iter => iter -> value -> 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. <tt>O(lg N)</tt>
delete :: IterLinkedList iter => iter -> LinkedList iter value -> LinkedList iter value

-- | Get a LinkedList from a list <tt>O(N)</tt>
fromList :: IterLinkedList iter => [value] -> LinkedList iter value

-- | Get a list from a LinkedList <tt>O(N lg N)</tt>
toList :: IterLinkedList iter => LinkedList iter value -> [value]

-- | The list
data LinkedList iter value

-- | 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.
--   <tt>O(lg N)</tt>
firstIter :: 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.
--   <tt>O(lg N)</tt>
lastIter :: LinkedList iter value -> iter
