discrete-histogram.ss
;;; PLT Scheme Science Collection
;;; discrete-histogram.ss
;;; Copyright (c) 2004 M. Douglas Williams
;;;
;;; This library is free software; you can redistribute it and/or
;;; modify it under the terms of the GNU Lesser General Public
;;; License as published by the Free Software Foundation; either
;;; version 2.1 of the License, or (at your option) any later version.
;;;
;;; This library is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
;;; Lesser General Public License for more details.
;;;
;;; You should have received a copy of the GNU Lesser General Public
;;; License along with this library; if not, write to the Free
;;; Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
;;; 02111-1307 USA.
;;;
;;; -------------------------------------------------------------------
;;;
;;; This module provides discrete histograms - that is, the range of
;;; the histogram (bins) must be integers.
;;;
;;; Version  Date      Description
;;  1.0.0    09/30/04  Marked as ready for Release 1.0.  (Doug
;;;                    Williams)

(module discrete-histogram mzscheme
  
  ;; Data Definition
  
  ;; discrete-histogram structure
  (define-values (struct:discrete-histogram
                  discrete-histogram-constructor
                  discrete-histogram?
                  discrete-histogram-field-ref
                  set-discrete-histogram-field!)
    (make-struct-type 'discrete-histogram #f 4 0))
  
  ;; Contracts
  
  (require (lib "contract.ss"))
  
  (provide/contract
   (discrete-histogram?
    (-> any/c boolean?))
   (make-discrete-histogram
    (case-> (->r ((n1 integer?)
                  (n2 (and/c integer?
                              (>=/c n1)))
                  (dynamic? boolean?))
                 discrete-histogram?)
            (->r ((n1 integer?)
                  (n2 (and/c integer?
                              (>=/c n1))))
                 discrete-histogram?)
            (-> discrete-histogram?)))
   (discrete-histogram-n1
    (-> discrete-histogram? integer?))
   (discrete-histogram-n2
    (-> discrete-histogram? integer?))
   (discrete-histogram-dynamic?
    (-> discrete-histogram? boolean?))
   (discrete-histogram-bins
    (-> discrete-histogram? (vectorof real?)))
   (discrete-histogram-increment!
    (-> discrete-histogram? integer? void?))
   (discrete-histogram-accumulate!
    (-> discrete-histogram? integer? real? void?))
   (discrete-histogram-get
    (-> discrete-histogram? integer? real?))
   (discrete-histogram-max
    (-> discrete-histogram? real?))
   (discrete-histogram-min 
    (-> discrete-histogram? real?))
   (discrete-histogram-sum
    (-> discrete-histogram? real?)))
  
  ;; make-discrete-histogram: integer x integer x boolean -> discrete-histogram
  (define make-discrete-histogram
    (case-lambda
      ((n1 n2 dynamic?)
       (discrete-histogram-constructor 
        n1 n2 dynamic? (make-vector (+ (- n2 n1) 1))))
      ((n1 n2)
       (make-discrete-histogram n1 n2 #f))
      (()
       (make-discrete-histogram 0 -1 #t))))
  
  ;; Define discrete-histogram fields
  (define discrete-histogram-n1
    (make-struct-field-accessor discrete-histogram-field-ref 0 'n1))
  
  (define set-discrete-histogram-n1!
    (make-struct-field-mutator set-discrete-histogram-field! 0 'n1))
  
  (define discrete-histogram-n2
    (make-struct-field-accessor discrete-histogram-field-ref 1 'n2))
  
  (define set-discrete-histogram-n2!
    (make-struct-field-mutator set-discrete-histogram-field! 1 'n2))
  
  (define discrete-histogram-dynamic?
    (make-struct-field-accessor discrete-histogram-field-ref 2 'dynamic?))
  
  (define discrete-histogram-bins
    (make-struct-field-accessor discrete-histogram-field-ref 3 'bins))
  
  (define set-discrete-histogram-bins!
    (make-struct-field-mutator set-discrete-histogram-field! 3 'bins))
  
  ;; discrete-histogram-increment!:
  ;;   discrete-histogram x integer -> void
  (define (discrete-histogram-increment! h i)
    (discrete-histogram-accumulate! h i 1))
  
  ;; discrete-histogram-accumulate!:
  ;;   discrete-histogram x integer x real -> void
  (define (discrete-histogram-accumulate! h i weight)
    (let* ((n1 (discrete-histogram-n1 h))
           (n2 (discrete-histogram-n2 h))
           (n (+ (- n2 n1) 1))
           (dynamic? (discrete-histogram-dynamic? h))
           (bins (discrete-histogram-bins h)))
      (let/ec exit
        (if (not (<= n1 i n2))
            (if (not dynamic?)
                (exit (void))
                (let* ((new-n1 (if (> n 0) (min i n1) i))
                       (new-n2 (if (> n 0) (max i n2) i))
                       (new-n (+ (- new-n2 new-n1) 1))
                       (new-bins (make-vector new-n)))
                  ;; Copy bins
                  (do ((i 0 (+ i 1)))
                      ((= i n) (void))
                    (vector-set! new-bins (+ (- n1 new-n1) i)
                                 (vector-ref bins i)))
                  ;; Update local variables
                  (set! n1 new-n1)
                  (set! n2 new-n2)
                  (set! n new-n)
                  (set! bins new-bins)
                  ;; Update discrete-histogram instance
                  (set-discrete-histogram-n1! h n1)
                  (set-discrete-histogram-n2! h n2)
                  (set-discrete-histogram-bins! h bins))))
        ;; Update bins (<= n1 i n2)
        (let ((bin (- i n1)))
          (vector-set! bins bin (+ (vector-ref bins bin) weight))))))
  
  ;; discrete-histogram-get: discrete-histogram x integer -> real
  (define (discrete-histogram-get h i)
    (let ((n1 (discrete-histogram-n1 h))
          (n2 (discrete-histogram-n2 h))
          (bins (discrete-histogram-bins h)))
      (if (<= n1 i n2)
          (vector-ref bins (- i n1))
          (raise-mismatch-error 'discrete-histogram-bins
                                "index out of range" i))))
  
  ;; discrete-histogram-max: discrete-histogram -> real
  (define (discrete-histogram-max h)
    (let* ((n1 (discrete-histogram-n1 h))
           (n2 (discrete-histogram-n2 h))
           (n (+ (- n2 n1) 1))
           (bins (discrete-histogram-bins h))
           (max -inf.0))
      (do ((i 0 (+ i 1)))
          ((>= i n) max)
        (let ((x (vector-ref bins i)))
          (if (> x max)
              (set! max x))))))
  
  ;; discrete-histogram-min: discrete-histogram -> real
  (define (discrete-histogram-min h)
    (let* ((n1 (discrete-histogram-n1 h))
           (n2 (discrete-histogram-n2 h))
           (n (+ (- n2 n1) 1))
           (bins (discrete-histogram-bins h))
           (min +inf.0))
      (do ((i 0 (+ i 1)))
          ((>= i n) min)
        (let ((x (vector-ref bins i)))
          (if (< x min)
              (set! min x))))))
  
  ;; discrete-histogram-sum: discrete-histogram -> real
  (define (discrete-histogram-sum h)
    (let* ((n1 (discrete-histogram-n1 h))
           (n2 (discrete-histogram-n2 h))
           (n (+ (- n2 n1) 1))
           (bins (discrete-histogram-bins h))
           (sum 0.0))
      (do ((i 0 (+ i 1)))
          ((>= i n) sum)
        (set! sum (+ sum (vector-ref bins i))))))
   
)