Safe Haskell | None |
---|---|

Language | Haskell2010 |

- data CSeq a
- cseq :: Seq a -> a -> Seq a -> CSeq a
- singleton :: a -> CSeq a
- fromNonEmpty :: NonEmpty a -> CSeq a
- fromList :: [a] -> CSeq a
- focus :: CSeq a -> a
- index :: CSeq a -> Int -> a
- adjust :: (a -> a) -> Int -> CSeq a -> CSeq a
- item :: Int -> Lens' (CSeq a) a
- rotateL :: CSeq a -> CSeq a
- rotateR :: CSeq a -> CSeq a
- rotateNL :: Int -> CSeq a -> CSeq a
- rotateNR :: Int -> CSeq a -> CSeq a
- rightElements :: CSeq a -> Seq a
- leftElements :: CSeq a -> Seq a
- asSeq :: CSeq a -> Seq a
- reverseDirection :: CSeq a -> CSeq a
- allRotations :: CSeq a -> CSeq (CSeq a)
- findRotateTo :: (a -> Bool) -> CSeq a -> Maybe (CSeq a)
- rotateTo :: Eq a => a -> CSeq a -> Maybe (CSeq a)

# Documentation

Nonempty circular sequence

fromNonEmpty :: NonEmpty a -> CSeq a Source

builds a CSeq

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

`>>>`

1`index (fromList [0..5]) 1`

`>>>`

2`index (fromList [0..5]) 2`

`>>>`

5`index (fromList [0..5]) 5`

`>>>`

4`index (fromList [0..5]) 10`

`>>>`

0`index (fromList [0..5]) 6`

`>>>`

5`index (fromList [0..5]) (-1)`

`>>>`

0`index (fromList [0..5]) (-6)`

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

`>>>`

CSeq [0,1,1000,3,4,5]`adjust (const 1000) 2 (fromList [0..5])`

rotateL :: CSeq a -> CSeq a Source

rotates the focus to the left

running time: O(1) (amortized)

`>>>`

CSeq [2,3,4,5,1]`rotateL $ fromList [3,4,5,1,2]`

`>>>`

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]`mapM_ print . take 5 $ iterate rotateL $ fromList [1..5]`

rotateR :: CSeq a -> CSeq a Source

rotates one to the right

running time: O(1) (amortized)

`>>>`

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

rotateNL :: Int -> CSeq a -> CSeq a Source

Rotates i elements to the left.

pre: 0 <= i < n

running time: $O(log i)$ amoritzed

`>>>`

CSeq [1,2,3,4,5]`rotateNL 0 $ fromList [1..5]`

`>>>`

CSeq [5,1,2,3,4]`rotateNL 1 $ fromList [1..5]`

`>>>`

CSeq [4,5,1,2,3]`rotateNL 2 $ fromList [1..5]`

`>>>`

CSeq [3,4,5,1,2]`rotateNL 3 $ fromList [1..5]`

`>>>`

CSeq [2,3,4,5,1]`rotateNL 4 $ fromList [1..5]`

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

Rotates i elements to the right.

pre: 0 <= i < n

running time: $O(log i)$ amortized

`>>>`

CSeq [1,2,3,4,5]`rotateNR 0 $ fromList [1..5]`

`>>>`

CSeq [2,3,4,5,1]`rotateNR 1 $ fromList [1..5]`

`>>>`

CSeq [5,1,2,3,4]`rotateNR 4 $ fromList [1..5]`

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

`>>>`

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

reverseDirection :: CSeq a -> CSeq a Source

Reversres the direction of the CSeq

running time: $O(n)$

`>>>`

CSeq [1,5,4,3,2]`reverseDirection $ fromList [1..5]`

allRotations :: CSeq a -> CSeq (CSeq a) Source

All rotations, the input CSeq is the focus.

`>>>`

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]`mapM_ print . allRotations $ fromList [1..5]`