fast-myers-diff 0.0.1 → 0.0.2

raw patch · 4 files changed

+43/−2 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Changelog.md +4/−0
• fast-myers-diff.cabal +2/−2
• src/Myers/Diff.hs +30/−0
• test/Main.hs +7/−0

@@ -1,5 +1,9 @@ # Revision history for fast-myers-diff +## 0.0.2 -- 2025-01-15++- Edit distance functions+ ## 0.0.1 -- 2024-09-08  - Added `NFData` instance for `PolyDiff`

@@ -1,11 +1,11 @@ cabal-version: 1.12 --- This file has been generated from package.yaml by hpack version 0.36.0.+-- This file has been generated from package.yaml by hpack version 0.36.1. -- -- see: https://github.com/sol/hpack  name:           fast-myers-diff-version:        0.0.1+version:        0.0.2 synopsis:       A fast implementation of the Myers diff algorithm. description:    A fast implementation of the diffing algorithm described in 'An O(ND) Difference Algorithm and Its Variations' by Eugene W. Myers. category:       Testing

@@ -22,6 +22,12 @@     getVectorDiffBy,     getGroupedVectorDiffBy, +    -- * Distance+    getTextEditDistance,+    getStringEditDistance,+    getEditDistance,+    getEditDistanceBy,+     -- ** Internals     Edit (..),     getEditScript,@@ -140,6 +146,30 @@ -- | Diff two 'Vector's with grouped results using a custom equality operator getGroupedVectorDiffBy :: forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Vector (PolyDiff (Vector a) (Vector b)) getGroupedVectorDiffBy eq old new = computeGroupedDiffFromEditScript old new (getEditScriptBy eq old new)++-- | 'Text edit distance+getTextEditDistance :: Text -> Text -> Word+getTextEditDistance actual expected = getStringEditDistance (T.unpack actual) (T.unpack expected)++-- | 'String' edit distance+getStringEditDistance :: String -> String -> Word+getStringEditDistance actual expected = getEditDistance (V.fromList actual) (V.fromList expected)++-- | Compute the total size of the edit script vector from 'getEditScript.+getEditDistance :: (Eq a) => Vector a -> Vector a -> Word+getEditDistance = getEditDistanceBy (==)++-- | Compute the total size of the edit script vector from 'getEditScriptBy'.+getEditDistanceBy :: (a -> b -> Bool) -> Vector a -> Vector b -> Word+getEditDistanceBy eq old new =+  -- This 'fromIntegral' is safe because you'd need a ridiculously large edit+  -- script for it to cause trouble, and that would crash the program before+  -- 'fromIntegral' could.+  (fromIntegral :: Int -> Word) $ sum $ V.map editCost $ getEditScriptBy eq old new+  where+    editCost = \case+      Delete _ c -> c+      Insert _ _ c -> c  -- | Compute the edit script to turn a given 'Vector' into the second given 'Vector' getEditScript :: forall a. (Eq a) => Vector a -> Vector a -> Vector Edit

@@ -85,6 +85,13 @@     exampleSpec "foofoo" "foo" [Delete 1 1, Delete 3 1, Delete 5 1] [Both 'f' 'f', First 'o', Both 'o' 'o', First 'f', Both 'o' 'o', First 'o']     exampleSpec "foo" "foofoo" [Insert 1 1 1, Insert 2 3 1, Insert 3 5 1] [Both 'f' 'f', Second 'o', Both 'o' 'o', Second 'f', Both 'o' 'o', Second 'o'] +  describe "getStringEditDistance" $ do+    prop "is 0 for identical strings" $ \t ->+      getStringEditDistance t t `shouldBe` 0++    it "returns 6 for these two completely different strings" $+      getStringEditDistance "abc" "def" `shouldBe` 6+   describe "getVectorDiff" $ do     let exampleSpec :: Vector Char -> Vector Char -> Vector (Diff Char) -> Spec         exampleSpec old new expected =