Resizing circular array, in deque implementation

Question

I am trying to implement a Deque using circular array here is the code I have (sorry to post entire class)

public class Deque<Item> implements Iterable<Item> {

    private int frontIndex;
    private int backIndex;
    private static final int defaulSize = 8;
    private int size;
    private Item holder[];

    private int capacity;

    public Deque() {
        holder = (Item[]) new Object[defaulSize];
        this.size = 0;
        this.frontIndex = 0;
        this.backIndex = 0;
        this.capacity = defaulSize;
    }

    public boolean isEmpty() {

        return this.size == 0;

    }

    public int size() {
        return this.size;
    }

    public void addFirst(Item item) throws Exception {

        if (item == null) {

            throw new NoSuchElementException();
        }
        if (size == capacity) {

            doubleCapacity();
        }
        holder[this.frontIndex] = item;
        this.frontIndex = Math.floorMod((this.frontIndex + 1), capacity);
        size++;

    }

    public void addLast(Item item) throws Exception {

        if (item == null) {

            throw new NoSuchElementException();
        }

        if (size == capacity) {

            doubleCapacity();
        }
        holder[this.backIndex] = item;
        this.backIndex = Math.floorMod((this.backIndex - 1), capacity);
        size++;

    }

    public Item removeFirst() throws Exception {

        if (isEmpty()) {
            throw new Exception("Deque is empty.");
        }

        this.frontIndex = Math.floorMod((this.frontIndex - 1), capacity);
        this.size--;
        Item e = holder[this.frontIndex];
        holder[this.frontIndex] = null;
        return e;
    }

    public Item removeLast() throws Exception {

        if (isEmpty()) {
            throw new Exception("Deque is empty.");
        }
        this.backIndex = Math.floorMod((this.backIndex + 1), capacity);
        this.size--;

        Item e = holder[this.backIndex];
        holder[this.backIndex] = null;
        return e;
    }

    private void doubleCapacity() {

        int p = this.backIndex;
        int n = holder.length;
        int r = n - p; // number of elements to the right of p
        capacity = (n) * 2;
        Object[] a = new Object[capacity];
        System.arraycopy(holder, p, a, 0, r);
        System.arraycopy(holder, 0, a, r, p);
        holder = (Item[]) a;
        this.backIndex = n;
        this.frontIndex = 0;

    }

    private class DequeIterator<E> implements Iterator<E> {

        private int pos = 0;

        public boolean hasNext() {
            return holder.length > pos;
        }

        public E next() {

            return (E) holder[pos++];
        }

        public void remove() {
            throw new UnsupportedOperationException("Cannot remove an element of an array.");
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return this.new DequeIterator<Item>();
    }

}

The problem come when I am trying to resize the circular array with deque it seems like all the indexes are getting messed up

I used this method similar to how it done in java implementation to experiment

private void doubleCapacity() {

    int p = this.backIndex;
    int n = holder.length;
    int r = n - p; // number of elements to the right of p
    capacity = (n) * 2;
    Object[] a = new Object[capacity];
    System.arraycopy(holder, p, a, 0, r);
    System.arraycopy(holder, 0, a, r, p);
    holder = (Item[]) a;
    this.backIndex = n;
    this.frontIndex = 0;

}

Is there a specific way on how to resize circular array if it used as deque, or how can I resize this deque

(IT NOT A HOMEWORK JUST PERSONAL STUDY)

If you call addFirst and then addLast the first element will be overwritten. — Selçuk Cihan
– Selçuk Cihan, Commented Feb 27, 2017 at 7:23

Massimo Petrus · Accepted Answer · 2017-02-27 14:53:18Z

the problem is basically due to the facts that

1- you don't update correctly the frontIndex and backIndex when adding items to the Deque

2- you don't use the right indexes when doubling the capacity.

Problem 1

When frontIndex and backIndex are equal and you're adding an element in any of the entry point of the deque, you need to update both of them otherwise you loose control of the Deque. Example: at the beginning both frontIndex and backIndex are ==0. If you add an item let's say in front, after that you'll have frontIndex=1 (correct) and backIndex=0 (incorrect, because the position 0 is occupied by the new item). This has a lot of side effects

Solution for 1

  public void addFirst(Item item) throws Exception {

      ... unchanged handling of capacity...

        holder[this.frontIndex] = item;
        //CHECK OF THE 2 INDEXES
        if(this.frontIndex==this.backIndex){
            this.backIndex= floorMod((this.backIndex - 1), capacity);
        }
        this.frontIndex = floorMod((this.frontIndex + 1), capacity);
        size++;
    }

     public void addLast(Item item) throws Exception {

      ... unchanged handling of capacity...

        holder[this.backIndex] = item;
        if(this.frontIndex==this.backIndex){
            this.frontIndex= floorMod((this.frontIndex + 1), capacity);
        }
        this.backIndex = floorMod((this.backIndex - 1), capacity);
        size++;
    }

NOTE that the problem exists in the remove functions as well and you should handle it correctly. I didn't have time to handle it but the solution is straightforward

Problem 2

You always use backIndex (and it's conceptually ok) to handle the copy of items in the new array, but ideally backIndex points to the location before the first element in the Deque so using that value messes up a little more the Deque itself. Also you assign completely wrong indexes to the new backIndex (which should be equal to the index of the last element of the newly created array and not to n, which refers to the size of the old array) and frontIndex (which should be equal to the position n, i.e. one element after the last populated item).

SOLUTION FOR 2

private void doubleCapacity() {

    int p = floorMod((this.backIndex+1 ), capacity);
    int n = holder.length;
    int r = n - p; // number of elements to the right of p
    capacity = (n) * 2;
    Object[] a = new Object[capacity];
    System.arraycopy(holder, p, a, 0, r);
    System.arraycopy(holder, 0, a, r, p);
    holder = (Item[]) a;
    //backIndex should be the last element of the whole array
    this.backIndex = capacity-1;
    //frontIndex must be 1 after the last element of the portio of array populated by items  
    this.frontIndex = n;
}

As design i would have handled frontIndex and backIndex as the (circular) indexes of the first and last element already in the Deque, and not as the indexes before and after them. But this is just my way.

Thank you very much, for your time and great explanation, that really helped me to better see the circular array and mistakes, I was making. Again Thank You for helping me.

Collectives™ on Stack Overflow

Resizing circular array, in deque implementation

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related