(module bag mzscheme
  
  (require "private/require.ss")
  (require-contracts)
  (require-lists)
  (require-etc)
  
  (require (lib "class.ss")
           "private/contracts.ss"
           "bag/bag-interface.ss"
           "bag/hashed-bag.ss"
           "bag/ordered-bag.ss"
           "bag/simple-bag.ss"
           "bag/unordered-bag.ss")
  
  ;; For predicates that also take a count of elements
  (define predicate/count/c
    (any/c positive? . -> . boolean?))
  
  (provide/contract
   ;;; Type predicate and contract
   [bag? predicate/c]
   [bag/c flat-contract?]
   ;;; Constructors
   ;; Single argument, list of elements
   [list->hashed (hash-fn/c equality/c (listof any/c) . -> . bag/c)]
   [list->ordered (comparison/c (listof any/c) . -> . bag/c)]
   [list->unordered (equality/c (listof any/c) . -> . bag/c)]
   [list->eq ((listof any/c) . -> . bag/c)]
   [list->eqv ((listof any/c) . -> . bag/c)]
   [list->equal ((listof any/c) . -> . bag/c)]
   ;; Variable-arity, elements
   [make-hashed ([hash-fn/c equality/c] (listof any/c) . ->* . [bag/c])]
   [make-ordered ([comparison/c] (listof any/c) . ->* . [bag/c])]
   [make-unordered ([equality/c] (listof any/c) . ->* . [bag/c])]
   [make-eq ([] (listof any/c) . ->* . [bag/c])]
   [make-eqv ([] (listof any/c) . ->* . [bag/c])]
   [make-equal ([] (listof any/c) . ->* . [bag/c])]
   ;;; Operations
   [elements (bag/c . -> . (listof any/c))]
   [to-sexp   (bag/c . -> . (listof (list/c any/c positive?)))]
   [to-alist  (bag/c . -> . (listof (cons/c any/c positive?)))]
   [rename bag-empty? empty? (bag/c . -> . boolean?)]
   [count  (any/c bag/c . -> . natural-number/c)]
   [member? (any/c bag/c . -> . boolean?)]
   [select (bag/c . -> . any/c)]
   [select/count (bag/c . -> . (values any/c positive?))]
   [clear  (bag/c . -> . bag/c)]
   [size   (bag/c . -> . natural-number/c)]
   [size/unique (bag/c . -> . natural-number/c)]
   [subbag? (bag/c bag/c . -> . boolean?)]
   [rename bag-equal? equal? (bag/c bag/c . -> . boolean?)]
   ;; Operates on a single element, doesn't use count
   [insert (any/c bag/c . -> . bag/c)]
   [lookup ([any/c bag/c] [(-> any) (any/c . -> . any)] . opt-> . any)]
   [rename bag-remove remove (any/c bag/c . -> . bag/c)]
   [remove/all (any/c bag/c . -> . bag/c)]
   [rename bag-fold fold ((any/c any/c . -> . any/c) any/c bag/c . -> . any/c)]
   [rename bag-map map ((any/c . -> . any/c) bag/c . -> . bag/c)]
   [rename bag-for-each for-each ((any/c . -> . void?) bag/c . -> . void?)]
   [rename bag-filter filter (predicate/c bag/c . -> . bag/c)]
   [any? (predicate/c bag/c . -> . boolean?)]
   [rename bag-ormap ormap (predicate/c bag/c . -> . boolean?)]
   [all? (predicate/c bag/c . -> . boolean?)]
   [rename bag-andmap andmap (predicate/c bag/c . -> . boolean?)]
   ;; Operates on multiple elements (variable-arity), doesn't use count
   [insert* ([bag/c] (listof any/c) . ->* . [bag/c])]
   [rename bag-remove* remove* ([bag/c] (listof any/c) . ->* . [bag/c])]
   ;; Operates on a single element, uses count
   [insert/count (any/c natural-number/c bag/c . -> . bag/c)]
   [lookup/count ([any/c bag/c] [(-> any) (any/c positive? . -> . any)] . opt-> . any)]
   [remove/count (any/c natural-number/c bag/c . -> . bag/c)]
   [fold/count ((any/c positive? any/c . -> . any/c) any/c bag/c . -> . any/c)]
   [map/count ((any/c positive? . -> . any/c) bag/c . -> . bag/c)]
   [for-each/count ((any/c positive? . -> . void?) bag/c . -> . void?)]
   [filter/count (predicate/count/c bag/c . -> . bag/c)]
   [any?/count (predicate/count/c bag/c . -> . boolean?)]
   [ormap/count (predicate/count/c bag/c . -> . boolean?)]
   [all?/count (predicate/count/c bag/c . -> . boolean?)]
   [andmap/count (predicate/count/c bag/c . -> . boolean?)]
   ;; Operates on more than one bag.  Result assumes the properties of the first bag.
   [union (bag/c bag/c . -> . bag/c)]
   [intersection (bag/c bag/c . -> . bag/c)]
   [difference (bag/c bag/c . -> . bag/c)]
   )
  
  ;; make-hashed : (Elem -> Integer) (Elem Elem -> Boolean) Elem ... -> (Bag Elem)
  ;; Constructs a bag with hashed elements.
  (define (make-hashed hash equ? . elems)
    (make-hashed-bag hash equ? elems))
  (define list->hashed make-hashed-bag)
  
  ;; make-ordered : (Elem Elem -> (Union -1 0 1)) Elem ... -> (Bag Elem)
  ;; Constructs a bag with ordered elements.
  (define (make-ordered compare . elems)
    (make-ordered-bag compare elems))
  (define list->ordered make-ordered-bag)
  
  ;; make-unordered : (Elem Elem -> Boolean) Elem ... -> (Bag Elem)
  ;; Constructs a bag with unordered elements.
  (define (make-unordered equ? . elems)
    (make-unordered-bag equ? elems))
  (define list->unordered make-unordered-bag)
  
  ;; make-eq : Elem ... -> (Bag Elem)
  ;; Constructs a hashed bag with eq? as the equality operator
  (define (list->eq elems)
    (make-hashed-bag eq-hash-code eq? elems))
  (define (make-eq . elems)
    (list->eq elems))
  
  ;; make-eqv : Elem ... -> (Bag Elem)
  ;; Constructs an unordered bag with eqv? as the equality operator
  (define (list->eqv elems)
    (make-unordered-bag eqv? elems))
  (define (make-eqv . elems)
    (list->eqv elems))
  
  ;; make-equal : Elem ... -> (Bag Elem)
  ;; Constructs a hashed bag with equal? as the equality operator
  (define (list->equal elems)
    (make-hashed-bag equal-hash-code equal? elems))
  (define (make-equal . elems)
    (list->equal elems))
  
  ;; elements : (Bag Elem) -> (List Elem)
  ;; Produces the elements of a bag.
  (define (elements bag)
    (send bag elements))

  ;; sexp : (Bag Elem) -> (List (List Elem Integer))
  ;; Produces an s-expression where each sublist is an element
  ;; of the bag and the number of times it appears.
  (define (to-sexp bag)
    (send bag sexp))

  ;; alist : (Bag Elem) -> (List (cons Elem Integer))
  ;; Produces an association list where each element of the bag is
  ;; associated with its count.
  (define (to-alist bag)
    (send bag alist))

  ;; insert : Elem (Bag Elem) -> (Bag Elem)
  ;; Produces an updated bag containing the new element.  If the
  ;; element was already contained by the bag, the new bag has
  ;; the element's count increased by one.
  (define (insert elem bag)
    (send bag insert elem))

  ;; insert* : (Bag Elem) Elem ... -> (Bag Elem)
  ;; Produces an updated bag containing the new elements.  If any
  ;; of the elements was already contained by the bag, the new bag
  ;; has that element's count increased by one.
  (define (insert* bag . elems)
    (send bag insert* . elems))

  ;; insert/count : Elem Integer (Bag Elem) -> (Bag Elem)
  ;; Produces an updated bag containing the new element.  If the
  ;; element was already contained by the bag, the new bag has
  ;; the element's count increased by the given count.
  (define (insert/count elem count bag)
    (send bag insert/count elem count))

  ;; lookup : Elem (Bag Elem) [(-> A) (Elem -> B)] -> (Union A B)
  ;; Looks up an element of a bag.
  ;; If found, calls the success function (default: return the element).
  ;; If not found, calls the failure function (default: return #f).
  (define (lookup elem bag . rest)
    (send bag lookup elem . rest))

  ;; lookup : Elem (Bag Elem) [(-> A) (Elem Integer -> B)] -> (Union A B)
  ;; Looks up an element of a bag.
  ;; If found, calls the success function with the element and the
  ;; element count (default: return the element).
  ;; If not found, calls the failure function (default: return #f).
  (define (lookup/count elem bag . rest)
    (send bag lookup/count elem . rest))
  
  ;; count : Elem (Bag Elem) -> Integer
  ;; Returns the amount of times the element appears in the bag.
  (define (count elem bag)
    (send bag count elem))
  
  ;; select : (Bag Elem) -> Elem
  ;; Returns an element from the bag.
  (define (select bag)
    (send bag select))
  
  ;; select/count : (Bag Elem) -> (values Elem PositiveNumber)
  ;; Returns an element and its count from the bag.
  (define (select/count bag)
    (send bag select/count))
  
  ;; bag-empty? : (Bag Elem) -> Boolean
  ;; Returns whether the given bag is empty.
  (define (bag-empty? bag)
    (send bag empty?))

  ;; size : (Bag Elem) -> Integer
  ;; Returns the size of the bag in total number of elements.
  (define (size bag)
    (send bag size))
  
  ;; size/unique : (Bag Elem) -> Integer
  ;; Returns the size of the bag in total number of unique
  ;; elements.
  (define (size/unique bag)
    (send bag size/unique))
  
  ;; member? : Elem (Bag Elem) -> Boolean
  ;; Returns whether a given element is in the bag or not.
  (define (member? elem bag)
    (send bag member? elem))
  
  ;; clear : (Bag Elem) -> (Bag Elem)
  ;; Returns a new bag having the same properties as the given bag.
  (define (clear bag)
    (send bag clear))
  
  ;; remove : Elem (Bag Elem) -> (Bag Elem)
  ;; Returns a new bag with all the same elements as the given bag
  ;; except for if the given element is a member.  If there is
  ;; only one of the given element, the new bag will not contain
  ;; it, else the new bag will contain one less of that element.
  (define (bag-remove elem bag)
    (send bag remove elem))

  ;; remove* : (Bag Elem) Elem ... -> (Bag Elem)
  ;; Returns a new bag with all the same elements as the given bag
  ;; except for if any of the given elements is a member.  If there
  ;; is only one of a given element, the new bag will not contain
  ;; it, else the new bag will contain one less of that element.
  (define (bag-remove* bag . elems)
    (send bag remove* .  elems))

  ;; remove/all : Elem (Bag Elem) -> (Bag Elem)
  ;; Returns a new bag with all the same elements as the given bag
  ;; except for if the given element is a member.  There will be
  ;; no occurrences of the given element in the new bag.
  (define (remove/all elem bag)
    (send bag remove/all elem))
  
  ;; remove/count : Elem Integer (Bag Elem) -> (Bag Elem)
  ;; Returns a new bag with all the same elements as the given bag
  ;; except for if the given element is a member.  If there is
  ;; a number of the given element less than or equal to the given
  ;; amount, the new bag will not contain it, else the new bag will
  ;; contain that many less of the given element.
  (define (remove/count elem count bag)
    (send bag remove/count elem count))

  ;; fold : (Elem T -> T) T (Bag Elem) -> T
  ;; Builds up a result from each element and element count in
  ;; the bag.
  (define (bag-fold f i bag)
    (send bag fold f i))
  
  ;; fold/count : (Elem Integer T -> T) T (Bag Elem) -> T
  ;; Builds up a result from each element and element count in
  ;; the bag.
  (define (fold/count f i bag)
    (send bag fold/count f i))
  
  ;; map : (Elem -> Elem) (Bag Elem) -> (Bag Elem)
  ;; Transforms each element in the bag using the given function.
  (define (bag-map f bag)
    (send bag map f))

  ;; map/count : (Elem PositiveNumber -> Elem) (Bag Elem) -> (Bag Elem)
  ;; Like map, but the transformer also takes an element count.
  (define (map/count f bag)
    (send bag map/count f))

  ;; for-each : (Elem -> Void) (Bag Elem) -> Void
  ;; Performs an action for each element in the bag.
  (define (bag-for-each f bag)
    (send bag for-each f))
  
  ;; for-each/count : (Elem Integer -> Void) (Bag Elem) -> Void
  ;; Performs an action for each element and element count in
  ;; the bag.
  (define (for-each/count f bag)
    (send bag for-each/count f))
  
  ;; filter : (Elem -> Boolean) (Bag Elem) -> (Bag Elem)
  ;; Filters out any elements in the bag that do not conform
  ;; to the predicate.
  (define (bag-filter f bag)
    (send bag filter f))
  
  ;; all? : (Elem -> Boolean) (Bag Elem) -> Boolean
  ;; Returns whether every element in the bag matches the predicate.
  (define (all? f bag)
    (send bag all? f))
  (define bag-andmap all?)
  
  ;; any? : (Elem -> Boolean) (Bag Elem) -> Boolean
  ;; Returns whether every element in the bag matches the predicate.
  (define (any? f bag)
    (send bag any? f))
  (define bag-ormap any?)

  ;; filter/count : (Elem Integer -> Boolean) (Bag Elem) -> (Bag Elem)
  ;; Like filter, but the predicate also takes an element count.
  (define (filter/count f bag)
    (send bag filter/count f))
  
  ;; all?/count : (Elem Integer -> Boolean) (Bag Elem) -> Boolean
  ;; Like all?, but the predicate also takes an element count.
  (define (all?/count f bag)
    (send bag all?/count f))
  (define andmap/count all?/count)
  
  ;; any?/count : (Elem Integer -> Boolean) (Bag Elem) -> Boolean
  ;; Like any?, but the predicate also takes an element count.
  (define (any?/count f bag)
    (send bag any?/count f))
  (define ormap/count any?/count)
  
  ;; union : (Bag Elem) (Bag Elem) : (Bag Elem)
  ;; Takes the union of the two bags given as an argument.
  ;; The element count for a given element will be the maximum of
  ;; the element count for each bag.
  (define (union b1 b2)
    (send b1 union b2))

  ;; intersection : (Bag Elem) (Bag Elem) : (Bag Elem)
  ;; Takes the intersection of the two bags given as an argument.
  ;; The element count for a given element will be the minimum of
  ;; the element count for each bag.
  (define (intersection b1 b2)
    (send b1 intersection b2))
  
  ;; difference : (Bag Elem) (Bag Elem) : (Bag Elem)
  ;; Returns the first bag with all elements from the second
  ;; bag removed.  That means the element count for a given
  ;; element will be the element count for the first bag minus
  ;; the element count for the second bag.
  (define (difference b1 b2)
    (send b1 difference b2))
  
  ;; subbag? : (Bag Elem) (Bag Elem) : Boolean
  ;; Returns whether the second bag contains all the elements
  ;; that the first contains.  This also means that the second
  ;; must contain at least as many occurrences of each element
  ;; as the first does.
  (define (subbag? b1 b2)
    (send b1 subbag? b2))
  
  ;; equal? : (Bag Elem) (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).
  (define (bag-equal? b1 b2)
    (send b1 equal? b2))
  )