Commits

Eric Rochester  committed 89c11bb

Added tests from the article.

  • Participants
  • Parent commits 7a60c40

Comments (0)

Files changed (4)

File Test/Main.hs

 module Main where
 
 import Data.Char
+import Test.HUnit
 import Test.QuickCheck
-import Test.SequiturQuick (tests)
+import qualified Test.SequiturQuick as SQuick
+import qualified Test.SequiturUnit as SUnit
 
 main = do
-    mapM_ quickCheck tests
+    SQuick.runTests
+    SUnit.runTests
 

File Test/SequiturQuick.hs

-module Test.SequiturQuick (tests) where
+module Test.SequiturQuick (tests, runTests) where
 
 import Data.Sequitur
 
-tests = [ prop_identity
+prop_idempotent :: [Char] -> Bool
+prop_idempotent xs =
+    expand (compress xs) == xs
+
+tests = [ prop_idempotent
         ]
 
+runTests = do
+    mapM_ quickCheck tests
+

File Test/SequiturUnit.hs

+module Test.SequiturUnit (tests, runTests) where
+
+import Test.HUnit
+import qualified Data.Sequitur as Seq
+
+
+testRule :: Compressor String -> Integer -> [Seq.Symbol] -> Assertion
+testRule compressor name expected =
+    assertEqual title expected actual
+    where actual = Seq.rule compressor name
+          title  = (show name) ++ " ->"
+
+test_abcdbc = TestCase (do
+    testRule compressed 0 [ Seq.Literal 'a'
+                          , Seq.Rule 1
+                          , Seq.Literal 'd'
+                          , Seq.Rule 1
+                          ]
+    testRule compressed 1 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    where compressed = Seq.compress "abcdbc")
+
+test_abcdbcabcdbc = TestCase (do
+    testRule compressed 0 [ Seq.Rule 1, Seq.Rule 1 ]
+    testRule compressed 1 [ Seq.Literal 'a'
+                          , Seq.Rule 2
+                          , Seq.Literal 'd'
+                          , Seq.Rule 2
+                          ]
+    testRule compressed 2 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    where compressed = Seq.compress "abcdbcabcdbc")
+
+-- This test actually has two valid outcomes.
+test_aabaaab = TestCase (do
+    case (Seq.rule compressed 0) of
+        [ Seq.Rule 1, Seq.Literal 'a', Seq.Rule 1 ] ->
+            testRule compressed 1 [ Seq.Literal 'a'
+                                  , Seq.Literal 'a'
+                                  , Seq.Literal 'b' ]
+        [ Seq.Rule 1, Seq.Literal 'b', Seq.Rule 1, Seq.Literal 'a', Seq.Literal 'b' ] ->
+            testRule compressed 1 [ Seq.Literal 'a', Seq.Literal 'a' ]
+        _ ->
+            assertFailure "aabbaaab not compressed correctly."
+    where compressed = Seq.compress "aabaaab"
+    )
+
+-- XXX: Seq.feed needs to be made functional.
+test_abcdbcabcd = TestCase (do
+    compressor <- Seq.init()
+
+    -- a
+    compressor <- Seq.feed compressor 'a'
+    testRule compressor 0 [ Seq.Literal 'a' ]
+    assertEqual "rule count" 1 $ Seq.ruleCount compressor
+
+    -- ab
+    compressor <- Seq.feed compressor 'b'
+    testRule compressor 0 [ Seq.Literal 'a', Seq.Literal 'b' ]
+    assertEqual "rule count" 1 $ Seq.ruleCount compressor
+
+    -- abc
+    compressor <- Seq.feed compressor 'c'
+    testRule compressor 0 [ Seq.Literal 'a', Seq.Literal 'b', Seq.Literal 'c' ]
+    assertEqual "rule count" 1 $ Seq.ruleCount compressor
+
+    -- abcd
+    compressor <- Seq.feed compressor 'd'
+    testRule compressor 0 [ Seq.Literal 'a'
+                          , Seq.Literal 'b'
+                          , Seq.Literal 'c'
+                          , Seq.Literal 'd'
+                          ]
+    assertEqual "rule count" 1 $ Seq.ruleCount compressor
+
+    -- abcdb
+    compressor <- Seq.feed compressor 'b'
+    testRule compressor 0 [ Seq.Literal 'a'
+                          , Seq.Literal 'b'
+                          , Seq.Literal 'c'
+                          , Seq.Literal 'd'
+                          , Seq.Literal 'b'
+                          ]
+    assertEqual "rule count" 1 $ Seq.ruleCount compressor
+
+    -- abcdbc
+    compressor <- Seq.feed compressor 'c'
+    testRule compressor 0 [ Seq.Literal 'a'
+                          , Seq.Rule 1
+                          , Seq.Literal 'd'
+                          , Seq.Rule 1
+                          ]
+    testRule compressor 1 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    assertEqual "rule count" 2 $ Seq.ruleCount compressor
+
+    -- abcdbca
+    compressor <- Seq.feed compressor 'a'
+    testRule compressor 0 [ Seq.Literal 'a'
+                          , Seq.Rule 1
+                          , Seq.Literal 'd'
+                          , Seq.Rule 1
+                          , Seq.Literal 'a'
+                          ]
+    testRule compressor 1 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    assertEqual "rule count" 2 $ Seq.ruleCount compressor
+
+    -- abcdbcab
+    compressor <- Seq.feed compressor 'b'
+    testRule compressor 0 [ Seq.Literal 'a'
+                          , Seq.Rule 1
+                          , Seq.Literal 'd'
+                          , Seq.Rule 1
+                          , Seq.Literal 'a'
+                          , Seq.Literal 'b'
+                          ]
+    testRule compressor 1 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    assertEqual "rule count" 2 $ Seq.ruleCount compressor
+
+    -- abcdbcabc
+    compressor <- Seq.feed compressor 'b'
+    testRule compressor 0 [ Seq.Rule 2
+                          , Seq.Literal 'd'
+                          , Seq.Rule 1
+                          , Seq.Rule 2
+                          ]
+    testRule compressor 1 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    testRule compressor 2 [ Seq.Literal 'a', Seq.Rule 1 ]
+    assertEqual "rule count" 3 $ Seq.ruleCount compressor
+
+    -- abcdbcabcd
+    compressor <- Seq.feed compressor 'd'
+    testRule compressor 0 [ Seq.Rule 3
+                          , Seq.Rule 1
+                          , Seq.Rule 3
+                          ]
+    testRule compressor 1 [ Seq.Literal 'b', Seq.Literal 'c' ]
+    testRule compressor 3 [ Seq.Literal 'a', Seq.Rule 1, Seq.Literal 'd' ]
+    assertEqual "rule count" 3 $ Seq.ruleCount compressor
+    )
+
+test_aaa = TestCase (do
+    testRule compress 0 [ Seq.Literal 'a', Seq.Literal 'a', Seq.Literal 'a' ]
+    assertEqual "rule count" 1 $ Seq.ruleCount compressor
+    where compress = Seq.compress "aaa")
+
+test_ababcabcdabcdeabcdef = (do
+    testRule compress 0 [ Seq.Rule 1
+                        , Seq.Rule 2
+                        , Seq.Rule 3
+                        , Seq.Rule 4
+                        , Seq.Rule 4
+                        , Seq.Literal 'f'
+                        ]
+    testRule compress 1 [ Seq.Literal 'a', Seq.Literal 'b' ]
+    testRule compress 2 [ Seq.Rule 1, Seq.Literal 'c' ]
+    testRule compress 3 [ Seq.Rule 2, Seq.Literal 'd' ]
+    testRule compress 4 [ Seq.Rule 3, Seq.Literal 'e' ]
+    where compress = Seq.compress "ababcabcdabcdeabcdef")
+
+test_yzxyzwxyzvwxy = (do
+    testRule compress 0 [ Seq.Rule 1
+                        , Seq.Rule 2
+                        , Seq.Literal 'w'
+                        , Seq.Rule 2
+                        , Seq.Literal 'v'
+                        , Seq.Literal 'w'
+                        , Seq.Literal 'x'
+                        , Seq.Literal 'y'
+                        ]
+    testRule compress 1 [ Seq.Literal 'y', Seq.Literal 'z' ]
+    testRule compress 2 [ Seq.Literal 'x', Seq.Rule 1 ]
+    where compress = Seq.compress "yzxyzwxyzvwxy")
+
+
+tests = [ TestLabel "test: abcdbc" test_abcdbc
+        , TestLabel "test: abcdbcabcdbc" test_abcdbcabcdbc
+        , TestLabel "test: aabaaab" test_aabaaab
+        , TestLabel "test: abcdbcabcd" test_abcdbcabcd
+        , TestLabel "test: aaa" test_aaa
+        , TestLabel "test: ababcabcdabcdeabcdef" test_ababcabcdabcdeabcdef
+        , TestLabel "test: yzxyzwxyzvwxy" test_yzxyzwxyzvwxy
+        ]
+
+runTests = do
+    runTestTT tests
+

File src/Data/Sequitur.hs

 module Data.Sequitur (prop_identity) where
 
-prop_identity :: [Char] -> Bool
-prop_identity xs = xs == xs
+-- Operations:
+--  * appending a symbol to rule S;
+--  * using an existing rule (substituting a non-terminal symbol for two symbols);
+--  * creating a new rule (creating a new non-terminal symbol and inserting two new symbols on the right-hand side); and
+--  * deleting a rule (removing rule and inserting its definition into another rule).
 
 
+data Compressor a =
+    Compressor a
+    deriving (Show)
+
+
+compress :: Eq a => [a] -> Compressor a
+
+expand :: Eq a => Compressor a -> [a]
+
+