NaturalSort (empty) → 0.2.1
raw patch · 11 files changed
+450/−0 lines, 11 filesdep +QuickCheckdep +basedep +bytestringsetup-changed
Dependencies added: QuickCheck, base, bytestring, strict
Files
- COPYING +30/−0
- Chunk.hs +55/−0
- Main.hs +59/−0
- NaturalSort.cabal +94/−0
- NaturalSort.hs +34/−0
- README.md +42/−0
- Setup.lhs +3/−0
- tests/Main.hs +7/−0
- tests/Properties.hs +44/−0
- tests/Unit.hs +63/−0
- tests/coverage.lhs +19/−0
+ COPYING view
@@ -0,0 +1,30 @@+Copyright (c) 2010 Joachim Fasting++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:++1. Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright+ notice, this list of conditions and the following disclaimer in the+ documentation and/or other materials provided with the distribution.++3. Neither the name of the author nor the names of his contributors+ may be used to endorse or promote products derived from this software+ without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN+ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE+POSSIBILITY OF SUCH DAMAGE.
+ Chunk.hs view
@@ -0,0 +1,55 @@+-- |+-- Module : Chunk+-- Copyright : (c) Joachim Fasting 2008-2010+-- License : BSD3 (see COPYING)+-- Maintainer : joachim.fasting@gmail.com+-- Stability : unstable+-- Portability : unportable+--+-- Break textual input into sortable chunks.++module Chunk (Chunk, toChunks) where++import Data.ByteString.Char8 (ByteString)+import qualified Data.ByteString.Char8 as B+import Data.Char (isDigit)+import Data.Function (on)+import Data.Maybe (fromJust)++import Prelude hiding (Either(..))+import Data.Strict.Either++-- | A chunk is either a pure integral value, or a string that might contain+-- digits, letters and other characters.+--+-- When preparing strings for natural comparison, they are first broken into+-- several chunks, which can then be compared and ordered \"naturally\".+type Chunk = Either Int ByteString++-- Returns 'True' if both inputs have the same \"digitness\", that is, both+-- are digits or non-digits.+digitness :: Char -> Char -> Bool+digitness = (==) `on` isDigit++-- Convert a string to a single 'Chunk'.+--+-- Note that leading 0s are not preserved.+-- As a consequence, this operation is _not_ reversible.+--+-- > convert "12" = Left 12+-- > convert "ab" = Right "ab"+-- > convert "a1" = Right "a1"+-- > convert "01" = Left 1+convert :: ByteString -> Chunk+convert x = (if B.all isDigit x then Left . parse else Right) x+ where+ parse = fst . fromJust . B.readInt++-- | Turn a string into a list of 'Chunk's.+--+-- > toChunks "a12x.txt" = [S "a", N 12, S "x.txt"]+-- > toChunks "7" `compare` toChunks "10" = LT+-- > toChunks "a7.txt" `compare` toChunks "a10.txt" = LT+-- > toChunks "7a.txt" `compare` toChunks "10a.txt" = LT+toChunks :: ByteString -> [Chunk]+toChunks = map convert . B.groupBy digitness
+ Main.hs view
@@ -0,0 +1,59 @@+-- |+-- Module : Main+-- Copyright : (c) Joachim Fasting 2008-2010+-- License : BSD3 (see COPYING)+-- Maintainer : joachim.fasting@gmail.com+-- Stability : unstable+-- Portability : unportable+--+-- Compilation: ghc -O2 --make Main.hs -o nsort+--+-- Usage: nsort [FILE]...+--+-- Write a sorted concatenation of all FILE(s) to standard output.+--+-- If no files are given, read from standard input.++module Main (main) where++import NaturalSort (natSort)++import Data.ByteString.Char8 (ByteString)+import qualified Data.ByteString.Char8 as B+import System.Console.GetOpt+import System.Environment (getArgs)+import System.Exit++data Flag = Help | Version deriving Eq++options :: [OptDescr Flag]+options = [Option "" ["help"] (NoArg Help) "Show program help"+ ,Option "" ["version"] (NoArg Version) "Show program version"+ ]++usage, version :: String+usage = usageInfo ("Usage: nsort [OPTION]... [FILE]...\n"+ ++ "Write sorted concatenation of all FILE(s) to stdout.\n")+ options+ ++ "\nWith no FILE read standard input.\n"+version = "nsort 0.2.1"++parseArgv :: [String] -> IO [String]+parseArgv argv =+ case getOpt Permute options argv of+ (flags, args, []) | Help `elem` flags -> putStr usage >>+ exitWith ExitSuccess+ | Version `elem` flags -> putStrLn version >>+ exitWith ExitSuccess+ | otherwise -> return args+ (_, _, errs) -> fail (head errs)++-- Read input from a list of files, or from standard input.+inp :: [FilePath] -> IO ByteString+inp [] = B.getContents+inp xs = B.concat `fmap` mapM B.readFile xs++-- | Main.+main :: IO ()+main = getArgs >>= parseArgv >>= inp >>= B.putStr . B.unlines . natSort+ . B.lines
+ NaturalSort.cabal view
@@ -0,0 +1,94 @@+Name: NaturalSort+Version: 0.2.1+License: BSD3+License-File: COPYING+Copyright: (c) Joachim Fasting 2008-2010+Maintainer: Joachim Fasting <joachim.fasting@gmail.com>+Homepage: http://github.com/joachifm/natsort+Synopsis: Natural sorting for strings+Description: A library for sorting strings "naturally", i.e. taking numerical+ values into account when comparing textual inputs.+ .+ E.g., "1" < "10", and "10 bottles of beer" < "100 bottles of beer".+Category: Text+Tested-With: GHC == 6.12.1+Build-Type: Simple+Cabal-Version: >= 1.6 && < 1.9+Extra-Source-Files: README.md tests/Properties.hs tests/Unit.hs tests/Main.hs+ tests/coverage.lhs++Source-Repository head+ type: git+ location: git://github.com/joachifm/natsort.git++flag base3+ Description: Use base version 3+ Default: False++flag driver+ Description: Build driver program+ Default: False++flag no-lib+ Description: Do not build the library (just the driver)+ Default: False++flag test+ Description: Build test driver+ Default: False++flag coverage+ Description: Build with code coverage+ Default: False++Library+ Exposed-Modules: NaturalSort++ if flag(base3)+ Build-Depends: base >= 3 && < 4+ else+ Build-Depends: base >= 4 && < 5++ Build-Depends: bytestring >= 0.9 && < 1,+ strict ==0.3.*++ if flag(no-lib) || flag(test)+ Buildable: False++Executable nsort+ Hs-Source-Dirs: .+ Main-Is: Main.hs+ Other-Modules: Chunk, NaturalSort++ if flag(base3)+ Build-Depends: base >= 3 && < 4+ else+ Build-Depends: base >= 4 && < 5++ Build-Depends: bytestring >= 0.9 && < 1,+ strict ==0.3.*++ if flag(test) || (!flag(driver) && !flag(no-lib))+ Buildable: False++Executable test+ Hs-Source-Dirs: . tests+ Main-Is: tests/Main.hs+ Other-Modules: NaturalSort++ if flag(base3)+ Build-Depends: base >= 3 && < 4+ else+ Build-Depends: base >= 4 && < 5++ Build-Depends:+ bytestring >= 0.9 && < 1,+ QuickCheck >= 2.1 && < 3,+ strict ==0.3.*+ ghc-options: -Wall -Werror -dcore-lint++ if flag(coverage)+ ghc-options: -fhpc++ if !flag(test)+ Buildable: False
+ NaturalSort.hs view
@@ -0,0 +1,34 @@+-- |+-- Module : NaturalSort+-- Copyright : (c) Joachim Fasting 2008-2010+-- License : BSD3 (see COPYING)+-- Maintainer : joachim.fasting@gmail.com+-- Stability : unstable+-- Portability : unportable+--+-- Natural sorting for strings.++module NaturalSort (natSort, natSortS) where++import Chunk++import Data.ByteString.Char8 (ByteString)+import qualified Data.ByteString.Char8 as B+import Data.List (sortBy)+import Data.Ord (comparing)++-- @sortWith f xs@ is equal to @sortBy (comparing f) xs@, except @f@+-- is applied only once for each element of @xs@.+-- In principle, this is equal to @sort . map f@, but preserves input+-- elements.+sortWith :: Ord b => (a -> b) -> [a] -> [a]+sortWith cmp xs = map snd $ sortBy (comparing fst) (zip (map cmp xs) xs)++-- | Sort a list of 'ByteString's using natural comparison.+natSort :: [ByteString] -> [ByteString]+natSort = sortWith toChunks++-- | Sort a list of 'String's using natural comparison+-- (converts to and from 'ByteString')+natSortS :: [String] -> [String]+natSortS = map B.unpack . natSort . map B.pack
+ README.md view
@@ -0,0 +1,42 @@+# NaturalSort - natural sorting for strings++NaturalSort is a library for sorting strings "naturally", i.e. taking+numerical values into account when comparing textual inputs.++For example, "1" < 10, and "10 bottles of beer" < "100 bottles of beer".++## Getting++* `git pull git://github.com/joachifm/natsort.git`++## Building++The preferred method of building is using [cabal-install]:++ cd natsort+ cabal install++A driver program is also available:++ cabal install -f driver++To run the test suite, do:++ cabal configure -f test+ ./dist/build/test/test++[cabal-install]: http://hackage.haskell.org/package/cabal-install++## Development++To contribute to the project, please create a fork of the [repository].++[repository]: http://github.com/joachifm/natsort++## Licence++NaturalSort is distributed under the terms of the BSD3 license (see COPYING)++## Author(s)++Joachim Fasting \<joachim.fasting@gmail.com\>
+ Setup.lhs view
@@ -0,0 +1,3 @@+#!/usr/bin/env runhaskell+> import Distribution.Simple+> main = defaultMain
+ tests/Main.hs view
@@ -0,0 +1,7 @@+module Main (main) where++import qualified Properties+import qualified Unit++main :: IO ()+main = Unit.main >> Properties.main
+ tests/Properties.hs view
@@ -0,0 +1,44 @@+{-# OPTIONS_GHC -fno-warn-missing-signatures -fno-warn-missing-methods+ -fno-warn-orphans #-}++module Properties (main) where++import Chunk+import NaturalSort++import Data.ByteString.Char8 (ByteString)+import qualified Data.ByteString.Char8 as B+import Data.List+import Data.Ord+import Test.QuickCheck+import Text.Printf++instance Arbitrary ByteString where+ arbitrary = B.pack `fmap` arbitrary++-- Verify that natSort preserves input elements+prop_natSort_integ xs = sort (natSort xs) == sort xs++-- Verify that natSort is idempotent+prop_natSort_idem xs = natSort xs == natSort (natSort xs)++-- Verify that natSort conforms to a model+prop_natSort_model xs = natSort xs == model xs+ where+ model = sortBy (comparing toChunks)++-- Verify that natSortS yields the same result as natSort+prop_natSortS xs = map B.pack (natSortS xs') == natSort xs+ where+ xs' = map B.unpack xs++mytest :: Testable a => a -> Int -> IO ()+mytest f n = quickCheckWith stdArgs { maxSize = n } f++main = mapM_ (\(s, f) -> printf "%-20s: " s >> f ntest) tests+ where+ tests = [("natSort / integrity", mytest prop_natSort_integ)+ ,("natSort / idempotent", mytest prop_natSort_idem)+ ,("natSort / model", mytest prop_natSort_model)+ ,("natSortS", mytest prop_natSortS)]+ ntest = 100
+ tests/Unit.hs view
@@ -0,0 +1,63 @@+{-# OPTIONS_GHC -fno-warn-missing-signatures #-}++module Unit (main) where++import NaturalSort++import qualified Data.ByteString.Char8 as B++unit1 = (["z10.txt"+ ,"z100.txt"+ ,"z400.txt"+ ,"z72.txt"+ ,"z71.txt"+ ,"z20.txt"+ ,"z1.txt"],+ ["z1.txt"+ ,"z10.txt"+ ,"z20.txt"+ ,"z71.txt"+ ,"z72.txt"+ ,"z100.txt"+ ,"z400.txt"])+unit2 = (["a10.txt"+ ,"a2.txt"+ ,"a1.txt"+ ,"a20.txt"+ ,"a2.txt"+ ,"a700.txt"],+ ["a1.txt"+ ,"a2.txt"+ ,"a2.txt"+ ,"a10.txt"+ ,"a20.txt"+ ,"a700.txt"])+unit3 = (["12 Geese a' Quackin'"+ ,"10 Monkeys a' Writin'"+ ,"1 Fish a' Flappin'"+ ,"And a Dwarf in a Pear Tree-e"],+ ["1 Fish a' Flappin'"+ ,"10 Monkeys a' Writin'"+ ,"12 Geese a' Quackin'"+ ,"And a Dwarf in a Pear Tree-e"])+unit4 = (["1c"+ ,"1a"+ ,"1b"],+ ["1a"+ ,"1b"+ ,"1c"])++test :: ([String], [String]) -> Bool+test (inp, out) = natSort inp' == out'+ where+ inp' = map B.pack inp+ out' = map B.pack out++runTests :: [(String, ([String], [String]))] -> IO ()+runTests = mapM_ (\(n, s) -> putStr (n ++ ": ") >>+ putStrLn (if test s then "OK" else "FALSE"))++main = runTests [("unit1", unit1)+ ,("unit2", unit2)+ ,("unit3", unit3)+ ,("unit4", unit4)]
+ tests/coverage.lhs view
@@ -0,0 +1,19 @@+#!/usr/bin/env runhaskell++> module Main (main) where+> import Control.Monad (when)+> import System.Cmd+> import System.Directory+> excludeModules = ["Main", "Properties", "Unit"]+> main = do+> hpcExists <- doesDirectoryExist ".hpc"+> when hpcExists $ do+> removeDirectoryRecursive ".hpc"+> removeFile "test.tix"+> system "cabal configure -f test -f coverage --disable-optimization"+> system "cabal build"+> system "dist/build/test/test >/dev/null"+> system ("hpc markup test.tix --destdir=coverage " ++ exclude)+> system ("hpc report test.tix " ++ exclude)+> where+> exclude = unwords (map ("--exclude=" ++) excludeModules)