# A CircularBuffer Data Structure--

I'm sure this has already been done, but to practice understanding Data Structures better I decided to try making one of my own, given only an idea of what type of functionality I want, a pencil and some paper (as well as .txt file, modified into a .java file =p ).

The motivation of this Data-Structure is to enable a user (programmer) to be able to traverse through an array of data easily as if it were "circular." For example, if I want to jump back to the front of an array after reaching the index, to treat the data as if it were circular, how do I do it without reproducing code, again and again, to get there? This class solves that problem and acts like a collection-type by being "Iterable" (usable by the improved for-loop). Not only that, but the range and starting position can be adjusted so certain data can be ignored since as if it is "outside of the circle."

Note: I think I need to refer back to the Modulos discussions of my Discrete Mathematics book to determine how to give the user the positive-version (or close-enough value) of the negative request they submit when retrieving data in constant time.

A final note: This class is incomplete - I'm still working on it. I did not set a restriction of Comparable data types for nothing.

Thank you for viewing my code! =)

103 Views
``````import java.util.Iterator;

/**
* A CircularBuffer data structure that can have its elements accesses in guaranteed
* constant time (TODO: fix negative input to also be constant time).
* In addition, ranges can be set on the data and a start-point can
* be chosen.
*
*/
public class CircularBuffer<T extends Comparable<? super T>> implements Iterable<T>{

protected Object values[];
private int initPosition = 0, picked, speedyPicked, range;

/**
* A CircularIterator that exists as an indirect helper class
* for iterating through the contents of a CircularBuffer
*/
public static class CircularIterator<E extends Comparable<? super E>>
implements Iterator<E>{

private CircularBuffer bufRef;
private int current = 0;
private boolean finished = true;

/**
* Constructs a CircularIterator, with the specified CircularBuffer
*/
CircularIterator(CircularBuffer bufRef){

this.bufRef = bufRef;
}

/**
* Returns true if this Iterator hasn't reached the first element
* again, and false otherwise.
*/
public boolean hasNext(){

if(current % bufRef.range == 0)
finished = !finished;
return !finished;
}

/**
* Returns the "next" element
*/
@SuppressWarnings("unchecked")
public E next(){

return (E)bufRef.get(current++);
}

/**
* Not supported!
*/
public void remove(){}
}

public static void main(String... args){

// Constructing an Integer CircularBuffer to store numbers
CircularBuffer<Integer> myBuf = new CircularBuffer<Integer>(8);

// assigning values at circularly-close indices
myBuf.assign(6, 12);
myBuf.assign(7, 38);
myBuf.assign(0, 55);
myBuf.assign(1, 99);
myBuf.assign(2, 107);

// setting the start-point
myBuf.setPosition(6);

// setting the range
myBuf.setRange(5);

// printing the contents
System.out.println(myBuf);

// printing the value at the true index from the user-given index, 4
System.out.println("Value at index 4 is: " + myBuf.get(4));

// shifting forward (and yes, this updates the last-picked value)
// then prints the result to the console window
System.out.println("Then the next value in front of that one" +
" is: " + myBuf.shiftForward());

// printing out the value that was last picked
System.out.println("Last-picked value is: " + myBuf.getLastPicked() + "\n");

// Shifting back and printing the value 9 times.
for(int i = 0; i < 9; i++)
System.out.print("" + myBuf.shiftBackward() + " ");

System.out.println("\n");

// Constructing a String CircularBuffer to store names
CircularBuffer<String> nameBuf =
new CircularBuffer<String>("Tom", "Jeff", "Suzie", "Mark", "Ben");

// setting the position to 1 (Jeff) and the range to 3 (Jeff, Suzie, Mark)
nameBuf.setPosition(1);
nameBuf.setRange(3);

// printing the result
System.out.println(nameBuf);

// setting the position to 2 (Suzie) and the range is still 3 (Suzie, Mark, Ben)
nameBuf.setPosition(2);

// Shifting forward and printing the value 6 times.
for(int i = 0; i < 6; i++)
System.out.print("" + nameBuf.shiftForward() + "\n");

System.out.println();
}

/**
* Constructs a CircularBuffer with an initial capacity of 2
*/
public CircularBuffer(){

this(2);
}

/**
* Constructs a CircularBuffer with the requested initial capacity,
* unless that capacity requested is 2 or less, then the initial
* capacity is 2.
*/
public CircularBuffer(int initCapacity){

values = (initCapacity <= 2) ? new Object : new Object[initCapacity];
range = values.length;
picked = 0;
speedyPicked = 0;
}

public CircularBuffer(T... data){
values = (Object[])data;
range = values.length;
picked = 0;
speedyPicked = 0;
}

/**
* Sets the initial position
*/
public void setPosition(int value){
initPosition = (value >= 0) ? value : 0;
}

/**
* Sets the range
*/
public void setRange(int value){
range = (value >= 1) ? value : 1;
}

/*
* Example of usage:
* The user requests the first element, which may seem to be '0' in his/her mind,
* but really is some other position. This method returns the
* true position of the requested index.
*
* In addition, a call to this method updates the optimised value of
* the last-index requested.
*/
private int getTrueIndex(int request){

while(request < -range) request += range;
speedyPicked = request;

return (((request + range) % range) + initPosition) % values.length;
}

/**
* Returns an element in the specified position, based on
* the value of the initial point and the range of values.
*
* In addition, a call to this method updates the last-index picked.
*/
@SuppressWarnings("unchecked")
public T get(int request){

picked = request;
return (T)values[getTrueIndex(request)];
}

/**
* Returns the element "in front" of the last-requested element.
*/
public T shiftForward(){
return get(getLastRequest(true) + 1);
}

/**
* Returns the element "behind" the last-requested element.
*/
public T shiftBackward(){
return get(getLastRequest(true) - 1);
}

/**
* Assigns the given value to the true index of the user-requested index.
*/
public void assign(int index, T element){

values[getTrueIndex(index)] = element;
}

/**
* Returns the number that was last requested by the user.
*/
public int getLastRequest(){

return picked;
}

/**
* Returns the speedy version of the last request (one which,
* upon its next submission to the get method, will return to the
* user in constant time).
*/
public int getLastRequest(boolean speed){
return (speed) ? speedyPicked : getLastRequest();
}

/**
* Gets the element that was recently retrieved.
*/
public T getLastPicked(){

return get(getLastRequest());
}

/**
* Returns a CircularIterator of this class
*/
public Iterator<T> iterator(){

return new CircularIterator<T>(this);
}

/**
* Returns a list-like representation of this CircularBuffer, based on
* the initial position and range values.
*/
@Override
public String toString(){

String temp = "";

for(T element : this)
temp += "[\t" + element + "\t]\n";

return temp;
}
}``````

