cardano-data-1.2.3.0: Specialized data for Cardano project
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.OSet.Strict

Synopsis

Documentation

data OSet a where Source #

A general-purpose finite, ordered, set that is strict in its values.

The strictness is enforced by the underlying StrictSeq from base, and the uniqueness of the values is enforced in this module, by the constructing functions by leveraging an accompanying Set.

TODO: @aniketd Implement DecShareCBOR

Bundled Patterns

pattern EmptyOSet a 
pattern (:<|:)Ord a ⇒ a → OSet a → OSet a infixr 5

\(O(\log n)\).

pattern (:|>:)Ord a ⇒ OSet a → a → OSet a infixl 5

\(O(\log n)\).

Instances

Instances details
Foldable OSet Source # 
Instance details

Defined in Data.OSet.Strict

Methods

foldMonoid m ⇒ OSet m → m Source #

foldMapMonoid m ⇒ (a → m) → OSet a → m Source #

foldMap'Monoid m ⇒ (a → m) → OSet a → m Source #

foldr ∷ (a → b → b) → b → OSet a → b Source #

foldr' ∷ (a → b → b) → b → OSet a → b Source #

foldl ∷ (b → a → b) → b → OSet a → b Source #

foldl' ∷ (b → a → b) → b → OSet a → b Source #

foldr1 ∷ (a → a → a) → OSet a → a Source #

foldl1 ∷ (a → a → a) → OSet a → a Source #

toListOSet a → [a] Source #

nullOSet a → Bool Source #

lengthOSet a → Int Source #

elemEq a ⇒ a → OSet a → Bool Source #

maximumOrd a ⇒ OSet a → a Source #

minimumOrd a ⇒ OSet a → a Source #

sumNum a ⇒ OSet a → a Source #

productNum a ⇒ OSet a → a Source #

