Comparing XML payloads during testing (Java)

Update: This solution assumes both payloads have same (deep) order of attributes and elements.

Writing tests often requires XML payloads to be compared for equality. As such, XML payloads cannot be compared using String.equals() method due to possible differences in canonical representations of similar payloads.

For an example, these are equal XML payloads but not equal strings:

<person>
  <name>Neil</name>
  <age>31</age>
</person>

<person><name>Neil</name><age>31</age></person>

In this post I am listing a solution I wrote some time ago to compare XML payloads.

import java.io.IOException;
import java.io.StringReader;

import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.SAXParseException;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.DefaultHandler;
import org.xml.sax.helpers.XMLReaderFactory;

public class XMLCompare extends DefaultHandler {

 private StringBuilder accumulator = new StringBuilder();
    
 public static boolean equal(String xml1, String xml2)
 throws SAXException, IOException {
  return new XMLCompare().compareEqual(xml1, xml2);
 }

 private boolean compareEqual(String actualXML, String expectedXML)
 throws IOException {
  
  XMLReader xr = null;
  try {
   xr = XMLReaderFactory.createXMLReader();
  } catch (SAXException e) {
   throw new IllegalStateException("Unable to get XMLReader object");
  }
  xr.setContentHandler(this);
  xr.setErrorHandler(this);
  
  accumulator = new StringBuilder("");
  try {
   xr.parse(new InputSource(new StringReader(actualXML)));
  } catch (SAXException e) {
   throw new IllegalStateException(getInvalidXMLExceptionMessage(
     "ActualXML", actualXML));
  }
  String xmlString1 = accumulator.toString();
  accumulator = new StringBuilder("");
  try {
   xr.parse(new InputSource(new StringReader(expectedXML)));
  } catch (SAXException e) {
   throw new IllegalStateException(getInvalidXMLExceptionMessage(
     "ExpectedXML", expectedXML));
  }
  String xmlString2 = accumulator.toString();
  return xmlString1.equals(xmlString2);
 }

 private String getInvalidXMLExceptionMessage(String prefix, String xml) {
  return "" + prefix + " is not valid XML: **" + xml + "**";
 }

    /* --- Event handlers --- */

 @Override
    public void startDocument () { }

 @Override
    public void endDocument () { }

    // Every time the parser encounters the beginning of a new element, it
    // calls this method, which resets the string buffer
 @Override
    public void startElement (String uri, String name,
         String qName, Attributes atts) {
     appendStartElement(accumulator, uri, name, qName, atts);
    }

 private static void appendStartElement(StringBuilder string,
   String uri, String name, String qName,
   Attributes attributes) {
  if ("".equals(uri)) {
   string.append("<" + qName);
  } else {
   string.append("<{" + uri + "}" + name);
  }
  for (int i=0; i < attributes.getLength(); i++) {
   string.append(" " + attributes.getLocalName(i) + "=\"" +
     attributes.getValue(i) + "\"");
  }
  string.append(">");
 }

    // When the parser encounters the end of an element, it calls this method
 @Override
    public void endElement (String uri, String name, String qName) {
  accumulator.append("</");
  if ("".equals (uri)) {
   accumulator.append(qName);
  } else {
   accumulator.append("{" + uri + "}" + name);
  }
  accumulator.append(">");
    }

 // When the parser encounters plain text (not XML elements), it calls
    // this method, which accumulates them in a string buffer
    @Override
    public void characters (char ch[], int start, int length) {
  for (int i = start; i < start + length; i++) {
   if (!Character.isWhitespace(ch[i])) {
    accumulator.append(ch[i]);
   }
  }
    }

    /** This method is called when warnings occur */
 @Override
    public void warning(SAXParseException exception) throws SAXException {
        System.err.println("WARNING: line " + exception.getLineNumber() + ": "+
                           exception.getMessage());
        throw(exception);
    }

    /** This method is called when errors occur */
 @Override
    public void error(SAXParseException exception) throws SAXException {
        System.err.println("ERROR: line " + exception.getLineNumber() + ": " +
                           exception.getMessage());
        throw(exception);
    }

    /** This method is called when non-recoverable errors occur. */
 @Override
    public void fatalError(SAXParseException exception) throws SAXException {
        System.err.println("FATAL: line " + exception.getLineNumber() + ": " +
                           exception.getMessage());
        throw(exception);
    }

}

