hgeometry-0.7.0.0: Geometric Algorithms, Data structures, and Data types.

Data.CircularSeq

Synopsis

# Documentation

data CSeq a Source #

Nonempty circular sequence

Instances
 Source # Instance detailsDefined in Data.CircularSeq Methodsfmap :: (a -> b) -> CSeq a -> CSeq b #(<$) :: a -> CSeq b -> CSeq a # Source # Instance detailsDefined in Data.CircularSeq Methodsfold :: Monoid m => CSeq m -> m #foldMap :: Monoid m => (a -> m) -> CSeq a -> m #foldr :: (a -> b -> b) -> b -> CSeq a -> b #foldr' :: (a -> b -> b) -> b -> CSeq a -> b #foldl :: (b -> a -> b) -> b -> CSeq a -> b #foldl' :: (b -> a -> b) -> b -> CSeq a -> b #foldr1 :: (a -> a -> a) -> CSeq a -> a #foldl1 :: (a -> a -> a) -> CSeq a -> a #toList :: CSeq a -> [a] #null :: CSeq a -> Bool #length :: CSeq a -> Int #elem :: Eq a => a -> CSeq a -> Bool #maximum :: Ord a => CSeq a -> a #minimum :: Ord a => CSeq a -> a #sum :: Num a => CSeq a -> a #product :: Num a => CSeq a -> a # Source # Instance detailsDefined in Data.CircularSeq Methodstraverse :: Applicative f => (a -> f b) -> CSeq a -> f (CSeq b) #sequenceA :: Applicative f => CSeq (f a) -> f (CSeq a) #mapM :: Monad m => (a -> m b) -> CSeq a -> m (CSeq b) #sequence :: Monad m => CSeq (m a) -> m (CSeq a) # Source # Instance detailsDefined in Data.CircularSeq Methodsfold1 :: Semigroup m => CSeq m -> m #foldMap1 :: Semigroup m => (a -> m) -> CSeq a -> m #toNonEmpty :: CSeq a -> NonEmpty a # Eq a => Eq (CSeq a) Source # Instance detailsDefined in Data.CircularSeq Methods(==) :: CSeq a -> CSeq a -> Bool #(/=) :: CSeq a -> CSeq a -> Bool # Show a => Show (CSeq a) Source # Instance detailsDefined in Data.CircularSeq MethodsshowsPrec :: Int -> CSeq a -> ShowS #show :: CSeq a -> String #showList :: [CSeq a] -> ShowS # Generic (CSeq a) Source # Instance detailsDefined in Data.CircularSeq Associated Typestype Rep (CSeq a) :: * -> * # Methodsfrom :: CSeq a -> Rep (CSeq a) x #to :: Rep (CSeq a) x -> CSeq a # NFData a => NFData (CSeq a) Source # Instance detailsDefined in Data.CircularSeq Methodsrnf :: CSeq a -> () # type Rep (CSeq a) Source # Instance detailsDefined in Data.CircularSeq type Rep (CSeq a) = D1 (MetaData "CSeq" "Data.CircularSeq" "hgeometry-0.7.0.0-3y7zA7ljCTE9s6EHvXHItM" False) (C1 (MetaCons "CSeq" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Seq a)) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Seq a))))) cseq :: Seq a -> a -> Seq a -> CSeq a Source # smart constructor that automatically balances the seq builds a CSeq fromList :: [a] -> CSeq a Source # focus :: CSeq a -> a Source # Gets the focus of the CSeq running time: O(1) index :: CSeq a -> Int -> a Source # Access the i^th item (w.r.t the focus) in the CSeq (indices modulo n). running time: $$O(\log (i \mod n))$$ >>> index (fromList [0..5]) 1 1 >>> index (fromList [0..5]) 2 2 >>> index (fromList [0..5]) 5 5 >>> index (fromList [0..5]) 10 4 >>> index (fromList [0..5]) 6 0 >>> index (fromList [0..5]) (-1) 5 >>> index (fromList [0..5]) (-6) 0  adjust :: (a -> a) -> Int -> CSeq a -> CSeq a Source # Adjusts the i^th element w.r.t the focus in the CSeq running time: $$O(\log (i \mod n))$$ >>> adjust (const 1000) 2 (fromList [0..5]) CSeq [0,1,1000,3,4,5]  item :: Int -> Lens' (CSeq a) a Source # Access te ith item in the CSeq (w.r.t the focus) as a lens rotateL :: CSeq a -> CSeq a Source # rotates the focus to the left running time: O(1) (amortized) >>> rotateL$ fromList [3,4,5,1,2]
