module Data.CircularList.Util where import Control.Lens import Data.Tuple import qualified Data.CircularList as C import qualified Data.List as L -------------------------------------------------------------------------------- -- $setup -- >>> let ordList = C.fromList [5,6,10,20,30,1,2,3] -- | Given a circular list, whose elements are in increasing order, insert the -- new element into the Circular list in its sorted order. -- -- >>> insertOrd 1 C.empty -- fromList [1] -- >>> insertOrd 1 $ C.fromList [2] -- fromList [2,1] -- >>> insertOrd 2 $ C.fromList [1,3] -- fromList [1,2,3] -- >>> insertOrd 31 ordList -- fromList [5,6,10,20,30,31,1,2,3] -- >>> insertOrd 1 ordList -- fromList [5,6,10,20,30,1,1,2,3] -- >>> insertOrd 4 ordList -- fromList [5,6,10,20,30,1,2,3,4] -- >>> insertOrd 11 ordList -- fromList [5,6,10,11,20,30,1,2,3] insertOrd :: Ord a => a -> C.CList a -> C.CList a insertOrd = insertOrdBy compare -- | Insert an element into an increasingly ordered circular list, with -- specified compare operator. insertOrdBy :: (a -> a -> Ordering) -> a -> C.CList a -> C.CList a insertOrdBy cmp x = C.fromList . insertOrdBy' cmp x . C.rightElements -- | List version of insertOrdBy; i.e. the list contains the elements in -- cirulcar order. Again produces a list that has the items in circular order. insertOrdBy' :: (a -> a -> Ordering) -> a -> [a] -> [a] insertOrdBy' cmp x xs = case (rest, x `cmp` head rest) of ([], _) -> L.insertBy cmp x pref (z:zs, GT) -> (z : L.insertBy cmp x zs) ++ pref (_:_, EQ) -> (x : xs) -- == x : rest ++ pref (_:_, LT) -> rest ++ L.insertBy cmp x pref where -- split the list at its maximum. (pref,rest) = splitIncr cmp xs -- given a list of elements that is supposedly a a cyclic-shift of a list of -- increasing items, find the splitting point. I.e. returns a pair of lists -- (ys,zs) such that xs = zs ++ ys, and ys ++ zs is (supposedly) in sorted -- order. splitIncr :: (a -> a -> Ordering) -> [a] -> ([a],[a]) splitIncr _ [] = ([],[]) splitIncr cmp xs@(x:_) = swap . bimap (map snd) (map snd) . L.break (\(a,b) -> (a `cmp` b) == GT) $ zip (x:xs) xs -- | Test if the circular list is a cyclic shift of the second list. -- Running time: O(n), where n is the size of the smallest list isShiftOf :: Eq a => C.CList a -> C.CList a -> Bool xs `isShiftOf` ys = let rest = tail . C.leftElements in maybe False (\xs' -> rest xs' == rest ys) $ C.focus ys >>= flip C.rotateTo xs