Sunday, December 21, 2008

Generating Control Logic for 5 stage pipeline Processor Verilog

This one takes a little while to explain but is a really bright idea. Control logic for a processor is one of the most confusing parts. Especially if this is your first processor your building. Cranking out a Control Logic Table in excel or something is very valuable because it allows you to see how it all works out.

I wrote a little ruby script to generate verilog control code based on my spread sheet. Not only do you not have to code any control logic, but fixing control logic bugs are really easy because it is all in the spread sheet.

Ruby Script:

require 'pp'

def clean(str)
if str.rindex("b")
return str[1...str.size]
else
return str
end


end
@size = []
@wirename = []
@table = []

File.open('table.txt','r') do |f|
@size = f.gets.split("\t").map{|x| x.strip }
@wirename = f.gets.split("\t").map{|x| x.strip }
f.readlines.each do |l|
@table << l.split("\t").map{|x| x.strip }
end
end

@size.delete_at(0)
@size.delete_at(0)

@wirename.delete_at(0)
@wirename.delete_at(0)

@wiredefs = []
@assignments = []

#pp @size
#pp @wirename
#pp @table

#wire assignments
cur = 0
@wirename.each_with_index do |n,i|
puts n
df = ""
sz = @size[i].to_i
if sz == 1
df ="wire "
ass = "assign " + n.to_s + " = data[" + cur.to_s + "];"
else
df = "wire[" + (sz-1).to_s + ":0] "
ass = "assign " + n.to_s + " = data[" + (cur+sz-1).to_s + ":" + cur.to_s + "];"
end
df +=n.to_s + ";"


cur += sz
@wiredefs << df
@assignments << ass
end
datasize = 0
File.open ('export.v','w') do |v|

v.puts @wiredefs.join("\n")



@table.each {|x|
data = x[2...x.size]
data = data.reverse
data = data.map {|c| clean(c)}
q = data.join
code = "data = 32'b" + q
datasize = q.size if q.size > datasize


v.puts "7'b" + x[0] + ": " + code + " ;" + '//' + x[1].to_s
}

v.puts @assignments.join("\n")
end
puts "data size: " + datasize.to_s


Example Verilog output:

