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 seqToOccCKB, seqToOccCKT, seqToCcB, seqToCcT, 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.

Given the following input, "abracadabra":

and

Given the following Burrows-Wheeler matrix (BWM) of the input "abracadabra":

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

The FM-index output of the Burrows-Wheeler transform of the input is:

C[c] of "ard$rcaaaabb"

c	$	a	b	c	d	r
C[c]	0	1	6	8	9	10

and

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 (CcB, OccCKB)

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.15-1U3drBT2M3HZ6U4DNXh3m" 'True) (C1 ('MetaCons "FMIndexB" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (CcB, OccCKB))))

newtype FMIndexT

Basic FMIndex (Text) data type.

Constructors

FMIndexT (CcT, OccCKT)

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.15-1U3drBT2M3HZ6U4DNXh3m" 'True) (C1 ('MetaCons "FMIndexT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (CcT, OccCKT))))

newtype OccCKB

Basic OccCKB (ByteString) data type.

Constructors

OccCKB (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))

Instances

Generic OccCKB

Defined in Data.FMIndex.Internal

Associated Types

type Rep OccCKB :: Type -> Type

Methods

from :: OccCKB -> Rep OccCKB x

to :: Rep OccCKB x -> OccCKB

Read OccCKB

Defined in Data.FMIndex.Internal

Methods

readsPrec :: Int -> ReadS OccCKB

readList :: ReadS [OccCKB]

readPrec :: ReadPrec OccCKB

readListPrec :: ReadPrec [OccCKB]

Show OccCKB

Defined in Data.FMIndex.Internal

Methods

showsPrec :: Int -> OccCKB -> ShowS

show :: OccCKB -> String

showList :: [OccCKB] -> ShowS

Eq OccCKB

Defined in Data.FMIndex.Internal

Methods

(==) :: OccCKB -> OccCKB -> Bool

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

Ord OccCKB

Defined in Data.FMIndex.Internal

Methods

compare :: OccCKB -> OccCKB -> Ordering

(<) :: OccCKB -> OccCKB -> Bool

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

(>) :: OccCKB -> OccCKB -> Bool

(>=) :: OccCKB -> OccCKB -> Bool

max :: OccCKB -> OccCKB -> OccCKB

min :: OccCKB -> OccCKB -> OccCKB

type Rep OccCKB

Defined in Data.FMIndex.Internal

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

newtype OccCKT

Basic OccCKT (Text) data type.

Constructors

OccCKT (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))

Instances

Generic OccCKT

Defined in Data.FMIndex.Internal

Associated Types

type Rep OccCKT :: Type -> Type

Methods

from :: OccCKT -> Rep OccCKT x

to :: Rep OccCKT x -> OccCKT

Read OccCKT

Defined in Data.FMIndex.Internal

Methods

readsPrec :: Int -> ReadS OccCKT

readList :: ReadS [OccCKT]

readPrec :: ReadPrec OccCKT

readListPrec :: ReadPrec [OccCKT]

Show OccCKT

Defined in Data.FMIndex.Internal

Methods

showsPrec :: Int -> OccCKT -> ShowS

show :: OccCKT -> String

showList :: [OccCKT] -> ShowS

Eq OccCKT

Defined in Data.FMIndex.Internal

Methods

(==) :: OccCKT -> OccCKT -> Bool

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

Ord OccCKT

Defined in Data.FMIndex.Internal

Methods

compare :: OccCKT -> OccCKT -> Ordering

(<) :: OccCKT -> OccCKT -> Bool

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

(>) :: OccCKT -> OccCKT -> Bool

(>=) :: OccCKT -> OccCKT -> Bool

max :: OccCKT -> OccCKT -> OccCKT

min :: OccCKT -> OccCKT -> OccCKT

type Rep OccCKT

Defined in Data.FMIndex.Internal

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

newtype CcB

Basic C[c] table (ByteString) data type.

Constructors

