Re: DS_CIRCULAR

Brian Heilig wrote:
> I'm in need of a circular class. I'm in the middle of implementing 
> one that I'd like to provide to the Gobo library. 

The reason why there is no circular class in Gobo is that
at the time I worked on the data structure library the
circular classes of ISE EiffelBase were broken. I don't
know if they are still broken, but at that time it was
just impossible to create such an object without breaking
the postcondition or invariant. I even remember some
colleagues come and ask me if this was normal that
they got an invariant violation at creation. When I
was asking whether they were using a circular class
the answer was often yes. So the advice was to use
a non-circular class instead. In most of the time
the design was not too much affected by this change.
So, because I was used not to use circular classes
I didn't have the need to put them in Gobo.

Now, back to your problems:

> I'm having a little difficulty and would like your advice. There are 
> a few things that make circular data structures beneficial over list 
> versions:
> 
> 1. iteration is circular (iteration over the `last' item brings the 
> cursor back to the `first', and vice versa)
> 2. removal of items from the beginning of the list is done in O(1)
> 
> [last is a synonym for `the item currently defined as last', and 
> likewise with first, since there really is no beginning and end of a 
> circular structure.]
> 
> The implication of 1 is that the cursor is never after, before, or 
> off.

Unless your container is empty.

> However, it is useful to be able to iterate over a circular 
> container once. I don't think Gobo is compatible with this type of 
> behavior. ISE's LINEAR has an `exhausted' query which is set true 
> when the cursor would have gone `off' (but instead the cursor was 
> brought back to the start). Gobo uses `after' as the query to 
> determine when a list has been exhausted.
> 
> In my opnion, 1 is not really that important. If you really want to 
> iterate over the structure in a circular manner then you can do it 
> manually; iterate over it in a linear manner and if the cursor is 
> `after' then restart it.

That's what I did during all these years to avoid having
to use a circular container. There is also Franck's suggestion
of having `circular_forth', although it is missing the
`exhausted' query. The solution with external DS_..._CIRCULAR_CURSOR
is probably better than internal cursor.

> 2 is however beneficial. It is useful for a producer/consumer 
> pattern, where a producer adds items to the end and a consumer `eats' 
> them from the beginning.

Do you need a circular container or a queue (FIFO)?

> My implementation so far does not have the capability to do 1 
> automatically. Here is a summary:
> 
> DS_CIRCULAR inherits from DS_BILINEAR and DS_INDEXABLE. I have found 
> myself duplicating much (all?) of the code in DS_LIST which would 
> imply that I should inherit from DS_LIST instead. But a circular is 
> not really a list...perhaps a minor detail. Also DS_CIRCULAR becomes 
> very empty if it inherits from DS_LIST.

But I'm not even sure that DS_CIRCULAR should be a descendant
of DS_LINEAR. Indeed the class DS_LINEAR specifies containers
that can be tarversed from start to end. Here DS_CIRCULAR
is slightly different because there is no end. So the assertions
are likely to be different. therefore, as shown in the class hierarchy
of one of Franck's messages, DS_CIRCULAR might actually have
to inherit from DS_TRAVERSABLE and not DS_LINEAR, so that it
can provide its own routine specifications. As you pointed
out, it seems overkill because there is apparently a lot of
code duplication.

> DS_ARRAYED_CIRCULAR inherits from DS_CIRCULAR and 
> DS_ARRAYED_CIRCULAR_CURSOR inherits from DS_CIRCULAR_CURSOR.
> 
> I define a `before_position' and an `after_position'. These are valid 
> indeces into `storage'. For example, if `storage' is 10 elements 
> long, `before_position' = 2 and `after_position' = 10, then there is 
> room for 7 elements at `storage' positions [3,9]. Likewise if 
> `before_position' = 8 and `after_position' = 2, then there is room 
> for 4 elements at `storage' positions [9,10] U [0,1].
> 
> Removal of items from the beginning of the list results in simply 
> moving the `before_position'

But this kind of implementation is not peculiar to
DS_ARRAYED_CIRCULAR. It could also be used to implement
a (non-circular) descendant of DS_LIST (it should not be
named DS_ARRAYED_LIST because this class provides an
implementation of its own which is optimized in terms
of calls to `item'). This kind of implementation can
also be used to implement DS_ARRAYED_QUEUE. But queues
are not traversable, so that's probably not what you
want. But still, I wonder whether you really need
a class DS_CIRCULAR. Wouldn't the class that I mentioned
above be enough: a non-circular container similar to
DS_ARRAYED_LIST but using your suggested implementation
(I don't know yet what its name could be)?

-- 
Eric Bezault
mailto:ericb-D6Qt/9opevxWk0Htik3J/[email protected]
http://www.gobosoft.com



To Post a message, send it to:   [email protected]
To Unsubscribe, send a blank message to: [email protected] 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/gobo-eiffel/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/