A CircularBuffer Data Structure--

Intrade 0 Tallied Votes 125 Views Share

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! =)

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.
 *
 * @author Intrade
 */
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[2] : 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;
	}
}
Intrade 33 Junior Poster

Here's an update.

import java.util.Iterator;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 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.
 *
 * Technically everything about this implementation is circular, from getting
 * 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.
 *
 * @author Intrade
 */
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
		 */
		public BadDataException(int pos){

			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[2] : 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
	 */
	public CircularBuffer(T... data) throws BadDataException{

			if(data == null)
				throw new BadDataException(0);
			else if(data.length == 0)
				throw new BadDataException(1);
			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{

				LinkedList<T> info = new LinkedList<T>();

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

				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[2];
		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 developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.