Data.CircularSeq

Documentation

data CSeq a

Nonempty circular sequence

Instances

Functor CSeq

Foldable CSeq

Traversable CSeq

Foldable1 CSeq

Eq a => Eq (CSeq a)

Show a => Show (CSeq a)

cseq :: Seq a -> a -> Seq a -> CSeq a

smart constructor that automatically balances the seq

singleton :: a -> CSeq a

fromNonEmpty :: NonEmpty a -> CSeq a

builds a CSeq

fromList :: [a] -> CSeq a

focus :: CSeq a -> a

Gets the focus of the CSeq running time: O(1)

index :: CSeq a -> Int -> a

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

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

Access te ith item in the CSeq (w.r.t the focus) as a lens

rotateL :: CSeq a -> CSeq a

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

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

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

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

All elements, starting with the focus, going to the right

leftElements :: CSeq a -> Seq a

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

Convert to a single Seq, starting with the focus.

reverseDirection :: CSeq a -> CSeq a

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)

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)

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)