definition module Data.SetBy

/**
 * An efficient implementation of sets.
 *
 * This version is the same as Data.Set, except that the overloaded API is replaced
 * with a higher-order function API.
 *
 * The naming convention is to add 'By' to a function or macro name that is overloaded
 * in Data.Set but uses a higher-order function argument in Data.SetBy.
 *
 * For all documentation, please consult Data.Set.
 *
 * The `morally equivalent` function from Data.Set is added in the comment. This is not
 * a strictly equivalent function because of the different types.
 *
 * When using the functions in Data.SetBy, make sure to use the same higher-order
 * function parameter for the same data structure to ensure internal integrity. 
 * This higher-order function represents the < ordering on your set elements and
 * should have the usual ordering properties:
 *
 * - if a < b and b < c then a < c
 * - if a < b then not (b < a)
 * - if not (a < b) and not (b < a) then a and b are considered to 'equal'
 *
 * @property-bootstrap
 *     import StdChar, StdInt
 *     from StdList import instance length []
 *
 * @property-test-with a = Char
 *
 * @property-test-generator [a] -> SetBy a | < a
 *     gen xs = fromListBy (<) xs
 */

from StdOverloaded	import class ==, class < (..)
from StdClass import class Ord (..), <=, >
from StdList import foldl, map
from Data.Maybe	import :: Maybe
from StdBool import not, &&
from Data.GenLexOrd import :: LexOrd
import qualified Data.Foldable
from Data.Foldable import class Foldable

:: SetBy a = TipBy
           | BinBy !Int !a !(SetBy a) !(SetBy a)

/**
 * True iff the two sets have the same number of elements, and these elements
 * are pairwise 'equal' as described above, so the higher-order function 
 * parameter represents < on a, *not* == on a(!)
 *
 * Morally equivalent function: instance == (Set a) | == a
 */
isEqualBy :: !(a a -> Bool) !(SetBy a) !(SetBy a) -> Bool

/**
 * True iff first set is `smaller` than second set, according to 
 * first argument (assuming the two sets are ordered with the
 * same first function argument).
 *
 * Morally equivalent function: instance < (Set a) | < a
 */
isOrderedBy :: !(a a -> Bool) !(SetBy a) !(SetBy a) -> Bool

/**
 * EQ iff the two sets have the same number of elements, occurring in the 
 *    same order. 
 * LT iff the first set is the common prefix of the second set or the common
 *    prefix is followed in the first set with an element that is considered 
 *    than the corresponding element in the second set.
 * GT iff the second set is the common prefix of the first set or the common
 *    prefix is followed in the second set with an element that is considered
 *    greater than the corresponding element in the first set.
 * The comparison of elements is done with the first function argument. 
 *
 * Morally equivalent function: derive gLexOrd Set
 */
lexOrdBy :: !(a a -> Bool) !(SetBy a) !(SetBy a) -> LexOrd

instance Foldable SetBy

/**
 * True iff this is the empty set.
 * @type (SetBy a) -> Bool
 * @property equivalence with size 0: A.s :: SetBy a:
 *     size s == 0 <==> null s
 * @property equivalence with newSet: A.s :: SetBy a:
 *     isEqualBy (<) s newSet <==> null s
 */
null s :== case s of
             TipBy -> True
             (BinBy sz _ _ _) -> False

/**
 * The number of elements in the set.
 * @type (SetBy a) -> Int
 * @property correctness: A.s :: SetBy a:
 *     size s =.= length (toList s)
 */
size s :== case s of
             TipBy -> 0
             (BinBy sz _ _ _) -> sz

/**
 * Is the element in the set?
 *
 * Morally equivalent function: Data.Set.member x s = Data.SetBy.memberBy (<) x s
 */
memberBy :: !(a a -> Bool) !a !(SetBy a) -> Bool

/**
 * Checks if an element is not in the set.
 */
notMemberBy comp x t :== not (memberBy comp x t)

/**
 * Is t1 a subset of t2?
 *
 * Morally equivalent function: Data.Set.isSubsetOf s1 s2 = Data.SetBy.isSubsetOfBy (<) s1 s2
 */
isSubsetOfBy comp t1 t2 :== (size t1 <= size t2) && (isSubsetOfXBy comp t1 t2)

isSubsetOfXBy :: !(a a -> Bool) !(SetBy a) !(SetBy a) -> Bool


/**
 * Is t1 a proper subset of t2?
 *
 * Morally equivalent function: Data.Set.isProperSubsetOf s1 s2 = Data.SetBy.isProperSubsetOfBy (<) s1 s2
 */
isProperSubsetOfBy comp s1 s2 :== (size s1 < size s2) && (isSubsetOfBy comp s1 s2)

/**
 * The empty set.
 * @complexity O(1)
 * @property is null:
 *     null newSet
 */
newSet :: SetBy a

/**
 * Create a singleton set.
 * @complexity O(1)
 */
singleton :: !u:a -> w:(SetBy u:a), [w <= u]

/**
 * Insert an element in a set. If the set already contains an element equal to
 * the given value, it is replaced with the new value.
 *
 * Morally equivalent function: Data.Set.insert x s = Data.SetBy.insertBy (<) x s
 */
