turpin@cs.utexas.edu (03/02/91)
----- ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes, in response to > I am still interested in a *clear* description of > - what "cones" _are_, and An cone of depth N is a collection of N circular lists such that: o the i-th list has i elements, and o the lists are interconnected through a pointer in each element, where this pointer in the j-th element of the i-th list points to the j-th element of the (i-1)-st list for j<i, and is null for j=i. (One can also run these the other way.) > - what they are _for_. Often when people talk about data structures at an abstract level, they content themselves with a class that is either largely tree-like or largely array-like. Those who have gotten their hands dirty in various applications know that on occasion one needs a data structure that is more complex. (Admittedly, 99% of all data structures are simple variants of trees or lists.) Now the real examples do not exhibit much "general interest", because their explanation is often closely associated with one particular problem, and the theorist is likely to say "that problem can be solved in this much neater fashion, and it still has the same theoretical performance with only two additional hash table probes", in ignorance of the fact that it *was* solved that way, performance analysis indicted those two hash table probes, and now pointers are being added to the data structures to reduce response time from 15 minutes to something interactive. Or if the theorist accedes that in this particular case one needs those messy pointers, well "that is just that particular case". The problem is that there is a lot of such particular cases. So with their hands dirtied and their complaints stifled, those in the business conspired to create a data structure that was more complex than trees or arrays to throw at the theoreticians, that reflected the kinds of things they often saw. They wanted it simple enough to explain quickly, but sufficiently complex in structure to be a real test. So they invented the cone. Its sole use is as a known hard data structure that is handed to those who claim they can handle data structures well. One can do all sorts of fun things with a cone. One can search a ring or search a stay (a continuous series of the cross-pointers), or add an outer ring or delete any ring and a stay from that ring outwards. And if one can do all these fun things, one has a fair claim to handling complex data structures. Russell