From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Re: Sigh. So, what is a proper class definition ?
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
Date: Thu, 1 Oct 1992 15:39:40 GMT

In article <KANZE.92Sep29202632@slsvcgt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
>In article <1992Sep23.162216.21027@ucc.su.OZ.AU>
>maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>
>> In article <4277@seti.UUCP> ziane@nuri.inria.fr (ziane mikal -) writes:
>> >
>> >A related problem is about the "insert" method of a list package.
>> >Should "insert" be considered as a defining property of a list class ?
>
>> 	IMHO, yes.
>> > 
>> >Intuitively it seems weird, since one might want to use lists whithout
>> >adding new elements. The very concept of a list seems, at first,
>> >well defined by access methods. However, if we look at a recursive
>> >definition of a list, there is likely to be an axiom for insertion.
>> >That is a complicated list is defined in terms of operations on simpler
>> >ones.
>> >But shouldn't insertion be defined as a constructor, if we only
>> >want to manipulate constant lists ?
>> >
>> >Mikal (Mikal.Ziane@inria.fr)
>
>> 	A list is an array with insert and remove operators.
>> Arrays have [] access and a length operator. I dont bother
>> with iterators for lists---integers do just fine. This
>> approach is inefficient, but a cache can improve that.
>> (If I really want ultra fast access I can use 'first' and 'next',
>> but I hardly ever bother)
>
>And what happens if efficiency later becomes important.

	I thought I said: attach a cache to the list. Or reimplement
the list as doublely linked.

	What do YOU do if you want to read the list backwards?
Woops, you have to write some special code, every time.
I just read it backwards. I dont make any assumptions about
the physical list organisation. I treat the list as an
Abstract Data Type.

	Besides, I *also* supply 'first' and 'next' which
return pointers, and they're even faster than an iterator.
>
>I almost never use int (for anything).  It's almost always better to
>whip up a small class.  How much work would it be to encapsulate your
>int in an iterator class?  And if efficiency does become important,
>re-implement the iterator class in a more efficient manner.  Without
>breaking any code that uses it.
>
>Once you've used int as the iterator, you're stuck.  Any improvements
>break user code.

	On the contrary, once you use a sequential iterator you're
stuck. Then you can ONLY read the list in sequence. But that is
absurd because mathematically that IMPLIES random access.
So the sequential nature of a list is usually an artefact
of the most efficient access method, which is not a very
good criterion for abstract class design.

	A second advantage of integers for iterators is that
they can be used to iterate lists in parallel. A third advantage
is that insertions and deletions into the list are safe at
all times (provided the integer index is compared with the length
of the list before each access) although the effect may not
be what is desired!

	But the principal advantage is simplicity: as a list
is just like an array, it is accessed accordingly. Any routine
coded for an array will work on a list. (BTW, I mean by
array something accessed by a[i], and which has a determinable
length).

	I can write: (+a is the no of elts in a)

	for(int i=0; i<+a; ++i) { ... a[i]; ... }

	and it always terminates, and every access to a is in bounds.
(provided a[i] and all elts to the end are not deleted prior to another
access to a[i])
	
>
>BTW, I'm not saying that the lack of efficiency is bad.  Just
>encapsulate it so you can change later, without too much effort.

	I agree. Its just that I've encapsulated something different
to an iterator or single linked list with sequential access.
I've encapsulated the idea of an array with insert and delete
operations.

	As an abstraction this is a great base for 'stack',
'queue', etc. And for subsequent addition of iterators.
Perhaps I should have called it something other than 'list'.

-- 
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------
Newsgroups: comp.lang.c++