-
Notifications
You must be signed in to change notification settings - Fork 249
Open
Description
I started the book and the first datastructure feels strange and it gave a strange view on the rest of the book.
See
https://github.com/Ducasse/Containers-XP/blob/master/Containers-XP/CTArrayStack.class.st
and copied here.
Started to implement ArrayStack from this book https://opendatastructures.org/
But the first datastructure feels strange and it gave a strange view on the rest of the book.
The book defines the state of ArrayStack as an array and a number representing the number of elements.
T[] a;
int n;
int size() {
return n; }
For example add is defined as follows:
void add(int i, T x) {
if (n + 1 > a.length) resize();
for (int j = n; j > i; j--)
a[j] = a[j-1];
a[i] = x;
n++;
}
Set is defined as follows:
T set(int i, T x) {
T y = a[i];
a[i] = x;
return y;
}
To me these definition are bogus.
Indeed
- first
set
does not update the number of elements, so using set break the invariant that n is the number of elements stored. - second
set
should not return the previous value because it propagates null value - third why
set
andget
are needed (I renamed them as at: at:put:) but they are not needed in a Stack API.
Metadata
Metadata
Assignees
Labels
No labels