/*
* $Id: Deque.java,v 1.7 2002/08/11 15:58:00 kredel Exp $
*/
//package edu.unima.ky.parallel;
package thread;
import java.io.*;
/**
* This Deque class implements a double ended queue in a
* similar way as the class BoundedBuffer does.
* It has some capacity to store objects.
* With the method put
objects are placed into
* the buffer. With the get
method objects are taken
* from the buffer in FIFO order and with pop
objects
* are taken from the buffer in LIFO order.
* put
blocks if there is no space to
* place a object into the buffer.
* get
and pop
block if there are
* no objects in the channel.
* This class is safe against Thread InterruptedException.
* @author Akitoshi Yoshida
* @author Heinz Kredel.
* @see BoundedBuffer
* see Channel
* see Queue
* see Deque
* see MemoryChannel
* see SyncChannel
* see Stack
*/
public class Deque implements Serializable {
/**
* the buffer is the deque contents.
*/
private Object[] buffer;
/**
* the buffer's size.
*/
private int size;
/**
* index to the first filled cell.
*/
private int front;
/**
* index to the first empty cell.
*/
private int rear;
/**
* a semaphore indicating an empty cell.
*/
private Semaphore empty;
/**
* a semaphore indicating a filled cell.
*/
private Semaphore full;
/**
* mutex for send.
*/
private Object snd;
/**
* mutex for receive.
*/
private Object rcv;
/**
* Declares an undefined value of type String
.
*/
public final static String undefined = "undefined value";
/**
* Construct a Deque.
* @param init An integer which defines the deques size.
*/
public Deque(int init) {
buffer = new Object[init];
size = init; front = 0; rear = 0;
empty = new Semaphore(init);
full = new Semaphore(0);
snd = new Object();
rcv = new Object();
}
/**
* Put an object to the deque.
* Return without object put if Interrupted.
* @exception InterruptedException.
*/
public void put(Object v) throws InterruptedException {
empty.P(); // return without Object put if Interrupted
synchronized (snd) {
if (rear < 0) rear += size;
if (rear >= size) rear -= size;
buffer[rear] = v;
rear++;
}
full.V();
}
/**
* Push an object to the deque.
* Return without object pushed if Interrupted.
* @exception InterruptedException.
*/
public void push(Object v) throws InterruptedException {
put(v);
}
/**
* Get an object from the deque, FIFO order.
* @exception InterruptedException.
* @return null object if Interrupted.
*/
public Object get() throws InterruptedException {
Object v = null;
full.P(); // return without Object if Interrupted
synchronized (rcv) {
if (front >= size) front -= size;
v = buffer[front];
front++;
}
empty.V();
return v;
}
/**
* Get an object from the deque within given timeout, FIFO order.
* @exception InterruptedException.
* @return null object if Interrupted.
*/
public Object get(int m) throws InterruptedException {
Object v = null;
if ( !full.P(m) ) return undefined;
// return without Object if Interrupted
synchronized (rcv) {
if (front >= size) front -= size;
v = buffer[front];
front++;
}
empty.V();
return v;
}
/**
* Pop an object from the deque, LIFO order.
* @exception InterruptedException.
* @return null object if Interrupted.
*/
public Object pop() throws InterruptedException {
Object v = null;
full.P(); // return without Object if Interrupted
synchronized (snd) {
rear--;
if (rear < 0) rear += size;
if (rear >= size) rear -= size;
v = buffer[rear];
}
empty.V();
return v;
}
/**
* Pop an object from the deque within given timeout, LIFO order.
* @exception InterruptedException.
* @return null object if Interrupted.
*/
public Object pop(int m) throws InterruptedException {
Object v = null;
if ( !full.P(m) ) return undefined;
// return without Object if Interrupted
synchronized (snd) {
rear--;
if (rear < 0) rear += size;
if (rear >= size) rear -= size;
v = buffer[rear];
}
empty.V();
return v;
}
/**
* Tests if the deque is empty.
*/
public boolean empty() {
return ( !full.isPositive() );
}
/**
* Get the number of elements in the deque.
* @return size of deque.
*/
public int size() {
int s = rear - front;
if ( s < 0 ) {
s += size;
}
return s;
}
}