Re: All paths through a tree

"Blaine" <Blaine.M.Nelson@xxxxxxxxx> writes:
Believe it or not, it's not homework. It's actual work work. I'm
trying to help a government organization that provides satellite
weather data design a ground system for processing the data. They make
300 or so data products. Many of the products take as inputs other
products. The numbers in the list are product ids so product 77, for
instance, depends on product 237. The issue is how best to schedule
the production of the products so as to meet data refresh and latency
requirements.

Since I'm not a programmer (perhaps too dumb) - just an analyst, I get
to use whatever language I want. I can't seem to code in any other
language....

Anyhow, it looks like I have homework now - that is, from Pascal (I
haven't forgotten the last one you assigned me). This one looks like
fun...

Ok, since it's not homework, one more hint.

When you must process a recusive data structure, or any kind of data
structure as it's often the case, the procedure has the same
'structure' as the data.

When you have a record, (a C struct, a lisp structure or object), the
procedure processing it will be the sequential processing of each
field:

(defstruct person name age sex)

(defun process-person (p)
(process-name (person-name p))
(process-age (person-age p))
(process-sex (person-sex p)))


When you have a vector, that is a repeatition of items of some kind,
the procedure processing it will be a repeating loop:

(defun process-vector (v)
(loop :for i :from 0 :below (length v)
:do (process-item (aref v i))))


And the same when you have a recursive structure:

;; list := nil | (cons first rest-list)

(defun process-list (list)
(if (null list)
(process-null)
(progn (process-first (first list))
(process-list (rest list)))))

;; bintree := nil | (make-tree label left-bintree right-bintree)

(defun process-bintree (bt)
(if (null bt)
(process-null)
(progn ;; Note here that a tree is firstly a structure
;; then we have sequence processing each field in turn.
;; Since some fields are recursive structures,
;; some of the processing will be recusive calls.
(process-label (tree-label bt))
(process-bintree (tree-left bt))
(process-bintree (tree-right bt)))))

Of course, the order in which you process the fields might be prefix
order, suffix order, infix order or some other random order ;-)


--
__Pascal Bourguignon__ http://www.informatimago.com/

"Indentation! -- I will show you how to indent when I indent your skull!"
.