;; Use of declarative programming to solve a bin packing problem. As
;; there is no known optimal algorithm to solve this, a declarative
;; approach is at least plausible. Alternatively, you can think of this
;; as just another little example.

;; TEMPLATES

(deftemplate bin
  (slot number (type INTEGER))
  (slot capacity (default 6) (type INTEGER))
  (slot current-load (default 0) (type INTEGER))
  (multislot items))

;; INITIAL STATE

(deffacts start-state
  (items-to-pack 1 3 3 5 5 2)
  (numbins 0))

;; RULES

(defrule all-done "If all items are packed, we're done"
  (items-to-pack $?all-items)
  (test (= (length$ ?all-items) 0))
  =>
  (printout t crlf "All items are packed as follows:" crlf)
  (assert (done)))

(defrule output-packing "Output contents of all bins"
  (done)
  (bin (number ?bin-number) (items $?bin-items))
  =>
  (printout t "Bin number " ?bin-number " contains " ?bin-items crlf))

(defrule new-bin "Create a new bin if no space for next item"
  (items-to-pack ?next-item $?)
  (not (bin (capacity ?cap)
            (current-load ?load&:(>= ?cap (+ ?load ?next-item)))))
  ?nb <- (numbins ?n)
  =>
  (assert (bin (number (+ ?n 1))))
  (retract ?nb)
  (assert (numbins (+ ?n 1)))
  (printout t "Created new bin number " (+ ?n 1) crlf))

(defrule pack-bin "Pack item into most full bin that can hold it"
  ?item-list <- (items-to-pack ?next-item $?rest)
  ?thebin <- (bin (number ?n)
                  (capacity ?cap)
                  (current-load ?load&:(>= ?cap (+ ?load ?next-item)))
                  (items $?contents))
  (not (bin (current-load ?otherload&:(> ?otherload ?load)
                                    &:(>= ?cap (+ ?otherload ?next-item)))))
  =>
  (retract ?item-list)
  (assert (items-to-pack ?rest))
  (modify ?thebin (current-load (+ ?load ?next-item))
                  (items ?next-item ?contents))
  (printout t "Packed item of weight " ?next-item " in bin " ?n crlf))

;; A new, subclassed bin, to implement tracking of bin identity (serial 
;; numbers).
;
;(deftemplate ordered-bin extends bin
;  (multislot item-numbers))