Copyright	(c) Matthew Mosior 2022
License	BSD-style
Maintainer	mattm.github@gmail.com
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.FMIndex.Internal

Contents

Base FM-index types
To OccCK (ByteString) functions
To OccCK (Text) functions
Cc (ByteString) functions
Cc (Text) functions
From FMIndex (ByteString) functions
From FMIndex (Text) functions
Count (ByteString) operation
Count (Text) operation
Locate (ByteString) operation
Locate (Text) operation

Description

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 library, 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

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

Keep in mind that the $ is translated into a Nothing.

Synopsis

newtype FMIndexB = FMIndexB (CcB, OccCKB, SAB)
newtype FMIndexT = FMIndexT (CcT, OccCKT, SAT)
newtype OccCKB = OccCKB (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
newtype OccCKT = OccCKT (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
newtype CcB = CcB (Seq (Int, Maybe ByteString))
newtype CcT = CcT (Seq (Int, Maybe Text))
newtype CB = CB (Maybe Int)
newtype CT = CT (Maybe Int)
newtype SAB = SAB (SuffixArray ByteString)
newtype SAT = SAT (SuffixArray Text)
type PBOccCKSeqB = Seq (Maybe ByteString)
type OccCKSeqB = Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
type STOccCKSeqB s a = STRef s OccCKSeqB
updateSTOccCKSeqAB :: STOccCKSeqB s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))) -> (Int, Int, Maybe ByteString) -> ST s ()
updateSTOccCKSeqBB :: STOccCKSeqB s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))) -> Maybe ByteString -> ST s ()
emptySTOccCKSeqB :: ST s (STOccCKSeqB s a)
type STOccCKILB s a = STRef s (Seq (Maybe ByteString))
loadSTOccCKILB :: STOccCKILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()
emptySTOccCKILB :: ST s (STOccCKILB s a)
type STOccCKCounterB s a = STRef s Int
updateSTOccCKCounterB :: STOccCKCounterB s Int -> Int -> ST s ()
emptySTOccCKCounterB :: ST s (STOccCKCounterB s Int)
seqToOccCKB :: PBOccCKSeqB -> ST s OccCKSeqB
type PTOccCKSeqT = Seq (Maybe Text)
type OccCKSeqT = Seq (Maybe Text, Seq (Int, Int, Maybe Text))
type STOccCKSeqT s a = STRef s OccCKSeqT
updateSTOccCKSeqAT :: STOccCKSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))) -> (Int, Int, Maybe Text) -> ST s ()
updateSTOccCKSeqBT :: STOccCKSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))) -> Maybe Text -> ST s ()
emptySTOccCKSeqT :: ST s (STOccCKSeqT s a)
type STOccCKILT s a = STRef s (Seq (Maybe Text))
loadSTOccCKILT :: STOccCKILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()
emptySTOccCKILT :: ST s (STOccCKILT s a)
type STOccCKCounterT s a = STRef s Int
updateSTOccCKCounterT :: STOccCKCounterT s Int -> Int -> ST s ()
emptySTOccCKCounterT :: ST s (STOccCKCounterT s Int)
seqToOccCKT :: PTOccCKSeqT -> ST s OccCKSeqT
type PBCcSeqB = Seq (Maybe ByteString)
type CcSeqB = Seq (Int, Maybe ByteString)
type STCcSeqB s a = STRef s CcSeqB
updateSTCcSeqB :: STCcSeqB s (Seq (Int, Maybe ByteString)) -> (Int, Maybe ByteString) -> ST s ()
emptySTCcSeqB :: ST s (STCcSeqB s a)
type STCcILB s a = STRef s (Seq (Maybe ByteString))
loadSTCcILB :: STCcILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()
emptySTCcILB :: ST s (STCcILB s a)
type STCcCounterB s a = STRef s Int
updateSTCcCounterB :: STCcCounterB s Int -> Int -> ST s ()
emptySTCcCounterB :: ST s (STCcCounterB s Int)
seqToCcB :: PBCcSeqB -> ST s CcSeqB
type PTCcSeqT = Seq (Maybe Text)
type CcSeqT = Seq (Int, Maybe Text)
type STCcSeqT s a = STRef s CcSeqT
updateSTCcSeqT :: STCcSeqT s (Seq (Int, Maybe Text)) -> (Int, Maybe Text) -> ST s ()
emptySTCcSeqT :: ST s (STCcSeqT s a)
type STCcILT s a = STRef s (Seq (Maybe Text))
loadSTCcILT :: STCcILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()
emptySTCcILT :: ST s (STCcILT s a)
type STCcCounterT s a = STRef s Int
updateSTCcCounterT :: STCcCounterT s Int -> Int -> ST s ()
emptySTCcCounterT :: ST s (STCcCounterT s Int)
seqToCcT :: PTCcSeqT -> ST s CcSeqT
type FFMIndexSeqB = Seq (Maybe ByteString)
seqFromFMIndexB :: FMIndexB -> FFMIndexSeqB
type FFMIndexSeqT = Seq (Maybe Text)
seqFromFMIndexT :: FMIndexT -> FFMIndexSeqT
type PBCPat = Seq ByteString
type CIntB = Maybe Int
type STCBoolB s a = STRef s Bool
updateSTCBoolB :: STCBoolB s Bool -> Bool -> ST s ()
emptySTCBoolB :: ST s (STCBoolB s Bool)
type STCCounterB s a = STRef s Int
updateSTCCounterB :: STCCounterB s Int -> Int -> ST s ()
emptySTCCounterB :: ST s (STCCounterB s Int)
type STCCurrentStartB s a = STRef s Int
updateSTCCurrentStartB :: STCCurrentStartB s Int -> Int -> ST s ()
emptySTCCurrentStartB :: ST s (STCCurrentStartB s Int)
type STCCurrentEndB s a = STRef s Int
updateSTCCurrentEndB :: STCCurrentEndB s Int -> Int -> ST s ()
emptySTCCurrentEndB :: ST s (STCCurrentEndB s Int)
countFMIndexB :: PBCPat -> FMIndexB -> ST s CIntB
type PTCPat = Seq Text
type CIntT = Maybe Int
type STCBoolT s a = STRef s Bool
updateSTCBoolT :: STCBoolT s Bool -> Bool -> ST s ()
emptySTCBoolT :: ST s (STCBoolT s Bool)
type STCCounterT s a = STRef s Int
updateSTCCounterT :: STCCounterT s Int -> Int -> ST s ()
emptySTCCounterT :: ST s (STCCounterT s Int)
type STCCurrentStartT s a = STRef s Int
updateSTCCurrentStartT :: STCCurrentStartT s Int -> Int -> ST s ()
emptySTCCurrentStartT :: ST s (STCCurrentStartT s Int)
type STCCurrentEndT s a = STRef s Int
updateSTCCurrentEndT :: STCCurrentEndT s Int -> Int -> ST s ()
emptySTCCurrentEndT :: ST s (STCCurrentEndT s Int)
countFMIndexT :: PTCPat -> FMIndexT -> ST s CIntT
type PBLPat = Seq ByteString
type LIntB = Seq (Maybe Int)
type STLBoolB s a = STRef s Bool
updateSTLBoolB :: STLBoolB s Bool -> Bool -> ST s ()
emptySTLBoolB :: ST s (STLBoolB s Bool)
type STLCounterB s a = STRef s Int
updateSTLCounterB :: STLCounterB s Int -> Int -> ST s ()
emptySTLCounterB :: ST s (STLCounterB s Int)
type STLCurrentStartB s a = STRef s Int
updateSTLCurrentStartB :: STLCurrentStartB s Int -> Int -> ST s ()
emptySTLCurrentStartB :: ST s (STLCurrentStartB s Int)
type STLCurrentEndB s a = STRef s Int
updateSTLCurrentEndB :: STLCurrentEndB s Int -> Int -> ST s ()
emptySTLCurrentEndB :: ST s (STCCurrentEndB s Int)
locateFMIndexB :: PBLPat -> FMIndexB -> ST s LIntB
type PTLPat = Seq Text
type LIntT = Seq (Maybe Int)
type STLBoolT s a = STRef s Bool
updateSTLBoolT :: STLBoolT s Bool -> Bool -> ST s ()
emptySTLBoolT :: ST s (STLBoolT s Bool)
type STLCounterT s a = STRef s Int
updateSTLCounterT :: STLCounterT s Int -> Int -> ST s ()
emptySTLCounterT :: ST s (STLCounterT s Int)
type STLCurrentStartT s a = STRef s Int
updateSTLCurrentStartT :: STLCurrentStartT s Int -> Int -> ST s ()
emptySTLCurrentStartT :: ST s (STLCurrentStartT s Int)
type STLCurrentEndT s a = STRef s Int
updateSTLCurrentEndT :: STLCurrentEndT s Int -> Int -> ST s ()
emptySTLCurrentEndT :: ST s (STLCurrentEndT s Int)
locateFMIndexT :: PTLPat -> FMIndexT -> ST s LIntT

