9am

Archive for 2010|Yearly archive page

Synchronized Blocking Queue

In Uncategorized on November 14, 2010 at 10:03 am

Synchronization can be solved using intrinsic locks, explicit locking or optimistic locking with Compare-And-Swap (CAS) logic.

This implementation uses notifyAll() which can be avoided using Java’s new Lock and Condition objects.
NotifyAll is needed for the implementation to work correctly but the down side is that more threads than necessary are signalled when state changes.

This post deals with a rudimentary in-efficient way of synchronization :

package self.synchronization;

public class BlockingQueue1<T> {

private Node head = null;
private Node tail = null;

private final int maxCount = 10;

private volatile int currentCount = 0;

public void produce(T item) throws InterruptedException

{

Node newTail = new Node(item, null);

synchronized(this)

{

// condition

while (this.currentCount >= maxCount)

{

this.wait();

}

 

if (tail != null)

{

tail.next = newTail;

}

else

{

tail = newTail;

head = newTail;

}

 

++this.currentCount;

this.notifyAll();

}

}

public T consume() throws InterruptedException

{

Node returnNode = null;

synchronized(this)

{

// condition

while (currentCount == 0)

{

this.wait();

}

returnNode = head;

head = head.next;

if (head == null) tail = null;

–currentCount;

this.notifyAll();

}

return returnNode.item;

}

private class Node

{

public final T item;

public Node next;

Node(T item, Node next)

{

this.item = item;

this.next = next;

}

}

}

Advertisements

What’s The Number Again ?

In Algorithms, Graphs, Programming, Strings on September 16, 2010 at 9:49 pm
The previous post “What’s The Number” had a non-recursive implementation. Here is a recursive way of doing the same. It’s not as bad to have a recursive implementation as the max recursion depth is limited by the length of  a telephone number. If the input was longer / without an upper bound, recursion would be a bad move. This Recursive algorithm does a Depth First walk. A recursive Breadth First walk is much more painful to implement and has a higher memory overhead.
/*
Given a telephone number like 4156434531, get all possible names that would match it.
e.g. If the number is 23, the names could be “ad”, “bd”, “cd”, “ae” etc..
*/
public static class TelNumber
{
private static char[][] KeyChars = new char[10][];
static TelNumber()
{
KeyChars[0] = new char[]{‘+’};
KeyChars[1] = new char[]{‘ ‘};
KeyChars[2] = new char[]{‘a’,’b’,’c’};
KeyChars[3] = new char[]{‘d’,’e’,’f’};
KeyChars[4] = new char[]{‘g’,’h’,’i’};
..
}
public static void PrintCombination(StringBuffer prefix, int[] tel_no)
{
int index = prefix.Count;
if (index >= tel_no.Length)
{
System.Console.Writeline(prefix);
return;
}
foreach(char c in KeyChars[tel_no[index]])
{
prefix.Add(c);
PrintCombination(prefix, tel_no);
prefix.RemoveLastChar();
}
}