CcB (Seq (Int, Maybe ByteString))

Instances

Generic CcB

Defined in Data.FMIndex.Internal

Associated Types

type Rep CcB :: Type -> Type

Methods

from :: CcB -> Rep CcB x

to :: Rep CcB x -> CcB

Read CcB

Defined in Data.FMIndex.Internal

Methods

readsPrec :: Int -> ReadS CcB

readList :: ReadS [CcB]

readPrec :: ReadPrec CcB

readListPrec :: ReadPrec [CcB]

Show CcB

Defined in Data.FMIndex.Internal

Methods

showsPrec :: Int -> CcB -> ShowS

show :: CcB -> String

showList :: [CcB] -> ShowS

Eq CcB

Defined in Data.FMIndex.Internal

Methods

(==) :: CcB -> CcB -> Bool

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

Ord CcB

Defined in Data.FMIndex.Internal

Methods

compare :: CcB -> CcB -> Ordering

(<) :: CcB -> CcB -> Bool

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

(>) :: CcB -> CcB -> Bool

(>=) :: CcB -> CcB -> Bool

max :: CcB -> CcB -> CcB

min :: CcB -> CcB -> CcB

type Rep CcB

Defined in Data.FMIndex.Internal

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

newtype CcT

Basic C[c] table (Text) data type.

Constructors

CcT (Seq (Int, Maybe Text))

Instances

Generic CcT

Defined in Data.FMIndex.Internal

Associated Types

type Rep CcT :: Type -> Type

Methods

from :: CcT -> Rep CcT x

to :: Rep CcT x -> CcT

Read CcT

Defined in Data.FMIndex.Internal

Methods

readsPrec :: Int -> ReadS CcT

readList :: ReadS [CcT]

readPrec :: ReadPrec CcT

readListPrec :: ReadPrec [CcT]

Show CcT

Defined in Data.FMIndex.Internal

Methods

showsPrec :: Int -> CcT -> ShowS

show :: CcT -> String

showList :: [CcT] -> ShowS

Eq CcT

Defined in Data.FMIndex.Internal

Methods

(==) :: CcT -> CcT -> Bool

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

Ord CcT

Defined in Data.FMIndex.Internal

Methods

compare :: CcT -> CcT -> Ordering

(<) :: CcT -> CcT -> Bool

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

(>) :: CcT -> CcT -> Bool

(>=) :: CcT -> CcT -> Bool

max :: CcT -> CcT -> CcT

min :: CcT -> CcT -> CcT

type Rep CcT

Defined in Data.FMIndex.Internal

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

type PBOccCKSeqB = Seq (Maybe ByteString)

Abstract PBOccCKSeqB type utilizing a Seq.

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

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

type STOccCKSeqB s a = STRef s OccCKSeqB

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

updateSTOccCKSeqAB :: STOccCKSeqB s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))) -> (Int, Int, Maybe ByteString) -> ST s ()

State function to update OccCKSeqB with each step of the OccCK.

updateSTOccCKSeqBB :: STOccCKSeqB s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))) -> Maybe ByteString -> ST s ()

State function to update OccCKSeqB with each step of the OccCK.

emptySTOccCKSeqB :: ST s (STOccCKSeqB s a)

State function to create empty STOccCKSeqB type.

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

Abstract STOccCKILB and associated state type.

loadSTOccCKILB :: STOccCKILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()

State function to load list into STOccCKILB.

emptySTOccCKILB :: ST s (STOccCKILB s a)

State function to create empty STOccCKILB type.

type STOccCKCounterB s a = STRef s Int

Abstract STOccCKCounterB and associated state type.

updateSTOccCKCounterB :: STOccCKCounterB s Int -> Int -> ST s ()

State function to update STOccCKCounterB.

emptySTOccCKCounterB :: ST s (STOccCKCounterB s Int)

State function to create empty STOccCKCounterB type.

seqToOccCKB :: PBOccCKSeqB -> ST s OccCKSeqB

