🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.lang.clos
Article #9

Re: CLOS data structures shelf

#9
From: Daniel LaLiberte
Date: Thu, 29 Oct 1992 19:41
30 lines
2087 bytes
Oh, what the heck, I'm not proud.  Below is the header from my
CLOS-based dag.lisp code.  It is certainly not the ultimate in clean
code, but I find it pretty useful and it is somewhere to start.  Please
include it in the archive.

Dan LaLiberte
liberte@cs.uiuc.edu
(Join the League for Programming Freedom: lpf@uunet.uu.net)
"If we don't succeed, we run the risk of failure.
		-- Vice President Dan Quayle."
---------
DAG (directed acyclic graph) structures are made of dag-nodes and dag-groups.
dag-group is a subclass of dag-node, and dag-group instances list all the 
sub-nodes of the group.  dag-nodes list all parents, which strictly speaking 
is not part of a dag data structure, so this should probably be called
something like a dag-with-backlinks structure.  One can look at the parent
references as forming an upside down dag structure, but CLOS doesnt deal
well with unshared slots with the same name.

Also, dag-group might be implemented as a subclass of a tree class.
The difference, of course, is that dag-nodes may be shared by multiple
parents.

To support traversals, an external hash table is used (see tally class
below).  This permits multiple simultaneous traversals, and avoids an
extra pass to unvisit.  It is also safer.  One problem is the wasted
space of a hash table each time a traversal occurs.

There is alot of redundancy in the traversal functions.  
How can I simplify them?
Technical Details
Message-ID: <LIBERTE.92Oct29134136@birch.cs.uiuc.edu>
Path: arc1-ca.pugleaf.net!sparky!uunet!ukma!wupost!cs.uiuc.edu!m.cs.uiuc.edu!m.cs.uiuc.edu!liberte
References: <1992Oct29.114419@disuns2.epfl.ch> <WELCH.92Oct29095546@sacral.cis.ohio-state.edu>

Show Full Headers
Complete Article Headers
Newsgroups: comp.lang.clos
Path: arc1-ca.pugleaf.net!sparky!uunet!ukma!wupost!cs.uiuc.edu!m.cs.uiuc.edu!m.cs.uiuc.edu!liberte
From: liberte@cs.uiuc.edu (Daniel LaLiberte)
Subject: Re: CLOS data structures shelf
In-Reply-To: welch@sacral.cis.ohio-state.edu's message of Thu, 29 Oct 1992 14:55:46 GMT
Message-ID: <LIBERTE.92Oct29134136@birch.cs.uiuc.edu>
Followup-To: comp.lang.clos
Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager))
Organization: University of Illinois, Urbana-Champaign, Dept CS
References: <1992Oct29.114419@disuns2.epfl.ch>
 <WELCH.92Oct29095546@sacral.cis.ohio-state.edu>
Date: Thu, 29 Oct 1992 19:41:36 GMT
Lines: 33