[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- To: common-lisp-object-system@SAIL.STANFORD.EDU
- Subject: Last-Visited Preorder
- From: Dick Gabriel <RPG@SAIL.STANFORD.EDU>
- Date: 28 Jan 87 1922 PST
If we decide the last-visited preorder is what we want for
a tiebreaker, then there is a simple linear way to compute it
without having to wonder whether reversed reversed postorder is
the same as last-visited preorder.
For every class you keep track of the in-degree with respect to the
sublattice of interest; the in-degree is the number of direct subclasses
of a class. When you walk from the class of interest, you keep track of
how many times you've visited that class. When you have visited it the
same number of times as its in-degree, you can walk from that class. The
exception is the class of interest, which you will visit once more than
its in-degree (you visit it once and its in-degree is 0).