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


-- | Suffix array construction
--   
@package SuffixStructures
@version 0.0.1.0


-- | The suffix array data structure. Supports (de-) serialization via
--   aeson,cereal,binary.
--   
--   Reading and writing to and from specialized "bio" formats is currently
--   open.
--   
--   TODO compression during serialization? TODO versioning? TODO read
--   sam/bam format? TODO what about mmap for really large indices?
module Data.SuffixStructure.ESA

-- | The Suffix Array data type, together with the longest common prefix
--   table.
--   
--   TODO skip table? TODO inverse suffix array?
--   
--   TODO maybe parametrize on the Int type (Int,Int64,Int32,Word's) This
--   will require better specialization of operations in
--   <tt>NaiveArray</tt> and elsewhere. Otherwise performance drops quite
--   noticable by <tt>x5</tt> to <tt>x10</tt>.
data SA
SA :: !(Vector Int) -> !(Vector Int8) -> !(IntMap Int) -> SA

-- | the actual suffix array using 8byte Ints
sa :: SA -> !(Vector Int)

-- | 1byte longest common prefix vector, negative number indicates to look
--   at lcpLong
lcp :: SA -> !(Vector Int8)

-- | lcp's that are unusual long, but this is sparse
lcpLong :: SA -> !(IntMap Int)

-- | Automatically check <a>lcp</a> and <a>lcpLong</a> to return the real
--   prefix length in <a>Int</a> (as opposed to <a>Int8</a> storage of
--   <a>lcp</a>).
lcpAt :: SA -> Int -> Int
instance Eq SA
instance Ord SA
instance Show SA
instance Generic SA
instance Datatype D1SA
instance Constructor C1_0SA
instance Selector S1_0_0SA
instance Selector S1_0_1SA
instance Selector S1_0_2SA
instance Default SA
instance ToJSON SA
instance Serialize SA
instance FromJSON SA
instance Binary SA


-- | TODO need to check performance of <a>drop</a> vs <tt>unsafeDrop</tt>
--   
--   TODO use <a>Word</a> instead of <a>Int</a> -- but check performance
--   due to all those conversions
module Data.SuffixStructure.NaiveArray

-- | Create Suffix Array via Introsort
genSA :: (ListLike ll a, Ord ll, Eq a) => ll -> SA

-- | Create Suffix Array via American Flag sort
genSAaf :: (ListLike ll a, Ord ll, Lexicographic ll, Eq a) => ll -> SA

-- | Build LCP array
buildLCP :: (ListLike ll a, Eq a) => ll -> Vector Int -> (Vector Int8, IntMap Int)

-- | Return the shared prefix of two strings.
commonPrefix :: (ListLike ll a, Eq a) => ll -> ll -> ll

-- | Return the length of the common prefix.
commonPrefixLength :: (ListLike ll a, Eq a) => ll -> ll -> Int