Documentation

Nonempty circular sequence

smart constructor that automatically balances the seq

builds a CSeq

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

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

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]

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

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]

rotates one to the right

running time: O(1) (amortized)

>>> rotateR $ fromList [3,4,5,1,2]
CSeq [4,5,1,2,3]

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]

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]

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

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

>>> leftElements $ fromList [3,4,5,1,2]
fromList [3,2,1,5,4]

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]

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]

Finds an element in the CSeq

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