DS_CIRCULAR

Guys,

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. There are currently 
four classes:

DS_CIRCULAR
DS_ARRAYED_CIRCULAR
DS_CIRCULAR_CURSOR
DS_ARRAYED_CIRCULAR_CURSOR

I will also probably implement linked versions, even though I don't 
need them.

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. 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.

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.

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.

Likewise DS_CIRCULAR_CURSOR inherits from DS_BILINEAR_CURSOR, 
DS_DYNAMIC_CURSOR, and DS_INDEXED_CURSOR.

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'

I suppose the proper thing to do is to leave the inheritance the way 
it is, but to rename some of the linear features. For example:

inherit DS_BILINEAR [G]
  rename
    forth as linear_forth,
    back as linear_back
  end

Then add some new features that iterate in a circular manner. The 
postcondition of the new `forth' would be not_after: not is_empty 
implies not after.

What do you think? Any suggestions?

Thanks,
Brian Heilig






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/