1
\$\begingroup\$

Following dreams, I have started learning Java for Game Programing purposes and, during code I figured out that Iterators such as Queue, Lists, Arraylists and what not are very common. I have written this code to replace any array and iterators based useage into one place.

what do i expect from this code?

  • Boost performance, less resources. I tried to minimize the code and process taken overall.
  • Flexibility. Having my code written in a dynamically way that I could use it for any Iterator as i pleased, in such way that it could be a Queue nor List or even a Stack, it's all in one package and i can handle it the way i want.
  • Back-scene overview. Get visual of what's going on, have track on variables and, it's always nicer to know what's going on behind our backs.

Code walk-through.

the full code is available here

Variables. @size: represent the amount of array units is visible to the user. @items: is the elements container. Those are private, handling through the class bounds only.

private int size;
private T[] items;

Constructors. Self explained, one for fixed sized though it could be modified for my desires anytime, and the other is for more dynamically approach.

public Array(int size){
    items = (T[]) new Object[size];
    this.size = size;
}

public Array(){
    items = (T[]) new Object[8];
    size = 0;
}

Setters. This set of methods is used to add elements to the Array node.

// Setting value to specific index.
public void set(int index, T value){
    ensurePointer(index);
    items[index] = value;
}

// Adding value at the end of the scheme.
public void add(T value){
    if(size == items.length) resize( (int)(size * 1.25) );
    items[size] = value;
    size++;
}

// Adding unknown number of variables in one call.
public void addAll(T... values){
    for(T value : values)
        add(value);
}

// Insert value at specific index without overriding.
public void insert(int index, T value){
    ensurePointer(index);
    System.arraycopy(items, index, items, index + 1, size - index);
    items[index] = value;
    size++;
}

// Merging two arrays into the current one.
public void merge(Array<T> arr){
    int length = arr.length();
    if(length == 0) return;
    int availability = items.length - size;
    if(length > availability) resize(items.length + (length - availability));
    for(int i = 0; i < length; i++){
        items[size] = arr.get(i);
        size++;
    }
}

Getters. set of methods used to pull data without modifying the array structure. though it include @pop and @poll, which is does.

// Get value by index.
public T get(int index){
    ensurePointer(index);
    return items[index];
}

// Remove and return last item.
public T pop(){
    if(size == 0) throw new IllegalStateException("Array is empty");
    size--;
    T value = items[size];
    items[size] = null;
    return value;
}

// Remove and return first item.
public T pool(){
    if(size == 0) throw new IllegalStateException("Array is empty");
    T value = items[0];
    remove(0);
    return value;
}

// Get last item.
public T peek(){
    if(size == 0) throw new IllegalStateException("Array is empty");
    return items[size - 1];
}

// Get first item.
public T first(){
    if(size == 0) throw new IllegalStateException("Array is empty");
    return items[0];
}

Modifications. Those methods I use to modificate the array. Rearrange, resize, remove and such.

// Deleting all indexes of & between range.
public void trim(int start, int end){
    ensurePointer(start);
    ensurePointer(end);
    if(start >= end) throw new IllegalStateException("Start can't be >= end.");
    int count = (end + 1) - start;
    System.arraycopy(items, end + 1, items, start, size - (count + start));
    size -= count;
    for(int i = size; i < items.length; i++) items[i] = null;
}

// Ditching all values.
public void clear(){
    for(int i = 0; i < size; i++)
        items[i] = null;
    size = 0;
}

// Remove value by index.
public void remove(int index){
    ensurePointer(index);
    size--;
    System.arraycopy(items, index + 1 , items, index , size - index);
    items[size] = null;
}

// Removing all elements containing specific value
public void removeAllValues(T value){
    int index = indexOf(value);
    while(index >= 0){
        remove(index);
        index = indexOf(value);
    }
}

// Starting clean
public void reset(){
    if(size == 0) return;
    items = (T[]) new Object[8];
    size = 0;
}