Here's an update.

``````import java.util.Iterator;
import java.util.Arrays;

/**
* A CircularBuffer data structure that can have its elements accesses in guaranteed
* constant time.
* In addition, ranges can be set on the data and a start-point can
* be chosen.
*
* the value from a particular indice to setting the position. The only
* restriction set is the range, which cannot exceept the length of the
* backing array.
*
*/
public class CircularBuffer<T extends Comparable<? super T>> implements Iterable<T>{

protected Object values[];
private int initPosition = 0, picked, range;

/**
* A CircularIterator that exists as an indirect helper class
* for iterating through the contents of a CircularBuffer
*/
public static class CircularIterator<E extends Comparable<? super E>>
implements Iterator<E>{

private CircularBuffer<E> bufRef;
private int current = 0;
private boolean finished = true;

/**
* Constructs a CircularIterator, with the specified CircularBuffer
*/
CircularIterator(CircularBuffer<E> bufRef){

this.bufRef = bufRef;
}

/**
* Returns true if this Iterator hasn't reached the first element
* again, and false otherwise.
*/
public boolean hasNext(){

if(current % bufRef.range == 0)
finished = !finished;
return !finished;
}

/**
* Returns the "next" element
*/
public E next(){

return (E)bufRef.get(current++);
}

/**
* Not supported!
*/
public void remove(){}
}

/**
* An indirect helper 'Exception' class for Bad Data.
*/
public static class BadDataException extends Exception{

private int code = 0;
private static final String bde = "BadDataException";
private static final String defString = bde + ": Error! Bad Data!";

/**
* Constructs a BadDataException with a message
* in correlation with the number specified.
*
* Let N be the number input.
*
*  N = 1 means there wasn't enough data.
*  N != 1, the default message
*/

code = pos;
}

/**
* An override to the toString of this exception,
* so a call to the printStackTrace will display
*
*/
@Override
public String toString(){

String temp = "";

switch(code){

case 1:
temp = bde + ": Not Enough Data!";
break;
default:
temp = defString;
}

return temp;
}
}