wire pc_en;
wire muxI;
wire[1:0] muxJ;
wire pc_select;
wire reg_write;
wire[1:0] rd_select;
wire sign_ext;
wire[1:0] sign_ext_mask;
wire[1:0] alu_rt_select;
wire alu_rs_select;
wire[1:0] alu_op;
wire[1:0] alu_cin_sign;
wire[1:0] alu_anot_bnot;
wire[1:0] shifter_op;
wire[2:0] logic_op;
wire exe_select;
wire save_select;
wire mem_write;
wire[2:0] write_select;
wire pc_add_select;
5'b00000: data = 32'bxxxx0xxxxxxxxxxxxxxxxxxxxx0xxxx0 ;//HALT
5'b00001: data = 32'bx0000x1xxxxx000100000xxxxx00xx01 ;//NOP
5'b01000: data = 32'bx0000x1xxxxx0001000101010010xx01 ;//ADDI
5'b01001: data = 32'bx0000x1xxxxx1011000101010010xx01 ;//SUBI
5'b01010: data = 32'bx0000x1xxxxx00xx100101000010xx01 ;//XORI
5'b01011: data = 32'bx0000x1xxxxx01xx110101000010xx01 ;//ANDNI
5'b10100: data = 32'bx0000x0xxx00xxxxxxx10xxx0010xx01 ;//ROLI
5'b10101: data = 32'bx0000x0xxx01xxxxxxx10xxx0010xx01 ;//SLLI
5'b10110: data = 32'bx0000x0xxx10xxxxxxx10xxx0010xx01 ;//SRAI
5'b10111: data = 32'bx0000x0xxx11xxxxxxx10xxx0010xx01 ;//SRLI
5'b10000: data = 32'bxxxx111xxxxx000100010101xx00xx01 ;//ST
5'b10001: data = 32'bx0100x1xxxxx0001000101010010xx01 ;//LD
5'b10011: data = 32'bx000111xxxxx0001000101010110xx01 ;//STU
5'b11001: data = 32'bx0010xx1xxxx00xx11001xxx1010xx01 ;//TM
5'b11011: data = 32'bx0000x1xxxxx000100001xxx1010xx01 ;//ADD
5'b11011: data = 32'bx0000x1xxxxx101100001xxx1010xx01 ;//SUB
5'b11011: data = 32'bx0000x1xxxxx00xx10001xxx1010xx01 ;//XOR
5'b11011: data = 32'bx0000x1xxxxx01xx11001xxx1010xx01 ;//ANDN
5'b11010: data = 32'bx0000x0xxx00xxxxxxx01xxx1010xx01 ;//ROL
5'b11010: data = 32'bx0000x0xxx01xxxxxxx01xxx1010xx01 ;//SLL
5'b11010: data = 32'bx0000x0xxx10xxxxxxx01xxx1010xx01 ;//SRA
5'b11010: data = 32'bx0000x0xxx11xxxxxxx01xxx1010xx01 ;//SRL
5'b11100: data = 32'bx0010xx000xx101000001xxx1010xx01 ;//SEQ
5'b11101: data = 32'bx0010xx001xx101000001xxx1010xx01 ;//SLT
5'b11110: data = 32'bx0010xx010xx101000001xxx1010xx01 ;//SLE
5'b11111: data = 32'bx0010xx011xx000000001xxx1010xx01 ;//SCO
5'b01100: data = 32'b0xxx0xxxxxxx00xx01000011xx0x0111 ;//BEQZ
5'b01101: data = 32'b0xxx0xxxxxxx00xx01000011xx0x0011 ;//BNEZ
5'b01110: data = 32'b0xxx0xxxxxxxxxxxxxxxx011xx0x1111 ;//BLTZ
5'b01111: data = 32'b0xxx0xxxxxxxxxxxxxxxx011xx0x1011 ;//BGEZ
5'b11000: data = 32'bx0110xxxxxxxxxxxxxx100110110xx01 ;//LBI
5'b10010: data = 32'bx0000x1xxxxx00xx011100100110xx01 ;//SLBI
5'b00100: data = 32'b0xxx0xxxxxxxxxxxxxxxx001xx01xx01 ;//J
5'b00101: data = 32'b1xxx0xxxxxxxxxxxxxxxx011xx01xx01 ;//JR
5'b00110: data = 32'b01000xxxxxxxxxxxxxxxx0011111xx01 ;//JAL
5'b00111: data = 32'b11000xxxxxxxxxxxxxxxx0111111xx01 ;//JALR
assign pc_en = data[0];
assign muxI = data[1];
assign muxJ = data[3:2];
assign pc_select = data[4];
assign reg_write = data[5];
assign rd_select = data[7:6];
assign sign_ext = data[8];
assign sign_ext_mask = data[10:9];
assign alu_rt_select = data[12:11];
assign alu_rs_select = data[13];
assign alu_op = data[15:14];
assign alu_cin_sign = data[17:16];
assign alu_anot_bnot = data[19:18];
assign shifter_op = data[21:20];
assign logic_op = data[24:22];
assign exe_select = data[25];
assign save_select = data[26];
assign mem_write = data[27];
assign write_select = data[30:28];
assign pc_add_select = data[31];


Example Excel File(csv):

