oset-0.4.0.1: An insertion-order-preserving set

Copyright (C) Richard Cook 2019 MIT rcook@rcook.org stable portable Safe Haskell2010

Data.Set.Ordered.Classes

Description

Synopsis

# Common operations on ordered sets

type Index = Int Source #

A zero-based index with respect to insertion order.

class OrderedSet a c where Source #

Common operations on ordered sets. Set type is c, element type is a.

Methods

empty :: c a Source #

$$O(1)$$. The empty set.

singleton :: a -> c a Source #

$$O(1)$$. A singleton set containing the given element.

fromListL :: Ord a => [a] -> c a Source #

$$O(N log(N))$$. Create a set from a finite list of elements. If an element occurs multiple times in the original list, only the first occurrence is retained in the resulting set. The function toList, $$O(N)$$, can be used to return a list of the elements in the original insert order with duplicates removed.

fromListR :: Ord a => [a] -> c a Source #

$$O(N log(N))$$. Create a set from a finite list of elements. If an element occurs multiple times in the original list, only the last occurrence is retained in the resulting set. The function toList, $$O(N)$$, can be used to return a list of the elements in the original insert order with duplicates removed.

member :: Ord a => a -> c a -> Bool Source #

$$O(log(N))$$. Determine if the element is in the set. Evaluate to True if element is in set, False otherwise.

notMember :: Ord a => a -> c a -> Bool Source #

$$O(log(N))$$. Determine if the element is not in the set. Evaluate to True if element is not in set, False otherwise.

map :: Ord b => (a -> b) -> c a -> c b Source #

$$O(N log(N))$$. Return the set obtained by applying a function to each element of this set. Note that the resulting set may be smaller than the original. Along with the Ord constraint, this means that OSet cannot provide a lawful Functor instance.

filter :: (a -> Bool) -> c a -> c a Source #

$$O(N)$$. Filter a set by returning a set whose elements satisfy the predicate.

size :: c a -> Int Source #

$$O(1)$$. The number of elements in the set.

toSeq :: c a -> Seq a Source #

$$O(1)$$. Return ordered sequence of elements in set. For obtaining a useful Functor instance this is recommended over toList due to its $$O(1)$$ performance. Similarly, if you want to pattern-match on the OSet, obtain the sequence and use view patterns or pattern synonyms instead of converting to a list.

toAscList :: c a -> [a] Source #

$$O(N)$$. Convert the set to an ascending list of elements.

findIndex :: Eq a => a -> c a -> Maybe Index Source #

$$O(N)$$. Finds the index of the leftmost element that matches the specified element or returns Nothing if no matching element can be found.

elemAt :: c a -> Index -> Maybe a Source #

$$O(log(min(i, N - i)))$$. Return the element at the specified position, $$i$$, counting from 0. If the specified position is out of range, this function returns Nothing.

delete :: Ord a => a -> c a -> c a Source #

$$O(log N)$$. Delete an element from the set.

(\\) :: Ord a => c a -> c a -> c a Source #

$$O(N M)$$. Find the set difference: r \\ s removes all M values in s from r with N values.

