[Go to first, previous, next page;   contents;   index]

Chapter 9

Sets

In the PLT Scheme Simulation Collection, a set is a general structure that maintains a (doubly linked) list of its elements. The length of the list, i.e. the n field, is implemented using a variable and, therefore, provides automatic data collection.

9.1  The set-cell Structure

set-cell

Structure: 
set-cell

Contract: 

(struct set-cell
        ((next set-cell?)
         (previous set-cell?)
         (priority real?)
         (item any?)))

The set-cell structure represents an item in a set.

9.2  The set Structure

set

Structure: 
set

Contract: 

(struct set
        ((variable-n variable?)
         (first-cell (union/c set-cell? #f))
         (last-cell (union/c set-cell? #f))
         (type (one-of/c #:fifo #:lifo #:priority))))

The set structure represents a collection of items.

variable-n - a variable that stores the number of elements in the set. This allows automatic data collection of the number of elements. Note that the actual number of elements is available (as a natural number) using the pseudo-field set-n.
first-cell - the set cell representing the first item in the set, or #f if the set is empty.
last-cell - the set cell representing the last item in the set, or #f if the set is empty.
type - the type of set (for the generic set operations). Valid values are: #:fifo for a first-in-first-out set (i.e. a queue), #:lifo for a last-in-first-out set (i.e. a stack), or #:priority for a priority set (i.e. a set ordered by priority).

make-set

Function: 
(make-set type)
(make-set)

Contract: 

(case-> (-> (one-of/c #:fifo #:lifo #:priority) set?)
        (-> set?))

This function returns a new (empty) set of the specified type. If type is not specified, a #:fifo set is created (i.e. a queue).

set-n

Function: 
(set-n set value)

Contract: 

(-> set? natural-number/c)

This function returns the value if the n field of the variable-n field of set. This is the number of elements in the set. Note that this is stored in a variable to facilitate automatic data collection of the number of elements in a set.

9.3  Set Operations

set-empty?

Function: 
(set-empty? x)

Contract: 

(-> any? boolean?)

This function returns #t if x is a set or #t otherwise.

set-first

Function: 
(set-first set)

Contract: 

(-> set? any)

This functions returns the first element in set. An error is signaled if set is empty.

set-last

Function: 
(set-last set)

Contract: 

(-> set? any)

This functions returns the last element in set. An error is signaled if set is empty.

set-for-each-cell

Function: 
(set-for-each-cell set proc)

Contract: 

(-> set? procedure? void)

This function iterates over the cells in set and applies the procedure proc to each cell in turn.

set-for-each

Function: 
(set-for-each set proc)

Contract: 

(-> set? procedure? void)

This function iterates over the elements in set and applies the procedure proc to each element in turn.

set-find-cell

Function: 
(set-find-cell set item)

Contract: 

(-> set? any? (union/c set-cell? #f))

This function returns the cell in set that contains item or #f if it is not found.

set-insert-cell-first!

Function: 
(set-insert-cell-first! set cell

Contract: 

(-> set? set-cell? void?)

This function inserts the cell as the first element of set. This is independent of the type of the set.

set-insert-first!

Function: 
(set-insert-first! set item)

Contract: 

(-> set? any? void?)

This function creates a new cell containing item and inserting it as the first element of set. This is independent of the type of the set.

set-insert-cell-last!

Function: 
(set-insert-cell-last! set cell

Contract: 

(-> set? set-cell? void?)

This function inserts the cell as the last element of set. This is independent of the type of the set.

set-insert-last!

Function: 
(set-insert-last! set item)

Contract: 

(-> set? any? void?)

This function creates a new cell containing item and inserting it as the last element of set. This is independent of the type of the set.

set-insert-cell-priority!

Function: 
(set-insert-cell-first! set cell

Contract: 

(-> set? set-cell? void?)

This function inserts the cell into set with its stored priority.

set-insert-priority!

Function: 
(set-insert-first! set item priority)

Contract: 

(-> set? any? real? void?)

This function creates a cell containing item and inserts into set with the given priority.

set-remove-cell!

Function: 
(set-remove-cell! set cell

Contract: 

(-> set? set-cell? void?)

This function removes the cell from set. No error is raised if the cell is not found.

set-remove-item!

Function: 
(set-remove-item! set item)

Contract: 

(-> set? any? (union/c set-cell? #f))

This function removes the cell containing the item from set. If the item was found, the cell containing it is returned, otherwise #f is returned.

set-remove-first-cell!

Function: 
(set-remove-first cell! set error-thunk)
(set-remove-first-cell! set

Contract: 

(case-> (-> set? procedure? any)
        (-> set? set-cell?))

This function removes the first cell from the set and returns it. If the set is empty and the error-think is provided, it is evaluated and the result returned. Otherwise, if the set is empty, an error is raised.

set-remove-first!

Function: 
(set-remove-first! set error-thunk)
(set-remove-first! set

Contract: 

(case-> (-> set? procedure? any)
        (-> set? any))

This function removes the first item from the set and returns it. If the set is empty and the error-think is provided, it is evaluated and the result returned. Otherwise, if the set is empty, an error is raised.

set-remove-last-cell!

Function: 
(set-remove-last cell! set error-thunk)
(set-remove-last-cell! set

Contract: 

(case-> (-> set? procedure? any)
        (-> set? set-cell?))

This function removes the last cell from the set and returns it. If the set is empty and the error-think is provided, it is evaluated and the result returned. Otherwise, if the set is empty, an error is raised.

set-remove-last!

Function: 
(set-remove-last! set error-thunk)
(set-remove-last! set

Contract: 

(case-> (-> set? procedure? any)
        (-> set? any))

This function removes the last item from the set and returns it. If the set is empty and the error-think is provided, it is evaluated and the result returned. Otherwise, if the set is empty, an error is raised.

9.3.1  Generic Routines

set-insert!

Function: 
(set-insert! set item priority)
(set-insert! set item)

Contract: 

(case-> (-> set? any? real? void?)
        (-> set? any? void?))

This function creates a cell containing item and inserts into set with the given priority according to the type of the set.

#:fifo - the item is inserted at the end of the set. The priority, if provided, is ignored.
#:lifo - the item is inserted at the beginning of the set. The priority, if provided, is ignored.
#:priority - the item is inserted in the set according to the priority. If priority is not provided, 100 is used.

set-remove!

Function: 
(set-remove! set item)
(set-remove! set)

Contract: 

(case-> (-> set? any? void?)
        (-> set? any?))

If an item is specified, the cell in the set containing the item is removed and returned.

If an item is not specified, then this function removes the dirst item from the set and returns it. An error is signaled if the set is empty.

9.4  Example - Furnace Model 1

The furnace model will be used in Chapter 10 Continuous Simulation Models to illustrate building a continuous model. This initial model is a purely discrete-event model of the same system. The furnace itself is modeled by a set.

This simulation model is derived from an example in Introduction to Combined Discrete-Continuous Simulation Using SIMSCRIPT II.5 by Abdel-Moaty M Fayek[1].

;;; Model 1 - Discrete Event Model
(require (planet "simulation-with-graphics.ss"
                 ("williams" "simulation.plt")))
(require (planet "random-distributions.ss"
                 ("williams" "science.plt")))

;;; Simulation Parameters
(define end-time 720.0)
(define n-pits 7)

;;; Data collection variables
(define total-ingots 0)
(define wait-time (make-variable))

;;; Model Definition
(define random-sources (make-random-source-vector 2))

(define furnace #f)
(define pit #f)

(define (scheduler)
  (let loop ()
    (schedule now (ingot))
    (wait (random-exponential (vector-ref random-sources 0) 1.5))
    (loop)))

(define-process (ingot)
  (let ((arrive-time (current-simulation-time)))
    (with-resource (pit)
      (set-variable-value!
        wait-time (- (current-simulation-time) arrive-time))
      (set-insert! furnace self)
      (work (random-flat (vector-ref random-sources 1) 4.0 8.0))
      (set-remove! furnace self))
    (set! total-ingots (+ total-ingots 1))))

(define (stop-sim)
  (printf
    "Report after ~a Simulated Hours - ~a Ingots Processed~n"
    (current-simulation-time) total-ingots)
  (printf "~n-- Ingot Waiting Time Statistics --~n")
  (printf "Mean Wait Time        = ~a~n"
          (variable-mean wait-time))
  (printf "Variance              = ~a~n"
          (variable-variance wait-time))
  (printf "Maximum Wait Time     = ~a~n"
          (variable-maximum wait-time))
  (printf "~n-- Furnace Utilization Statistics --~n")
  (printf "Mean No. of Ingots    = ~a~n"
          (variable-mean (set-variable-n furnace)))
  (printf "Variance              = ~a~n"
          (variable-variance (set-variable-n furnace)))
  (printf "Maximum No. of Ingots = ~a~n"
          (variable-maximum (set-variable-n furnace)))
  (printf "Minimum No. of Ingots = ~a~n"
          (variable-minimum (set-variable-n furnace)))
  (printf "~a~n"
          (history-plot
            (variable-history (set-variable-n furnace))
            "Furnace Utilization History"))
  (stop-simulation))

(define (initialize)
  (set! total-ingots 0)
  (set! wait-time (make-variable))
  (set! pit (make-resource n-pits))
  (set! furnace (make-set))
  (accumulate (variable-history (set-variable-n furnace)))
  (tally (variable-statistics wait-time))
  (schedule (at end-time) (stop-sim))
  (schedule (at 0.0) (scheduler)))

(define (run-simulation)
  (with-new-simulation-environment
    (initialize)
    (start-simulation)))

The following is the output from the simulation.

>(run-simulation)
Report after 720.0 Simulated Hours - 479 Ingots Processed

-- Ingot Waiting Time Statistics --
Mean Wait Time        = 0.1482393804317038
Variance              = 0.24601817483957691
Maximum Wait Time     = 3.593058032365832

-- Furnace Utilization Statistics --
Mean No. of Ingots    = 4.0063959874393795
Variance              = 3.2693449366238347
Maximum No. of Ingots = 7
Minimum No. of Ingots = 0

[sets-Z-G-1.gif] 
>

[Go to first, previous, next page;   contents;   index]