So my program has a need of a type of circular ArrayList.
Only circular thing about it has to be the get(int index) method, this is the original:
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
If index is -1 it should get the element with index ArrayList.size()-1 and if index is ArrayList.size(), it should get the element with index 0.
Simplest way of achieveing this which came to my mind is simply extending ArrayList from the java.util package and just overriding the get(int index) so it does not throw IndexOutOfBoundsException for the two indexes above, but change them to what I want. It would throw IndexOutOfBoundsException for any other index that is out of bounds.
However, since elementData(index) access a
private transient Object[] elementData;
I cannot make it work, because my class doesn't see it since it's private.
Also, I don't want to use any external libraries for this, simply because I think there are none that suit my needs, since I don't want a real circularArray, but only a part of it's functionality, rest of it being of the regular ArrayList.
So I have two questions:
How can I make this work? Is there a way to do it without copying the whole ArrayList class along with AbstractCollection, Collection and Iterable into my program? That seems like bad design even to me.
If I can somehow make it work, is there anything else I should watch for? If I make the changes described above, would that change the behaviour of the class only the way I want it to, or could there be any other undesired behaviour changes?
EDIT: Thanks for the answer, here's what I've done:
import java.util.ArrayList;
public class CircularArrayList<E> extends ArrayList<E>
{
private static final long serialVersionUID = 1L;
public E get(int index)
{
if (index == -1)
{
index = size()-1;
}
else if (index == size())
{
index = 0;
}
return super.get(index);
}
}
It will wrap around the ArrayList, but only by one. I want it to throw an exception if I try to access any other element but the first and the last with anything except their regular ArrayList indexes.
As many other have said, yes, you can extend class ArrayList , but it is not something that you should normally do; it is not considered good practice in Java.
An array list has an O(1) operation to remove the last element. A circular array list has O(1) operations to remove the first and last elements.
The grow method in the ArrayList class gives the new size array. In Java 8 and later The new capacity is calculated which is 50% more than the old capacity and the array is increased by that capacity.
You can extend the ArrayList class to change the functionality of the get
method, without the need to access the elementData
field:
public class CircularList<E> extends ArrayList<E> {
@Override
public E get(int index) {
return super.get(index % size());
}
}
The super.get
method will still perform the range checks (but those will never fail).
You should be aware that doing this can give the ArrayList unstable indices. If the size of the list changes, then all indices outside of the normal range will change. For instance, if you have a list ['a','b','c','d','e']
, then get(7)
will return c
. If you then do add('f')
, then get(7)
will suddenly return b
, because get
will now be working modulo 6 instead of modulo 5.
Can't you derive from ArrayList and override the the get(int index) method along those lines:
@Override
public E get(int index)
{
if(index < 0)
index = index + size();
return super.get(index);
}
What am I missing?
Note that this implementation would not fold arbitrary indices into your valid index range but only allow you to properly address your list from both the left and right sides (with positive and negative indices respectively, a bit like in Python).
What you described is basically getting the modulus of the index you want, and accessing that element in a list.
You could do the following with composition over inheritance:
List<T>
, let's call it ListWrapper now
wrapped
Why do all this crap? This is implementation agnostic. One day, you might want to use this convenience on another implementation. Then you'll have to duplicate code, and hell begins. If you need a 3rd implementation too, and then add just one tiny bit of new functionality, you are doomed.
With a wrapper class in between:
Remember, we are writing programs that will have to be maintainable!
Wrapper class
public abstract class ListWrapper<T> implements List<T> {
protected final List<T> wrapped;
public ListWrapper(List<T> wrapped) {
this.wrapped = wrapped;
}
public T get(int index) {
return wrapped.get(index);
}
//omitting the other wrapper methods, for sake of brevity.
//Note: you still have to add them.
// Eclipse: Source menu, Generate Delegate methods does the trick nicely
}
Now the real new class
public class ModList<T> extends ListWrapper<T> {
public ModList(List<T> list) {
super(list);
}
@Override
public T get(int index) {
int listSize = wrapped.size();
int indexToGet = index % listSize;
//this might happen to be negative
indexToGet = (indexToGet < 0) ? indexToGet+listSize : indexToGet;
return wrapped.get(indexToGet);
}
}
BEWARE
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With