data-clist 0.0.4 → 0.0.5

raw patch · 2 files changed

+51/−15 lines, 2 filesdep ~QuickCheckPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: QuickCheck

API changes (from Hackage documentation)

Files

• data-clist.cabal +3/−3
• src/Data/CircularList.hs +48/−12

@@ -5,7 +5,7 @@              Given that the ring terminiology clashes with certain              mathematical branches, we're using the term CList or              CircularList instead.-Version: 0.0.4+Version: 0.0.5 License: BSD3 License-File: LICENSE Author: John Van Enk <vanenkj@gmail.com>@@ -14,11 +14,11 @@ Category: Data Structures Cabal-Version: >= 1.6 Build-Type: Simple-Package-URL: http://github.com/sw17ch/data-clist+Package-URL: https://github.com/sw17ch/data-clist  Library     Build-Depends: base >= 4 && < 5,-                   QuickCheck >= 2.1 && < 2.2+                   QuickCheck >= 2.4 && < 2.5      Exposed-Modules:         Data.CircularList

@@ -10,7 +10,7 @@ often finds in an (Americanized) Chinese Restaurant).  Only the closest item on the table is avialable to us. In order to reach-other elements on the table, we need to rotate the table to the left or +other elements on the table, we need to rotate the table to the left or the right.  Our convention for this problem says that rotations to the right are a@@ -59,13 +59,15 @@     focus, insertL, insertR,     removeL, removeR,     -- ** Manipulation of Focus-    rotR, rotL,+    allRotations, rotR, rotL, rotateTo,     -- ** Manipulation of Packing     balance, packL, packR,     -- ** Information     isEmpty, size, ) where +import Data.List(find,unfoldr)+import Control.Monad(join) import Test.QuickCheck.Arbitrary import Test.QuickCheck.Gen @@ -144,7 +146,7 @@ removeL (CList [] _ []) = Empty removeL (CList (l:ls) _ rs) = CList ls l rs removeL (CList [] _ rs) = let (f:ls) = reverse rs-                          in CList ls f [] +                          in CList ls f []  -- |Remove the focus from the CList. removeR :: CList a -> CList a@@ -156,6 +158,15 @@  {- Manipulating Rotation -} +-- |Return all possible rotations of the provided 'CList', where the+-- focus is the provided 'CList'.+allRotations :: CList a -> CList (CList a)+allRotations Empty = singleton Empty+allRotations cl = CList ls cl rs+  where+    ls = unfoldr (fmap (join (,)) . mRotL) cl+    rs = unfoldr (fmap (join (,)) . mRotR) cl+ -- |Rotate the focus to the previous (left) element. rotL :: CList a -> CList a rotL Empty = Empty@@ -164,6 +175,12 @@ rotL (CList [] f rs) = let (l:ls) = reverse rs                        in CList ls l [f] +-- |A non-cyclic version of 'rotL'; that is, only rotate the focus if+-- there is a previous (left) element to rotate to.+mRotL :: CList a -> Maybe (CList a)+mRotL (CList (l:ls) f rs) = Just $ CList ls l (f:rs)+mRotL _ = Nothing+ -- |Rotate the focus to the next (right) element. rotR :: CList a -> CList a rotR Empty = Empty@@ -172,6 +189,17 @@ rotR (CList ls f []) = let (r:rs) = reverse ls                        in CList [f] r rs +-- |A non-cyclic version of 'rotL'; that is, only rotate the focus if+-- there is a previous (left) element to rotate to.+mRotR :: CList a -> Maybe (CList a)+mRotR (CList ls f (r:rs)) = Just $ CList (f:ls) r rs+mRotR _ = Nothing++-- |Rotate the 'CList' such that the specified element (if it exists)+-- is focused.+rotateTo :: (Eq a) => a -> CList a -> Maybe (CList a)+rotateTo a = find (maybe False (a==) . focus) . toList . allRotations+ {- Manipulating Packing -}  -- |Balance the CList. Equivalent to `fromList . toList`@@ -202,18 +230,26 @@  {- Instances -} --- | The show instance prints a tuple of the--- balanced CList where the left list's right-most--- element is the first element to the left. The--- left most-most element of the right list is the--- next element to the right. instance (Show a) => Show (CList a) where-    show cl = case balance cl of-                     (CList l f r) -> show (reverse l,f,r)-                     Empty -> "Empty"+ showsPrec d cl  = showParen (d > 10) $+                   showString "fromList " . shows (toList cl) +instance (Read a) => Read (CList a) where+ readsPrec p = readParen (p > 10) $ \ r -> do+   ("fromList",s) <- lex r+   (xs,t) <- reads s+   return (fromList xs,t)+ instance (Eq a) => Eq (CList a) where-    a == b = (toList a) == (toList b)+  a == b = any (identical a) . toList $ allRotations b++-- |Determine if two 'CList's are structurally identical.+identical :: (Eq a) => CList a -> CList a -> Bool+identical Empty Empty = True+identical (CList ls1 f1 rs1) (CList ls2 f2 rs2) = f1 == f2+                                                  && ls1 == ls2+                                                  && rs1 == rs2+identical _ _ = False  instance Arbitrary a => Arbitrary (CList a) where     arbitrary = frequency [(1, return Empty), (10, arbCList)]