{-# LANGUAGE TupleSections #-}
{-# LANGUAGE LambdaCase #-}

module Boolean2TMHelpers where

import GrammarType
import DebuggingTMTypes
import qualified Data.Set as Set
import qualified Data.Map as Map
import Data.List
import Data.Ord
import Data.Maybe

calculateMaxNumberOfRulesForNonterminal :: Grammar -> Int
calculateMaxNumberOfRulesForNonterminal :: Grammar -> Int
calculateMaxNumberOfRulesForNonterminal (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_)) = let
    listRelations :: [Relation]
listRelations = Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations
    groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals [Relation]
listRelations
    in ((Nonterminal, Int) -> Int
forall a b. (a, b) -> b
snd ((Nonterminal, Int) -> Int) -> (Nonterminal, Int) -> Int
forall a b. (a -> b) -> a -> b
$ ((Nonterminal, Int) -> (Nonterminal, Int) -> Ordering)
-> [(Nonterminal, Int)] -> (Nonterminal, Int)
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
maximumBy (((Nonterminal, Int) -> Int)
-> (Nonterminal, Int) -> (Nonterminal, Int) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (Nonterminal, Int) -> Int
forall a b. (a, b) -> b
snd) (Map Nonterminal Int -> [(Nonterminal, Int)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map Nonterminal Int -> [(Nonterminal, Int)])
-> Map Nonterminal Int -> [(Nonterminal, Int)]
forall a b. (a -> b) -> a -> b
$ ([[Conj]] -> Int)
-> Map Nonterminal [[Conj]] -> Map Nonterminal Int
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map [[Conj]] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Map Nonterminal [[Conj]]
groupedRelations))


calculateGroupRelationsByNonterminals :: [Relation] -> Map.Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals :: [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals [Relation]
relations = let
    relations' :: [Relation]
relations' = (Relation -> Relation) -> [Relation] -> [Relation]
forall a b. (a -> b) -> [a] -> [b]
map (\case
        Relation (Nonterminal
w, [Symbol]
cfgRightPart) -> (Nonterminal, [Conj]) -> Relation
BooleanRelation (Nonterminal
w, [[Symbol] -> Conj
PosConj [Symbol]
cfgRightPart])
        Relation
boolRel -> Relation
boolRel) [Relation]
relations

    mapWithReversedRelationsOrder :: Map Nonterminal [[Conj]]
mapWithReversedRelationsOrder = ([[Conj]] -> [[Conj]] -> [[Conj]])
-> [(Nonterminal, [[Conj]])] -> Map Nonterminal [[Conj]]
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith [[Conj]] -> [[Conj]] -> [[Conj]]
forall a. [a] -> [a] -> [a]
(++)
        [(Nonterminal
nonterminal, [[Conj]
conjs]) | BooleanRelation (Nonterminal
nonterminal, [Conj]
conjs) <- [Relation]
relations']
    in ([[Conj]] -> [[Conj]])
-> Map Nonterminal [[Conj]] -> Map Nonterminal [[Conj]]
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map [[Conj]] -> [[Conj]]
forall a. Ord a => [a] -> [a]
sort Map Nonterminal [[Conj]]
mapWithReversedRelationsOrder

-- Helpers for working with conjunctions

calculateNextConjunctionInSameRule :: Grammar -> SymbolsPair -> Maybe SymbolsPair
calculateNextConjunctionInSameRule :: Grammar -> SymbolsPair -> Maybe SymbolsPair
calculateNextConjunctionInSameRule (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_))
    (SymbolsPair (Nonterminal
nonterminal, Int
relNumber, Bool
hasNeg, N Nonterminal
nonterminal1, N Nonterminal
nonterminal2)) = let
    groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations
    relationsForNonterminal :: [[Conj]]
relationsForNonterminal = Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! Nonterminal
nonterminal
    conjs :: [Conj]
conjs = [[Conj]]
relationsForNonterminal [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! Int
relNumber
    list :: Conj
list = if Bool
hasNeg
        then [Symbol] -> Conj
NegConj [Nonterminal -> Symbol
N Nonterminal
nonterminal1, Nonterminal -> Symbol
N Nonterminal
nonterminal2]
        else [Symbol] -> Conj
PosConj [Nonterminal -> Symbol
N Nonterminal
nonterminal1, Nonterminal -> Symbol
N Nonterminal
nonterminal2]
    conjPairIndex :: Maybe Int
conjPairIndex = Conj -> [Conj] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
elemIndex Conj
list [Conj]
conjs in
    case Maybe Int
conjPairIndex of
        Just Int
index | Int
index Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== ([Conj] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Conj]
conjs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) -> Maybe SymbolsPair
forall a. Maybe a
Nothing
                   | Bool
otherwise -> let conj :: Conj
conj = [Conj]
conjs [Conj] -> Int -> Conj
forall a. [a] -> Int -> a
!! (Int
index Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) in
                        SymbolsPair -> Maybe SymbolsPair
forall a. a -> Maybe a
Just (SymbolsPair -> Maybe SymbolsPair)
-> SymbolsPair -> Maybe SymbolsPair
forall a b. (a -> b) -> a -> b
$ Nonterminal -> Int -> Conj -> SymbolsPair
convertListToConjunctionPair Nonterminal
nonterminal Int
relNumber Conj
conj
        Maybe Int
Nothing -> [Char] -> Maybe SymbolsPair
forall a. HasCallStack => [Char] -> a
error [Char]
"No such conjunction in given rule. "
calculateNextConjunctionInSameRule Grammar
_ SymbolsPair
_ = [Char] -> Maybe SymbolsPair
forall a. HasCallStack => [Char] -> a
error [Char]
"Conjunction must be pair of nonterminals. "

calculateFirstConjunctionInNextRule :: Grammar -> SymbolsPair -> Maybe SymbolsPair
calculateFirstConjunctionInNextRule :: Grammar -> SymbolsPair -> Maybe SymbolsPair
calculateFirstConjunctionInNextRule (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_))
    (SymbolsPair (Nonterminal
nonterminal, Int
relationNumber, Bool
_, Symbol
_, Symbol
_)) = do
    let groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations
    let relationsForNonterminal :: [[Conj]]
relationsForNonterminal = Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! Nonterminal
nonterminal
    let nextRelationNumber :: Int
nextRelationNumber = Int
relationNumber Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
    if Int
nextRelationNumber Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= [[Conj]] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [[Conj]]
relationsForNonterminal
        then Maybe SymbolsPair
forall a. Maybe a
Nothing
        else let conjs :: [Conj]
conjs = [[Conj]]
relationsForNonterminal [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! Int
nextRelationNumber in
        SymbolsPair -> Maybe SymbolsPair
forall a. a -> Maybe a
Just (SymbolsPair -> Maybe SymbolsPair)
-> SymbolsPair -> Maybe SymbolsPair
forall a b. (a -> b) -> a -> b
$ Nonterminal -> Int -> Conj -> SymbolsPair
convertListToConjunctionPair Nonterminal
nonterminal Int
nextRelationNumber (Conj -> SymbolsPair) -> Conj -> SymbolsPair
forall a b. (a -> b) -> a -> b
$ [Conj] -> Conj
forall a. [a] -> a
head [Conj]
conjs

getFstConjInKthRel :: Grammar -> String -> String -> SymbolsPair
getFstConjInKthRel :: Grammar -> [Char] -> [Char] -> SymbolsPair
getFstConjInKthRel (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_)) [Char]
nontermVal [Char]
number = let
    number' :: Int
number' = [Char] -> Int
forall a. Read a => [Char] -> a
read [Char]
number :: Int
    nonterminal :: Nonterminal
nonterminal = [Char] -> Nonterminal
Nonterminal [Char]
nontermVal
    groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations
    relationsForNonterminal :: [[Conj]]
relationsForNonterminal = Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! Nonterminal
nonterminal
    conjs :: [Conj]
conjs = [[Conj]]
relationsForNonterminal [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! Int
number'
    in Nonterminal -> Int -> Conj -> SymbolsPair
convertListToConjunctionPair Nonterminal
nonterminal Int
number' (Conj -> SymbolsPair) -> Conj -> SymbolsPair
forall a b. (a -> b) -> a -> b
$ [Conj] -> Conj
forall a. [a] -> a
head [Conj]
conjs

-- Helpers for working with long/short relations

getLongRels :: [Relation] -> [Relation]
getLongRels :: [Relation] -> [Relation]
getLongRels = (Relation -> Bool) -> [Relation] -> [Relation]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Relation -> Bool) -> Relation -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation -> Bool
relationHasOneTerminalInRightPart)
                    