Base FM-index types

newtype FMIndexB Source #

Basic FMIndex (ByteString) data type.

Constructors

FMIndexB (CcB, OccCKB, SAB)

Instances

Instances details

Generic FMIndexB Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS FMIndexB # readList :: ReadS [FMIndexB] # readPrec :: ReadPrec FMIndexB # readListPrec :: ReadPrec [FMIndexB] #
Show FMIndexB Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> FMIndexB -> ShowS # show :: FMIndexB -> String # showList :: [FMIndexB] -> ShowS #
Eq FMIndexB Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: FMIndexB -> FMIndexB -> Bool # (/=) :: FMIndexB -> FMIndexB -> Bool #
Ord FMIndexB Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal type Rep FMIndexB = D1 ('MetaData "FMIndexB" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "FMIndexB" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (CcB, OccCKB, SAB))))

newtype FMIndexT Source #

Basic FMIndex (Text) data type.

Constructors

FMIndexT (CcT, OccCKT, SAT)

Instances

Instances details

Generic FMIndexT Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS FMIndexT # readList :: ReadS [FMIndexT] # readPrec :: ReadPrec FMIndexT # readListPrec :: ReadPrec [FMIndexT] #
Show FMIndexT Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> FMIndexT -> ShowS # show :: FMIndexT -> String # showList :: [FMIndexT] -> ShowS #
Eq FMIndexT Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: FMIndexT -> FMIndexT -> Bool # (/=) :: FMIndexT -> FMIndexT -> Bool #
Ord FMIndexT Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal type Rep FMIndexT = D1 ('MetaData "FMIndexT" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "FMIndexT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (CcT, OccCKT, SAT))))

newtype OccCKB Source #

Basic OccCKB (ByteString) data type.

Constructors

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

Instances

Instances details

Generic OccCKB Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS OccCKB # readList :: ReadS [OccCKB] # readPrec :: ReadPrec OccCKB # readListPrec :: ReadPrec [OccCKB] #
Show OccCKB Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> OccCKB -> ShowS # show :: OccCKB -> String # showList :: [OccCKB] -> ShowS #
Eq OccCKB Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: OccCKB -> OccCKB -> Bool # (/=) :: OccCKB -> OccCKB -> Bool #
Ord OccCKB Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal type Rep OccCKB = D1 ('MetaData "OccCKB" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" '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 Source #

Basic OccCKT (Text) data type.

Constructors

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

Instances

Instances details

Generic OccCKT Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS OccCKT # readList :: ReadS [OccCKT] # readPrec :: ReadPrec OccCKT # readListPrec :: ReadPrec [OccCKT] #
Show OccCKT Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> OccCKT -> ShowS # show :: OccCKT -> String # showList :: [OccCKT] -> ShowS #
Eq OccCKT Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: OccCKT -> OccCKT -> Bool # (/=) :: OccCKT -> OccCKT -> Bool #
Ord OccCKT Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal type Rep OccCKT = D1 ('MetaData "OccCKT" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" '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 Source #

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

Constructors

CcB (Seq (Int, Maybe ByteString))

Instances

Instances details

Generic CcB Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS CcB # readList :: ReadS [CcB] # readPrec :: ReadPrec CcB # readListPrec :: ReadPrec [CcB] #
Show CcB Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> CcB -> ShowS # show :: CcB -> String # showList :: [CcB] -> ShowS #
Eq CcB Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: CcB -> CcB -> Bool # (/=) :: CcB -> CcB -> Bool #
Ord CcB Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal type Rep CcB = D1 ('MetaData "CcB" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "CcB" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Seq (Int, Maybe ByteString)))))

newtype CcT Source #

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

Constructors

CcT (Seq (Int, Maybe Text))

Instances

Instances details

Generic CcT Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS CcT # readList :: ReadS [CcT] # readPrec :: ReadPrec CcT # readListPrec :: ReadPrec [CcT] #
Show CcT Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> CcT -> ShowS # show :: CcT -> String # showList :: [CcT] -> ShowS #
Eq CcT Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: CcT -> CcT -> Bool # (/=) :: CcT -> CcT -> Bool #
Ord CcT Source #
Instance details 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 Source #
Instance details Defined in Data.FMIndex.Internal type Rep CcT = D1 ('MetaData "CcT" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "CcT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Seq (Int, Maybe Text)))))

newtype CB Source #

Basic count (ByteString) operation data type.

Constructors

CB (Maybe Int)

Instances

Instances details

Generic CB Source #
Instance details Defined in Data.FMIndex.Internal Associated Types type Rep CB :: Type -> Type # Methods from :: CB -> Rep CB x # to :: Rep CB x -> CB #
Read CB Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS CB # readList :: ReadS [CB] # readPrec :: ReadPrec CB # readListPrec :: ReadPrec [CB] #
Show CB Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> CB -> ShowS # show :: CB -> String # showList :: [CB] -> ShowS #
Eq CB Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: CB -> CB -> Bool # (/=) :: CB -> CB -> Bool #
Ord CB Source #
Instance details Defined in Data.FMIndex.Internal Methods compare :: CB -> CB -> Ordering # (<) :: CB -> CB -> Bool # (<=) :: CB -> CB -> Bool # (>) :: CB -> CB -> Bool # (>=) :: CB -> CB -> Bool # max :: CB -> CB -> CB # min :: CB -> CB -> CB #
type Rep CB Source #
Instance details Defined in Data.FMIndex.Internal type Rep CB = D1 ('MetaData "CB" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "CB" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Maybe Int))))

newtype CT Source #

Basic count (Text) operation data type.

Constructors

CT (Maybe Int)

Instances

Instances details

Generic CT Source #
Instance details Defined in Data.FMIndex.Internal Associated Types type Rep CT :: Type -> Type # Methods from :: CT -> Rep CT x # to :: Rep CT x -> CT #
Read CT Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS CT # readList :: ReadS [CT] # readPrec :: ReadPrec CT # readListPrec :: ReadPrec [CT] #
Show CT Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> CT -> ShowS # show :: CT -> String # showList :: [CT] -> ShowS #
Eq CT Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: CT -> CT -> Bool # (/=) :: CT -> CT -> Bool #
Ord CT Source #
Instance details Defined in Data.FMIndex.Internal Methods compare :: CT -> CT -> Ordering # (<) :: CT -> CT -> Bool # (<=) :: CT -> CT -> Bool # (>) :: CT -> CT -> Bool # (>=) :: CT -> CT -> Bool # max :: CT -> CT -> CT # min :: CT -> CT -> CT #
type Rep CT Source #
Instance details Defined in Data.FMIndex.Internal type Rep CT = D1 ('MetaData "CT" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "CT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Maybe Int))))

newtype SAB Source #

Basic SuffixArray (ByteString) data type.

Constructors

SAB (SuffixArray ByteString)

Instances

Instances details

Generic SAB Source #
Instance details Defined in Data.FMIndex.Internal Associated Types type Rep SAB :: Type -> Type # Methods from :: SAB -> Rep SAB x # to :: Rep SAB x -> SAB #
Read SAB Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS SAB # readList :: ReadS [SAB] # readPrec :: ReadPrec SAB # readListPrec :: ReadPrec [SAB] #
Show SAB Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> SAB -> ShowS # show :: SAB -> String # showList :: [SAB] -> ShowS #
Eq SAB Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: SAB -> SAB -> Bool # (/=) :: SAB -> SAB -> Bool #
Ord SAB Source #
Instance details Defined in Data.FMIndex.Internal Methods compare :: SAB -> SAB -> Ordering # (<) :: SAB -> SAB -> Bool # (<=) :: SAB -> SAB -> Bool # (>) :: SAB -> SAB -> Bool # (>=) :: SAB -> SAB -> Bool # max :: SAB -> SAB -> SAB # min :: SAB -> SAB -> SAB #
type Rep SAB Source #
Instance details Defined in Data.FMIndex.Internal type Rep SAB = D1 ('MetaData "SAB" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "SAB" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (SuffixArray ByteString))))

newtype SAT Source #

Basic SuffixArray (Text) data type.

Constructors

SAT (SuffixArray Text)

Instances

Instances details

Generic SAT Source #
Instance details Defined in Data.FMIndex.Internal Associated Types type Rep SAT :: Type -> Type # Methods from :: SAT -> Rep SAT x # to :: Rep SAT x -> SAT #
Read SAT Source #
Instance details Defined in Data.FMIndex.Internal Methods readsPrec :: Int -> ReadS SAT # readList :: ReadS [SAT] # readPrec :: ReadPrec SAT # readListPrec :: ReadPrec [SAT] #
Show SAT Source #
Instance details Defined in Data.FMIndex.Internal Methods showsPrec :: Int -> SAT -> ShowS # show :: SAT -> String # showList :: [SAT] -> ShowS #
Eq SAT Source #
Instance details Defined in Data.FMIndex.Internal Methods (==) :: SAT -> SAT -> Bool # (/=) :: SAT -> SAT -> Bool #
Ord SAT Source #
Instance details Defined in Data.FMIndex.Internal Methods compare :: SAT -> SAT -> Ordering # (<) :: SAT -> SAT -> Bool # (<=) :: SAT -> SAT -> Bool # (>) :: SAT -> SAT -> Bool # (>=) :: SAT -> SAT -> Bool # max :: SAT -> SAT -> SAT # min :: SAT -> SAT -> SAT #
type Rep SAT Source #
Instance details Defined in Data.FMIndex.Internal type Rep SAT = D1 ('MetaData "SAT" "Data.FMIndex.Internal" "text-compression-0.1.0.25-K28PrKXhRjY68F48yTv8pv" 'True) (C1 ('MetaCons "SAT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (SuffixArray Text))))

To OccCK (ByteString) functions

type PBOccCKSeqB = Seq (Maybe ByteString) Source #

Abstract PBOccCKSeqB type utilizing a Seq.

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

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

type STOccCKSeqB s a = STRef s OccCKSeqB Source #

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 () Source #

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 () Source #

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

emptySTOccCKSeqB :: ST s (STOccCKSeqB s a) Source #

State function to create empty STOccCKSeqB type.

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

Abstract STOccCKILB and associated state type.

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

State function to load list into STOccCKILB.

emptySTOccCKILB :: ST s (STOccCKILB s a) Source #

State function to create empty STOccCKILB type.

type STOccCKCounterB s a = STRef s Int Source #

Abstract STOccCKCounterB and associated state type.

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

State function to update STOccCKCounterB.

emptySTOccCKCounterB :: ST s (STOccCKCounterB s Int) Source #

State function to create empty STOccCKCounterB type.

seqToOccCKB :: PBOccCKSeqB -> ST s OccCKSeqB Source #

Strict state monad function.

To OccCK (Text) functions

type PTOccCKSeqT = Seq (Maybe Text) Source #

Abstract PTOccCKSeqT type utilizing a Seq.

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

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

type STOccCKSeqT s a = STRef s OccCKSeqT Source #

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 () Source #

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 () Source #

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

emptySTOccCKSeqT :: ST s (STOccCKSeqT s a) Source #

State function to create empty STOccCKSeqT type.

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

Abstract STOccCKILT and associated state type.

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

State function to load list into STOccCKILT.

emptySTOccCKILT :: ST s (STOccCKILT s a) Source #

State function to create empty STOccCKILT type.

type STOccCKCounterT s a = STRef s Int Source #

Abstract STOccCKCounterT and associated state type.

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

State function to update STOccCKCounterT.

emptySTOccCKCounterT :: ST s (STOccCKCounterT s Int) Source #

State function to create empty STOccCKCounterT type.

seqToOccCKT :: PTOccCKSeqT -> ST s OccCKSeqT Source #

Strict state monad function.

Cc (ByteString) functions

type PBCcSeqB = Seq (Maybe ByteString) Source #

Abstract PBCcSeqB type utilizing a Seq.

type CcSeqB = Seq (Int, Maybe ByteString) Source #

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

type STCcSeqB s a = STRef s CcSeqB Source #

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

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

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

emptySTCcSeqB :: ST s (STCcSeqB s a) Source #

State function to create empty STCcSeqT type.

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

Abstract STCcILB and associated state type.

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

State function to load list into STCcILB.

emptySTCcILB :: ST s (STCcILB s a) Source #

State function to create empty STCcILB type.

type STCcCounterB s a = STRef s Int Source #

Abstract STCcCounterB and associated state type.

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

State function to update STCcCounterB.

emptySTCcCounterB :: ST s (STCcCounterB s Int) Source #

State function to create empty STCcCounterT type.

seqToCcB :: PBCcSeqB -> ST s CcSeqB Source #

Strict state monad function.

Cc (Text) functions

type PTCcSeqT = Seq (Maybe Text) Source #

Abstract PTCcSeqT type utilizing a Seq.

type CcSeqT = Seq (Int, Maybe Text) Source #

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

type STCcSeqT s a = STRef s CcSeqT Source #

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

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

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

emptySTCcSeqT :: ST s (STCcSeqT s a) Source #

State function to create empty STCcSeqT type.

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

Abstract STCcILT and associated state type.

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

State function to load list into STCcILT.

emptySTCcILT :: ST s (STCcILT s a) Source #

State function to create empty STCcILT type.

type STCcCounterT s a = STRef s Int Source #

Abstract STCcCounterT and associated state type.

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

State function to update STCcCounterT.

emptySTCcCounterT :: ST s (STCcCounterT s Int) Source #

State function to create empty STCcCounterT type.

seqToCcT :: PTCcSeqT -> ST s CcSeqT Source #

Strict state monad function.

From FMIndex (ByteString) functions

type FFMIndexSeqB = Seq (Maybe ByteString) Source #

Abstract FFMIndexSeqB type utilizing a Seq.

seqFromFMIndexB :: FMIndexB -> FFMIndexSeqB Source #

Simple Inverse FMIndex function.

From FMIndex (Text) functions

type FFMIndexSeqT = Seq (Maybe Text) Source #

Abstract FFMIndexSeqT type utilizing a Seq.

seqFromFMIndexT :: FMIndexT -> FFMIndexSeqT Source #

Simple Inverse FMIndex function.

Count (ByteString) operation

type PBCPat = Seq ByteString Source #

Abstract PBCPat type utilizing a Seq.

type CIntB = Maybe Int Source #

Abstract CIntB type utilizing an Int.

type STCBoolB s a = STRef s Bool Source #

Abstract STCBoolB type utilizing a Bool.

updateSTCBoolB :: STCBoolB s Bool -> Bool -> ST s () Source #

State function to update STCBoolB in the (strict) ST monad.

emptySTCBoolB :: ST s (STCBoolB s Bool) Source #

State function to create empty STCBoolB type.

type STCCounterB s a = STRef s Int Source #

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

updateSTCCounterB :: STCCounterB s Int -> Int -> ST s () Source #

State function to update STCCounterB

emptySTCCounterB :: ST s (STCCounterB s Int) Source #

State function to create empty STCCounterB type.

type STCCurrentStartB s a = STRef s Int Source #

Abstract STCCurrentStartB type utilizing a Seq.

updateSTCCurrentStartB :: STCCurrentStartB s Int -> Int -> ST s () Source #

State function to update STCCurrentStartB.

emptySTCCurrentStartB :: ST s (STCCurrentStartB s Int) Source #

State function to create empty STCCurrentStartB type.

type STCCurrentEndB s a = STRef s Int Source #

Abstract STCCurrentEndB type utilizing a Seq.

updateSTCCurrentEndB :: STCCurrentEndB s Int -> Int -> ST s () Source #

State function to update STCCurrentEndB.

emptySTCCurrentEndB :: ST s (STCCurrentEndB s Int) Source #

State function to create empty STCCurrentEndB type.

countFMIndexB :: PBCPat -> FMIndexB -> ST s CIntB Source #

Count operation on a FMIndexB. This operation takes a pattern (Seq ByteString) and returns the number of occurences of that pattern in the original text T credit.

Count (Text) operation

type PTCPat = Seq Text Source #

Abstract PTCPat type utilizing a Seq.

type CIntT = Maybe Int Source #

Abstract CIntT type utilizing an Int.

type STCBoolT s a = STRef s Bool Source #

Abstract STCBoolT type utilizing a Bool.

updateSTCBoolT :: STCBoolT s Bool -> Bool -> ST s () Source #

State function to update STCBoolT in the (strict) ST monad.

emptySTCBoolT :: ST s (STCBoolT s Bool) Source #

State function to create empty STCBoolT type.

type STCCounterT s a = STRef s Int Source #

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

updateSTCCounterT :: STCCounterT s Int -> Int -> ST s () Source #

State function to update STCCounterT

emptySTCCounterT :: ST s (STCCounterT s Int) Source #

State function to create empty STCCounterT type.

type STCCurrentStartT s a = STRef s Int Source #

Abstract STCCurrentStartT type utilizing a Seq.

updateSTCCurrentStartT :: STCCurrentStartT s Int -> Int -> ST s () Source #

State function to update STCCurrentStartT.

emptySTCCurrentStartT :: ST s (STCCurrentStartT s Int) Source #

State function to create empty STCCurrentStartT type.

type STCCurrentEndT s a = STRef s Int Source #

Abstract STCCurrentEndT type utilizing a Seq.

updateSTCCurrentEndT :: STCCurrentEndT s Int -> Int -> ST s () Source #

State function to update STCCurrentEndT.

emptySTCCurrentEndT :: ST s (STCCurrentEndT s Int) Source #

State function to create empty STCCurrentEndT type.

countFMIndexT :: PTCPat -> FMIndexT -> ST s CIntT Source #

Count operation on a FMIndexT. This operation takes a pattern (Seq Text) and returns the number of occurences of that pattern in the original text T credit.

Locate (ByteString) operation

type PBLPat = Seq ByteString Source #

Abstract PBLPat type utilizing a Seq.

type LIntB = Seq (Maybe Int) Source #

Abstract LIntB type utilizing an Int.

type STLBoolB s a = STRef s Bool Source #

Abstract STLBoolB type utilizing a Bool.

updateSTLBoolB :: STLBoolB s Bool -> Bool -> ST s () Source #

State function to update STLBoolB in the (strict) ST monad.

emptySTLBoolB :: ST s (STLBoolB s Bool) Source #

State function to create empty STLBoolB type.

type STLCounterB s a = STRef s Int Source #

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

updateSTLCounterB :: STLCounterB s Int -> Int -> ST s () Source #

State function to update STLCounterB

emptySTLCounterB :: ST s (STLCounterB s Int) Source #

State function to create empty STLCounterB type.

type STLCurrentStartB s a = STRef s Int Source #

Abstract STLCurrentStartB type utilizing a Seq.

updateSTLCurrentStartB :: STLCurrentStartB s Int -> Int -> ST s () Source #

State function to update STLCurrentStartB.

emptySTLCurrentStartB :: ST s (STLCurrentStartB s Int) Source #

State function to create empty STLCurrentStartB type.

type STLCurrentEndB s a = STRef s Int Source #

Abstract STLCurrentEndB type utilizing a Seq.

updateSTLCurrentEndB :: STLCurrentEndB s Int -> Int -> ST s () Source #

State function to update STLCurrentEndB.

emptySTLCurrentEndB :: ST s (STCCurrentEndB s Int) Source #

State function to create empty STLCurrentEndB type.

locateFMIndexB :: PBLPat -> FMIndexB -> ST s LIntB Source #

Locate operation on a FMIndexB. This operation takes a pattern (Seq ByteString) and returns the indexe(s) of occurences of that pattern in the original text T credit.

Locate (Text) operation

type PTLPat = Seq Text Source #

Abstract PTLPat type utilizing a Seq.

type LIntT = Seq (Maybe Int) Source #

Abstract LIntT type utilizing an Int.

type STLBoolT s a = STRef s Bool Source #

Abstract STLBoolT type utilizing a Bool.

updateSTLBoolT :: STLBoolT s Bool -> Bool -> ST s () Source #

State function to update STLBoolT in the (strict) ST monad.

emptySTLBoolT :: ST s (STLBoolT s Bool) Source #

State function to create empty STLBoolT type.

type STLCounterT s a = STRef s Int Source #

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

updateSTLCounterT :: STLCounterT s Int -> Int -> ST s () Source #

State function to update STLCounterT

emptySTLCounterT :: ST s (STLCounterT s Int) Source #

State function to create empty STLCounterT type.

type STLCurrentStartT s a = STRef s Int Source #

Abstract STLCurrentStartT type utilizing a Seq.

updateSTLCurrentStartT :: STLCurrentStartT s Int -> Int -> ST s () Source #

State function to update STLCurrentStartT.

emptySTLCurrentStartT :: ST s (STLCurrentStartT s Int) Source #

State function to create empty STLCurrentStartT type.

type STLCurrentEndT s a = STRef s Int Source #

Abstract STLCurrentEndT type utilizing a Seq.

updateSTLCurrentEndT :: STLCurrentEndT s Int -> Int -> ST s () Source #

State function to update STLCurrentEndT.

emptySTLCurrentEndT :: ST s (STLCurrentEndT s Int) Source #

State function to create empty STLCurrentEndT type.

locateFMIndexT :: PTLPat -> FMIndexT -> ST s LIntT Source #

Locate operation on a FMIndexT. This operation takes a pattern (Seq Text) and returns the indexe(s) of occurences of that pattern in the original text T credit.

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

	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

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

	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

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

	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