(module set-interface mzscheme

  (require "../private/require.ss")
  (require-class)
  (require-contracts)
  (require-lists)

  (provide set<%> set?
           set/c non-empty-set/c
           set-of/c non-empty-set-of/c)

  ;; set<%> : Interface
  ;; The interface for objects of type (Set Elem) for any type Elem,
  ;; representing sets of any element type.
  (define set<%>
    (interface ()

      ;; (send (Set Elem) elements) : (List Elem)
      ;; Produces the elements of the set.
      elements

      ;; (send (Set Elem) insert Elem) : (Set Elem)
      ;; Produces a new set containing all elements of the receiver
      ;; and the given element.  If the receiver contained an equivalent
      ;; element, the prior value is replaced with the new one.
      insert

      ;; (send (Set Elem) lookup Elem [(-> T) (Elem -> T)]) : T
      ;; Looks up an element in the receiver.  If an equivalent one is found,
      ;; the success function is applied to it (returns the element by default).
      ;; If not found, the failure thunk is applied (returns #f by default).
      lookup

      ;; (send (Set Elem) iterator) : (Iterator Elem)
      ;; Constructs an iterator for the elements of a set.
      iterator

      ;; (send (Set Elem) remove Elem) : (Set Elem)
      ;; Produces a new set containing all elements of the receiver
      ;; except the given element.  Produces a set equivalent to the receiver
      ;; if the given element is not present.
      remove
      
      ;; (send (Set Elem) select) : (Set Elem)
      ;; Produces an element from the set. It is an error to
      ;; use select on an empty set.
      select

      ;; (send (Set Elem) empty?) : Boolean
      ;; Reports whether the set is empty.
      empty?

      ;; (send (Set Elem) clear) : (Set Elem)
      ;; Produces an empty set with the same properties as the receiver.
      clear

      ;; (send (Set Elem) size) : NaturalNumber
      ;; Produces the number of elements in the set.
      size

      ;; (send (Set Elem) member? Elem) : Boolean
      ;; Reports whether an element is a member of a set.
      member?

      ;; (send (Set Elem) fold (Elem T -> T) T) : T
      ;; Builds a result from each element in a set.
      fold

      ;; (send (Set Elem) map (Elem -> Elem)) : (Set Elem)
      ;; Adds the image of each element in the receiver to a new set.
      map

      ;; (send (Set Elem) for-each (Elem -> Void)) : Void
      ;; Performs an action for each element of a set.
      for-each

      ;; (send (Set Elem) filter (Elem -> Boolean)) : (Set Elem)
      ;; Produces a new set containing those elements satisfying the predicate.
      filter

      ;; (send (Set Elem) all? (Elem -> Boolean)) : Boolean
      ;; Reports whether all elements of the set satisfy the predicate.
      all?

      ;; (send (Set Elem) any? (Elem -> Boolean)) : Boolean
      ;; Reports whether any element of the set satisfies the predicate.
      any?

      ;; (send (Set Elem) union (Set Elem) [(Elem Elem -> Elem)]) : (Set Elem)
      ;; Produces a set containing all elements present in either,
      ;; with an optional function to choose among duplicate elements.
      union

      ;; (send (Set Elem) intersection (Set Elem) [(Elem Elem -> Elem)])
      ;; : (Set Elem)
      ;; Produces a set containing all elements present in both,
      ;; with an optional function to choose among duplicate elements.
      intersection

      ;; (send (Set Elem) difference (Set Elem)) : (Set Elem)
      ;; Produces a set containing all elements present in the receiver
      ;; but not the argument.
      difference

      ;; (send (Set Elem) subset? (Set Elem)) : Boolean
      ;; Reports whether one set is a subset of another.
      subset?

      ;; (send (Set Elem) equal? (Set Elem)) : Boolean
      ;; Reports whether two sets contain the same elements.
      equal?
      ))

  (define set/c (is-a?/c set<%>))
  (define non-empty/c (not/c (lambda (set) (send set empty?))))

  (define non-empty-set/c
    (and/c set/c non-empty/c))

  (define (set-of/c elem/c)
    (and/c set/c
           (lambda (set)
             (send set all? (predicate-of elem/c)))))

  (define (non-empty-set-of/c elem/c)
    (and/c (set-of/c elem/c) non-empty/c))
  
  ;; set? : Any -> Boolean
  ;; Reports whether a value is a set.
  (define (set? v)
    (is-a? v set<%>))

  )