Data.CircularList.Util

Documentation

>>> let ordList = C.fromList [5,6,10,20,30,1,2,3]

insertOrd :: Ord a => a -> CList a -> CList a

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]

insertOrdBy :: (a -> a -> Ordering) -> a -> CList a -> CList a

Insert an element into an increasingly ordered circular list, with specified compare operator.

insertOrdBy' :: (a -> a -> Ordering) -> a -> [a] -> [a]

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.

splitIncr :: (a -> a -> Ordering) -> [a] -> ([a], [a])

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.

isShiftOf :: Eq a => CList a -> CList a -> Bool

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