Thanks for reading through here -- your feedback is most welcome.

Collections.synchronizedXxx() methods are bad for concurrent scenarios (Java)

The java.util.Collections class provides easy factory methods for collections and maps. In this post, I am trying to highlight why the synchronizedXxx() methods are bad for concurrent scenarios. If you look at the source code of Sun JDK and IBM JDK (I haven't checked Oracle/BEA's) for these methods:

Collections.synchronizedList
Collections.synchronizedSet
Collections.synchronizedMap

you will find they essentially maintain a storage-object-level mutex -- every access obtains a lock upon that mutex to maintain thread-safety before going ahead with the operation. For concurrent scenarios, this is a disaster because you can only invoke one operation at a time.

Fortunately, there are few alternatives you can look at right inside the JDK. For maps, you can use:

java.util.concurrent.ConcurrentHashMap

and for lists or sets, you can look at these:

java.util.concurrent.CopyOnWriteArrayList
java.util.concurrent.CopyOnWriteArraySet

Java 6 users can also use these (Note: they are not O(1), but rather O(log(n)) operations):

java.util.concurrent.ConcurrentSkipListMap
java.util.concurrent.ConcurrentSkipListSet

However, there are few points worth knowing:

1. CopyOnWriteXxx collections are suited only for those scenarios where the read operations hugely outnumber the write operations.

2. Concurrent scenarios are better dealt with a strategy at application architecture level rather than brute force use of concurrency-optimized collections.

3. For concurrent scenarios, isolate operations with lifecycle-managed threads each dealing with immutable objects and/or small concurrent datasets rather than giant thread-safe ones. Minimize obtaining of locks rather than making everything thread-safe.

Please let me know what you think.

Detecting NullPointerException with Transparent checks (Java)

NullPointerException is a bane of programming in pointer or reference based programming languages. In this post I am suggesting a way to transparently detect NPEs at a very early stage in a less verbose manner, which should help minimize their occurrence.

Rule #1: Go for immutable references -- use "final" while declaring data members as much as you can.

Rule #2: Use transparent (and less verbose) NPE checks

For example, do NOT do this:

if (x == null) {
    throw new IllegalArgumentException("'x' is null");
}
x.doSomething();

Rather define a static method like this:

public static <T>T assertNotNull(final T object, final String errorMsg) {
    if (object == null) {
        throw new IllegalArgumentException(errorMsg);
    }
    return object;
}

and use it in a fluent style:

assertNotNull(x, "'x' is null").doSomething();

You can probably put the validating method in a utility class to reuse it everywhere. The good thing about this style is this can be used for cases other than NPEs -- for example you can use it to validate other things as well.

Thread-safe Time vs Frequency keeper (Java)

This post is to discuss the approach for counting operation frequency across time units. For example:

Question: How many stock prices were updated in the last 10 seconds (per second count)?

Answer: [6, 3, 0, 5, 2, 1, 4, 0, 9]

After 1 second: [4, 6, 3, 0, 5, 2, 1, 4, 0]
After 2 second: [7, 4, 6, 3, 0, 5, 2, 1, 4]

The answer varies depending on when the question is asked. To answer such questions at any point of time, we need a collector that would record the operation frequency per time unit, and slide the counter windows at the end of each time unit.

One solution is shown below: TimeVersusCountKeeper -- compile and run the class to see it in action.

Update: I have re-posted the code without line numbers. I am using this code in a highly multi-threaded message queuing (multiple queues) scenario, and it works fantastically -- there is one counter per queue and I display the live traffic for about 15-16 queues on a webpage that refreshes every second. But again, this may not be a use-case for every need.

import java.util.Arrays;
import java.util.Formatter;

/**
 * Keeps count across time slabs.
 */
public class TimeVersusCountKeeper {
    
    private final long[] UNITS;
    private final long   UNIT_DURATION_MILLIS;
    private final String UNIT_DURATION_NAME;
    
    private volatile long till = System.currentTimeMillis();
    private final String TILL_LOCK = new String("LOCK");
    