CSeq [2,3,4,5,1]
>>> mapM_ print . take 5 $iterate rotateL$ fromList [1..5]
CSeq [1,2,3,4,5]
CSeq [5,1,2,3,4]
CSeq [4,5,1,2,3]
CSeq [3,4,5,1,2]
CSeq [2,3,4,5,1]


rotateR :: CSeq a -> CSeq a Source #

rotates one to the right

running time: O(1) (amortized)

>>> rotateR $fromList [3,4,5,1,2] CSeq [4,5,1,2,3]  rotateNL :: Int -> CSeq a -> CSeq a Source # Rotates i elements to the left. pre: 0 <= i < n running time: $$O(\log i)$$ amoritzed >>> rotateNL 0$ fromList [1..5]
CSeq [1,2,3,4,5]
>>> rotateNL 1 $fromList [1..5] CSeq [5,1,2,3,4] >>> rotateNL 2$ fromList [1..5]
CSeq [4,5,1,2,3]
>>> rotateNL 3 $fromList [1..5] CSeq [3,4,5,1,2] >>> rotateNL 4$ fromList [1..5]
CSeq [2,3,4,5,1]


rotateNR :: Int -> CSeq a -> CSeq a Source #

Rotates i elements to the right.

pre: 0 <= i < n

running time: $$O(\log i)$$ amortized

>>> rotateNR 0 $fromList [1..5] CSeq [1,2,3,4,5] >>> rotateNR 1$ fromList [1..5]
CSeq [2,3,4,5,1]
>>> rotateNR 4 $fromList [1..5] CSeq [5,1,2,3,4]  rightElements :: CSeq a -> Seq a Source # All elements, starting with the focus, going to the right leftElements :: CSeq a -> Seq a Source # All elements, starting with the focus, going to the left >>> leftElements$ fromList [3,4,5,1,2]
fromList [3,2,1,5,4]


asSeq :: CSeq a -> Seq a Source #

Convert to a single Seq, starting with the focus.

Reversres the direction of the CSeq

running time: $$O(n)$$

>>> reverseDirection $fromList [1..5] CSeq [1,5,4,3,2]  allRotations :: CSeq a -> CSeq (CSeq a) Source # All rotations, the input CSeq is the focus. >>> mapM_ print . allRotations$ fromList [1..5]
CSeq [1,2,3,4,5]
CSeq [2,3,4,5,1]
CSeq [3,4,5,1,2]
CSeq [4,5,1,2,3]
CSeq [5,1,2,3,4]


findRotateTo :: (a -> Bool) -> CSeq a -> Maybe (CSeq a) Source #

Finds an element in the CSeq

>>> findRotateTo (== 3) $fromList [1..5] Just (CSeq [3,4,5,1,2]) >>> findRotateTo (== 7)$ fromList [1..5]
Nothing


rotateTo :: Eq a => a -> CSeq a -> Maybe (CSeq a) Source #

zipLWith :: (a -> b -> c) -> CSeq a -> CSeq b -> CSeq c Source #

"Left zip": zip the two CLists, pairing up every element in the *left* list with its corresponding element in the right list. If there are more items in the right clist they are discarded.

zipL :: CSeq a -> CSeq b -> CSeq (a, b) Source #

see 'zipLWith

zip3LWith :: (a -> b -> c -> d) -> CSeq a -> CSeq b -> CSeq c -> CSeq d Source #

same as zipLWith but with three items

insertOrd :: Ord a => a -> CSeq a -> CSeq a Source #

Given a circular seq, whose elements are in increasing order, insert the new element into the Circular seq in its sorted order.

>>> insertOrd 1 $fromList [2] CSeq [2,1] >>> insertOrd 2$ fromList [1,3]
CSeq [1,2,3]
>>> insertOrd 31 ordList
CSeq [5,6,10,20,30,31,1,2,3]
>>> insertOrd 1 ordList
CSeq [5,6,10,20,30,1,1,2,3]
>>> insertOrd 4 ordList
CSeq [5,6,10,20,30,1,2,3,4]
>>> insertOrd 11 ordList
CSeq [5,6,10,11,20,30,1,2,3]


running time: $$O(n)$$

insertOrdBy :: (a -> a -> Ordering) -> a -> CSeq a -> CSeq a Source #

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

running time: $$O(n)$$

isShiftOf :: Eq a => CSeq a -> CSeq a -> Bool Source #

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