getShortRightParts :: Nonterminal -> [[Conj]] -> [String]
getShortRightParts :: Nonterminal -> [[Conj]] -> [[Char]]
getShortRightParts Nonterminal
nonterminal [[Conj]]
rightParts = let
    shortOrNotRels :: [(Maybe Int, Bool)]
shortOrNotRels = ([Conj] -> (Maybe Int, Bool)) -> [[Conj]] -> [(Maybe Int, Bool)]
forall a b. (a -> b) -> [a] -> [b]
map (\[Conj]
t ->
        ([Conj] -> [[Conj]] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
elemIndex [Conj]
t [[Conj]]
rightParts,
        Relation -> Bool
relationHasOneTerminalInRightPart ((Nonterminal, [Conj]) -> Relation
BooleanRelation (Nonterminal
nonterminal, [Conj]
t)))) [[Conj]]
rightParts
    indices' :: [Maybe Int]
indices' = ((Maybe Int, Bool) -> Maybe Int)
-> [(Maybe Int, Bool)] -> [Maybe Int]
forall a b. (a -> b) -> [a] -> [b]
map (\(Maybe Int
i, Bool
t) -> if Bool
t then Maybe Int
i else Maybe Int
forall a. Maybe a
Nothing) [(Maybe Int, Bool)]
shortOrNotRels
    indices :: [[Char]]
