Data.FMIndex.Internal

WARNING

This module is considered internal.

The Package Versioning Policy does not apply.

The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.

Authors importing this library are expected to track development closely.

All credit goes to the author(s)/maintainer(s) of the containers library for the above warning text.

Description

Various data structures and custom data types to describe the Full-text Minute-space index (FM-index) and the Inverse FM-index implementations, namely seqToFMIndexB, seqToFMIndexT, seqFromFMIndexB, and seqFromFMIndexT.

The FM-index implementations rely heavily upon Seq provided by the containers, STRef and associated functions in the stref library, and runST in the Control.Monad.ST library.

Example FM-index Output

The below example is taken from this wikipedia page.

FM-index output of the Burrows-Wheeler transform of the input "abracadabra" -> "ard$rcaaaabb"

Occ(c,k) of "ard$rcaaaabb"

	a	r	d	$	r	c	a	a	a	a	b	b
	1	2	3	4	5	6	7	8	9	10	11	12
$	0	0	0	1	1	1	1	1	1	1	1	1
a	1	1	1	1	1	1	2	3	4	5	5	5
b	0	0	0	0	0	0	0	0	0	0	1	2
c	0	0	0	0	0	1	1	1	1	1	1	1
d	0	0	1	1	1	1	1	1	1	1	1	1
r	0	1	1	1	2	2	2	2	2	2	2	2

Documentation

newtype FMIndexB

Basic FMIndex (ByteString) data type.

Constructors

FMIndexB (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))

Instances

Generic FMIndexB

Defined in Data.FMIndex.Internal

Associated Types

type Rep FMIndexB :: Type -> Type

Methods

from :: FMIndexB -> Rep FMIndexB x

to :: Rep FMIndexB x -> FMIndexB

Read FMIndexB

Defined in Data.FMIndex.Internal

Methods

readsPrec :: Int -> ReadS FMIndexB

readList :: ReadS [FMIndexB]

readPrec :: ReadPrec FMIndexB

readListPrec :: ReadPrec [FMIndexB]

Show FMIndexB

Defined in Data.FMIndex.Internal

Methods

showsPrec :: Int -> FMIndexB -> ShowS

show :: FMIndexB -> String

showList :: [FMIndexB] -> ShowS

Eq FMIndexB

Defined in Data.FMIndex.Internal

Methods

(==) :: FMIndexB -> FMIndexB -> Bool

(/=) :: FMIndexB -> FMIndexB -> Bool

Ord FMIndexB

Defined in Data.FMIndex.Internal

Methods

compare :: FMIndexB -> FMIndexB -> Ordering

(<) :: FMIndexB -> FMIndexB -> Bool

(<=) :: FMIndexB -> FMIndexB -> Bool

(>) :: FMIndexB -> FMIndexB -> Bool

(>=) :: FMIndexB -> FMIndexB -> Bool

max :: FMIndexB -> FMIndexB -> FMIndexB

min :: FMIndexB -> FMIndexB -> FMIndexB

type Rep FMIndexB

Defined in Data.FMIndex.Internal

type Rep FMIndexB = D1 ('MetaData "FMIndexB" "Data.FMIndex.Internal" "text-compression-0.1.0.14-9ORM6NM9jqVJfQeS6LjkQQ" 'True) (C1 ('MetaCons "FMIndexB" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))))))

newtype FMIndexT

Basic FMIndex (Text) data type.

Constructors

FMIndexT (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))

Instances

Generic FMIndexT

Defined in Data.FMIndex.Internal

Associated Types

type Rep FMIndexT :: Type -> Type

Methods

from :: FMIndexT -> Rep FMIndexT x

to :: Rep FMIndexT x -> FMIndexT

Read FMIndexT

Defined in Data.FMIndex.Internal

Methods

readsPrec :: Int -> ReadS FMIndexT

readList :: ReadS [FMIndexT]

readPrec :: ReadPrec FMIndexT

readListPrec :: ReadPrec [FMIndexT]

Show FMIndexT

Defined in Data.FMIndex.Internal

Methods

showsPrec :: Int -> FMIndexT -> ShowS

show :: FMIndexT -> String

showList :: [FMIndexT] -> ShowS

Eq FMIndexT

Defined in Data.FMIndex.Internal

Methods

(==) :: FMIndexT -> FMIndexT -> Bool

(/=) :: FMIndexT -> FMIndexT -> Bool

Ord FMIndexT

Defined in Data.FMIndex.Internal

Methods

compare :: FMIndexT -> FMIndexT -> Ordering

(<) :: FMIndexT -> FMIndexT -> Bool

(<=) :: FMIndexT -> FMIndexT -> Bool

(>) :: FMIndexT -> FMIndexT -> Bool

(>=) :: FMIndexT -> FMIndexT -> Bool

max :: FMIndexT -> FMIndexT -> FMIndexT

min :: FMIndexT -> FMIndexT -> FMIndexT

type Rep FMIndexT

Defined in Data.FMIndex.Internal

type Rep FMIndexT = D1 ('MetaData "FMIndexT" "Data.FMIndex.Internal" "text-compression-0.1.0.14-9ORM6NM9jqVJfQeS6LjkQQ" 'True) (C1 ('MetaCons "FMIndexT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Seq (Maybe Text, Seq (Int, Int, Maybe Text))))))

type PBFMIndexSeqB = Seq (Maybe ByteString)

Abstract PBFMIndexSeqB type utilizing a Seq.

type FMIndexSeqB = Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))

Abstract FMIndexSeqB type utilizing a Seq. (c,(indexofinputcurrentelement,Occ(c,k),inputcurrentelement))

type STFMIndexSeqB s a = STRef s FMIndexSeqB

Abstract data type representing a FMIndexSeqB in the (strict) ST monad.

updateSTFMIndexSeqAB :: STFMIndexSeqB s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))) -> (Int, Int, Maybe ByteString) -> ST s ()