Instances
 Source # Instance detailsDefined in Data.Set.Ordered.OSet Methodssingleton :: a -> OSet a Source #fromListL :: [a] -> OSet a Source #fromListR :: [a] -> OSet a Source #member :: a -> OSet a -> Bool Source #notMember :: a -> OSet a -> Bool Source #map :: Ord b => (a -> b) -> OSet a -> OSet b Source #filter :: (a -> Bool) -> OSet a -> OSet a Source #size :: OSet a -> Int Source #toSeq :: OSet a -> Seq a Source #toAscList :: OSet a -> [a] Source #findIndex :: a -> OSet a -> Maybe Index Source #elemAt :: OSet a -> Index -> Maybe a Source #delete :: a -> OSet a -> OSet a Source #(\\) :: OSet a -> OSet a -> OSet a Source # Source # Instance detailsDefined in Data.Set.Ordered.LR Methodssingleton :: a -> OSetR a Source #fromListL :: [a] -> OSetR a Source #fromListR :: [a] -> OSetR a Source #member :: a -> OSetR a -> Bool Source #notMember :: a -> OSetR a -> Bool Source #map :: Ord b => (a -> b) -> OSetR a -> OSetR b Source #filter :: (a -> Bool) -> OSetR a -> OSetR a Source #size :: OSetR a -> Int Source #toSeq :: OSetR a -> Seq a Source #toAscList :: OSetR a -> [a] Source #findIndex :: a -> OSetR a -> Maybe Index Source #elemAt :: OSetR a -> Index -> Maybe a Source #delete :: a -> OSetR a -> OSetR a Source #(\\) :: OSetR a -> OSetR a -> OSetR a Source # Source # Instance detailsDefined in Data.Set.Ordered.LR Methodssingleton :: a -> OSetL a Source #fromListL :: [a] -> OSetL a Source #fromListR :: [a] -> OSetL a Source #member :: a -> OSetL a -> Bool Source #notMember :: a -> OSetL a -> Bool Source #map :: Ord b => (a -> b) -> OSetL a -> OSetL b Source #filter :: (a -> Bool) -> OSetL a -> OSetL a Source #size :: OSetL a -> Int Source #toSeq :: OSetL a -> Seq a Source #toAscList :: OSetL a -> [a] Source #findIndex :: a -> OSetL a -> Maybe Index Source #elemAt :: OSetL a -> Index -> Maybe a Source #delete :: a -> OSetL a -> OSetL a Source #(\\) :: OSetL a -> OSetL a -> OSetL a Source #

# Insertion

class PreserveL a c where Source #

OSet and OSetL operations that preserve elements from the left-hand operand in the case of duplicate elements. Set type is c, element type is a.

Methods

(|<) :: a -> c a -> c a infixr 5 Source #

$$O(log(N))$$ if the element is not in the set, $$O(N)$$ if the element is already in the set. Add an element to the left end of the sequence if the set does not already contain the element. Move the element to the left end of the sequence if the element is already present in the set.

(|>) :: c a -> a -> c a infixl 5 Source #

$$O(log(N))$$. Add an element to the right end of the sequence if the set does not already contain the element. Otherwise ignore the element.

(|<>) :: c a -> c a -> c a infixr 6 Source #

$$O(Nlog(N))$$ worst case. Add elements from the right-hand set to the left-hand set. If elements occur in both sets, then this operation discards elements from the right-hand set and preserves those from the left.

Instances
 Ord a => PreserveL a OSet Source # Instance detailsDefined in Data.Set.Ordered.OSet Methods(|<) :: a -> OSet a -> OSet a Source #(|>) :: OSet a -> a -> OSet a Source #(|<>) :: OSet a -> OSet a -> OSet a Source # Ord a => PreserveL a OSetL Source # Instance detailsDefined in Data.Set.Ordered.LR Methods(|<) :: a -> OSetL a -> OSetL a Source #(|>) :: OSetL a -> a -> OSetL a Source #(|<>) :: OSetL a -> OSetL a -> OSetL a Source #

class PreserveR a c where Source #

OSet and OSetR operations that preserve elements from the right-hand operand in the case of duplicate elements. Set type is c, element type is a.

Methods

(<|) :: a -> c a -> c a infixr 5 Source #

$$O(log(N))$$. Add an element to the left end of the sequence if the set does not already contain the element. Otherwise ignore the element.

(>|) :: c a -> a -> c a infixl 5 Source #

$$O(log(N))$$ if the element is not in the set, $$O(N)$$ if the element is already in the set. Add an element to the right end of the sequence if the set does not already contain the element. Move the element to the right end of the sequence if the element is already present in the set.

(<>|) :: c a -> c a -> c a infixr 6 Source #

$$O(N^2)$$ worst case. Add elements from the right-hand set to the left-hand set. If elements occur in both sets, then this operation discards elements from the left-hand set and preserves those from the right.

Instances
 Ord a => PreserveR a OSet Source # Instance detailsDefined in Data.Set.Ordered.OSet Methods(<|) :: a -> OSet a -> OSet a Source #(>|) :: OSet a -> a -> OSet a Source #(<>|) :: OSet a -> OSet a -> OSet a Source # Ord a => PreserveR a OSetR Source # Instance detailsDefined in Data.Set.Ordered.LR Methods(<|) :: a -> OSetR a -> OSetR a Source #(>|) :: OSetR a -> a -> OSetR a Source #(<>|) :: OSetR a -> OSetR a -> OSetR a Source #