indices = (Int -> [Char]) -> [Int] -> [[Char]]
forall a b. (a -> b) -> [a] -> [b]
map Int -> [Char]
forall a. Show a => a -> [Char]
show ([Int] -> [[Char]]) -> [Int] -> [[Char]]
forall a b. (a -> b) -> a -> b
$ [Maybe Int] -> [Int]
forall a. [Maybe a] -> [a]
catMaybes [Maybe Int]
indices'
    in [[Char]]
indices
    
-- short relation is relation with one terminal in right part
getNumbersOfShortRelations :: Grammar -> Map.Map Nonterminal [String]
getNumbersOfShortRelations :: Grammar -> Map Nonterminal [[Char]]
getNumbersOfShortRelations (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_)) =
    (Nonterminal -> [[Conj]] -> [[Char]])
-> Map Nonterminal [[Conj]] -> Map Nonterminal [[Char]]
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey Nonterminal -> [[Conj]] -> [[Char]]
getShortRightParts (Map Nonterminal [[Conj]] -> Map Nonterminal [[Char]])
-> Map Nonterminal [[Conj]] -> Map Nonterminal [[Char]]
forall a b. (a -> b) -> a -> b
$ [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations

-- Helpers for building conjunctions

-- grammar -> string (nonterminal in left part)
--         -> string (number of relation) -> list of first nonterminals
getFstNonterminalsInConjsOfGivenRel :: Grammar -> String -> String -> [String]
getFstNonterminalsInConjsOfGivenRel :: Grammar -> [Char] -> [Char] -> [[Char]]
getFstNonterminalsInConjsOfGivenRel
    (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
rels, Nonterminal
_)) [Char]
nonterminal [Char]
number = do
    let groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
rels
    let conjs :: [Conj]
