CircularBlockingDeque.java

Go to the documentation of this file.

/*
 * Copyright (C) 2012 Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */

package org.ros.concurrent;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class CircularBlockingDeque<T> implements Iterable<T> {

  private final T[] deque;
  private final Object mutex;

  private final int limit;

  private int start;

  private int length;

  @SuppressWarnings("unchecked")
  public CircularBlockingDeque(int capacity) {
    deque = (T[]) new Object[capacity];
    mutex = new Object();
    limit = capacity;
    start = 0;
    length = 0;
  }

  public boolean addLast(T entry) {
    synchronized (mutex) {
      deque[(start + length) % limit] = entry;
      if (length == limit) {
        start = (start + 1) % limit;
      } else {
        length++;
      }
      mutex.notify();
    }
    return true;
  }

  public boolean addFirst(T entry) {
    synchronized (mutex) {
      if (start - 1 < 0) {
        start = limit - 1;
      } else {
        start--;
      }
      deque[start] = entry;
      if (length < limit) {
        length++;
      }
      mutex.notify();
    }
    return true;
  }

  public T takeFirst() throws InterruptedException {
    T entry;
    synchronized (mutex) {
      while (true) {
        if (length > 0) {
          entry = deque[start];
          start = (start + 1) % limit;
          length--;
          break;
        }
        mutex.wait();
      }
    }
    return entry;
  }

  public T peekFirst() {
    synchronized (mutex) {
      if (length > 0) {
        return deque[start];
      }
      return null;
    }
  }

  public T takeLast() throws InterruptedException {
    T entry;
    synchronized (mutex) {
      while (true) {
        if (length > 0) {
          entry = deque[(start + length - 1) % limit];
          length--;
          break;
        }
        mutex.wait();
      }
    }
    return entry;
  }

  public T peekLast() {
    synchronized (mutex) {
      if (length > 0) {
        return deque[(start + length - 1) % limit];
      }
      return null;
    }
  }

  public boolean isEmpty() {
    return length == 0;
  }

  @Override
  public Iterator<T> iterator() {
    return new Iterator<T>() {
      int offset = 0;

      @Override
      public boolean hasNext() {
        return offset < length;
      }

      @Override
      public T next() {
        if (offset == length) {
          throw new NoSuchElementException();
        }
        T entry = deque[(start + offset) % limit];
        offset++;
        return entry;
      }

      @Override
      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }
}