\documentclass[10pt,letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\lstnewenvironment{code}{\lstset{language=Haskell,basicstyle=\small}}{}
\author{Alexander Schaap}
\title{Line Storage}
\begin{document}

\maketitle

\section{Thoughts}

Input primarily needs an add/insert function/method, and the Storage only needs to hold lines at this point.
It is assumed the order of the words in the lines has meaning.

Shifter needs a get/ith method/function, and while it typically writes into a new storage (or creates a table of indices according to Parnas), a single heterogeneous storage might be considered - the distinction between shifts and original lines is all that is ultimately required

Parnas mentions that shifter produces shifts in some order, which is more than we asked for - and that this order could be alphabetical, meaning that not allowing for a decomposition in which sorter is empty is a design error

Since some (but not all) storages will need to be ordered, the concept of indices seems necessary, but only to sorter.
Iterators should be a valid alternative to indices.
The distinction between shifts and originals may not matter, unless required by output (e.g. when printing the keyword and then the original line).

Bringing sorter closer to storage is only possible if there is a storage (e.g. not pipe and filter), but sorter would be the only module to swap lines

Output intuitively also needs a get/ith function/method to pretty-print a storage (though it could print a desired shift according to Parnas, presumably working with indices from sorter)

Add and set could be combined into insert, but this separation might reduce the required functionality for different storages.

\subsection{Conclusion}

Ultimately, there should be 3 storages to hold the data between the various steps of KWIC.
The first primarily for input, just containing lines with only an add function for input and a get for shifter.
The second storage would be for shifter, storing shifts (still only an add and a get function).
The third storage is for sorter, containing shifts in a certain order (add function would work if all data was available at once and add added lines sequentially, but insert/set would be necessary if that was not the case).
Output needs a get function as well, but if the pretty-printing requirement is relaxed it might just request the contents of the entire storage instead.
\textbf{(Addition:)}
However, the similarity between a line that holds words and a storage that holds lines is fairly apparent.
For this purpose the thirt storage type could potentially also be used to store individual words to form lines, because it needs to store words in a certain order with the possibility to change that order.

The secret for this module is the way elements are stored.
\begin{code}
{-# LANGUAGE TypeSynonymInstances, FlexibleInstances, MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE StandaloneDeriving, UndecidableInstances #-}
module LineStorage where

import Data.IntMap (IntMap)
import qualified Data.IntMap as IntMap
import Data.Maybe
import Data.Array.IO
import Control.Monad
import Data.Array.Unboxed
import Data.IORef
import Foreign.StablePtr

newtype StorageList e = ListStorage [e] deriving (Show) -- e = Storage or Word
type StorageMap = IntMap
type StorageArray = IOArray Int
newtype StorageGrowableArray e = SGA (IORef (UArray Int e)) 
--deriving instance Show (IORef (UArray Int e)) => Show (StorageGrowableArray e)

class LineStorage s where
  add :: (s e) -> e -> (s e)
  get :: (s e) -> Int -> e
  set :: (s e) -> Int -> e -> (s e)
  len :: (s e) -> Int
  
instance LineStorage StorageList where
  add (ListStorage s) e = ListStorage (s ++ [e])
  get (ListStorage s) i = s !! i
  set (ListStorage s) i e 
    | i >= l || i < 0 = error "Index out of bounds"
    | otherwise = ListStorage $ (take i s) ++ [e] ++ (drop (i+1) s)
      where l = len (ListStorage s)
  len (ListStorage s) = length s

instance LineStorage StorageMap where
  add m e = IntMap.insert (len m) e m
  get m i = x
    where Just x = IntMap.lookup i m
  set m i e = IntMap.insert i e m
  len m = IntMap.size m

class SortableMutableLineStorage s m where
  ini_ :: IArray UArray e => Int -> [e] -> m (s e)
  --add_ :: (s e) -> e -> m (s e)
  get_ :: IArray UArray e => (s e) -> Int -> m e
  set_ :: IArray UArray e => (s e) -> Int -> e -> m ()
  len_ :: IArray UArray e => (s e) -> m Int
  --sort_ :: IArray UArray e => (s e) -> ([e] -> [e]) -> m ()
  --list :: (Show e, IArray UArray e) => (s (StablePtr e)) -> m String
instance SortableMutableLineStorage StorageArray IO where
  ini_ i e = newListArray (1, i) e
  {-add_ a e = do oldElems <- getElems a
                oldBounds <- getBounds a
                let oldLen = snd oldBounds
                a <- newListArray (1, oldLen + 1) oldElems
                writeArray a (oldLen+1) e
                return a-}
  get_ a i = readArray a i
  set_ a i e = writeArray a i e
  len_ a = liftM snd $ getBounds a
  
class ExpandableMutableLineStorage s m where
  add_ :: IArray UArray e => (s e) -> e -> m ()

instance ExpandableMutableLineStorage StorageGrowableArray IO where
  add_ (SGA r) e = 
    do a <- readIORef r
       let els = elems a
           new = listArray (1, (length els) + 1) (els ++ [e])
       writeIORef r new

instance SortableMutableLineStorage StorageGrowableArray IO where
  ini_ i e = do
    --ptrs <- mapM newStablePtr 
    r <- newIORef $ listArray (1, i) e
    return $ SGA r
  get_ (SGA r) i = 
    do a <- readIORef r
       return $ a ! i
  set_ (SGA r) i e =
    do a <- readIORef r
       writeIORef r $ a // [(i, e)]
  len_ (SGA r) =
    do a <- readIORef r
       let ins = indices a
       return $ length ins
  {-sort_ (SGA r) f =
    do a <- readIORef r
       let els = elems a
           new = listArray (1, length els) $ f els
       writeIORef r new-}
--instance Show (StorageGrowableArray e) where

class SortingIterator s m where
  next :: IArray UArray e => (s e) -> e -> e
  hasNext :: IArray UArray e => (s e) -> e -> Bool
  setElem :: IArray UArray e => (s e) -> e -> m ()

--instance SortingIterator StorageGrowableArray State where

    
  
\end{code}
\end{document}