hgeometry-0.5.0.0: Geometric Algorithms, Data structures, and Data types.

Data.CircularSeq

Synopsis

# Documentation

data CSeq a Source

Nonempty circular sequence

Instances

 Source Source Source Source Eq a => Eq (CSeq a) Source Show a => Show (CSeq a) Source

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

smart constructor that automatically balances the seq

builds a CSeq

fromList :: [a] -> CSeq a Source

focus :: CSeq a -> a Source

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

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

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

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 Source

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

rotateL :: CSeq a -> CSeq a Source

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 Source

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 Source

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 Source

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

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

asSeq :: CSeq a -> Seq a Source

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

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

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

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