Documentation

Nonempty circular sequence

smart constructor that automatically balances the seq

O(1) CSeq with exactly one element.

builds a CSeq

O(n) Convert from a list to a CSeq.

Warning: the onus is on the user to ensure that their list is not empty, otherwise all bets are off!

Gets the focus of the CSeq.

running time: O(1)

Access the i^th item (w.r.t the focus; elements numbered in increasing order towards the right) 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 the 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.

Label the elements with indices.

>>> withIndices $ fromList [0..5]
CSeq [0 :+ 0,1 :+ 1,2 :+ 2,3 :+ 3,4 :+ 4,5 :+ 5]

Reverses 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

Rotate to a specific element in the CSeq.

"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.

see 'zipLWith

same as zipLWith but with three items

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)\)

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

running time: \(O(n)\)

Test if the circular list is a cyclic shift of the second list. We have that

(xs `isShiftOf` ys) == (xs `elem` allRotations (ys :: CSeq Int))

Running time: \(O(n+m)\), where \(n\) and \(m\) are the sizes of the lists.