Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package mt3.util;
- /*************************************************************************
- * Compilation: javac RingBuffer.java
- * Execution: java RingBuffer
- *
- * Ring buffer (fixed size queue) implementation using a circular array
- * (array with wrap-around).
- *
- * Copyright (c) 2007, Robert Sedgewick and Kevin Wayne.
- * Edited by Chris Dennett (C.R.Dennett@2006.ljmu.ac.uk)
- *
- *************************************************************************/
- // suppress unchecked warnings in Java 1.5.0_6 and later
- @SuppressWarnings("unchecked")
- public class IntRingBuffer {
- private int[] a; // queue elements
- private int N = 0; // number of elements on queue
- private int first = 0; // index of first element of queue
- private int last = 0; // index of next available slot
- private int iter_i = 0;
- // cast needed since no generic array creation in Java
- public IntRingBuffer(int capacity) {
- a = new int[capacity];
- for (int i = 0; i < capacity; i++) {
- a[i] = Integer.MIN_VALUE;
- }
- }
- public boolean isEmpty() { return N == 0; }
- public int size() { return N; }
- public void enqueue(int item) {
- if (N == a.length) { throw new RuntimeException("Ring buffer overflow"); }
- a[last] = item;
- last = (last + 1) % a.length; // wrap-around
- N++;
- }
- // remove the least recently added item - doesn't check for underflow
- public int dequeue() {
- if (isEmpty()) { throw new RuntimeException("Ring buffer underflow"); }
- int item = a[first];
- a[first] = Integer.MIN_VALUE; // to help with garbage collection
- N--;
- first = (first + 1) % a.length; // wrap-around
- return item;
- }
- public void iter_reset() {
- iter_i = 0;
- }
- public boolean contains(final int n) {
- iter_reset();
- int i = 0;
- while ((i = iter_next()) != Integer.MIN_VALUE) {
- if (i == n) return true;
- }
- return false;
- }
- public int iter_next() {
- if (!iter_hasNext()) return Integer.MIN_VALUE;
- return a[iter_i++];
- }
- public boolean iter_hasNext() {
- return iter_i < N;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement