How can I convert my circular array into a String?

Question

I have a class ArrayDeque where I take in a circular array and I'm trying to implement a function turntoString() to turn my Array into a string.

I'm currently stumped on how can I do this due to the fact that this is a circular array. Here is my code so far:

public class ArrayDeque<T> {
    private int volume = 0;
    private int size = 0;
    private int head = 0;
    private int tail = 0;
    private Object[] A1;

    public ArrayDeque(int volume) {
        this.volume = volume;
        A1 = new Object[volume];
    }
    public String turntoString() {
        String S = "";
        for (int x = 0; x < A1.length; x++) {
            S += x;
        }
        return S;

However, this doesn't work for circular arrays. Can anyone please help explain how can I do this?

Answer 1

It's a very bad idea to name your class ArrayDeque, given that java's built in library already has such a beast. If this is not homework, use that one. If it is, it's a bit odd to ask SO to 'do your homework' for you.

The idea behind a circular array is that they do not start at 0, so your for (int x = 0 loop is incorrect. They start at head and they end at tail, with the caveat that when you loop through it, the 'index' increment operation isn't i++ but i = (i + 1) % size, i.e. if your backing store (A1 here) is 100 large, head is 98, and tail is 5, to loop through the whole thing in sequence, the indices you want to hit are:

• 98, 99, 0, 1, 2, 3, 4

int idx = head;

while (idx != tail) {
  Object item = A1[idx];
  // do stuff with `item` here
  idx = (idx + 1) % A1.length;
}

Key point here is the % operator. It is crucial for circular implementations of any sort. If you don't recognize it, scroll to the end of this answer.

This assumes head is inclusive and tail is exclusive. If it isn't, change your code so that it works that way, the math is a ton easier, and doing ranges like [1, 2) so (start is inclusive, end is exclusive) is idiomatic java.

That's your loop. Get rid of the for loop.

There are many more smaller problems with this code:

Superfluous data

The size of your ArrayDeque is (length + tail - head) % length. There is no need to store it separately, and it significantly complicates matters by storing it separately. What if you fail to update size in accordance, for example? There's a ton more to test. Just don't do that. Similarly, the total length of the backing store is simply A1.length, there is no need to separately store this, it just introduces opportunity for things to fall out of sync. Get rid of the volume field entirely.

Failure to adhere to java standards

Variable names are writtenLikeThis, so the right name is a1, not A1. Also, names should be descriptive; tha thing should be called data or store, not A1.

Shouldn't that method simply be called toString()? If not, at least it should be called turnToString, not turntoString.

Your S variable in turntoString should be called s.

Bad string concatenation

x += y where x and y are strings is very expensive. You do it in the loop. It's got O(n^2) performance behaviour because of this. Use a StringBuilder instead. So instead of:

String x = "";
for (String item : list) x += item;
return x;

you do:

StringBuilder x = new StringBuilder();
for (String item : list) x.append(item);
return x.toString();

---

What's %?

It's the modulo operator. In basis a % b means: Divide a by b, but toss the result in the garbage; what we care about is the remainder. 7 divided by 2 is 3 (toss that in the garbage, we don't care), with a remainder of 1 (ah, that's what we care about).

However, that's generally not the right way to think about it. What % does is make math circular. Stick % X at the end of anything and it's basically saying: "... but do the operation on a number line that loops right back around at X". Hence why its so crucial for circular operations. It's an easy way to 'solve' the problem. For example, in a deque with volume 100, if I want to go: "What element is 50 to the right of the 80th element", in basis it's just 80+50, except that gives you 130 which is 'past' the range of your arraydeque. You want 30 instead. %100 will do that: 130%100 is 30.

One weird thing about % is that it doesn't fix signs. -30%100 is -30, not 30. This can be fixed by adding 100 to it all. (-30+100)%100 is 70. This is what you want: Imagine I ask: We're at index 5. Now go 35 to the left. 5-35 is -30, but what we really want is store[70]. In general in 'circular math world' adding the total size of the loop is a no-op. If you have a circle of size 100 and ask 'go 100 elements to the right', that's just walking around the circle and does nothing. Hence you can always just add that to any index lookups.