Comments (2)
from ods.
Thanks ok for the names. I will continue to read the book but code breaks invariants and this is a pity because it could be a great book.
Here is my full log of analysis of the first ArrayStack implementation.
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.
Here are the code snippets of the book.
T[] a;
int n;
int size() {
return n; }
T set(int i, T x) {
T y = a[i];
a[i] = x;
return y;
}
T get(int i) {
return a[i];
}
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++;
}
T remove(int i) {
T x = a[i];
for (int j = i; j < n-1; j++)
a[j] = a[j+1];
n--;
if (a.length >= 3*n) resize();
return x;
}
void resize() {
T[] b = newArray(max(n*2,1));
for (int i = 0; i < n; i++) {
b[i] = a[i]; }
a = b; }
Analysis
To me these definitions are bogus. The name is particularly not good because this is not a stack but a list. So a better name is SimpleArrayList or NaiveArrayList.
About set and get
-
set
andget
do not check for n range. This is done in the Java implementation but not in the book. This is ok since array will raise an error if the bounds are not correct. -
More important,
set
does not update the number of elements, so using set break the invariant that n is the number of elements stored. -
set
should not return the previous value because it propagates null value -
why
set
andget
are needed (I renamed them as at: at:put:) but they are not needed in a Stack API.
API problems
The java implementation is better than the algo in the book but still some of them are bogus.
The Java implementation mentioned that ArrayStack is a copy of the JCF class ArrayList but this is not the same API in particular add(i, object) is not good because the user can add anywhere an element.
Let us have a look at add add(int i, T x)
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++;
}
Imagine that we have a ArrayStack with 5 of capacity and with 5 elements, the user can use add(3000, anObject). This example raises two problems:
- first the resize is not good because it will not grow enough :), here resize will grow to 10 only :). When giving the user the possibility to specify a given an index.
- Index should be validated. The Java implementation is better because it does bound check.
T remove(int i) {
T x = a[i];
for (int j = i; j < n-1; j++)
a[j] = a[j+1];
n--;
if (a.length >= 3*n) resize();
return x;
}
- Second what will happens if we remove a not occupied element, eg remove(8) on a collection of capacity 10 with 5 elements #(x x x x x _ _ _ _ _), 8 is in range, the collection keeps the same data but the number of elements is decreased.
Unclear points
It is unclear why elements are shifted in the remove or add. It looks like add is in fact an insertAt a given index. The fact that we can add an element at a given index is mixing lot of concerns.
from ods.
Related Issues (20)
- Truncated text in pseudocode version
- I think it is better to make it deep copy. HOT 1
- [Java] Book update
- Can't access the website HOT 1
- Possible typo in Section 1.3.1
- figure 2.3 error?
- Piece of (pseudo)code missing
- Pseudocode snippet missing in 4.3 Skiplist
- SLList wrong function addAfter HOT 1
- std::copy overlap, key overwrite after copy.
- Some very serious error at page 184 HOT 1
- Change of parameter of inkscape in latex/images/Makefile
- Python 2 scripts
- Conflict between package babel and fancyhead
- 5.2.3 tabulation hashing
- 5.3.2 the proof of theorem 5.3
- suggestion to improve discoverability
- DLList.remove and SLList.remove in the python version do not return values.
- Integer Overflow (?) on implementation pp. 127, in section 5.3.3 Hash Codes for Arrays and Strings, C++ edition
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from ods.