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

Language | Haskell2010 |

## Synopsis

- 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)
- zipLWith :: (a -> b -> c) -> CSeq a -> CSeq b -> CSeq c
- zipL :: CSeq a -> CSeq b -> CSeq (a, b)
- zip3LWith :: (a -> b -> c -> d) -> CSeq a -> CSeq b -> CSeq c -> CSeq d
- insertOrd :: Ord a => a -> CSeq a -> CSeq a
- insertOrdBy :: (a -> a -> Ordering) -> a -> CSeq a -> CSeq a
- isShiftOf :: Eq a => CSeq a -> CSeq a -> Bool

# Documentation

Nonempty circular sequence

## Instances

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]`

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

Finds an element in the CSeq

`>>>`

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

`>>>`

Nothing`findRotateTo (== 7) $ fromList [1..5]`

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.

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.

`>>>`

CSeq [2,1]`insertOrd 1 $ fromList [2]`

`>>>`

CSeq [1,2,3]`insertOrd 2 $ fromList [1,3]`

`>>>`

CSeq [5,6,10,20,30,31,1,2,3]`insertOrd 31 ordList`

`>>>`

CSeq [5,6,10,20,30,1,1,2,3]`insertOrd 1 ordList`

`>>>`

CSeq [5,6,10,20,30,1,2,3,4]`insertOrd 4 ordList`

`>>>`

CSeq [5,6,10,11,20,30,1,2,3]`insertOrd 11 ordList`

running time: \(O(n)\)