    private String getDurationName(final long unitDurationMillis) {
        final int unitCount = UNITS.length;
        final String s;
        String unitName;
        if (unitCount <= 1) {
            s = "";
            unitName = "unit of duration " + UNIT_DURATION_MILLIS + "ms";
        } else {
            s = "s";
            unitName = "unit(s) of duration " + UNIT_DURATION_MILLIS + "ms each";
        }
        if (UNIT_DURATION_MILLIS == 1000L)                         { unitName = "sec"; }
        else if (UNIT_DURATION_MILLIS == 60 * 1000L)               { unitName = "min"; }
        else if (UNIT_DURATION_MILLIS == 60 * 60 * 1000L)          { unitName = "hr";  }
        else if (UNIT_DURATION_MILLIS == 24 * 60 * 60 * 1000L)     { unitName = "day"  + s; }
        else if (UNIT_DURATION_MILLIS == 7 * 24 * 60 * 60 * 1000L) { unitName = "week" + s; }
        return unitName;
    }
    
    private synchronized void update() {
        long diff = 0;
        synchronized (TILL_LOCK) {
            diff = System.currentTimeMillis() - till;
        }
        
        if (diff > UNIT_DURATION_MILLIS) {
            final long TRUNCATE_UNITS_COUNT = diff / UNIT_DURATION_MILLIS;
            synchronized (UNITS) {
                if (TRUNCATE_UNITS_COUNT >= UNITS.length) {
                    Arrays.fill(UNITS, 0L);
                } else {
                    System.arraycopy(UNITS, 0, UNITS, (int) TRUNCATE_UNITS_COUNT,
                            UNITS.length - (int) TRUNCATE_UNITS_COUNT);
                    for (int i = 0; i < TRUNCATE_UNITS_COUNT; i++) {
                        UNITS[i] = 0;
                    }
                }
            }
            synchronized (TILL_LOCK) {
                till += TRUNCATE_UNITS_COUNT * UNIT_DURATION_MILLIS;
                //till = System.currentTimeMillis();
            }
        }
    }
    
    public TimeVersusCountKeeper() {
        UNITS = new long[10];         // last 10
        UNIT_DURATION_MILLIS = 1000L; // seconds
        UNIT_DURATION_NAME = getDurationName(UNIT_DURATION_MILLIS);
    }
    
    public TimeVersusCountKeeper(final int maxUnitsCount,
            final long unitLengthMillis) {
        this.UNITS = new long[maxUnitsCount];
        this.UNIT_DURATION_MILLIS = unitLengthMillis;
        UNIT_DURATION_NAME = getDurationName(UNIT_DURATION_MILLIS);
    }
    
    public void incrementBy(final long count) {
        update();
        synchronized (UNITS) {
            UNITS[0] += count;
        }
    }
    
    public void setCount(final long count) {
        update();
        synchronized (UNITS) {
            UNITS[0] = count;
        }
    }
    
    public long[] getElements() {
        update();
        synchronized (UNITS) {
            return UNITS.clone();
        }
    }
    
    @Override
    public String toString() {
        int unitsCount = 0;
        synchronized (UNITS) {
            unitsCount = UNITS.length;
        }
        return new StringBuilder()
        .append(unitsCount)
        .append(' ')
        .append(UNIT_DURATION_NAME)
        .append(": ")
        .append(getElementsAsString(1) /*Arrays.toString(units)*/)
        .toString();
    }
    
    public String getElementsAsString(final int minElementWidth) {
        final StringBuilder sb = new StringBuilder();
        final Formatter numFormatter = new Formatter(sb);
        final String format = "%" + minElementWidth + "d";
        final long[] array = getElements();
        long totalSum = 0;
        String delim = "";
        sb.append('[');
        for (int i = 0; array != null && i < array.length; i++) {
            numFormatter.format(delim + format, array[i]);
            totalSum += array[i];
            delim = ", ";
        }
        sb.append("](Avg:");
        numFormatter.format(format, (long) (totalSum / array.length));
        sb.append(')');
        return sb.toString();
    }
    
    public static void main(String[] args) {
        final TimeVersusCountKeeper keeper = new TimeVersusCountKeeper();
        for (int i = 0; i < 100; i++) {
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {}
            keeper.incrementBy(i);
            for (int j = 0; j < 100; j++) {
                keeper.incrementBy(1);
            }
            System.out.println(keeper.toString());
        }
    }
    
}

Fun with Iterators - UnionIterator

The problem
You want to create an iterator for a union of iterators. For example, you have 5 iterators and you want to create an iterator so that it represents elements in all 5 of them in linear fashion.

