[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: ADT List (2)
Hallo!
> To keep traffic low, I collect the mails that appear on the mailing
> list over the day until 16:00 local time (currently GMT+2). Then I
> will post a reply at approximately 18:00 (also local time).
That's ok for me. I also want to announce that I'll be away on holiday
from saturday this week to friday next week. So dont be suprised when
I suddenly stop argumenting ;-)
> What would we gain with this approach? Obviously, it is very
I also asked for this.
> Actually, I am changing the procedure `Filter' to be not destructive.
> I have the nagging feeling that it is more useful this way.
Good. This gives you the possibilty to filter by deleting, copying or
moving to another list.
> list has a number of properties. Of course, these properties can be
> used to make the use of a list more efficient. That is the reason
> why, e.g., the fields `prev' and `next' are visible to the user.
These fields are special to this special implementation of a list (one
could implement a gap list or a list using nodes of short arrays...).
So you can export them, the user can use them but he must be aware that
he cannot exchange the implementation on the fly a sa result.
> provided by the ADT implementation itself. For convenience and
> efficiency. That is, we don't need a minimal set of procedures, but a
> minimal _convenient_ set.
That is my understanding of "confortable", too.
> You should provide some information how these iterators of yours are
I'll give a statement on iterator later, too...
> If you extend List, the new type's interface is a superset of the one
> of List. If Stack _uses_ List, then the interfaces can be distinct.
If Stack uses List as its implementation it must not inherit but List
must be a private member and Stack should delegate all its calls to
List. This gives us another principal question. Should it be allowed
for the library to reuse other datatypes (like Stack uses List) or
should every datatype be implemented "native". The first one reduces
code bloat and minimizes bugs my reusing proofed code the later one
maybe more speed optimized.
> Correct. The operations provided by a ADT should be based on its
> "characteristics" sheet.
True. No "Last" for stacks only "First".
> This is certainly worth consideration. Of course, this can only be
> decided once the general form of the whole library is less hazy.
True. So just fix now that abstract interfaces have the name of the
datatype and derived class that implement functionality have some
suffix or prefix.
> TT> > Currently, ADT List is a direct descendant of the type `Object'.
> TT> > Should we define a intermediate (possibly abstract) type
> TT> > Container/Collection/Bag? And what properties should this
> TT> > intermediate type have? [If anyone answers to this with "let's
> TT> > introduce xyz" WITHOUT giving a detailed outline and a module
> TT> > interface, I am seriously annoyed.]
> For now, we can ignore any ADTs that need a half order between
> objects.
What do you mean?
> Also, your statements confuse me. Is it worthwhile to introduce
> intermediate classes? Should they be abstract or concrete? How
> should these classes look like?
Ok. As a result of my own implementation I would state that some base
classes are usefull while others are not. Exspecially good was the
introduction of a Comparable Object, that implements comparisons, I
would sugest to implement this again. I would also suggest to implement
the evaluation of a hashvalue (LONGINT) somewhere in the baseclass.
This way you can heasily hash any objects not only string. hashtables
get simpler.
Not good was the implemenation of baseclass for collections
(Collectable). f.e. Collectable implemented the generic method:
PROCEDURE (c : Collectable) Add*(object : Object);
However not all collections inherting from Collectable were able to
implement this methods correct (Note, a hashtable needs two objects -
a key and a value - for adding). Other collections imposed restrictions
on the to be added object that weren't covered by the paramtertype
Object. E.g. A Tree can only add objects that derive from Comparable
not Object itself. Tree as a result has to do heavy casting. There
interface implemented had non-visible restrictions. I wouldn't do that
again. There are other ways (through iterators) to implement generic
communication between collections.
> TT> Different Lists (dynamic-, array
> TT> implementation) should derive from List and implement the needed
> TT> methods.
> Based on the current List outline, how would you define the common
> base class of all lists? Or would you suggest to create the base
> class by simply defining ListDesc to the empty record, and replace
> the Element data types with generic navigation methods? Mh, maybe you
> should provide a module interface!
Yes. We should implement a module List, that defines all methods common
to all List implementations. This methods should be abstract (empty, or
using HALT).
E.g. (not syntax checked)
MODULE Iterator;
IMPORT StdTypes;
TYPE
ReadIterator* = POINTER TO IteratorDesc;
ReadIteratorDesc* = RECORD
END;
PROCEDURE (i : ReadIterator) Last*():BOOLEAN;
BEGIN
HALT(1);
END Last;
PROCEDURE (i : ReadIterator) Next*():BOOLEAN;
BEGIN
HALT(1);
END Last;
PROCEDURE (i : ReadIterator) Value*()StdTypes.Object;
BEGIN
HALT(1);
END Value;
END Iterator.
MODULE List;
IMPORT StdTypes, Iterator;
TYPE
List* = POINTER TO ListDesc;
ListDesc* = RECORD
END;
(* initialisation *)
...
PROCEDURE (l : List) Add*(object : StdTypes.Object);
BEGIN
HALT(1); (* Special error code for abstract method call? *)
END Add;
(*
Since we cannot define any implementation specific memebers
we need a generic way to access object in orur list
*)
PROCEDURE (l : List) ReadIterator*():Iterator.Iterator;
BEGIN
HALT(1);
END ReadIterator;
(* We could also defined a WriteIterator if possible *)
...
END List.
MODULE DynList;
IMPORT StdTypes, Iterator;
TYPE
Node* = POINTER TO NodeDesc;
NodeDesc* = RECORD
prev-,next- : Node;
value- : StdTypes.Object;
END;
List* = POINTER TO ListDesc;
ListDesc* = RECORD (List.List)
first- : Node;
count- LONGINT;
END;
ReadIterator* = POINTER TO ReadIteratorDesc*;
ReadItertorDesc* = RECORD (Iterator.ReadIterator)
current : Node;
END;
(* initialisation *)
...
PROCEDURE (l : List) Add*(object : StdTypes.Object);
BEGIN
(* Special code for allocation and initialisation of Node *)
END Add;
(*
Since we cannot define any implementation specific memebers
we need a generic way to access object in orur list
*)
PROCEDURE (l : List) ReadIterator*():Iterator.Iterator;
BEGIN
(* return special DynList iterator *)
END ReadIterator;
PROCEDURE (i : ReadIterator) Last*():BOOLEAN;
BEGIN
IF current.last#NIL THEN
current:=current.last;
RETURN TRUE;
ELSE
RETURN FALSE;
END;
END Last;
PROCEDURE (i : ReadIterator) Next*():BOOLEAN;
BEGIN
IF current.next#NIL THEN
current:=current.next;
RETURN TRUE;
ELSE
RETURN FALSE;
END;
END Last;
PROCEDURE (i : ReadIterator) Value*()StdTypes.Object;
BEGIN
ASSERT(current#NIL);
RETURN current.value;
END Value;
END DynList.
Important: List does not implement Node, nor does it show how vales are
stored. Access to values is only defined by the use Iterators. DynList
inherits from List and implements all methods. It also shows its
internal datastructures for faster access. By using only methods
defined in List the user can easily switch between different list
implementations. See DoubleList in my sources. Note, that List does not
derive itself from some baseclass Collectable, however it may inherit
from StdTypes.Objects?
Btw., we are currently defining a datatype List, that is made for
implementing it as a double list. Note, that there are slightly
different datatypes List that use a Lisp/single linked like definition.
Their structure is by design far more recursive. In fact our datatype
should not be named List but should be given a more special name. Not
that that special name is for the abstract baseclass (formally called
List). The derived implementations then must get another pre/suffix.
You now may understand why I proposed a clearly defined naming sheme
for modules.
> This should conclude the first round of proposal/counter proposal. I
> was hoping for feedback from more people. We need to address many
> topics, which makes the mails a bit unwieldy. I don't think we can
> split the topics at this early stage, though.
I again offer my hardware help in form of a special mailinglist for it
and some http space. However, the mailinglist will get much slower
then, because I use a dial up connection and normaly onyl call a few
times a day. I also propose to write some paper to post to
comp.lang.oberon *as soon as we can show some results*. This may gave use
some additional help.
> Final remark: If someone throws an idea at me without providing enough
> sample code to get an impression of how it works, and without an
> evaluation of the benefits and disadvantages, then I can do nothing
> except throwing the idea back to the original author, asking for
That is ok, because I will do that, too ;-)
> - a list holds a finite number of objects; the number of objects
> is its length
Finite (because of finite hardware) but not fixed!
> PROCEDURE (l: List) Apply* (op: StdTypes.Operator);
> PROCEDURE (l: List) Map* (fct: StdTypes.Function): List;
> PROCEDURE (l: List) Select* (pred: StdTypes.Predicate);
Am I correct that argument parsing will be implemented by deriving from the
Stdtypes classes?
Note, that sorting can be don, too. The sorting method then casts
Node.obj to type Comparable. You then will get a runtime error, if you
have added elements that are not comparable.
--
Gru...
Tim.