State function to update FMIndexSeqB with each step of the FMIndex.

updateSTFMIndexSeqBB :: STFMIndexSeqB s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))) -> Maybe ByteString -> ST s ()

State function to update FMIndexSeqB with each step of the FMIndex.

emptySTFMIndexSeqB :: ST s (STFMIndexSeqB s a)

State function to create empty STFMIndexSeqB type.

type STFMIndexILB s a = STRef s (Seq (Maybe ByteString))

Abstract STFMIndexILB and associated state type.

loadSTFMIndexILB :: STMTFILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()

State function to load list into STFMIndexILB.

emptySTFMIndexILB :: ST s (STFMIndexILB s a)

State function to create empty STFMIndexILB type.

type STFMIndexCounterB s a = STRef s Int

Abstract STFMIndexCounterB and associated state type.

updateSTFMIndexCounterB :: STFMIndexCounterB s Int -> Int -> ST s ()

State function to update STFMIndexCounterB.

emptySTFMIndexCounterB :: ST s (STFMIndexCounterB s Int)

State function to create empty STFMIndexCounterB type.

seqToFMIndexB :: PBFMIndexSeqB -> ST s FMIndexSeqB

Strict state monad function.

type PTFMIndexSeqT = Seq (Maybe Text)

Abstract PTFMIndexSeqT type utilizing a Seq.

type FMIndexSeqT = Seq (Maybe Text, Seq (Int, Int, Maybe Text))

Abstract FMIndexSeqT type utilizing a Seq. (c,(indexofinputcurrentelement,Occ(c,k),inputcurrentelement))

type STFMIndexSeqT s a = STRef s FMIndexSeqT

Abstract data type representing a FMIndexSeqT in the (strict) ST monad.

updateSTFMIndexSeqAT :: STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))) -> (Int, Int, Maybe Text) -> ST s ()

State function to update FMIndexSeqT with each step of the FMIndex.

updateSTFMIndexSeqBT :: STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))) -> Maybe Text -> ST s ()

State function to update FMIndexSeqT with each step of the FMIndex.

emptySTFMIndexSeqT :: ST s (STFMIndexSeqT s a)

State function to create empty STFMIndexSeqT type.

type STFMIndexILT s a = STRef s (Seq (Maybe Text))

Abstract STFMIndexILT and associated state type.

loadSTFMIndexILT :: STMTFILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()

State function to load list into STFMIndexILT.

emptySTFMIndexILT :: ST s (STFMIndexILT s a)

State function to create empty STFMIndexILT type.

type STFMIndexCounterT s a = STRef s Int

Abstract STFMIndexCounterT and associated state type.

updateSTFMIndexCounterT :: STFMIndexCounterT s Int -> Int -> ST s ()

State function to update STFMIndexCounterT.

emptySTFMIndexCounterT :: ST s (STFMIndexCounterT s Int)

State function to create empty STFMIndexCounterT type.

seqToFMIndexT :: PTFMIndexSeqT -> ST s FMIndexSeqT

Strict state monad function.

type FFMIndexSeqB = Seq (Maybe ByteString)

Abstract FFMIndexSeqB type utilizing a Seq.

seqFromFMIndexB :: FMIndexB -> FFMIndexSeqB

Simple Inverse FMIndex function.

type FFMIndexSeqT = Seq (Maybe Text)

Abstract FFMIndexSeqT type utilizing a Seq.

seqFromFMIndexT :: FMIndexT -> FFMIndexSeqT

Simple Inverse FMIndex function.