Threads: Producer-Consumer Problem

Producer-Consumer problem is a very common question related to threads. Following is a simple solution to the problem. QueueClass represents the queue which both the Producer and Consumer has to access. The critical methods in the QueueClass - add() and remove() are synchronized in order to maintain the status quo between the Producer and Consumer threads.

import java.util.List;
import java.util.ArrayList;

public class ProducerConsumerTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  QueueClass q = new QueueClass();
  Producer p = new Producer(q, 10);
  Consumer c = new Consumer(q, 10);
  
  Thread t1 = new Thread(p);
  Thread t2 = new Thread(c);
  c.setpThread(t1);
  t1.start();
  t2.start();
 }

}

class Producer implements Runnable {
 QueueClass q;
 int size;
 
 Producer(QueueClass q, int size) {
  this.q = q;
  this.size = size;
 }

 public void run() {
  int index = -1;
  while(true) {
   q.add(new String("" + ++index));
   try {
    Thread.sleep(1000);
   }
   catch(InterruptedException e) {
    e.printStackTrace();
   }
  }
 }
}

class Consumer implements Runnable {
 QueueClass q;
 int size;
 Thread pThread;
 
 public void setpThread(Thread pThread) {
  this.pThread = pThread;
 }

 Consumer(QueueClass q, int size) {
  this.q = q;
  this.size = size;
 }

 public void run() {
  while(true) {
   q.remove();
   try {
    Thread.sleep(1000);
   }
   catch(InterruptedException e) {
    e.printStackTrace();
   }
  }
 }
}

class QueueClass {
 List queue = new ArrayList();
 int size = 10;
 
 public synchronized void add(String s) {
  if(getSize() < size) queue.add(s);
  System.out.println("Added: " + queue);
  try {
   if(getSize() >= size) {
    notifyAll();
    wait();
   }
  }
  catch(InterruptedException e) {
   e.printStackTrace();
  }
 }
 
 public synchronized void remove() {
  if(getSize() > 0) queue.remove(queue.size()-1);
  System.out.println("Removed: " + queue);
  try {
   if(getSize() <= 0) {
    notifyAll();
    wait();
   }
  }
  catch(InterruptedException e) {
   e.printStackTrace();
  }
 }
 
 public synchronized int getSize() {
  return queue.size();
 }
}

Linked List

Linked list is a fundamental data structure, which uses reference stored in each node to iterate through subsequent nodes. A linked list has many types like singly linked list, doubly linked list and circular linked list. Following is a simple bare bone implementation of singly linked list:

The base interface:

public interface LinkedList {
 public boolean add(T t);
 public boolean remove(T t);
 public void removeAll();
 public int size();
 public boolean isEmpty();
}

Class representing each node:

public class LinkNode {
 private LinkNode nextNode = null;
 private T node = null;

 public LinkNode() {
  
 }
 
 public LinkNode(T node) {
  this.node = node;
 }
 
 public T getNode() {
  return node;
 }

 public void setNode(T node) {
  this.node = node;
 }
 
 public LinkNode getNextNode() {
  return nextNode;
 }

 public void setNextNode(LinkNode nextNode) {
  this.nextNode = nextNode;
 }
 
 public String toString() {
  return node.toString();
 }
 
 public int hashCode() {
  return node.hashCode();
 }
 
 public boolean equals(LinkNode t) {
  return node.equals(t.getNode());
 }
}

Implementation for a singly linked list:

public class SingleLinkedList implements LinkedList {
 LinkNode header = null;
 LinkNode lastNode = null;
 
 public SingleLinkedList() {
  
 }
 
 public boolean add(T t) {
  LinkNode newNode = new LinkNode(t);
  if(header == null) {
   header = newNode;
  }
  else {
   lastNode.setNextNode(newNode);
  }
  lastNode = newNode;
  return true;
 }
 
 public boolean remove(T t) {
  LinkNode tmp = header;
  LinkNode prev = null;
  
  while(tmp != null) {
   if(tmp.getNode().equals(t)) {
    if(prev == null) header = null;
    else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());
    return true;
   }
   prev = tmp;
   tmp = tmp.getNextNode();
  }
  return false;
 }
 
 public void removeAll() {
  header = null;
 }
 
 public boolean isEmpty() {
  return header == null;
 }
 
 public int size() {
  LinkNode tmp = header;
  int size = 0;
  while(tmp != null) {
   size++;
   tmp = tmp.getNextNode();
  }
  
  return size;
 }
 
 public String toString() {
  StringBuffer str = new StringBuffer("[");
  LinkNode tmp = header;
  while(tmp != null) {
   str.append(tmp.toString());
   tmp = tmp.getNextNode();
   if(tmp != null) str.append(", ");
  }
  str.append("]");
  return str.toString();
 }
}

Test class which uses the singly linked list implementation:

public class LinkedListTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  LinkedList list = new SingleLinkedList();
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.add("1");
  list.add("2");
  list.add("3");
  list.add("2");
  list.add("2");
  list.add("3");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.remove("2");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.removeAll();
  System.out.println("Is list empty? " + list.isEmpty());
 }

}

Reversing a String in Java

The following code shows different methods of reversing a String in Java. The simplest being using the reverse() method of StringBuffer, while the other methods use char array and recursion:

public class StringReverse {<br />	public static void main(String[] args) {<br />		String s = "zyxwvutsrqponmlkjihgfedcba";<br />		System.out.println(charReverse(s));<br />		System.out.println(recursiveReverse(s , new StringBuffer()));<br />		System.out.println(recursiveReverse2(s, new StringBuffer()));<br />		System.out.println(bufferReverse(s));<br />	}<br />	<br />	public static String charReverse(String s) {<br />		char[] cArr = s.toCharArray();<br />		StringBuffer reversed = new StringBuffer();<br />		for(int i=cArr.length-1; i>=0; i--) reversed.append(cArr[i]);<br />		return reversed.toString();<br />	}<br />	<br />	public static String recursiveReverse(String s, StringBuffer t) {<br />		if(s.length() > 0) {<br />			t.append(s.substring(s.length()-1));<br />			recursiveReverse(s.substring(0, s.length()-1), t);<br />		}<br />		return t.toString();<br />	}<br />	<br />	public static String recursiveReverse2(String s, StringBuffer sb) {<br />		if (s.length() == 1){<br />			sb.append(s);<br />		}<br />		else{<br />			recursiveReverse2(s.substring(1, s.length()), sb);  <br />			sb.append(s.substring(0,1));<br />		}<br />		return sb.toString();<br />	}<br />	<br />	public static String bufferReverse(String s) {<br />		StringBuffer sb = new StringBuffer(s);<br />		return sb.reverse().toString();<br />	}<br />}

HSQLDB

HSQLDB is a 100% Java database which is embeddable. It has a small footprint and can be used for self-contained applications. The source files, the JAR file and support documents can be downloaded from hsqldb.org. It also provides a JDBC driver. HSQLDB is perfect for quick implementation and testing.

Following is a sample program which uses the JDBC driver for creating a table, inserting some data in the table and listing the rows from the table:

import java.sql.DriverManager;
import java.sql.Connection;
import java.sql.Statement;
import java.sql.SQLException;
import java.sql.DatabaseMetaData;
import java.sql.ResultSet;
import java.sql.PreparedStatement;

public class HSQLTest {
 Connection conn;
 Statement stmt;
 PreparedStatement add_stmt, get_stmt;
 
 static {
  try{
   Class.forName("org.hsqldb.jdbcDriver").newInstance();
  }
  catch(ClassNotFoundException e) {
   e.printStackTrace();
  }
  catch(InstantiationException e) {
   e.printStackTrace();
  }
  catch(IllegalAccessException e) {
   e.printStackTrace();
  }
 }
 
 HSQLTest() {
  try {
   initializeDB();
   createTable();
   populateTable();
   displayRows();
  }
  catch(SQLException e) {
   e.printStackTrace();
  }
 }
 
 void initializeDB() throws SQLException {
  conn = DriverManager.getConnection("jdbc:hsqldb:db/test", "sa", "");
  stmt = conn.createStatement();
 }
 
 public void createTable() throws SQLException {
  String table_name = "sample_table";
  DatabaseMetaData dbM = conn.getMetaData();
  ResultSet rs = dbM.getTables(null, null, "%", null);
  boolean found = false;
  while(rs.next()) {
   String s = rs.getString(3);
   //System.out.println(s);
   if(s.equalsIgnoreCase(table_name)) {
    found = true;
    break;
   }
  }
  
  if(!found) {
   String s = "CREATE TABLE " + table_name + "(id INTEGER GENERATED BY DEFAULT AS IDENTITY(START WITH 1000) PRIMARY KEY, " +
      "category VARCHAR(40), name VARCHAR(40))";
   stmt.execute("SET WRITE_DELAY FALSE;");
   stmt.executeUpdate(s);
  }
 }
 
 public void populateTable() throws SQLException {
  stmt.executeUpdate("insert into SAMPLE_TABLE (category, name) values ('E0', 'Ben')");
 }
 
 public void displayRows() throws SQLException {
  ResultSet rs = stmt.executeQuery("SELECT * FROM SAMPLE_TABLE");
  int numCols = rs.getMetaData().getColumnCount();
  while(rs.next()) {
   for(int i=1; i<=numCols; i++) {
    System.out.println(rs.getString(i) + ": " + rs.getString(i));
   }
  }
 }
 
 public static void main(String[] args) {
  HSQLTest hTest = new HSQLTest();
 }
}