Re: DS_CIRCULAR

Franck Arnaud:

> Brian Heilig:

> > 1. iteration is circular (iteration over the `last'
> >    item brings the cursor back to the `first', and
> >    vice versa)
>
> We could add this trivially to all cursors if that's useful:

I suppose it is useful, but I believe the type I am referring to 
deserves its own class.

> > 2. removal of items from the beginning of the list
> >    is done in O(1)
> 
> DS_LINKED_LIST already has this property...

But this is a circular array, and thus gains all the benefits of 
having an array for storage.

> Even a more circular version as you suggest with wraparound (where 
> 'before' can be after 'last') need only be an implementation of 
> DS_LIST

That's where I was headed. I asked, "Is a DS_CIRCULAR a DS_LIST"? 
List seems to indicate sequential access from start to finish. 
Circular seems to indicate sequential circular access. Hence the 
dilemma. However DS_LIST has most of the necessary features (albeit 
mostly deferred). Also list access is required in addition to 
circular access.

> (and probably, but not necessarily, descendant of 
> DS_ARRAYED_LIST for implementation purposes)

As it turns out inheriting from DS_ARRAYED_LIST for implementation 
purposes is a bad idea. Almost all features would need to be 
redefined because either they do not take advantage of the ease of 
removal from the beginning, or they do not handle the fact the the 
elements may span the array bounds.

> , as this does not 
> introduce any interesting new feature beyond the faster inserts 
> at the start, so it's an implementation detail.

That's what I thought, but from an overall perspective of the library 
(and from a theoretical perspective) is a circular also a list?

Here are the two possibilities I have (I hope they render Ok):

--- Option 1 ----------------------------------------------

          DS_LIST                    DS_LIST_CURSOR
             ^                             ^
             |                             |
      DS_CIRCULAR_LIST           DS_CIRCULAR_LIST_CURSOR
             ^                             ^
             |                             |
   DS_ARRAYED_CIRCULAR_LIST  DS_ARRAYED_CIRCULAR_LIST_CURSOR


DS_CIRCULAR_LIST and DS_CIRCULAR_LIST_CURSOR include features to 
perform circular traversal.


--- Option 2 -----------------------------------------------

DS_BILINEAR        DS_INDEXABLE
     ^                    ^
     |                    |
     ----------------------
                |
           DS_CIRCULAR
                ^
                |
        DS_ARRAYED_CIRCULAR


            DS_INDEXED_CURSOR
                    ^
DS_BILINEAR_CURSOR  |  DS_DYNAMIC_CURSOR
         ^          |           ^
         |          |           |
         ------------------------
                    |
            DS_CIRCULAR_CURSOR
                    ^
                    |
        DS_ARRAYED_CIRCULAR_CURSOR

Here DS_CIRCULAR and DS_CIRCULAR_CURSOR duplicate a lot of the code 
that is in DS_LIST and DS_LIST cursor. The advantage of this 
architecture might be that it is clearer from an overall perspective 
(a list is not circular, and a circular is not a list). But now that 
I think of it, I like the perspective that a circular is a list that 
_can also_ be traversed circularly. Any more thoughts?

Thanks for your help,
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/