// Ensure index pointer is in array range
private void ensurePointer(int index){
    if(index < 0 || index >= size)
        throw new IllegalStateException("Index pointer is out of range");
}

// Adding array slots
private void resize(int newSize){
    T[] temp = (T[]) new Object[newSize];
    System.arraycopy(items, 0, temp, 0, ((size < newSize) ? size : newSize) );
    items = temp;
}

// Reverse array first<>last,
public void reverse(){
    if(size == 0) return;
    for(int i = 0, io = size - 1, c = size / 2; i < c; i++){
        int ii = io - i;
        T temp = items[ii];
        items[ii] = items[i];
        items[i] = temp;
    }
}

// Swapping values of two indexes
public void swap(int indexOne, int indexTwo){
    ensurePointer(indexOne);
    ensurePointer(indexTwo);
    T temp = items[indexOne];
    items[indexOne] = items[indexTwo];
    items[indexTwo] = temp;
}

// Shuffling random
public void shuffle(){
    if(size == 0) return;
    java.util.Random r = new Random();
    for(int i = 0; i < size; i++){
        int ii = r.nextInt(size);
        int iii = r.nextInt(size);
        T temp = items[ii];
        items[ii] = items[iii];
        items[iii] = temp;
    }
}

// removing unnecessary cells
public void shrink(){
    if(size != items.length) resize(size);
}

// return index of value if exist
public int indexOf(T value){
    for(int i = 0; i < size; i++){
        if(items[i] == value) return i;
    }
    return -1;
}

// Check if such value exist
public boolean contains(T value){
    return indexOf(value) == -1 ? false : true;
}

// Return current visible size of the array
public int length(){
    return size;
}

So far i have bug tested it for a couple of hours and it seems like it fits what i need overall but,

  1. Is it structured well enough to meet my expectations related to performance and resources approach?
  2. Any visible problems that may caught your eye? Anything poorly designed? anything wrong performed?
  3. Implementation needed? how can i improve this code?
  4. Are there any structure design problems that could pop bugs/problems in the future that I might not aware of?
  5. Any overall comments, adjustments, tips and tricks are welcome! Trying to make my code slightly less wrong.
\$\endgroup\$
  • 2
    \$\begingroup\$ Not sure if I'm getting this right, but Iterator is just an interface that doesn't add any bloat other than to provide a consistent way to traverse through a Collection of elements. Users of your Array class will be forced to use only this implementation, losing compatibility with the Collections framework, and to a large extent, Java 8's stream-based features. Or do you foresee reinventing that as well? \$\endgroup\$ – h.j.k. Jan 8 '16 at 7:19
  • \$\begingroup\$ Your class is more or less same as default ArrayList implementation, so you might want to implement same interfaces as ArrayList does. Also the shuffle() algorithm looks wrong, it doesn't guarantee equal distribution. \$\endgroup\$ – user158037 Jan 8 '16 at 9:50
3
\$\begingroup\$

It's a kind of default review, without going into the performance or implementation.

Naming

You really like short naming for variable :

for(int i = 0; i < size; i++){
    int ii = r.nextInt(size);
    int iii = r.nextInt(size);
    T temp = items[ii];
    items[ii] = items[iii];
    items[iii] = temp;
}

i, ii, iii this can be better no?
It's just making the code readable so readers of the code knows what you are doing.
i can be called counter, ii can be called swapSourceLocation and iii could be called swapDestinationLocation.

Let's go a little further on this.
Aren't you swapping the elements?
I believe so, so why not make usage of your method : public void swap(int indexOne, int indexTwo)?

Never use ternary to return a boolean

// Check if such value exist
public boolean contains(T value){
    return indexOf(value) == -1 ? false : true;
}

indexOf(value)==-1 returns true or false correct?
The reason why you use the ternary is because you want it returned inverse. By this you are doing more then needed.
This is exactly doing the same :

// Check if such value exist
public boolean contains(T value){
    return indexOf(value) != -1;
}

Each if deserves curly braces