ToJSON a ⇒ ToJSON (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Ord a ⇒ Monoid (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

memptyOSet a Source #

mappendOSet a → OSet a → OSet a Source #

mconcat ∷ [OSet a] → OSet a Source #

Ord a ⇒ Semigroup (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

(<>)OSet a → OSet a → OSet a Source #

sconcatNonEmpty (OSet a) → OSet a Source #

stimesIntegral b ⇒ b → OSet a → OSet a Source #

Ord a ⇒ IsList (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Associated Types

type Item (OSet a) Source #

Methods

fromList ∷ [Item (OSet a)] → OSet a Source #

fromListNInt → [Item (OSet a)] → OSet a Source #

toListOSet a → [Item (OSet a)] Source #

Generic (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Associated Types

type Rep (OSet a) ∷ TypeType Source #

Methods

fromOSet a → Rep (OSet a) x Source #

toRep (OSet a) x → OSet a Source #

Show a ⇒ Show (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

showsPrecIntOSet a → ShowS Source #

showOSet a → String Source #

showList ∷ [OSet a] → ShowS Source #

(Show a, Ord a, DecCBOR a) ⇒ DecCBOR (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

decCBORDecoder s (OSet a) Source #

dropCBORProxy (OSet a) → Decoder s () Source #

labelProxy (OSet a) → Text Source #

EncCBOR a ⇒ EncCBOR (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

encCBOROSet a → Encoding Source #

encodedSizeExpr ∷ (∀ t. EncCBOR t ⇒ Proxy t → Size) → Proxy (OSet a) → Size Source #

encodedListSizeExpr ∷ (∀ t. EncCBOR t ⇒ Proxy t → Size) → Proxy [OSet a] → Size Source #

NFData a ⇒ NFData (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

rnfOSet a → () Source #

Eq a ⇒ Eq (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

(==)OSet a → OSet a → Bool Source #

(/=)OSet a → OSet a → Bool Source #

Ord a ⇒ Ord (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

Methods

compareOSet a → OSet a → Ordering Source #

(<)OSet a → OSet a → Bool Source #

(<=)OSet a → OSet a → Bool Source #

(>)OSet a → OSet a → Bool Source #

(>=)OSet a → OSet a → Bool Source #

maxOSet a → OSet a → OSet a Source #

minOSet a → OSet a → OSet a Source #

NoThunks a ⇒ NoThunks (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

type Item (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

type Item (OSet a) = a
type Rep (OSet a) Source # 
Instance details

Defined in Data.OSet.Strict

type Rep (OSet a) = D1 ('MetaData "OSet" "Data.OSet.Strict" "cardano-data-1.2.3.0-inplace" 'False) (C1 ('MetaCons "OSet" 'PrefixI 'True) (S1 ('MetaSel ('Just "osSSeq") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (StrictSeq a)) :*: S1 ('MetaSel ('Just "osSet") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (Set a))))

nullOSet a → Bool Source #

\( O(1) \).

sizeOSet a → Int Source #

\( O(1) \).

emptyOSet a Source #

\( O(1) \).

singleton ∷ a → OSet a Source #

\( O(1) \). Strict in its argument.

lookupIntOSet a → Maybe a Source #

\( O(\log(\min(i,n-i))) \). The element at the specified position, counting from 0. If the specified position is negative or at least the length of the sequence, lookup returns Nothing.

memberOrd a ⇒ a → OSet a → Bool Source #

\(O(\log n)\). Membership check.

(!?)OSet a → IntMaybe a Source #

fliped version of lookup

fromListOrd a ⇒ [a] → OSet a Source #

\(O(n \log n)\). Convert to an OSet from a List.

fromStrictSeqOrd a ⇒ StrictSeq a → OSet a Source #

\(O(n \log n)\). Checks membership before snoc-ing. De-duplicates the StrictSeq without overwriting.

fromStrictSeqDuplicatesOrd a ⇒ StrictSeq a → (Set a, OSet a) Source #

\(O(n \log n)\). Checks membership before snoc-ing. Returns a 2-tuple, with fst as a Set of duplicates found and the snd as the de-duplicated OSet without overwriting. Starts from the left or head, using foldl`

toStrictSeqOSet a → StrictSeq a Source #

\( O(1) \) - Extract underlying strict sequence

toSetOSet a → Set a Source #

\( O(1) \) - Extract underlying Set

fromSetSet a → OSet a Source #

\( O(n) \).

fromFoldable ∷ (Foldable f, Ord a) ⇒ f a → OSet a Source #

Using a Foldable instance of the source data structure convert it to an OSet

fromFoldableDuplicates ∷ (Foldable f, Ord a) ⇒ f a → (Set a, OSet a) Source #

\(O(n \log n)\). Checks membership before snoc-ing. Returns a 2-tuple, with fst as a Set of duplicates found and the snd as the de-duplicated OSet without overwriting.

invariantHoldsOSet a → Bool Source #

\( O(1) \). Shallow invariant using just length and size.

invariantHolds'Ord a ⇒ OSet a → Bool Source #

\( O(n \log n) \). Deep invariant using set membership check for each value. By the pigeon-hole principle, this check is exhaustive.

(|>)Ord a ⇒ OSet a → a → OSet a infixl 5 Source #

(<|)Ord a ⇒ a → OSet a → OSet a infixr 5 Source #

(|><)Ord a ⇒ OSet a → OSet a → OSet a infixl 5 Source #

\( O(n\log(m*n)) \). For every uncons-ed element from the sequence on the right, checks its membership in the sequence on the left, before snoc'ing it. Preserves order. Remove duplicates from sequence on the right.

(><|)Ord a ⇒ OSet a → OSet a → OSet a infixr 5 Source #

\( O(m\log(m+n)) \). For every unsnoc-ed element from the sequence on the left, checks its membership in the sequence on the right, before cons'ing it. Preserves order. Remove duplicates from sequence on the left.

filterOrd a ⇒ (a → Bool) → OSet a → OSet a Source #

\( O(n \log n) \)