1 1 2 1 1 2 1 2 2 1 2 2 2 2 3 1 1 1 3 1
pc_en muxI muxJ pc_select reg_write rd_select sign_ext sign_ext_mask alu_rt_select alu_rs_select alu_op alu_cin_sign alu_anot_bnot shifter_op logic_op exe_select save_select mem_write write_select pc_add_select
00000xx HALT 0 x bxx x 0 xx x xx xx x xx xx xx xx xxx x x 0 xxx x
00001xx NOP 1 0 bxx 0 0 bxx x xx b00 0 b00 b01 b00 bxx bxxx 1 x 0 b000 x
01000xx ADDI 1 0 bxx 0 1 b00 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 x 0 b000 x
01001xx SUBI 1 0 bxx 0 1 b00 1 b10 b10 0 b00 b11 b10 bxx bxxx 1 x 0 b000 x
01010xx XORI 1 0 bxx 0 1 b00 0 b10 b10 0 b10 bxx b00 bxx bxxx 1 x 0 b000 x
01011xx ANDNI 1 0 bxx 0 1 b00 0 b10 b10 0 b11 bxx b01 bxx bxxx 1 x 0 b000 x
10100xx ROLI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b00 bxxx 0 x 0 b000 x
10101xx SLLI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b01 bxxx 0 x 0 b000 x
10110xx SRAI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b10 bxxx 0 x 0 b000 x
10111xx SRLI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b11 bxxx 0 x 0 b000 x
10000xx ST 1 0 bxx 0 0 bxx 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 1 1 bxxx x
10001xx LD 1 0 bxx 0 1 b00 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 x 0 b010 x
10011xx STU 1 0 bxx 0 1 b01 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 1 1 b000 x
11001xx TM 1 0 bxx 0 1 b10 x bxx b01 0 b11 bxx b00 bxx b1xx x x 0 b001 x
1101100 ADD 1 0 bxx 0 1 b10 x bxx b01 0 b00 b01 b00 bxx bxxx 1 x 0 b000 x
1101101 SUB 1 0 bxx 0 1 b10 x bxx b01 0 b00 b11 b10 bxx bxxx 1 x 0 b000 x
1101110 XOR 1 0 bxx 0 1 b10 x bxx b01 0 b10 bxx b00 bxx bxxx 1 x 0 b000 x
1101111 ANDN 1 0 bxx 0 1 b10 x bxx b01 0 b11 bxx b01 bxx bxxx 1 x 0 b000 x
1101000 ROL 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b00 bxxx 0 x 0 b000 x
1101001 SLL 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b01 bxxx 0 x 0 b000 x
1101010 SRA 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b10 bxxx 0 x 0 b000 x
1101011 SRL 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b11 bxxx 0 x 0 b000 x
11100xx SEQ 1 0 bxx 0 1 b10 x bxx b01 0 b00 b10 b10 bxx b000 x x 0 b001 x
11101xx SLT 1 0 bxx 0 1 b10 x bxx b01 0 b00 b10 b10 bxx b001 x x 0 b001 x
11110xx SLE 1 0 bxx 0 1 b10 x bxx b01 0 b00 b10 b10 bxx b010 x x 0 b001 x
11111xx SCO 1 0 bxx 0 1 b10 x bxx b01 0 b00 b00 b00 bxx b011 x x 0 b001 x
01100xx BEQZ 1 1 b01 x 0 bxx 1 b01 b00 0 b01 bxx b00 bxx bxxx x x 0 bxxx 0
01101xx BNEZ 1 1 b00 x 0 bxx 1 b01 b00 0 b01 bxx b00 bxx bxxx x x 0 bxxx 0
01110xx BLTZ 1 1 b11 x 0 bxx 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 0
01111xx BGEZ 1 1 b10 x 0 bxx 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 0
11000xx LBI 1 0 bxx 0 1 b01 1 b01 b10 x bxx bxx bxx bxx bxxx x x 0 b011 x
10010xx SLBI 1 0 bxx 0 1 b01 0 b01 b10 1 b01 bxx b00 bxx bxxx 1 x 0 b000 x
00100xx J 1 0 bxx 1 0 bxx 1 b00 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 0
00101xx JR 1 0 bxx 1 0 bxx 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 1
00110xx JAL 1 0 bxx 1 1 b11 1 b00 bxx x bxx bxx bxx bxx bxxx x x 0 b100 0
00111xx JALR 1 0 bxx 1 1 b11 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 b100 1

Lazy List in Ruby

A Lazy List is a list that evaluates and constructs it self as it is used. Very much a functional language concept.

class LazyList
attr_accessor :head, :tail


def initialize(h, t)
@head = h
@tail = t
end

def nil?
return head.nil?
end

def self.null
return LazyList.new(nil, nil)
end

def self.seq(start, finish)
if start > finish
return LazyList.null
else
return LazyList.new(start, proc { seq( start + 1, finish) })
end
end

def self.infseq(start)
return LazyList.new(start, proc { infseq( start + 1 ) })
end