Solution
(For brevity and simplicity, the UnionIterator is a readonly iterator.)

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Iterator;
 import java.util.List;
 import java.util.NoSuchElementException;
 
 public class ReadonlyUnionIterator<E> implements Iterator<E> {
     
     private final Iterator<? extends Iterator<E>> parts;
     
     private Iterator<E> current = null;
     
     public ReadonlyUnionIterator(final Iterator<? extends Iterator<E>> parts) {
         this.parts = parts;
         alignForwardCurrent();
     }
     
     public static <E>ReadonlyUnionIterator<E> fromIterables(
             final Iterable<? extends Iterable<E>> iterableParts) {
         final List<Iterator<E>> itlist = new ArrayList<Iterator<E>>();
         for (final Iterable<E> each: iterableParts) {
             itlist.add(each.iterator());
         }
         return new ReadonlyUnionIterator<E>(itlist.iterator());
     }
     
     public static <E>ReadonlyUnionIterator<E> fromIterables(
             final Iterable<E>... parts) {
         return fromIterables(Arrays.asList(parts));
     }
     
     /**
      * Aligns 'current' by advancing to a non-empty element.
      * @return true if current has next element, false otherwise
      */
     private synchronized boolean alignForwardCurrent() {
         while (parts.hasNext()) {  // parts has next, but they may be empty!
             current = parts.next();
             if (current.hasNext()) { return true; }
         }
         current = null;
         return false;
     }
     
     public synchronized boolean hasNext() {
         // NULL is end-of-union marker for 'current'
         if (current == null)   { return false; }
         if (current.hasNext()) { return true; }
         // control reached here means current does not have next
         return alignForwardCurrent();
     }
     
     public synchronized E next() {
         if (hasNext()) { return current.next(); }
         throw new NoSuchElementException("No more element available");
     }
     
     public void remove() {
         throw new UnsupportedOperationException(
                 "Readonly iterator -- remove() is not supported");
     }
     
 }

Watch your Java compiler

So, scenario #1 is like:

class A {
  public static final String x = "foo";
  public static String y = "bar";
}

class B {
  public static void main(String[] args) {
    System.out.println(A.x);
    System.out.println(A.y);
  }
}

You compile both classes and run B - you get an output as follows:
foo
bar

And then you change A thusly:

class A {
  public static final String x = "baz";
  public static String y = "qux";
}

and compile only A. Then run B. The output?
foo
qux

What just happened? The compiler is in-lining the static final x, but not y. Well, that comes from the Java language spec.

Scenario #2:

public abstract class A {
  public A() {
    System.out.println(bar().getClass());
  }
  public void foo() {
    // do something
  }
  public abstract String bar();
}

public class B extends A {
  final String value = getBar();
  public String bar() {
    return value;
  }
  private String getBar() {
    return "barvalue";
  }
  public static void main(String[] args) {
    System.out.println(new B().bar());
  }
}

// invoke it
new B().foo();

Throws NullPointerException, but why? If you decompile B.class, you will find:

public class B extends A {
  String value = null;
  public B() {
    super();
    value = getBar();
  }
  public String bar() {
    return value;
  }
  private String getBar() {
    return "barvalue";
  }
  public static void main(String[] args) {
    System.out.println(new B().bar());
  }
}

So as it turns out, "final" variable is a compiler trick, as are keywords like "private" and "protected". You better be watching your Java compiler.

Almost literals - Initializing Java collections

Dynamic languages like Python and Ruby provide built-in syntax to express common data structures as literals. However, Java provides literal syntax only for arrays.

Although not pretty, here is how you can quickly initialize Java collections:

import java.util.*;

public class Literals {
   private static class HashMapNow<K, V> extends HashMap<K, V> {
       public HashMapNow<K, V> with(K key, V value) {
           put(key, value);
           return this;
       }
   }
  
   public static void main(String[] args) {
       // initialize a list
       List<String> list = Arrays.asList("a", "b", "c", "c");
      
       // initialize a set
       Set<String> set = new HashSet<String>(Arrays.asList("a", "b", "c", "c"));
      
       // initialize a map
       Map<String, String> map = new HashMapNow<String, String>()
       .with("a", "1")
       .with("b", "2")
       .with("c", "3")
       .with("c", "4");
      
       // print them all
       System.out.println(list);
       System.out.println(set);
       System.out.println(map);
   }
}

2009 Aug 25 [Update]: As suggested by Eric (in comments below), the initialization can be done in the static block - though it is admittedly quirkier. Cleaner options are available in Google Collections and LambdaJ.