sym 0.2.1 → 0.2.2
raw patch · 6 files changed
+207/−54 lines, 6 files
Files
- Math/Sym/Internal.hs +46/−1
- Math/Sym/Stat.hs +49/−25
- cbits/stat.c +62/−0
- include/stat.h +3/−0
- sym.cabal +1/−1
- tests/Properties.hs +46/−27
Math/Sym/Internal.hs view
@@ -77,7 +77,13 @@ , comp -- components , ep -- rank a la Elizalde & Pak , dim -- dimension+ , asc0 -- small ascents+ , des0 -- small descents + -- * List valued permutation statistics+ , lminValues+ , lminIndices+ -- * Sorting operators , stackSort , bubbleSort@@ -104,7 +110,7 @@ , head, last, filter, maximum, minimum, null, reverse, map ) import qualified Data.Vector.Storable.Mutable as MV- ( unsafeNew, unsafeWrite, unsafeWith, swap, replicate+ ( unsafeNew, unsafeWrite, unsafeWith, unsafeSlice, swap, replicate ) import Foreign (Ptr, castPtr) import System.IO.Unsafe (unsafePerformIO)@@ -353,6 +359,12 @@ foreign import ccall unsafe "stat.h dim" c_dim :: Ptr CLong -> CLong -> CLong +foreign import ccall unsafe "stat.h asc0" c_asc0+ :: Ptr CLong -> CLong -> CLong++foreign import ccall unsafe "stat.h des0" c_des0+ :: Ptr CLong -> CLong -> CLong+ -- Marshal a permutation statistic defined in C to on in Haskell. stat :: (Ptr CLong -> CLong -> CLong) -> Perm0 -> Int stat f w = unsafePerformIO $@@ -451,6 +463,39 @@ dim :: Perm0 -> Int dim = stat c_dim +-- | The number of small ascents.+asc0 :: Perm0 -> Int+asc0 = stat c_asc0++-- | The number of small descents.+des0 :: Perm0 -> Int+des0 = stat c_des0++-- Vector valued permutation statistics+-- ----------------------------------++foreign import ccall unsafe "stat.h lmin_values" c_lmin_values+ :: Ptr CLong -> Ptr CLong -> CLong -> IO CLong++foreign import ccall unsafe "stat.h lmin_indices" c_lmin_indices+ :: Ptr CLong -> Ptr CLong -> CLong -> IO CLong++record :: (Ptr CLong -> Ptr CLong -> CLong -> IO CLong) -> Perm0 -> SV.Vector Int+record f w = unsafePerformIO $ do+ let n = SV.length w+ v <- MV.unsafeNew n+ SV.unsafeWith w $ \w_ptr ->+ MV.unsafeWith v $ \v_ptr -> do+ k <- f (castPtr v_ptr) (castPtr w_ptr) (fromIntegral n)+ SV.unsafeFreeze $ MV.unsafeSlice 0 (fromIntegral k) v++-- | The list of values of left-to-right minima+lminValues :: Perm0 -> SV.Vector Int+lminValues = record c_lmin_values++-- | The list of indices of left-to-right minima+lminIndices :: Perm0 -> SV.Vector Int+lminIndices = record c_lmin_indices -- Sorting operators -- -----------------
Math/Sym/Stat.hs view
@@ -19,29 +19,33 @@ module Math.Sym.Stat (- asc -- ascents- , des -- descents- , exc -- excedances- , fp -- fixed points- , inv -- inversions- , maj -- the major index- , peak -- peaks- , vall -- valleys- , dasc -- double ascents- , ddes -- double descents- , lmin -- left-to-right minima- , lmax -- left-to-right maxima- , rmin -- right-to-left minima- , rmax -- right-to-left maxima- , head -- the first element- , last -- the last element- , lir -- left-most increasing run- , ldr -- left-most decreasing run- , rir -- right-most increasing run- , rdr -- right-most decreasing run- , comp -- components- , ep -- rank a la Elizalde & Pak- , dim -- dimension+ asc -- ascents+ , des -- descents+ , exc -- excedances+ , fp -- fixed points+ , inv -- inversions+ , maj -- the major index+ , peak -- peaks+ , vall -- valleys+ , dasc -- double ascents+ , ddes -- double descents+ , lmin -- left-to-right minima+ , lmax -- left-to-right maxima+ , rmin -- right-to-left minima+ , rmax -- right-to-left maxima+ , head -- the first element+ , last -- the last element+ , lir -- left-most increasing run+ , ldr -- left-most decreasing run+ , rir -- right-most increasing run+ , rdr -- right-most decreasing run+ , comp -- components+ , ep -- rank a la Elizalde & Pak+ , dim -- dimension+ , asc0 -- small ascents+ , des0 -- small descents+ , lminValues+ , lminIndices ) where import Prelude hiding (head, last)@@ -49,10 +53,12 @@ import Math.Sym.Internal (Perm0) import qualified Math.Sym.Internal as I ( asc, des, exc, fp, inv, maj, peak, vall, dasc, ddes, lmin, lmax, rmin, rmax- , head, last, lir, ldr, rir, rdr, comp, ep, dim+ , head, last, lir, ldr, rir, rdr, comp, ep, dim, asc0, des0+ , lminValues, lminIndices )+import qualified Data.Vector.Storable as SV (toList) -generalize :: Perm a => (Perm0 -> Int) -> a -> Int+generalize :: Perm a => (Perm0 -> b) -> a -> b generalize f = f . toVector . st -- | The number of ascents. An /ascent/ in @w@ is an index @i@ such@@ -158,3 +164,21 @@ -- non-fixed-point, or zero if all points are fixed. dim :: Perm a => a -> Int dim = generalize I.dim++-- | The number of small ascents. A /small ascent/ in @w@ is an index+-- @i@ such that @w[i] + 1 == w[i+1]@.+asc0 :: Perm a => a -> Int+asc0 = generalize I.asc0++-- | The number of small descents. A /small descent/ in @w@ is an+-- index @i@ such that @w[i] == w[i+1] + 1@.+des0 :: Perm a => a -> Int+des0 = generalize I.des0++-- | The list of values of left-to-right minima+lminValues :: Perm a => a -> [Int]+lminValues = generalize (SV.toList . I.lminValues)++-- | The list of indices of left-to-right minima+lminIndices :: Perm a => a -> [Int]+lminIndices = generalize (SV.toList . I.lminIndices)
cbits/stat.c view
@@ -255,3 +255,65 @@ } return j; }++/* The number of small ascents: i such that w[i] + 1 == w[i+1] */+long+asc0(const long *w, long len)+{+ long acc = 0;++ for (; len > 1; len--, w++) {+ if (*w + 1 == *(w+1))+ acc++;+ }+ return acc;+}+++/* The number of small descents: i such that w[i] == w[i+1] + 1*/+long+des0(const long *w, long len)+{+ long acc = 0;++ for (; len > 1; len--, w++) {+ if (*w == *(w+1) + 1)+ acc++;+ }+ return acc;+}+++/* The array of left-to-right minima */+long+lmin_values(long *v, const long *w, long len)+{+ long m = *w + 1;+ long acc = 0;++ for (; len > 0; len--, w++) {+ if (*w < m) {+ m = *w;+ acc++;+ *(v++) = m;+ }+ }+ return acc;+}++/* The array of indices of left-to-right minima */+long+lmin_indices(long *v, const long *w, long len)+{+ long i, m = *w + 1;+ long acc = 0;++ for (i = 0; i < len; i++, w++) {+ if (*w < m) {+ m = *w;+ acc++;+ *(v++) = i;+ }+ }+ return acc;+}
include/stat.h view
@@ -14,3 +14,6 @@ long ldr (const long *, long); /* left-most decreasing run */ long comp (const long *, long); /* components */ long ep (const long *, long); /* rank a la Elizalde & Pak */++long lmin_values (long *, const long *, long);+long lmin_indices (long *, const long *, long);
sym.cabal view
@@ -1,5 +1,5 @@ Name: sym-Version: 0.2.1+Version: 0.2.2 Synopsis: Permutations, patterns, and statistics Description: Definitions for permutations with an emphasis on permutation
tests/Properties.hs view
@@ -470,10 +470,13 @@ des, asc, inv, lmin, lmax, rmin, rmax, peak, vall :: [Int] -> Int dasc, ddes, maj, comp, ep, dim :: [Int] -> Int -dim w = maximum $ 0 : [ i | (i,x) <- zip [0..] (st w), i /= x ]-maj w = sum [ i | (i,x,y) <- zip3 [1..] w (tail w), x > y ]-des = length . descents+dim w = maximum $ 0 : [ i | (i,x) <- zip [0..] (st w), i /= x ]+maj w = sum [ i | (i,x,y) <- zip3 [1..] w (tail w), x > y ]+asc0 w = sum [ 1 | (x,y) <- ascents $ st w, y-x == 1 ]+des0 w = sum [ 1 | (x,y) <- descents $ st w, x-y == 1 ]+ asc = length . ascents+des = length . descents inv = length . inversions lmin = length . lMinima lmax = length . lMaxima@@ -507,34 +510,50 @@ prop_rdr = forAll perm $ \w -> rdr w == S.rdr w prop_comp = forAll perm $ \w -> comp w == S.comp w prop_dim = forAll perm $ \w -> dim w == S.dim w+prop_asc0 = forAll perm $ \w -> asc0 w == S.asc0 w+prop_des0 = forAll perm $ \w -> des0 w == S.des0 w prop_inv_21 = forAll perm $ \w -> S.inv w == length (Sym.copiesOf (Sym.st "21") w) +prop_lmin_values =+ forAll perm $ \w -> lMinima (st w) == S.lminValues w+prop_lmin_indices =+ forAll perm $ \w -> [ head $ elemIndices x w | x <- lMinima w ] == S.lminIndices w+prop_lmin_card =+ forAll perm $ \w -> and [ S.lmin w == length (S.lminValues w)+ , S.lmin w == length (S.lminIndices w)+ ]+ testsStat =- [ ("asc", check prop_asc)- , ("des", check prop_des)- , ("exc", check prop_exc)- , ("fp", check prop_fp)- , ("inv", check prop_inv)- , ("maj", check prop_maj)- , ("lmin", check prop_lmin)- , ("lmax", check prop_lmax)- , ("rmin", check prop_rmin)- , ("rmax", check prop_rmax)- , ("head", check prop_head)- , ("last", check prop_last)- , ("peak", check prop_peak)- , ("vall", check prop_vall)- , ("dasc", check prop_dasc)- , ("ddes", check prop_ddes)- , ("ep", check prop_ep)- , ("lir", check prop_lir)- , ("ldr", check prop_ldr)- , ("rir", check prop_rir)- , ("rdr", check prop_rdr)- , ("comp", check prop_comp)- , ("dim", check prop_dim)- , ("inv/21", check prop_inv_21)+ [ ("asc", check prop_asc)+ , ("des", check prop_des)+ , ("exc", check prop_exc)+ , ("fp", check prop_fp)+ , ("inv", check prop_inv)+ , ("maj", check prop_maj)+ , ("lmin", check prop_lmin)+ , ("lmax", check prop_lmax)+ , ("rmin", check prop_rmin)+ , ("rmax", check prop_rmax)+ , ("head", check prop_head)+ , ("last", check prop_last)+ , ("peak", check prop_peak)+ , ("vall", check prop_vall)+ , ("dasc", check prop_dasc)+ , ("ddes", check prop_ddes)+ , ("ep", check prop_ep)+ , ("lir", check prop_lir)+ , ("ldr", check prop_ldr)+ , ("rir", check prop_rir)+ , ("rdr", check prop_rdr)+ , ("comp", check prop_comp)+ , ("dim", check prop_dim)+ , ("asc0", check prop_asc0)+ , ("des0", check prop_des0)+ , ("inv/21", check prop_inv_21)+ , ("lmin/values", check prop_lmin_values)+ , ("lmin/indices", check prop_lmin_indices)+ , ("lmin/card", check prop_lmin_card) ] ---------------------------------------------------------------------------------