def self.constList(val)
return LazyList.new(val, proc { constList(val) })
end

def self.boolseq(start)
return LazyList.new(start, proc { boolseq(!start) })
end


def self.filter(listcontrol, listdata)
if listcontrol.nil? || listdata.nil?
return LazyList.new
end

if listcontrol.head
LazyList.new(listdata.head, proc { filter(listcontrol.tail.call, listdata.tail.call)})
else
filter(listcontrol.tail.call, listdata.tail.call)
end

end

def Nth(n)
return if nil?

if n == 0
return head
else
tail.call.Nth(n-1)
end
end

def self.filter_check(data, check)
if nil?
return
end

if data.head % check != 0
LazyList.new(data.head, proc { filter_check(data.tail.call, check)})
else
filter_check(data.tail.call, check)
end

end

def self.prime_help(list)
return LazyList.new(list.head, proc { prime_help(filter_check(list.tail.call, list.head))})
end

def self.primes
return prime_help(infseq(2))
end

def printN(n)
if nil?
return
end

puts head
if n >= 0 && !tail.nil?
tail.call.printN(n-1)
end
end
end

l = LazyList.seq(2, 8)
l.printN(34)
l = LazyList.infseq(3)
l.printN(34)
b = LazyList.boolseq(false)
b.printN(6)
f = LazyList.filter(b,l)
f.printN(6)

a = LazyList.primes()
a.printN(8)
puts "nth #{f.Nth(2)}"

Make Sublists in Scheme

A fairly useful function in scheme is to turn a list of elements into a list of list of elements

example: [1,2,3] => [[1], [2], [3]]

(define (make-sublists l)
(map (lambda (x) (list x )) l))

Tree Map Scheme

Very similar to the Map function for a list in scheme, you can apply a map to a tree.
This traverses the entire tree applying a map function to the value and stuffing back into a tree.
(define (tree-map f t)
(if (null? t)
()
(if (null? (cdr t))
()
(append (append (tree-map f (car t))
(list (f (cadr t))))
(tree-map f (caddr t))))
))

Valid and Equal Binary Tree Scheme

This is one possible way of determining whether two binary trees are equal. Granted this implementation is dependent on them being valid. Which is that they are both symmetric around the top head node.

