home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / object / 2969 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  2.6 KB
  1. Xref: sparky comp.object:2969 comp.programming:2063
  2. Newsgroups: comp.object,comp.programming
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!wupost!m.cs.uiuc.edu!m.cs.uiuc.edu!liberte
  4. From: liberte@cs.uiuc.edu (Daniel LaLiberte)
  5. Subject: Re: How to design a data structure library.
  6. In-Reply-To: richieb@bony1.bony.com's message of Tue, 21 Jul 92 12:42:56 GMT
  7. Message-ID: <LIBERTE.92Jul22123315@birch.cs.uiuc.edu>
  8. Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager))
  9. Organization: University of Illinois, Urbana-Champaign, Dept CS
  10. References: <1820@snap> <1992Jul21.124256.17256@bony1.bony.com>
  11. Date: Wed, 22 Jul 1992 18:33:15 GMT
  12. Lines: 38
  13.  
  14. This is a great question which should probably be stated more
  15. specifically as "How to design an object-oriented data structure
  16. library", though there should be large overlap with non-OO techniques.
  17. (I removed comp.lang.eiffel and added comp.programming.)
  18.  
  19. In article <1992Jul21.124256.17256@bony1.bony.com> richieb@bony1.bony.com (Richard Bielak) writes:
  20.  
  21.    I think that cursors should be separate from the data structure they
  22.    are used to traverse. The main reason is to allow multiple iterations
  23.    over the same list. 
  24.  
  25. I would agree that cursors for iteration should at least be separable
  26. from the objects being iterated over.  However, in some applications,
  27. it may be sufficient, and probably more efficient, to mixin the
  28. cursors with the objects being iterated over.  How to define a class
  29. such that it may be either mixed in or used separately sounds like
  30. an interesting problem.  The functionality is very similar in both cases
  31. so there should be some way to share common features.
  32.  
  33. Related to this problem of multiple simultaneous uses of a feature
  34. (the multiple iterators, not the mixin vs. separable uses of a class),
  35. I have been working with iterators over DAGs.  To avoid traversing a
  36. subdag more than once, I mark nodes as having been visited.  The
  37. visited status needs to be consistently cleared either before or after
  38. the traversal, though before seemed better but I forget why.  
  39.  
  40. This traversal scheme does not allow multiple simultaneous traversals
  41. even if the cursor (which I also dont use) is external to the DAG
  42. nodes.  I havent needed this feature (yet!), but I wonder about the
  43. alternatives.  One alternative would be to pretraverse the structure
  44. building a linear list of nodes to traverse.  This requires extra
  45. temporary space but could probably be faster than my current scheme if
  46. you hashed the elements of the constructed linear list to avoid linear
  47. searches.
  48.  
  49. Dan LaLiberte
  50. liberte@cs.uiuc.edu
  51. (Join the League for Programming Freedom: league@prep.ai.mit.edu)
  52.