Thursday, November 29, 2007

Filter Iterators Using Predicates

Processing arrays is a simple affair: you can access elements directly by using their indexes, or iterate these simple data structures from start to end. Pretty soon though, you'll begin wishing for more flexibility with the use of more complex data structures and business rules. For example, if you wish to process only elements with a certain attribute, or exclude elements based on some selection criteria, or write applications that do not need to copy entire contents into arrays before processing, simple arrays are not what you need.
The solution is to write customized iterators that can manipulate your basic array without creating duplicate data, minimize having to write duplicate code if you wish to process the array in more than one place, and really separate logic for selecting data from code that processes the data. The easy way is to couple an iterator with a predicate: the iterator can visit any of the elements of the array, while the predicate evaluates whether the elements visited meet some criteria for selection.

Here's an implementation of this idea: this driver class shows how you can filter elements of an array based on a simple criterion. The program generates randomly an array of graph coordinates, and uses a predicate iterator to select only coordinates in the first quadrant.

package com.strive.research.algorithms.iteration;

public class PredicateIteration {

* Generates an array of coordinates.
* @param number Number of coordinates to generate.
* @return Array of coordinates.
public Coordinate[] generateCoordinates(int number) {
Coordinate[] array = new Coordinate[number];
for(int i = 0; i < array.length; i++) {
array[i] = new Coordinate();
return array;

* Prints the contents of an iterator by calling elements' toString() method.
* @param label Label to prefix ahead of iterator contents.
* @param iterator The iterator with contents to print
public void print(String label, Iterator iterator) {
String contents = "{";
boolean comma = false;
for(iterator.first(); !iterator.isDone();, comma = true) {
if(comma) {
contents += ", ";
contents += iterator.current().toString();
contents += "}";
System.out.println(label + ": " + contents);

* Demo and test ...
* @param args (Not used).
public static void main(String[] args) {
PredicateIteration prediter = new PredicateIteration();
// How many test items to use
int number = 10;
// Generate the coordinates
Coordinate[] coordinates = prediter.generateCoordinates(number);
// Print the generated list
Iterator general = new ArrayIterator(coordinates);
prediter.print("Original", general);
// Use predicate to show only coordinates in first quadrant
FilterIterator filtered = new FilterIterator(general, new FirstQuadrantPredicate());
prediter.print("Filtered", filtered);
// Exit

These projects are built using Eclipse 3.3.x (Europa) with JDK 1.6.x. You can find complete source code here:
Base project (AlgorithmsInJava) = defines the interfaces and base implementations that largely implement the idea above.
Demo project (IterationWithPredicates) = references the base project and implements a class the shows how to use iterators and predicates to filter data in arrays.

Monday, November 26, 2007

My "New" Bass Guitar

I don't own a new bass guitar, but it sure feels like it. I had it restrung and set up last week, an exercise that involved re-trussing the neck, using a much lighter string gauge, pickup tuning, and general cleaning. It sounds as good as new, as a result, much punchier and much cleaner.
It feels like a new beginning: suddenly I'm practicing more and trying new things on the bass. For a long time, I had not been able to slap/pick on this bass, but it seems I should be able to do it now. For slap/funk, I used another (4-string Aria Pro II) bass guitar, my first one ever. After four years, it still has a great sound.
I need to stop a very bad habit with the bass: not changing strings often enough. My mentor Dan Cervone always advocated for a monthly change of strings, but both my bass guitar can go a full year without fresh strings, even when I play somewhere every week. With this tune up, I also lost "tune retention", my term for when my bass guitar used to stay in tune for a long time. It might be weather changes too, but now I have to tune every time I play the bass. I'm in love with my bass guitar once again.

My bass is a Peavey Grind Bass Guitar 5 BXP NTB series, 5 string neck-through of mahogany wood. It comes as a passive bass, but I installed electronics to make it an active bass. These basses have a great sound, better than many bass guitars I have tried at music shops. The downside is that they are quite heavy, so after a 4-hour gig, your shoulders may complain. Which reminds me - it tends to get ungrounded often, giving off an ugly hiss; I should have remembered to have that checked into.
I'm still looking for a rig: an amp head (350-watts or more) and speaker cabinets (preferably a 4x10 and 1x18 or something within that combination range).
What all this means? I'm almost back to play my regular gigs. Three months off have been wonderful. I'll be up for grabs around the Christmas season.
This fine work on my bass was done at Pro Sound, Colorado Springs. The bass guitar specialist there is very knowledgeable, and prices are reasonable.

Saturday, November 10, 2007

Bernoulli Trials

When you toss a coin, the chances that a head shows are 50/50. But using Bernoulli Trials, we can repeats the coin tosses any number of times to obtain a spread of probabilities - the bell curve we all know. Below is the Java implementation of this idea. The algorithm likely runs in O(n2) time, so it is not efficient for large experiments.

* Prints a histogram showing the results of tossing a coin many times
* and the probability that either heads or tails will be shown. This is
* generally known as the sequence of Bernoulli Trials in probability theory.
* @param trials Number of times to repeat the experiment.
* @param flips Number of coin flips per experiment.
public static void bernoulliTrials(int trials, int flips) {
int i, j, cnt;
int[] f = new int[flips + 1];
for (j = 0; j <= flips; j++)
f[j] = 0;
for (i = 0; i < trials; i++, f[cnt]++)
for (cnt = 0, j = 0; j <= flips; j++)
if (Math.random() < 0.5)
// Drawing the histogram
for (j = 0; j <= flips; j++) {
if (f[j] == 0)
for (i = 0; i < f[j]; i += 10)

Friday, November 09, 2007

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for determining prime numbers less than a given maximum number. Prime numbers have become suddenly important to me, especially in scenarios where events must not collide. In that case, staggering timeouts minimizes the chances when primes are used.
This is the Java implementation of the algorithm, the quick and dirty way. Of course there's more complex and efficient algorithms out there. This one is good enough for small maximums and runs in O(n lg n) time. Beyond a certain number, the system will run out of memory and begin taking longer to determine the next prime.:
* Prints a list of prime numbers less than the max given.
* @param max Prime numbers will be less than this maximum.
private static void printPrimes(int max) {
// Create max-sized array
boolean[] a = new boolean[max];
// Initially assume all numbers are not non-prime
for (int i = 2; i+=1)
a[i] = true;
// Sieve of Eratosthenes algorithm
for (int i = 2; i+=1)

if (a[i] != false) {
for (int j = i; j * i < max; j+=1)
a[i * j] = false;
// Print the primes, 0 and 1 are not
for (int i = 2; i+=1)
if (a[i]) {
System.out.print(" " + i);

Tuesday, November 06, 2007

JPA Connections In Invalid State

Using Glassfish or the Sun Java System Application Server (SJSAS), you will occassionally get the following error:

javax.resource.spi.LocalTransactionException: Connection.close() has already been called. Invalid operation in this state.

It's more prevalent when using JPA with EJB 3.0 in your applications. The solution is surprisingly simple: stop the application server, restart the database (in my case the MySql service), and restart the application server. Simple!

Thursday, November 01, 2007

EJB3.0 Persistence Relationships

The EJB 3.0 persistence relationships via annotations always elude me, so I figured I should take note of them here now that I got it right (finally).
Suppose you want to express the idea that an activity is done on one task at a time by one user. Three objects are involved: Activity, User, Task. To build a database relation between these:
Activity(n)<->(1)User = @ManyToOne in Activity, @OneToMany in User. :: Activity can be associated with only one user while User can be associated with many activities.
Activity(n)<->(1)Task = @ManyToOne in Activity, @OneToMany in Task. :: Activity can be associated with only one task while Task can be associated with many activities.
User(1)<->(n)Task = @OneToMany in User, @ManyToOne in Task. :: A user can have many tasks, but a task can be owned by at most one user.
@ManyToMany is trivial and the commonest used.

For a person without the mental picture of database relationships, these simple rules will help.