Please do not make the same mistake as apple with the goto fail bug.
Learn from there faults and put curly braces on every if statement.

Repeating needs a separate method

if(size == 0) throw new IllegalStateException("Array is empty");

I see this 4 times appearing in 1 class.

Why not make a method checkEmpty?

public void checkEmpty(int size) {
    if (size ==0) {
        throw new IllegalStateException("Array is empty");
    }
}

Now you need to adjust only this method when you want to change the check or the message instead of 4 times.

Better usage of the ++

items[size] = value;
size++;

This is the same :

items[size++] = value;

Because the ++ stands for get mine integer.
After you are done using it, raise it by one.

\$\endgroup\$
3
\$\begingroup\$

TL;DR

It seems you're trying to make a general purpose array-like storage that can be used as a Queue, or List, or Stack, at the same time. This doesn't seem like a good idea. Typically we need only one of these behaviors at a time, and never some combination of them.

One of the crucial points in implementing the solution for something is the choice of storage. The right tool for the job is typically the right specialization, not something general purpose.

I seriously doubt that there is a realistic use case where such class will be the best tool for the job. It would make more sense to create more specializations that don't exist in the JDK than something general purpose.

Finally, when creating a new kind of storage, it should follow one or more of the existing interfaces, for consistency, and easier adoption.

Terminology

Some of the terms you use are very confusing, I think it will be useful to clarify.


  • Flexibility. Having my code written in a dynamically way that I could use it for any Iterator as i pleased, in such way that it could be a Queue nor List or even a Stack, it's all in one package and i can handle it the way i want.

You mention "Iterators", but I guess you really meant "Collections".


  • Back-scene overview. Get visual of what's going on, have track on variables and, it's always nicer to know what's going on behind our backs.

I guess what you really wanted to say is: you wanted to reinvent the wheel to learn how stuff works at the lower level. Which is perfectly fine.

Normally we don't want to know what goes on behind the scene, that's why we use encapsulation and information hiding. We program in terms of interfaces, and trust that the implementation will do what's promised by the interface's contract, and not care about how it does it.


In the error message "Index pointer is out of range", it's strange to mix the terms "index" and "pointers". These are very different things. In this example, the message will be correct if you drop the term "pointer".

The same goes for the ensurePointer method. Actually the ensurePointer method is misleading in many ways:

  • it's not really about pointers
  • it doesn't "ensure" anything

"ensure" usually means making sure that some expectations will be met, by providing what's needed. For example the ensureCapacity method in the implementation of ArrayList makes sure the internal array is big enough to contain some number of elements.

Your ensurePointer method doesn't provide or ensure anything, it validates that an index is within the allowed range. A more common name for such method is rangeCheck (also borrowed from the implementation ArrayList).


About getters. Methods that return private fields are called getters (or accessors), and typically have a prefix "get" or "is". Other methods that return values are "just methods", and not normally called "getters".

Also, you misspelled poll as "pool".

Learning from what exists

When reinventing the wheel, it's good to learn from what exists, and follow practices of the JDK.

For example when trying to peek or pop an empty stack, the preferred exception is java.util.EmptyStackException instead of IllegalStateException.

Or when trying to access an invalid index, the preferred exception is java.lang.IndexOutOfBoundsException instead of IllegalStateException.

Magic numbers

Although you mention that the constructors are self-explanatory, the number 8 as the initial size of the storage is not. It also appears one more time in the reset method. It would be good to put this in a private static final constant, and perhaps add a comment to explain your choice of this number.

Testing

So far i have bug tested it for a couple of hours and it seems like it fits what i need overall but,

You haven't included unit tests. If you don't use unit tests, then if you make some change, then you will have to repeat some tests, which is really boring. It's so boring that many programs just skip that entirely and wishfully assume that "it probably still works".

2 hours spent on writing unit tests is 2 hours well spent. The result is something repeatable, and allows you to refactor confidently, knowing that you can easily repeat the same boring tests with no extra effort whatsoever. I suggest to take a look at JUnit.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.