conjs = (Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! [Char] -> Nonterminal
Nonterminal [Char]
nonterminal) [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! ([Char] -> Int
forall a. Read a => [Char] -> a
read [Char]
number :: Int)
    if Relation -> Bool
relationHasOneTerminalInRightPart (Relation -> Bool) -> Relation -> Bool
forall a b. (a -> b) -> a -> b
$ (Nonterminal, [Conj]) -> Relation
BooleanRelation ([Char] -> Nonterminal
Nonterminal [Char]
nonterminal, [Conj]
conjs)
        then []
        else let
        firstSymbolsInConjunctions :: [Symbol]
firstSymbolsInConjunctions = ([Symbol] -> Symbol) -> [[Symbol]] -> [Symbol]
forall a b. (a -> b) -> [a] -> [b]
map [Symbol] -> Symbol
forall a. [a] -> a
head ([[Symbol]] -> [Symbol]) -> [[Symbol]] -> [Symbol]
forall a b. (a -> b) -> a -> b
$ (Conj -> [Symbol]) -> [Conj] -> [[Symbol]]
forall a b. (a -> b) -> [a] -> [b]
map Conj -> [Symbol]
symbols [Conj]
conjs
        in (Symbol -> [Char]) -> [Symbol] -> [[Char]]
forall a b. (a -> b) -> [a] -> [b]
map Symbol -> [Char]
refineSymbolInConjunctionToNonterminal [Symbol]
firstSymbolsInConjunctions

-- grammar -> string (nonterminal in left part) -> string (number of relation)
--         -> string (first nonterminal in conjunction) -> list of first nonterminals
getSndNonterminalsInConjsOfGivenRel :: Grammar -> String -> String -> String -> [String]
getSndNonterminalsInConjsOfGivenRel :: Grammar -> [Char] -> [Char] -> [Char] -> [[Char]]
getSndNonterminalsInConjsOfGivenRel
    (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
rels, Nonterminal
_)) [Char]
leftNonterminal [Char]
number [Char]
fstNontermInConj = let
    groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
rels
    conjs :: [Conj]
conjs = (Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! [Char] -> Nonterminal
Nonterminal [Char]
leftNonterminal) [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! ([Char] -> Int
forall a. Read a => [Char] -> a
read [Char]
number :: Int)
    symbol :: Symbol
symbol = Nonterminal -> Symbol
N ([Char] -> Nonterminal
Nonterminal [Char]
fstNontermInConj)
    possibleConjs :: [Conj]
possibleConjs = (Conj -> Bool) -> [Conj] -> [Conj]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Conj
t -> Symbol
symbol Symbol -> Symbol -> Bool
forall a. Eq a => a -> a -> Bool
== [Symbol] -> Symbol
forall a. [a] -> a
head (Conj -> [Symbol]
symbols Conj
t)) [Conj]
conjs
    possibleSndNonterminals :: [Symbol]
possibleSndNonterminals = (Conj -> Symbol) -> [Conj] -> [Symbol]
forall a b. (a -> b) -> [a] -> [b]
map (\Conj
t -> Conj -> [Symbol]
symbols Conj
t [Symbol] -> Int -> Symbol
forall a. [a] -> Int -> a
!! Int
1) [Conj]
possibleConjs
    in (Symbol -> [Char]) -> [Symbol] -> [[Char]]
forall a b. (a -> b) -> [a] -> [b]
map Symbol -> [Char]
refineSymbolInConjunctionToNonterminal [Symbol]
possibleSndNonterminals

-- Helpers for generating quads and triplets

calculateTriplets :: Grammar -> String -> [String] -> [(String, String, String)]
calculateTriplets :: Grammar -> [Char] -> [[Char]] -> [([Char], [Char], [Char])]
calculateTriplets Grammar
grammar [Char]
number
  = ([Char] -> [([Char], [Char], [Char])])
-> [[Char]] -> [([Char], [Char], [Char])]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\[Char]
t -> let
        firstNonterminals :: [[Char]]
firstNonterminals = Grammar -> [Char] -> [Char] -> [[Char]]
getFstNonterminalsInConjsOfGivenRel Grammar
grammar [Char]
t [Char]
number
        in ([Char] -> ([Char], [Char], [Char]))
-> [[Char]] -> [([Char], [Char], [Char])]
forall a b. (a -> b) -> [a] -> [b]
map ([Char]
number, [Char]
t,) [[Char]]
firstNonterminals)