(define (valid-bintree? t)
(if (null? t)
#t
(if (list? t)
(if (valid-bintree? (car t))
(if (valid-bintree? (caddr t))
#t
#f)
#f)
#f)
))

(define (equal-bintrees? a b)
(if (null? a)
(if (null? b)
#t
#f)
(if (null? b)
#f
(if (and (valid-bintree? a) (valid-bintree? b))
(and (= (cadr a) (cadr b)) (equal-bintrees?(car a) (car b)) (equal-bintrees?(caddr a) (caddr b)))
#f)
)
))

Extend Function Scheme

See merge and distrib for reference.
An extend function is a pretty handy function for doing some advance list procedures.

(define (extend L E)
(merge L (distrib L E))
)

Subsets function in Scheme

Subsets computes all the possible subsets possible for a list of unique values.

(define (subsets L)
(if (null? L)
(list ())
(extend (subsets (cdr L)) (car L))
))

Distrib function Scheme


(define (distrib L E)
(if (null? L)
()
(cons (cons E (car L))
(distrib (cdr L) E))
))

Merge List in Scheme


(define (merge a b)
(if (null? a)
b
(if (null? b)
a
(if (< (length (car a)) (length (car b)))
(append (list (car a)) (merge (cdr a) b))
(append (list (car b)) (merge (cdr b) a))
))))

Binary Search Tree in Java


import java.io.PrintWriter;

public class BinaryTreeNode {

private Comparable key;
private Object data;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode(Comparable pKey, Object pData)
{
key = pKey;
data = pData;
}

/**
* @return Returns the data.
*/
public Object getData() {
return data;
}

/**
* @param data The data to set.
*/
public void setData(Object data) {
this.data = data;
}

/**
* @return Returns the key.
*/
public Comparable getKey() {
return key;
}

/**
* @param key The key to set.
*/
public void setKey(Comparable key) {
this.key = key;
}

/**
* @return Returns the left.
*/
public BinaryTreeNode getLeft() {
return left;
}

/**
* @param left The left to set.
*/
public void setLeft(BinaryTreeNode left) {
this.left = left;
}

/**
* @return Returns the right.
*/
public BinaryTreeNode getRight() {
return right;
}

/**
* @param right The right to set.
*/
public void setRight(BinaryTreeNode right) {
this.right = right;
}



}

public class BinarySearchTree implements Dictionary {

private BinaryTreeNode mRoot;
private int mNumberItems=0;

/* insert
* -exact same functionality as update, see update (drops the return value though)
*/
public void insert(Comparable key, Object data) {
update(key,data);


}
/*recrusiveUpdateChild
* -runs through the entire tree, and updates a child with new data,
* -if the child doesn't exist, it is add at the appropriate branch ending
*
* returns true if update a node
* returns false if added a child at the end of the branch
*
*/
private boolean recurisiveUpdateChild(BinaryTreeNode parent, Comparable key, Object data)
{
if (key.compareTo(parent.getKey())==0)
{
parent.setData(data);
return true; //replaced an associated data node
}
if (key.compareTo(parent.getKey())<0)
{
if (parent.getLeft()==null)
{

parent.setLeft(new BinaryTreeNode(key,data));
mNumberItems++;
return false; //no replacement, addition to the tree
}
return recurisiveUpdateChild(parent.getLeft(),key,data);
}
else
{
if (parent.getRight()==null)
{
parent.setRight(new BinaryTreeNode(key,data));
mNumberItems++;
return false; // no replacement
}
return recurisiveUpdateChild(parent.getRight(),key,data);
}


}
/*Update
* -Provides add, and modify functionality
*
* -returns true if it did a modify
* -returns false if it did an add
*/
public boolean update(Comparable key, Object data) {
if (mRoot==null)
{
mRoot = new BinaryTreeNode(key,data);
mNumberItems++;
return false;
}
else
{
return recurisiveUpdateChild(mRoot,key,data);
}
}
/*recursiveLookupChild
* -simple lookup, traverses through the tree
*
* returns the associated data of the found node, if it found one
*
* returns null - if no node was found (fell off the tree)
*
*/
private Object recurisiveLookupChild(BinaryTreeNode parent, Comparable key)
{
if (key.compareTo(parent.getKey())==0)
{
return parent.getData();
}
if (key.compareTo(parent.getKey())<0)
{
if (parent.getLeft()==null) //fell off the tree
{
return null;
}
else
{
return recurisiveLookupChild(parent.getLeft(),key);
}
}
else
{
if (parent.getRight()==null) //fell off the tree
{
return null;
}
else
{
return recurisiveLookupChild(parent.getRight(),key);
}
}
}

/*lookup
* -looksup the data from the tree
* returns Data or null if not found
*/
public Object lookup(Comparable key) {
if (mRoot==null) return null;

return recurisiveLookupChild(mRoot,key);
}
/*size
* returns number of items in tree
*/
public int size() {
return mNumberItems;
}
/*print
* does an inorder traversal, printing out a sorted list of items
*/
public void print(PrintWriter p) {
//p.println("Printing Binary Search Tree");
printNode(mRoot,p);
}
/*printnode
* -recursive aux method for the print funcationality
*/
private void printNode(BinaryTreeNode node,PrintWriter p)
{
if (node==null) return;
//simple inorder traversal
printNode(node.getLeft(),p);

p.print(node.getKey());
p.print(" ");
p.println(node.getData());

printNode(node.getRight(),p);
}
}

Sorted Arraylist in Java


public class SortedArrayList implements Dictionary {

//number of items in the array
private int mNumberItems=0;

private DictionaryItem mItems[] = new DictionaryItem[10];
/*expand array
* -checks to see if array needs expansion, if so, it builds a new array
*/
private void expandArray()
{
if (checkExpandArray())
{
DictionaryItem newarray[] = new DictionaryItem[mItems.length*2];
System.arraycopy(mItems,0,newarray,0,mNumberItems); // copy all items into the new array
mItems = newarray;
}
}
/*checkExpandArray
*-if the numberofitems in the array is getting large, increase the size of the array to make room for another item
*/
private boolean checkExpandArray()
{
if (mNumberItems+1>=mItems.length)
{
return true;
}
return false;
}
/*insert
* -see update, same functionality, just drops the return value
*/
public void insert(Comparable key, Object data) {
update(key,data);

}
/*InsertIntoArray
* -Copies the data over in the array to make room
* -then slips the new value into that index
*/
private void insertIntoArray(int index, DictionaryItem item)
{
System.arraycopy(mItems,index,mItems,index+1,mNumberItems-index); // copy all items infront of the index
mItems[index] = item;
}
/*getIndexForKey
* does a linear search to find out where a certain key should be inserted
*/
private int getIndexForKey(Comparable key)
{
int i;
for(i=0;i<= mNumberItems-1;i++)
{
DictionaryItem curr = mItems[i];

if(curr.getKey().compareTo(key) >=0)
{
return i;
}
}
return mNumberItems;
}
/*getKeyAt
* -returns the key at a certain index
*/
private Object getKeyAt(int index)
{
return mItems[index].getKey();
}
/*lookupIndexForKey
* -does a binary search for a certain index location
* -returns -1 if value not found
*/
private int lookupIndexForKey(Comparable key)
{
return auxBinSearch(key,0,mNumberItems-1);
}
/*auxBinSearch
* -is the aux recursive method to implement the binary search
*/
private int auxBinSearch(Comparable key, int startindex,int endindex)
{
if (startindex > endindex) return -1;
int mid = (startindex + endindex)/2;

if (key.compareTo(getKeyAt(mid))==0) return mid;
if (key.compareTo(getKeyAt(mid))<0)
return auxBinSearch(key,startindex,mid-1); //go left
else
return auxBinSearch(key,mid+1,endindex);//go right

}


/*update
* -provides update functionality (insert, and replace
* returns true if it replaced
* returns false if inserted new record
*/
public boolean update(Comparable key, Object data) {

int insertindex=lookupIndexForKey(key);

if (insertindex!=-1)
{
mItems[insertindex] = new DictionaryItem(key,data);
return true;
}

//now we have to insert
//perform linear search and get insert location
insertindex= getIndexForKey(key);

expandArray();

insertIntoArray(insertindex,new DictionaryItem(key,data));
mNumberItems++;
return false;



}
/*lookup
* -uses a binary search to retrieve an object
* returns the Object if found
* return null if not found
*/
public Object lookup(Comparable key) {
int index = lookupIndexForKey(key);

if (index <0 || index > mNumberItems-1) return null;
return mItems[index].getData();
}
/*size
*-returns number of items in the array
*/
public int size() {
return mNumberItems;
}

/*print
* spits out the sorted arraylist contents
*/
public void print(PrintWriter p) {
//p.println("Printing Sorted ArrayList");
for(DictionaryItem curr: mItems )
{
if(curr!=null)
{
p.print(curr.getKey());
p.print(" ");
p.println(curr.getData());
}
}

}

}

Queue in Java


import java.util.ArrayList;

/*Queue
* implements a simple queue first in, first out
*/
public class Queue {

public Queue()
{

}

private ArrayList mItems = new ArrayList();

/* empty
* -returns true if there are 0 items in the queue
* other wise false
*/
public boolean empty()
{
return mItems.isEmpty();
}
/* size
* -returns the number of items in the queue
*/
public int size()
{
return mItems.size();
}
/*enqueue
* -adds a node to the back end of the queue
*
*/
public void enqueue(Object obj)
{
mItems.add(0,obj);
}
/*dequeue
* -removes the last Object from the inner list
* other words, pulls the first Object off the front of the queue
*/
public Object dequeue()
{
if (this.empty()) throw new EmptyQueueException();

return mItems.remove(mItems.size()-1);
}
/*peek
* -returns the front Object of the que
*/
public Object peek()
{
if (this.empty()) throw new EmptyQueueException();

return mItems.get(mItems.size()-1);
}

}

Stack in Java


import java.util.ArrayList;
import java.util.EmptyStackException;

/* Stack class
* A basic stack, you can push items in, last in, is first out.
*
*/
public class Stack {
/// stores my data member in the stack
private ArrayList mItems = new ArrayList();

public Stack()
{
}
/* empty
* -returns true if there are 0 items in the stack
* other wise false
*/
public boolean empty()
{
return mItems.isEmpty();
}
/* size
* -returns the number of items in the stack
*/
public int size()
{
return mItems.size();
}
/*push
* -adds an object to the Top of the stack
*/
public void push(Object obj)
{
mItems.add(obj);
}
/*pop
* -removes the top object from the stack and returns it
* throws EmptyStackException if stack is empty
*/
public Object pop()
{
if (this.empty()) throw new EmptyStackException();

return mItems.remove(mItems.size()-1);

}
/*peek
* -returns the current top object in the stack
* DOES NOT REMOVE IT
*/
public Object peek()
{
if (this.empty()) throw new EmptyStackException();

return mItems.get(mItems.size()-1);
}
}

Double Linked List in Java


/**
* LinkedList
*
* This is the core List class
* Provides a facility to a doublly linked list.
*
* Has Header Node optimization
* Has LastNode optimization as well
*
* Future Features:
* Optimized iterator support
* actually use some more of the optimization doublly linked lists gives you
*
*/

/**
* ListNode
*
* -The workhorse of the LinkedList Class
*
* Provides a doublely linked potencial to other list nodes
* Provides recursion for relative position Node lookups
* Provides automatic linking of next and previous nodes
*
*/
public class ListNode
{
/**
* Blank constructor
*/
public ListNode()
{
}
/**
* Purposeful constructor:
* passes data, and previous node, allows you to build node lists, easily by chaining
*/
public ListNode(Object pData,ListNode pPrevious)
{
mData = pData;
if (pPrevious != null) //since you can pass null to it
{
pPrevious.setNext(this); //automatic hook up
}
}

private Object mData; // stores the Object of value here

//Accessors to the Data Object
public Object getData()
{
return mData;
}
public void setData(Object obj)
{
mData = obj;
}


private ListNode mNext; // stores link to the next node in the list
//accessor to the Next reference
public ListNode getNext()
{
return mNext;
}
/**
* Automatic linking on setNext
* -set the mNext field's data
* but also will automaticly link the "nextNodes previous link to this Node's
*/
public void setNext(ListNode pNode)
{
mNext = pNode;
if (mNext != null)
{
mNext.mPrevious = this; //internal auto link MUST USE INTERNAL, If you use mNext.setPrevious infinite loop become evident
}
}

private ListNode mPrevious;
//public accessor to Previous Link
public ListNode getPrevious()
{
return mPrevious;
}
/**
* Automatic linking on setPrevious
* -set the mPrevious field's data
* but also will automaticly link the "previousNodes next link to this Node's
*/
public void setPrevious(ListNode pNode)
{
mPrevious = pNode;
if (mPrevious != null)
{
mPrevious.mNext = this; //internal auto link MUST USE INTERNAL, If you use mPrevious.setNext infinite loop become evident
}
}

/**
* Recurisve GetNext
* will return the node that is relativePos offset from this node only in the forward direction
*/
public ListNode getNextRecurisive(int relaitivePos)
{
if (relaitivePos <= 0) // if pos =0 return self
{
return this;
}
else
{
ListNode next = this.getNext(); //move to the next node
if (next != null)
{
return next.getNextRecurisive(relaitivePos - 1); //Let it count the rest of the way
}
else
{
throw new IndexOutOfBoundsException("Recursive search for rel pos could not find a node soon enough");
}
}

}

public class LinkedList
{

private ListNode mHeaderNode = new ListNode();
private ListNode mLastNode;
private int mNumItems = 0;

/**
* Constructor, sets up the default last node
*/
public LinkedList()
{
mLastNode = mHeaderNode;
}



/**
* Add is your basic add operation
* Adds to the end of the list, using the last node optimization
* the setNext function automaticly links in the previous links.
*
*/
public void add(Object obj)
{
ListNode node = new ListNode(obj,null);
mLastNode.setNext(node);
mLastNode = node; //update the last node optimization
mNumItems++;
}
/** add overload -> Insert
* Inserts a Object in the list node at any position
*
*/
public void add(int pos, Object obj)
{
if (pos == mNumItems)
{
//special case adding at the end of the list
add(obj); // use the regular add
return;
}
IsPositionInBoundsOf(pos); //Insure the pos is a vaild pos
ListNode node = getNode(pos);//node I am inserting at
ListNode newNode = new ListNode(obj, node.getPrevious());
// hook up new node to node that was behind current node
newNode.setNext(node);
// hook up old node, to the new position
mNumItems++;
}
/**
* Contains
* Returns true if LinkedList Contains a certain object
* Object.equals is our comparer method of choice
*
* other wise false
*
*/
public boolean contains(Object obj)
{
ListNode node = mHeaderNode.getNext(); //get the first node in the list

while (node != null) // go through till the end of the list
{
if (node.getData() != null) // check so you don't get a null ref exception
{
if (node.getData().equals(obj)) // use equals so.. ref type weird data types.. cough STRINGS don't hang us up
{
return true;
}
}
else
{
// if null was passed we want to return true if the obj is null
if (obj == null) return true;
}
node = node.getNext(); // increment up to the next node
}
return false;

}

/**
* IsPositionInBoundsOf
* Returns true if pos would return a valid node in this list, if not, it will throw and indexOutOfBoundsException
*
*/
protected boolean IsPositionInBoundsOf(int pos)
{
if (pos > mNumItems - 1)
{
throw new IndexOutOfBoundsException(pos + " Is out of the bounds of the List");
}
return true;

}
/**
* get
* Returns The object of a node at a certain position
*
*/
public Object get(int pos)
{
IsPositionInBoundsOf(pos); // insure pos is accurate

ListNode node = getNode(pos); //grab the node

return node.getData(); //return the data ; null is ok

}

/**
* INTERNAL METHOD
* getNode(pos)
* Returns the list node at a certain position
*
* does a recursive search for the specified position
*
*/
protected ListNode getNode(int pos)
{
IsPositionInBoundsOf(pos);
return mHeaderNode.getNextRecurisive(pos + 1); // +1 because of header node
}
/**
* isEmpty
* returns true if their are 0 items in this list
* otherwise false
*/
public boolean isEmpty()
{
return mHeaderNode.getNext() == null;

}
/**
* remove(pos)
* Returns the object at the pos you are removeing from
* Remove the last node, will re update the lastnode reference
*
* deincrements the count in list
*
*/
public Object remove(int pos)
{
IsPositionInBoundsOf(pos);
ListNode deletednode = getNode(pos);
if (deletednode == this.mLastNode) //last node special case
{
this.mLastNode = deletednode.getPrevious(); // just patch up the last node reference
}
deletednode.getPrevious().setNext(deletednode.getNext()); //patch the whole you just made

mNumItems--;
return deletednode.getData();
}
/**
* size
* Returns the number of items in this list
*/
public int size()
{
return mNumItems;
}

//DEBUG Methods
//remove these methods
/**
* Prints out the entire list of objects in list
*/
//public void printList()
//{
// System.out.println("");
// for (int i = 0; i < mNumItems; i++)
// {
// System.out.println(get(i));
// }
// System.out.println("
");
//}

}

Priority Queue in Java using ArrayList


class PriorityQueue {

private ArrayList maxHeap;

public PriorityQueue () {
maxHeap = new ArrayList();
maxHeap.add(null); //to fill element 0
}

public boolean empty () {
return maxHeap.size() == 1;
}

public void insert (Comparable p) {
if (p==null) return;
maxHeap.add(p);
int index = maxHeap.size()-1;
swapWithParent(index);

}

private void swapWithParent(int index)
{
int parentindex = index/2;
if (parentindex==0) return;
if (p.compareTo(maxHeap.get(parentindex)) > 0)
{
//swap them
Comparable p = maxHeap.get(index);
maxHeap.set(index,maxHeap.get(parentindex));
maxHeap.set(parentindex,p);
swapWithParent(parentindex);
}


}

}