Strict state monad function.

type PTOccCKSeqT = Seq (Maybe Text)

Abstract PTOccCKSeqT type utilizing a Seq.

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

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

type STOccCKSeqT s a = STRef s OccCKSeqT

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

updateSTOccCKSeqAT :: STOccCKSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))) -> (Int, Int, Maybe Text) -> ST s ()

State function to update OccCKSeqT with each step of the OccCK.

updateSTOccCKSeqBT :: STOccCKSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))) -> Maybe Text -> ST s ()

State function to update OccCKSeqT with each step of the OccCK.

emptySTOccCKSeqT :: ST s (STOccCKSeqT s a)

State function to create empty STOccCKSeqT type.

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

Abstract STOccCKILT and associated state type.

loadSTOccCKILT :: STOccCKILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()

State function to load list into STOccCKILT.

emptySTOccCKILT :: ST s (STOccCKILT s a)

State function to create empty STOccCKILT type.

type STOccCKCounterT s a = STRef s Int

Abstract STOccCKCounterT and associated state type.

updateSTOccCKCounterT :: STOccCKCounterT s Int -> Int -> ST s ()

State function to update STOccCKCounterT.

emptySTOccCKCounterT :: ST s (STOccCKCounterT s Int)

State function to create empty STOccCKCounterT type.

seqToOccCKT :: PTOccCKSeqT -> ST s OccCKSeqT

Strict state monad function.

type PBCcSeqB = Seq (Maybe ByteString)

Abstract PBCcSeqB type utilizing a Seq.

type CcSeqB = Seq (Int, Maybe ByteString)

Abstract CcSeqB type utilizing a Seq. (C[c],c)

type STCcSeqB s a = STRef s CcSeqB

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

updateSTCcSeqB :: STCcSeqB s (Seq (Int, Maybe ByteString)) -> (Int, Maybe ByteString) -> ST s ()

State function to update CcSeqB with each step of the C[c].

emptySTCcSeqB :: ST s (STCcSeqB s a)

State function to create empty STCcSeqT type.

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

Abstract STCcILB and associated state type.

loadSTCcILB :: STCcILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()

State function to load list into STCcILB.

emptySTCcILB :: ST s (STCcILB s a)

State function to create empty STCcILB type.

type STCcCounterB s a = STRef s Int

Abstract STCcCounterB and associated state type.

updateSTCcCounterB :: STCcCounterB s Int -> Int -> ST s ()

State function to update STCcCounterB.

emptySTCcCounterB :: ST s (STCcCounterB s Int)

State function to create empty STCcCounterT type.

seqToCcB :: PBCcSeqB -> ST s CcSeqB

Strict state monad function.

type PTCcSeqT = Seq (Maybe Text)

Abstract PTCcSeqT type utilizing a Seq.

type CcSeqT = Seq (Int, Maybe Text)

Abstract CcSeqT type utilizing a Seq. (C[c],c)

type STCcSeqT s a = STRef s CcSeqT

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

updateSTCcSeqT :: STCcSeqT s (Seq (Int, Maybe Text)) -> (Int, Maybe Text) -> ST s ()

State function to update CcSeqT with each step of the C[c].

emptySTCcSeqT :: ST s (STCcSeqT s a)

State function to create empty STCcSeqT type.

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

Abstract STCcILT and associated state type.

loadSTCcILT :: STCcILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()

State function to load list into STCcILT.

emptySTCcILT :: ST s (STCcILT s a)

State function to create empty STCcILT type.

type STCcCounterT s a = STRef s Int

Abstract STCcCounterT and associated state type.

updateSTCcCounterT :: STCcCounterT s Int -> Int -> ST s ()

State function to update STCcCounterT.

emptySTCcCounterT :: ST s (STCcCounterT s Int)

State function to create empty STCcCounterT type.

seqToCcT :: PTCcSeqT -> ST s CcSeqT

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.