calculateQuads' :: Grammar -> [([Char], [Char], [Char])] -> [(String, String, String, [String])]
calculateQuads' :: Grammar
-> [([Char], [Char], [Char])]
-> [([Char], [Char], [Char], [[Char]])]
calculateQuads' Grammar
grammar = (([Char], [Char], [Char]) -> ([Char], [Char], [Char], [[Char]]))
-> [([Char], [Char], [Char])]
-> [([Char], [Char], [Char], [[Char]])]
forall a b. (a -> b) -> [a] -> [b]
map (\([Char]
k, [Char]
t, [Char]
j)
    -> ([Char]
k, [Char]
t, [Char]
j, Grammar -> [Char] -> [Char] -> [Char] -> [[Char]]
getSndNonterminalsInConjsOfGivenRel Grammar
grammar [Char]
t [Char]
k [Char]
j))

calculateQuads :: Grammar -> String -> [String] -> [(String, String, String, String)]
calculateQuads :: Grammar -> [Char] -> [[Char]] -> [([Char], [Char], [Char], [Char])]
calculateQuads Grammar
grammar [Char]
k' [[Char]]
nonterminalsWithKthRel = let
    triplets :: [([Char], [Char], [Char])]
triplets = Grammar -> [Char] -> [[Char]] -> [([Char], [Char], [Char])]
calculateTriplets Grammar
grammar [Char]
k' [[Char]]
nonterminalsWithKthRel
    quads' :: [([Char], [Char], [Char], [[Char]])]
quads' = Grammar
-> [([Char], [Char], [Char])]
-> [([Char], [Char], [Char], [[Char]])]
calculateQuads' Grammar
grammar [([Char], [Char], [Char])]
triplets
    in (([Char], [Char], [Char], [[Char]])
 -> [([Char], [Char], [Char], [Char])])
-> [([Char], [Char], [Char], [[Char]])]
-> [([Char], [Char], [Char], [Char])]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\ ([Char]
k, [Char]
t, [Char]
j, [[Char]]
s) -> ([Char] -> ([Char], [Char], [Char], [Char]))
-> [[Char]] -> [([Char], [Char], [Char], [Char])]
forall a b. (a -> b) -> [a] -> [b]
map ([Char]
k, [Char]
t, [Char]
j,) [[Char]]
s) [([Char], [Char], [Char], [[Char]])]
quads'

calculateAllQuads :: Grammar -> [(String, String, String, String)]
calculateAllQuads :: Grammar -> [([Char], [Char], [Char], [Char])]
calculateAllQuads gr :: Grammar
gr@(Grammar (Set Nonterminal
nonterminals, Set Terminal
_, Set Relation
rels, Nonterminal
_)) = let
    maxNumber :: Int
maxNumber = Grammar -> Int
calculateMaxNumberOfRulesForNonterminal Grammar
gr
    indices :: [[Char]]
