4

I'm looking for a Deque which has the following characteristics:

  • it has fixed size
  • if I add elements at the head/tail elements at the opposite end drop out
  • it is array-based so I can access random elements in constant time
  • I can add elements at the front or at the end (deque)

I checked the Deque implementations in the JCF but I did not find anything that fits.

Adam Arold
  • 29,285
  • 22
  • 112
  • 207
  • http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html it exists, but it sounds like you'll have to make your own subclass to make it work in the fixed size – CBredlow Oct 31 '12 at 12:24
  • I know Deque exists in JCF I mentioned it in my question. – Adam Arold Oct 31 '12 at 12:29
  • The closest is ArrayDeque. Why do you want to discard element? Why do you want random access in a queue esp as the random element might not be there any more? – Peter Lawrey Oct 31 '12 at 13:17
  • I'm reading in lines from a very big file and I want to buffer them in a collection so I can display it for the user. If the user scrolls down or up I want to read in the previous/next lines into this collection. I can't read in the whole file because it would lead to an `OutOfMemoryError`. – Adam Arold Oct 31 '12 at 13:30
  • Are you willing to accept a home-grown type, as opposed to one already available in a public library? – seh Oct 31 '12 at 14:13

1 Answers1

2

Because I love writing my own data types,

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class Ring {

    private String[] data;
    int n = 0;

    public Ring(int size) {
        data = new String[size];
    }

    public void push(String s) {
        data[n] = s;
        n = (n + 1) % data.length;
    }

    public void shift(String s) {
        data[n = (n - 1) % data.length] = s;
    }

    public String get(int index) {
        return data[(n + index) % data.length];
    }

    public static class Examples {

        @Test
        public void shouldDropElementsWhenPushingTooFar() {
            Ring ring = new Ring(3);
            ring.push("A");
            ring.push("B");
            ring.push("C");
            ring.push("D");
            ring.push("E");
            assertEquals("C", ring.get(0));
            assertEquals("D", ring.get(1));
            assertEquals("E", ring.get(2));
        }

        @Test
        public void shouldAddElementsAtTheFront() {
            Ring ring = new Ring(3);
            ring.push("A");
            ring.push("B");
            ring.push("C");
            ring.push("D");
            ring.push("E");
            // rewind
            ring.shift("B");
            assertEquals("B", ring.get(0));
            assertEquals("C", ring.get(1));
            assertEquals("D", ring.get(2));
        }

    }

}
akuhn
  • 27,477
  • 2
  • 76
  • 91
  • There is a bug in here: shifting will lead to an `ArrayIndexOutOfBoundsException`. The fix is to change `(n - 1) % data.length` to `(n - 1 + data.length) % data.length`. Reason is that Java's modulo operator [can result in negative values](https://stackoverflow.com/q/4412179). – Just a student Nov 22 '17 at 12:21
  • There is a bug in the code. Try below to run it. Ring ring = new Ring(4); ring.push("A"); ring.push("B"); System.out.println(ring.get(1)); It return null, which is not expected output. – TheGraduateGuy May 02 '19 at 18:39