public static void main(String... args){

// Constructing an Integer CircularBuffer to store numbers
CircularBuffer<Integer> myBuf = new CircularBuffer<Integer>(8);

// assigning values at circularly-close indices
myBuf.assign(6, 12);
myBuf.assign(7, 38);
myBuf.assign(0, 55);
myBuf.assign(1, 99);
myBuf.assign(2, 107);

// setting the start-point
myBuf.setPosition(6);

// setting the range
myBuf.setRange(5);

// printing the contents
System.out.println(myBuf);

// printing the value at the true index from the user-given index, 4
System.out.println("Value at index 4 is: " + myBuf.get(4));

// shifting forward (and yes, this updates the last-picked value)
// then prints the result to the console window
System.out.println("Then the next value in front of that one" +
" is: " + myBuf.shiftForward());

// printing out the value that was last picked
System.out.println("Last-picked value is: " + myBuf.getLastPicked() + "\n");

// Shifting back and printing the value 9 times.
for(int i = 0; i < 9; i++)
System.out.print("" + myBuf.shiftBackward() + " ");

System.out.println("\n");

// Constructing a String CircularBuffer to store names
CircularBuffer<String> nameBuf = null;

try{

nameBuf = new CircularBuffer<String>("Tom", "Jeff", "Suzie", "Mark", "Ben");

// setting the position to 1 (Jeff) and the range to 3 (Jeff, Suzie, Mark)
nameBuf.setPosition(-9); // -9%5 is congruent -4%5 is congruent 1%5 which is 1
nameBuf.setRange(3);

// printing the result
System.out.println(nameBuf);

// setting the position to 2 (Suzie) and the range is still 3 (Suzie, Mark, Ben)
nameBuf.setPosition(2);

// Shifting forward and printing the value 6 times.
for(int i = 0; i < 6; i++)
System.out.print("" + nameBuf.shiftForward() + "\n");

System.out.println();

System.out.println(nameBuf.get(-31));

// increasing the range to 5 then additionally increasing the capacity by 10
nameBuf.setRange(5);
System.out.println("Increasing capacity to 10...");
nameBuf.increaseCapacity(10);
System.out.println("Capacity has been increased to 10!");

System.out.println(nameBuf);

// setting the range to 9 before a final print
nameBuf.setRange(9);
System.out.println("\n\n" + nameBuf + "\n");

// clearing the name buffer and storing its previous data into
// originalBuffer
String originalBuffer[] = nameBuf.clear();

// printing out the contents of the originalBuffer
for(String element : originalBuffer)
System.out.println( element );

// printing out the new name buffer
System.out.println("\n" + nameBuf + "\n");

// testing the exception class
CircularBuffer<Double> dummyBuf = new CircularBuffer<Double>((Double[])null);
}catch(Exception e){

e.printStackTrace();
System.exit(1);
}
}

/**
* Constructs a CircularBuffer with an initial capacity of 2
*/
public CircularBuffer(){

this(2);
}

/**
* Constructs a CircularBuffer with the requested initial capacity,
* unless that capacity requested is 2 or less, then the initial
* capacity is 2.
*/
public CircularBuffer(int initCapacity){

values = (initCapacity <= 2) ? new Object : new Object[initCapacity];
range = values.length;
picked = 0;
}

/**
* Constructs a CircularBuffer with the given data.
*
* Throws a BadDataException object if:
*	- The array submitted is null, or
*	- The array submitted is of length 0
*/

if(data == null)
else if(data.length == 0)
else{
values = (Object[])data;
range = values.length;
picked = 0;
}
}

/**
* Sets the initial position
*/
public void setPosition(int value){

// This requires an explanation.
// Apparently, to negate negativity, we must first mod the position to the length of the
// array, returning the negative value that is closest to the positive congruent modulo,
// then we simply add the range again and take the mod. This is so the below operation
// is usable for both positive and negative values.
initPosition = (((value) % values.length) + values.length) % values.length;
}

/**
* Sets the range
*/
public void setRange(int value){

range = (value >= 1) ? ( (value <= values.length) ? value : (values.length) ) : 1 ;
}

/*
* Example of usage:
* The user requests the first element, which may seem to be '0' in his/her mind,
* but really is some other position. This method returns the
* true position of the requested index.
*
* In addition, a call to this method updates the optimised value of
* the last-index requested.
*/
private int getTrueIndex(int request){

request = (request % range) + range;
picked = request;

return (((request + range) % range) + initPosition) % values.length;
}

/**
* Returns an element in the specified position, based on
* the value of the initial point and the range of values.
*/
@SuppressWarnings("unchecked")
public T get(int request){

return (T)values[getTrueIndex(request)];
}

/**
* Returns the element "in front" of the last-requested element.
*/
public T shiftForward(){

return get(getLastRequest() + 1);
}

/**
* Returns the element "behind" the last-requested element.
*/
public T shiftBackward(){

return get(getLastRequest() - 1);
}

/**
* Assigns the given value to the true index of the user-requested index.
*/
public void assign(int index, T element){

values[getTrueIndex(index)] = element;
}

/**
* Returns the optimized version of the number that was last requested by the user.
*/
public int getLastRequest(){

return picked;
}

/**
* Gets the element that was recently retrieved.
*/
public T getLastPicked(){

return get(getLastRequest());
}

/**
* Returns a CircularIterator of this class
*/
public Iterator<T> iterator(){

return new CircularIterator<T>(this);
}

/**
* Increase the capacity of this CircularBuffer. If the
* new size requested is smaller than, or the same as the
* current capacity, no action is performed.
*
* This method does "grouping" in which the data specified
* by the current position and range is considered to be
* highest priority. The information is kept grouped together
* by copying the contents of the data within the range and
*/
@SuppressWarnings("unchecked")
public void increaseCapacity(int newSize){

if(newSize <= values.length)
return;
else{

if(initPosition < ((initPosition + range) % values.length) ){

T tempArray[] = Arrays.<T>copyOf((T[])values, newSize);
values = (Object[])tempArray;
}else{

// We have to do this first so our current data is not disjoint
for(T element : this)

T tempArray[] = Arrays.<T>copyOf((T[])values, newSize);
values = (Object[])tempArray;

for(int i = 0; info.size() != 0; i++)
assign(i, info.pollFirst());
}
}
}

/**
* Clears this buffer and replaces it with a new one with a capacity
* of 2, and initial position of 0, with range set as the length of the
* new array.
*
* Returns the original buffer, should the user need it.
*/
@SuppressWarnings("unchecked")
public T[] clear(){

T[] temp = (T[])values;

values = new Object;
initPosition = 0;
range = values.length;
picked = 0;

return temp;
}

/**
* Returns a list-like representation of this CircularBuffer, based on
* the initial position and range values.
*/
@Override
public String toString(){

String temp = "";

for(T element : this)
temp += "[ " + ((element != null) ? element.toString() : "empty") + " ]";

return temp;
}
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.