indices = (Int -> [Char]) -> [Int] -> [[Char]]
forall a b. (a -> b) -> [a] -> [b]
map Int -> [Char]
forall a. Show a => a -> [Char]
show [Int
0..Int
maxNumber Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
    nonterminalsList :: [[Char]]
nonterminalsList = (Nonterminal -> [Char]) -> [Nonterminal] -> [[Char]]
forall a b. (a -> b) -> [a] -> [b]
map Nonterminal -> [Char]
nonterminalValue ([Nonterminal] -> [[Char]]) -> [Nonterminal] -> [[Char]]
forall a b. (a -> b) -> a -> b
$ Set Nonterminal -> [Nonterminal]
forall a. Set a -> [a]
Set.toList Set Nonterminal
nonterminals
    indicesWithNonterms :: [([Char], [[Char]])]
indicesWithNonterms = ([Char] -> ([Char], [[Char]])) -> [[Char]] -> [([Char], [[Char]])]
forall a b. (a -> b) -> [a] -> [b]
map (\[Char]
i -> ([Char]
i, ([Char] -> Bool) -> [[Char]] -> [[Char]]
forall a. (a -> Bool) -> [a] -> [a]
filter (\[Char]
t ->
        [Relation] -> [Char] -> [Char] -> Bool
kthRelForNonterminalLong (Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
rels) [Char]
t [Char]
i) [[Char]]
nonterminalsList)) [[Char]]
indices
    in (([Char], [[Char]]) -> [([Char], [Char], [Char], [Char])])
-> [([Char], [[Char]])] -> [([Char], [Char], [Char], [Char])]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (([Char] -> [[Char]] -> [([Char], [Char], [Char], [Char])])
-> ([Char], [[Char]]) -> [([Char], [Char], [Char], [Char])]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (([Char] -> [[Char]] -> [([Char], [Char], [Char], [Char])])
 -> ([Char], [[Char]]) -> [([Char], [Char], [Char], [Char])])
-> ([Char] -> [[Char]] -> [([Char], [Char], [Char], [Char])])
-> ([Char], [[Char]])
-> [([Char], [Char], [Char], [Char])]
forall a b. (a -> b) -> a -> b
$ Grammar -> [Char] -> [[Char]] -> [([Char], [Char], [Char], [Char])]
calculateQuads Grammar
gr) [([Char], [[Char]])]
indicesWithNonterms

-- Helpers which check sth

checkIfConjHasNeg :: Grammar -> (String, String, String, String) -> Bool
checkIfConjHasNeg :: Grammar -> ([Char], [Char], [Char], [Char]) -> Bool
checkIfConjHasNeg (Grammar(Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_)) ([Char]
number, [Char]
leftN, [Char]
fstN, [Char]
sndN) = do
    let listRelations :: [Relation]
listRelations = Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations
    let groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals [Relation]
listRelations
    let relsForNonterminal :: [[Conj]]
relsForNonterminal = Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! [Char] -> Nonterminal
Nonterminal [Char]
leftN
    let conjs :: [Conj]
conjs = [[Conj]]
relsForNonterminal [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! ([Char] -> Int
forall a. Read a => [Char] -> a
read [Char]
number :: Int)
    (Conj -> Bool) -> [Conj] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\Conj
t -> Conj
t Conj -> Conj -> Bool
forall a. Eq a => a -> a -> Bool
== [Symbol] -> Conj
NegConj [Nonterminal -> Symbol
N ([Char] -> Nonterminal
Nonterminal [Char]
fstN), Nonterminal -> Symbol
N ([Char] -> Nonterminal
Nonterminal [Char]
sndN)]) [Conj]
conjs
        
kthRelForNonterminalLong :: [Relation] -> String -> String -> Bool
kthRelForNonterminalLong :: [Relation] -> [Char] -> [Char] -> Bool
kthRelForNonterminalLong [Relation]
relations [Char]
nontermVal [Char]
k = do
    let k' :: Int
k' = [Char] -> Int
forall a. Read a => [Char] -> a
read [Char]
k :: Int
    let groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals [Relation]
relations
    let nonterminal :: Nonterminal
nonterminal = [Char] -> Nonterminal
Nonterminal [Char]
nontermVal
    let relationsForNonterm :: [[Conj]]
relationsForNonterm = Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! Nonterminal
nonterminal
    let relation :: Relation
relation = (Nonterminal, [Conj]) -> Relation
BooleanRelation (Nonterminal
nonterminal, [[Conj]]
relationsForNonterm [[Conj]] -> Int -> [Conj]
forall a. [a] -> Int -> a
!! Int
k')
    [[Conj]] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [[Conj]]
relationsForNonterm Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
k' Bool -> Bool -> Bool
&&
        Bool -> Bool
not (Relation -> Bool
relationHasOneTerminalInRightPart Relation
relation)

relationHasOneTerminalInRightPart :: Relation -> Bool
relationHasOneTerminalInRightPart :: Relation -> Bool
relationHasOneTerminalInRightPart (Relation (Nonterminal
_, [T (Terminal [Char]
_)])) = Bool
True
relationHasOneTerminalInRightPart (BooleanRelation (Nonterminal
_, [PosConj [T (Terminal [Char]
_)]])) = Bool
True
relationHasOneTerminalInRightPart Relation
_ = Bool
False

symbolAcceptedByNonterminal :: Grammar -> String -> String -> Bool
symbolAcceptedByNonterminal :: Grammar -> [Char] -> [Char] -> Bool
symbolAcceptedByNonterminal (Grammar (Set Nonterminal
_, Set Terminal
_, Set Relation
relations, Nonterminal
_)) [Char]
nontermValue [Char]
symbol = let
    groupedRelations :: Map Nonterminal [[Conj]]
groupedRelations = [Relation] -> Map Nonterminal [[Conj]]
calculateGroupRelationsByNonterminals ([Relation] -> Map Nonterminal [[Conj]])
-> [Relation] -> Map Nonterminal [[Conj]]
forall a b. (a -> b) -> a -> b
$ Set Relation -> [Relation]
forall a. Set a -> [a]
Set.toList Set Relation
relations
    nonterminal :: Nonterminal
nonterminal = [Char] -> Nonterminal
Nonterminal [Char]
nontermValue
    nontermRels :: [[Conj]]
nontermRels = Map Nonterminal [[Conj]]
groupedRelations Map Nonterminal [[Conj]] -> Nonterminal -> [[Conj]]
forall k a. Ord k => Map k a -> k -> a
Map.! Nonterminal
nonterminal
    terminalsInRightPart' :: [Maybe Symbol]
terminalsInRightPart' = ([Conj] -> Maybe Symbol) -> [[Conj]] -> [Maybe Symbol]
forall a b. (a -> b) -> [a] -> [b]
map (\[Conj]
conjs ->
        if Relation -> Bool
relationHasOneTerminalInRightPart ((Nonterminal, [Conj]) -> Relation
BooleanRelation (Nonterminal
nonterminal, [Conj]
conjs))
            then Symbol -> Maybe Symbol
forall a. a -> Maybe a
Just (Symbol -> Maybe Symbol) -> Symbol -> Maybe Symbol
forall a b. (a -> b) -> a -> b
$ [Symbol] -> Symbol
forall a. [a] -> a
head ([Symbol] -> Symbol) -> [Symbol] -> Symbol
forall a b. (a -> b) -> a -> b
$ Conj -> [Symbol]
symbols (Conj -> [Symbol]) -> Conj -> [Symbol]
forall a b. (a -> b) -> a -> b
$ [Conj] -> Conj
forall a. [a] -> a
head [Conj]
conjs
            else Maybe Symbol
forall a. Maybe a
Nothing) [[Conj]]
nontermRels
    terminalsInRightPart :: [Symbol]
terminalsInRightPart = [Maybe Symbol] -> [Symbol]
forall a. [Maybe a] -> [a]
catMaybes [Maybe Symbol]
terminalsInRightPart'
    terminalsValues :: [[Char]]
terminalsValues = (Symbol -> [Char]) -> [Symbol] -> [[Char]]
forall a b. (a -> b) -> [a] -> [b]
map Symbol -> [Char]
refineSymbolToTerminalValue [Symbol]
terminalsInRightPart
    in [Char] -> [[Char]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
elem [Char]
symbol [[Char]]
terminalsValues    

-- Helpers for converting/refining sth to sth

refineSymbolInConjunctionToNonterminal :: GrammarType.Symbol -> String
refineSymbolInConjunctionToNonterminal :: Symbol -> [Char]
refineSymbolInConjunctionToNonterminal (N Nonterminal
nonterminal) = Nonterminal -> [Char]
nonterminalValue Nonterminal
nonterminal
refineSymbolInConjunctionToNonterminal Symbol
_ = [Char] -> [Char]
forall a. HasCallStack => [Char] -> a
error [Char]
"Not a nonterminal, conjunction pair must be a pair of nonterminals"

addCollectionToMap :: (Ord k) => [(k, a)] -> Map.Map k a -> Map.Map k a
addCollectionToMap :: [(k, a)] -> Map k a -> Map k a
addCollectionToMap ((k
a,a
b) : [(k, a)]
xs) Map k a
myMap = [(k, a)] -> Map k a -> Map k a
forall k a. Ord k => [(k, a)] -> Map k a -> Map k a
addCollectionToMap [(k, a)]
xs (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
a a
b Map k a
myMap
addCollectionToMap [] Map k a
myMap = Map k a
myMap

refineSymbolToTerminalValue :: GrammarType.Symbol -> String
refineSymbolToTerminalValue :: Symbol -> [Char]
refineSymbolToTerminalValue (T Terminal
t) = Terminal -> [Char]
terminalValue Terminal
t
refineSymbolToTerminalValue Symbol
_ = [Char] -> [Char]
forall a. HasCallStack => [Char] -> a
error [Char]
"Given symbol is not terminal"

constructSymbolsPairByQuad :: (String, String, String, String) -> Bool -> SymbolsPair
constructSymbolsPairByQuad :: ([Char], [Char], [Char], [Char]) -> Bool -> SymbolsPair
constructSymbolsPairByQuad ([Char]
number, [Char]
leftN, [Char]
fstN, [Char]
sndN) Bool
hasNeg =
    (Nonterminal, Int, Bool, Symbol, Symbol) -> SymbolsPair
SymbolsPair ([Char] -> Nonterminal
Nonterminal [Char]
leftN, [Char] -> Int
forall a. Read a => [Char] -> a
read [Char]
number :: Int, Bool
hasNeg, Nonterminal -> Symbol
N (Nonterminal -> Symbol) -> Nonterminal -> Symbol
forall a b. (a -> b) -> a -> b
$ [Char] -> Nonterminal
Nonterminal [Char]
fstN, Nonterminal -> Symbol
N (Nonterminal -> Symbol) -> Nonterminal -> Symbol
forall a b. (a -> b) -> a -> b
$ [Char] -> Nonterminal
Nonterminal [Char]
sndN)

convertListToConjunctionPair :: Nonterminal -> Int -> Conj -> SymbolsPair
convertListToConjunctionPair :: Nonterminal -> Int -> Conj -> SymbolsPair
convertListToConjunctionPair Nonterminal
nonterminal Int
relationNumber
    (NegConj [N Nonterminal
conjNonterminal1, N Nonterminal
conjNonterminal2]) =
    (Nonterminal, Int, Bool, Symbol, Symbol) -> SymbolsPair
SymbolsPair (Nonterminal
nonterminal, Int
relationNumber, Bool
True, Nonterminal -> Symbol
N Nonterminal
conjNonterminal1 , Nonterminal -> Symbol
N Nonterminal
conjNonterminal2)
convertListToConjunctionPair Nonterminal
nonterminal Int
relationNumber
    (PosConj [N Nonterminal
conjNonterminal1, N Nonterminal
conjNonterminal2]) =
    (Nonterminal, Int, Bool, Symbol, Symbol) -> SymbolsPair
SymbolsPair (Nonterminal
nonterminal, Int
relationNumber, Bool
False, Nonterminal -> Symbol
N Nonterminal
conjNonterminal1, Nonterminal -> Symbol
N Nonterminal
conjNonterminal2)
convertListToConjunctionPair Nonterminal
_ Int
_ Conj
_ = [Char] -> SymbolsPair
forall a. HasCallStack => [Char] -> a
error [Char]
"Conjunction must be pair of nonterminals. "

-- other

getShiftsDecrements :: Int -> String -> [(String, String)]
getShiftsDecrements :: Int -> [Char] -> [([Char], [Char])]
getShiftsDecrements Int
shiftSize [Char]
symbol = let
    fstPair :: [([Char], [Char])]
fstPair = [([Char]
symbol, Int -> [Char]
forall a. Show a => a -> [Char]
show Int
shiftSize)]
    indices :: [Int]
indices = [Int
1..Int
shiftSize]
    midPairs :: [([Char], [Char])]
midPairs = (Int -> ([Char], [Char])) -> [Int] -> [([Char], [Char])]
forall a b. (a -> b) -> [a] -> [b]
map (\Int
i -> if
        Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 then (Int -> [Char]
forall a. Show a => a -> [Char]
show Int
i, [Char]
symbol)
        else (Int -> [Char]
forall a. Show a => a -> [Char]
show Int
i, Int -> [Char]
forall a. Show a => a -> [Char]
show (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1))
        ) [Int]
indices
    in ([([Char], [Char])]
fstPair [([Char], [Char])] -> [([Char], [Char])] -> [([Char], [Char])]
forall a. [a] -> [a] -> [a]
++ [([Char], [Char])]
midPairs)