insertBy :: !(a a -> Bool) !a !.(SetBy a) -> SetBy a

/**
 * Delete an element from a set.
 *
 * Morally equivalent function: Data.Set.delete x s = Data.SetBy (<) x s
 */
deleteBy :: !(a a -> Bool) !a !.(SetBy a) -> SetBy a


/**
 * The minimal element of a set.
 *
 * Morally equivalent function: Data.Set.findMin
 */
findMin :: !(SetBy a) -> a

/**
 * The maximal element of a set.
 *
 * Morally equivalent function: Data.Set.findMax
 */
findMax :: !(SetBy a) -> a

/**
 * Delete the minimal element.
 *
 * Morally equivalent function: Data.Set.deleteMin
 */
deleteMin :: !.(SetBy a) -> SetBy a

/**
 * Delete the maximal element.
 *
 * Morally equivalent function: Data.Set.deleteMax
 */
deleteMax :: !.(SetBy a) -> SetBy a

/**
 * deleteFindMin set = (findMin set, deleteMin set)
 */
deleteFindMin :: !.(SetBy a) -> (!a, !SetBy a)

/**
 * deleteFindMax set = (findMax set, deleteMax set)
 */
deleteFindMax :: !.(SetBy a) -> (!a, !SetBy a)

/**
 * Retrieves the minimal key of the set, and the set stripped of that element,
 * or 'Nothing' if passed an empty set.
 */
minView :: !.(SetBy a) -> .(Maybe (!a, !SetBy a))

/**
 * Retrieves the maximal key of the set, and the set stripped of that element,
 * or 'Nothing' if passed an empty set.
 */
maxView :: !.(SetBy a) -> .(Maybe (!a, !SetBy a))

/**
 * The union of two sets, preferring the first set when equal elements are
 * encountered.
 *
 * Morally equivalent function: Data.Set.union s1 s2 = Data.SetBy.unionBy (<) s1 s2
 */
unionBy :: !(a a -> Bool) !u:(SetBy a) !u:(SetBy a) -> SetBy a

/**
 * The union of a list of sets.
 *
 * Morally equivalent function: Data.Set.unions ts = Data.SetBy.unionsBy (<) ts
 */
unionsBy ts :== foldl unionBy newSet ts

/**
 * Difference of two sets.
 *
 * Morally equivalent function: Data.Set.difference s1 s2 = Data.SetBy.differenceBy (<) s1 s2
 */
differenceBy :: !(a a -> Bool) !(SetBy a) !(SetBy a) -> SetBy a

/**
 * The intersection of two sets.
 * Elements of the result come from the first set.
 *
 * Morally equivalent function: Data.Set.intersection s1 s2 = Data.SetBy.intersectionBy (<) s1 s2
 */
intersectionBy :: !(a a -> Bool) !(SetBy a) !(SetBy a) -> SetBy a

/**
 * The intersection of a list of sets.
 * Elements of the result come from the first set
 *
 * Morally equivalent function: Data.Set.intersections ts = Data.SetBy.intersectionsBy (<) ts
 */
intersectionsBy :: !(a a -> Bool) ![SetBy a] -> SetBy a

/**
 * Filter all elements that satisfy the predicate.
 *
 * Morally equivalent function: Data.Set.filter
 */
filter :: !(a -> Bool) !(SetBy a) -> SetBy a

/**
 * Partition the set into two sets, one with all elements that satisfy the
 * predicate and one with all elements that don't satisfy the predicate.
 *
 * Morally equivalent function: Data.Set.partition
 */
partition :: !(a -> Bool) !(SetBy a) -> (!SetBy a, !SetBy a)

/**
 * Split a set in elements less and elements greater than a certain pivot.
 *
 * Morally equivalent function: Data.Set.split x s = Data.SetBy.splitBy (<) x s
 */
splitBy :: !(a a -> Bool) !a !(SetBy a) -> (!SetBy a, !SetBy a)

/**
 * Performs a 'split' but also returns whether the pivot element was found in
 * the original set.
 *
 * Morally equivalent function: Data.Set.splitMember x s = Data.SetBy.splitMemberBy (<) x s
 */
splitMemberBy :: !(a a -> Bool) !a !(SetBy a) -> (!SetBy a, !Bool, !SetBy a)

/**
 * Convert the set to an ascending list of elements.
 */
toList s :== toAscList s

/**
 * Same as toList.
 */
toAscList t :== 'Data.Foldable'.foldr` (\a as -> [a:as]) [] t

/**
 * Create a set from a list of elements.
 *
 * Morally equivalent function: Data.Set.fromList xs = Data.SetBy.fromListBy (<) xs
 */
fromListBy :: !(a a -> Bool) ![a] -> SetBy a

/**
 * Map a function to all elements in a set.
 *
 * Morally equivalent function: Data.Set.mapSet f s = Data.SetBy.mapSetBy (<) f s
 */
mapSetBy comp_b f s :== fromListBy comp_b (map f (toList s))

/**
 * Map a set without converting it to and from a list.
 *
 * Morally equivalent function: Data.Set.mapSetMonotonic
 */
mapSetByMonotonic :: !(a -> b) !(SetBy a) -> SetBy b