CODEWITHSUNDEEP
javaoptimizationdata-structuresstackdeque
bigcodeszzer
bigcodeszzer

Reputation: 940

Circular Buffer in Java?

I need a deque-like data structure, which I believe is called a circular buffer.

This is what I've done.

public class MyStack {


    byte[][] orders = {  {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1}, {3, 0, 1, 2}  };

    byte state      = 0;

    int[] data      = {1, 2, 3, 4};


    void swap(int value){           
        data[state] = value;

        if(state == 3){
            state = 0;

        }else{
            state ++;

        }       
    }

    int[] dump(){

        int[] output = {  
                          data[  orders[state][0]  ],
                          data[  orders[state][1]  ],
                          data[  orders[state][2]  ],
                          data[  orders[state][3]  ],
                       };

        return output;
    }

}

The output here is exactly the type of functionality I need. It is basically a window of length four, moving through a infinite, discrete space, or along a number line.

My question is: Is this solution efficient? Are there any built in libraries designed for this functionality? If so, is it worth using instead?

Upvotes: 1

Views: 2118

Answers (2)

PyThon
PyThon

Reputation: 1067

One improvement to this can be, remove the orders 2D array of size n.

byte[][] orders = {  {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1}, {3, 0, 1, 2}  };

because if you know the state , then the orders array can also be determined dynamically by formula

for(int i =0; i<data.length; i++){
  output[i] = data[(state+i)%data.length];
}

this can be used to return output.

Upvotes: 2

Joni
Joni

Reputation: 111349

A typical implementation of a circular buffer uses two indexes to mark the first and last element of the queue. There's no need to store the states explicitly because enqueue and dequeue can be done with index calculations. A better name for swap method is rotate.

You could remove the orders array and change the dump implementation to:

    int[] output = {  
                      data[  (state+0)%4  ],
                      data[  (state+1)%4  ],
                      data[  (state+2)%4  ],
                      data[  (state+3)%4  ],
                   };

Upvotes: 0

Related Questions