(module bag-interface mzscheme
  
  (require "../private/require.ss")
  (require-class)
  (require-contracts)
  (require-lists)
  
  (provide bag<%> bag?
           bag/c non-empty-bag/c
           bag-of/c non-empty-bag-of/c)
  
  ;; bag<%> : Interface
  ;; The interface for objects of type (Bag Elem) for any type Elem,
  ;; representing bags of any element type.
  (define bag<%>
    (interface ()
      
      ;; (send (Bag Elem) alist) : (List (cons Elem Integer))
      ;; Produces an association list where each element of the bag is
      ;; associated with its count.
      alist
      
      ;; (send (Bag Elem) elements) : (List Elem)
      ;; Produces the elements of the bag (without counts).
      elements
      
      ;; (send (Bag Elem) insert Elem) : (Bag Elem)
      ;; Produces a new bag containing all elements of the receiver
      ;; and the given element.  If the receiver contained an equivalent
      ;; element, the count of that element is increased by one.  The
      ;; counts for all other elements remain the same.
      insert

      ;; (send (Bag Elem) insert/count Elem Integer) : (Bag Elem)
      ;; Produces a new bag containing all elements of the receiver
      ;; and the given element.  If the receiver contained an equivalent
      ;; element, the count of that element is increased by the given
      ;; number.  The counts for all other elements remain the same.
      ;; If the count given is not positive, the resulting bag is the
      ;; same as this bag.
      insert/count

      ;; (send (Bag 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 (Bag Elem) lookup Elem [(-> T) (Elem Integer -> T)]) : T
      ;; Looks up an element in the receiver.  If an equivalent one is found,
      ;; the success function is applied to it and its count(returns the
      ;; element by default).  If not found, the failure thunk is applied
      ;; (returns #f by default).
      lookup/count

      ;; (send (Bag Elem) count Elem) : Integer
      ;; Returns the number of times the given element appeared in the
      ;; given bag.
      count
      
      ;; (send (Bag Elem) remove Elem) : (Bag Elem)
      ;; Produces a new bag containing all elements of the receiver not
      ;; equivalent to the given element with the same counts.  If the
      ;; given element is present, then its count is reduced by 1.  If
      ;; its count becomes 0, it is not present in the new bag.  If the
      ;; given element is not present, then this produces a bag
      ;; equivalent to the receiver.
      remove

      ;; (send (Bag Elem) remove* Elem ...) : (Bag Elem)
      ;; Produces a new bag containing all elements of the receiver not
      ;; equivalent to the given elements with the same counts.  If the
      ;; given elements are present, then each's count is reduced by 1.
      ;; If an element's count becomes 0, it is not present in the new bag.
      ;; If the given elements are not present, then this produces a bag
      ;; equivalent to the receiver.
      remove*

      ;; (send (Bag Elem) remove-all Elem) : (Bag Elem)
      ;; Produces a new bag containing all elements of the receiver not
      ;; equivalent to the given element with the same counts.  If the
      ;; given element is present, then it is not present in the new bag.
      ;; If the given element is not present, then this produces a bag
      ;; equivalent to the receiver.
      remove/all
      
      ;; (send (Bag Elem) remove/count Elem Integer) : (Bag Elem)
      ;; Produces a new bag containing all elements of the receiver not
      ;; equivalent to the given element with the same counts.  If the
      ;; given element is present, then its count is reduced by the given
      ;; amount.  If its count becomes <= 0, it is not present in the new
      ;; bag.  If the given element is not present, then this produces a
      ;; bag equivalent to the receiver.
      remove/count

      ;; (send (Bag Elem) empty?) : Boolean
      ;; Reports whether the given bag is empty.
      empty?
      
      ;; (send (Bag Elem) size) : Integer
      ;; Returns the size of the bag.  Equivalent elements are counted
      ;; separately.
      size
      
      ;; (send (Bag Elem) size/unique) : Integer
      ;; Returns the size of the bag.  Equivalent elements are only counted
      ;; once.
      size/unique
      
      ;; (send (Bag Elem) member? Elem) : Boolean
      ;; Returns whether the given element is a member of the bag.
      member?
      
      ;; (send (Bag Elem) select) : Elem
      ;; Returns a unspecified element from the bag.
      select

      ;; (send (Bag Elem) select/count) : (values Elem PositiveNumber)
      ;; Returns a unspecified element and its count from the bag.
      select/count

      ;; (send Bag Elem) clear) : (Bag Elem)
      ;; Produces an empty bag with the same properties as the receiver.
      clear
      
      ;; (send (Bag Elem) iterator) : (Iterator (cons Elem Integer))
      ;; Constructs an iterator for the elements and counts of a set.
      iterator
      
      ;; (send (Bag Elem) fold (Elem -> T) T) : T
      ;; Builds up a result from each element in the bag.
      fold
      
      ;; (send (Bag Elem) fold/count (Elem Integer -> T) T) : T
      ;; Builds up a result from each element and element count in the
      ;; bag.
      fold/count
      
      ;; (send (Bag Elem) map (Elem -> Elem)) : (Bag Elem)
      ;; Transforms each element in the bag according to the given function.
      map
      
      ;; (send (Bag Elem) map/count (Elem PositiveNumber -> Elem)) : (Bag Elem)
      ;; Like map, but the transformer takes an element count as well.
      map/count
      
      ;; (send (Bag Elem) for-each (Elem -> Void) : Void
      ;; Performs an action for each element in the bag.
      for-each
      
      ;; (send (Bag Elem) for-each (Elem Integer -> Void) : Void
      ;; Performs an action for each element and element count in the bag.
      for-each/count

      ;; (send (Bag Elem) filter (Elem -> Boolean)) : (Bag Elem)
      ;; Returns a new bag that contains all the elements of the given
      ;; bag that pass the given predicate.
      filter

      ;; (send (Bag Elem) filter/count (Elem Integer -> Boolean)) : (Bag Elem)
      ;; Returns a new bag that contains all the elements of the given
      ;; bag that pass the given predicate.  The predicate for this also
      ;; takes the number of times the element occurs.
      filter/count

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

      ;; (send (Bag Elem) all?/count (Elem Integer -> Boolean)) : Boolean
      ;; Reports whether all elements of the bag satisfy the predicate.
      ;; The predicate takes both the element and the number of times
      ;; it occurs.
      all?/count

      ;; (send (Bag Elem) any? (Elem -> Boolean)) : Boolean
      ;; Reports whether any elements of the bag satisfy the predicate.
      any?

      ;; (send (Bag Elem) any?/count (Elem Integer -> Boolean)) : Boolean
      ;; Reports whether any elements of the bag satisfy the predicate.
      ;; The predicate takes both the element and the number of times
      ;; it occurs.
      any?/count

      ;; (send (Bag Elem) union (Bag Elem)) : (Bag Elem)
      ;; Returns the union of this bag with the given bag.
      ;; The new bag will have the same properties as this bag.
      union
      
      ;; (send (Bag Elem) intersection (Bag Elem)) : (Bag Elem)
      ;; Returns the intersection of this bag with the given bag.
      ;; The new bag will have the same properties as this bag.
      intersection

      ;; (send (Bag Elem) difference (Bag Elem)) : (Bag Elem)
      ;; Returns the difference of this bag with the given bag.
      ;; The new bag will have the same properties as this bag.
      difference

      ;; (send (Bag Elem) subbag? (Bag Elem)) : Boolean
      ;; Returns whether the given bag contains all the elements
      ;; that this bag contains.  This also means that the given
      ;; bag must contain at least as many occurrences of each
      ;; element as this bag does.
      subbag?

      ;; (send (Bag Elem) equal? (Bag Elem)) : Boolean
      ;; Returns whether the two bags are equal (i.e. have the same
      ;; elements and the same number of occurrences of each element).
      equal?
      
      ))
  
  (define bag/c (is-a?/c bag<%>))
  (define non-empty/c (not/c (lambda (bag) (send bag empty?))))

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

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

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