The complexity of Map in Java

I just posted an updated version of my util library of extensions to Java Collections in the course of which I added a ListMap interface to replace UnionMap and an implementation, ArrayHashListMap.

If one were to write read-only Map implementations, the procedure is straight-forward and well-documented in the Javadocs for Map. However, writing a modifiable map is much more of an undertaking.

Consider all the places that "modifiability" can be leaked:

entrySet()

This is burdensome as the Set has to provide modifiable operations which effect the original Map and all methods of Set which themselves return modifiable collections or iterators need to tie back to the original Map all the way down to Map.Entry.

keySet()

The same remarks for entrySet() apply to keySet() (exception Map.Entry).

values()

Similarly for values() although it is a Collection rather than a Set, a distinction of very little.

layers()

A method particular to ListMap, it returns a list of maps which comprise the PATH-like layers which are collapsed to present a single Map view.

What did I do in face of this? I introduced a new interface, Refreshing (would Refreshable have been better?), which has one method, void refresh(), implemented versions of Map List, Set and Iterator which take a Refreshing object to signal after modifiable operations complete, and extended AbstractMap to return refreshing versions of collection classes for each of the possible points where modifiability leaks. You can see the result in ListMap and ArrayHashListMap.

Thank goodness for mock objects and unit tests!

More automake, now with packages

Murray Cumming had a lot of helpful things to say about automake and libraries. Drawing from that, I found the right way to package our inhouse libraries for reuse was to add this to the library's Makefile.am:

pkgconfigdir = $(libdir)/pkgconfig
pkgconfig_DATA = name_of_library_project.pc

And drop a name_of_library_project.pc.in into the top-level library project directory:

prefix=@prefix@
exec_prefix=@exec_prefix@
libdir=@libdir@
includedir=@includedir@

Name: Name of library project
Description: Some description here.
Requires:
Version: @VERSION@
Libs: -L${libdir} -lname_of_library link list of libraries for this project
Cflags:

The rest was magic, and "just worked". To other projects wanting to use the library, add this to their configure.in (or configure.ac; different names, same files):

PKG_CHECK_MODULES(DEPS, name_of_library_project)
AC_SUBST(DEPS_CFLAGS)
AC_SUBST(DEPS_LIBS)

(See my earlier post on autogen.sh.)

Porting the Angband borg to 3.0.6

The very excellent APWBorg for Angband does not compile out of the box for version 3.0.6, but the fix is simple. Make these substitutions in the borg?.c file:

Term->offset_x for p_ptr->wx
Term->offset_y for p_ptr->wy

This matches the ChangeLog description:

2004-05-31 17:26  rr9

        * src/: cave.c, cmd3.c, defines.h, dungeon.c, files.c, generate.c,
        l-player.pkg, spells2.c, types.h, wizard2.c, xtra2.c: Replaced the
        'wx' and 'wy' main term viewport coordinates with window specific
        offsets.

A simple diff of src/cave.c between versions 3.0.5 and 3.0.6 shows this change in the mainline sources.

UPDATE: Some tips on installing APWBorg under Linux in the form of command history:

$ unzip 305Borg.zip
$ cd 305Borg
$ rm MAIN-WIN.C
$ for x in *
> do mv $x $(echo $x | tr '[:upper:]' '[:lower:]')
> done
$ dos2unix *
$ ANGBAND=... # where ever you unpacked angband-3.0.6.tar.gz
$ cp borg*.[ch] $ANGBAND/src
$ cp borg.txt $ANGBAND/lib/user

You still need to fix up the make process to compile and link the borg sources into angband. Copy the sample autogen.sh to $ANGBAND and chmod +rx autogen.sh. Add the nine borg?.c files to the list of sources in $ANGBAND/src/Makefile.am. Add borg.txt to the list of sources in $ANGBAND/lib/user/Makefile.am. Then:

$ cd $ANGBAND
$ ./autogen.sh
$ ./configure --prefix=$ANGBAND
$ make install

Now play angband.

UPDATE: I dropped Dr. White a line and got a reply. Looks like my patch will make it into the next version of his borg. Yah for open source!

ReverseList for Java

One of my Java pastimes is writing trivial utility classes. Part of my interest is stylistic: I hate seeing blocky, chunky code that could be replaced by elegant, simple code. Illustrating my point, I needed a reversed list which presented an underlying list in reverse order. So I created a simple utility class, ReverseList, which fits the bill:

class ReverseList<E>
        extends AbstractList<E> {
    private final List<E> list;

    public ReverseList(final List<E> list) {
        this.list = list;
    }

    public void add(final int index, final E element) {
        list.add(reverseIndex(index) + 1, element);
    }

    public E remove(final int index) {
        return list.remove(reverseIndex(index));
    }

    public E get(final int index) {
        return list.get(reverseIndex(index));
    }

    public E set(final int index, final E element) {
        return list.set(reverseIndex(index), element);
    }

    public int size() {
        return list.size();
    }

    private int reverseIndex(final int index) {
        return size() - index - 1;
    }
}

The only trick to it is to note that add(int, Object) requires one bump the reversed index. I only discovered this during unit testing and was puzzled for a while. Then I realized that add is conceptually akin to inserting in that it shifts elements to the right: reversing the list shifts to the left, hence, requires that indices be off by one.

UPDATE: An even better explanation for the index in add: The indices are akin to point in Emacs, that is, they note the spot between elements and are just to the left of a given element. If you think of elements as boxes in a row, the point is the gap to the left of a box between it and the box next to it.

Reversing a list is like reflecting it in a mirror: traversing it from beginning to end becomes end to beginning when reversing. Likewise, point is reflected from being just to the left of an element to just to the right of an element. To represent this change in the original, underlying list is to increase the index of point by one.

UPDATE: Andrew McCormick pointed out that "reverse list" also has another name: Stack.

Java's weakness, C++'s strength

For the most part I enjoy coding in Java more than in C++. Especially with tools like the Intellij IDEA refactoring editor, my productivity is higher in Java and my pain lower. However, the one thing from C++ I miss the most is the destructor.

Strangely, many C++ programmers (at least those I witness) seem to overlook this strength. One of my favorite utility classes is so simple:

#include <stdio.h>

class auto_file {
  FILE* filep;

public:
  auto_file (const char *path, const char *mode) {
    if (!(filep = open (path, mode))
      throw some_program_specific_exception (path, mode);
  }

  ~auto_file () { close (filep); }

  operator FILE* () { return filep; }
};

Most times I could just use <fstream>, but sometimes I need to pass around file descriptors or FILE pointers to code outside my control. And when you work with sockets (which need the same treatment), there is no standard library facility.

Java's try-finally approach to releasing system resources is ok for many uses, but is prone to forgetfulness and does not work at all when object scope is complex.

The one thing I miss most in Java is the destructor. It would be swell to introduce a new language facility for them (something different from the finalize() fiasco). With garbage collection, Java could do an even better job than C++.

Rich text editing for HTML

I've been playing with LiveJournal and noticed they, too, have a rich text textarea widget. But when I tried the simplest thing that could possibly work:

<html>
    <head>
        <title>Rich text?</title>
    </head>
    <body>
        <form>
            <textarea rows="5" cols="20"></textarea>
        </form>
    </body>
</html>

It did not work. If I turn on the richtext feature of LiveJournal and paste in text I copy from a webpage which includes links, LiveJournal pastes the links as well as the text and formatting; with my sample page I just get plain text.

George Hotelling does write about this and points to Epoz project on SourceForge.

Sadly, there are no files to download in spite of the project claiming to be mature.

I just want to figure out how LiveJournal's rich text widget works.

A starter autogen.sh

I looked around quite a bit before jimmying together this autogen.sh for autoconfiscating a project at work:

#!/bin/sh
set -x
autoscan
libtoolize --automake --copy
aclocal
autoconf
autoheader
automake --foreign --add-missing --copy

The point of autoscan is to catch any new portability problems as they crop up.

To go with autogen.sh, here is a starter configure.in:

C_PREREQ(2.59)
AC_INIT([aproject], [0.0.0], [binkley@alumni.rice.edu])
AC_CONFIG_SRCDIR([config.h.in])
AC_CONFIG_HEADER([config.h])
AM_INIT_AUTOMAKE
AC_CONFIG_FILES([Makefile])
AC_OUTPUT

And Makefile.am:

lib_LTLIBRARIES = libsample.la
libsample_la_LDFLAGS = -version-info 0:0:0
libsample_la_SOURCES = sample.cc

It would have saved me considerable effort to begin with starter files such a these. Just plop them into the top-level of your project, and run ./autogen.sh. Correct for errors in the output and look at configure.scan for suggestion for updating configure.in. And update Makefile.am with a real list of your sources.

Rinse, lather, repeat.

UPDATE: With modern autotools installations, an even cleaner starter script:

#!/bin/sh
autoscan # show autotools lint
autoreconf --install "$@" # add -I dir for local M4 macros

NB — If you add -I m4 (for example) to pick up custom M4 macros in the m4/ directory of your project, remember to update Makefile.am as well and add to the top:

ACLOCAL_AMFLAGS = -I m4

Unfortunate duplicity, but necessary with current tools (autoconf 2.59 / automake 1.95). See this post for details.

The man who really knows his Linux

The Man Also Known As "I'm Batman!" has some great ideas about Linux and UNIX and can write about them.

And Slashdot thinks so, too.

The many ways to skin a cat

I just ran across yet another way to write the Factory pattern in Java:

public class Factory {
    private static interface Lineman {
        Thing create(final Widget widget);
    }

    private static Lineman[] LINEMEN = {
        new Lineman() {
            public Thing create(final Widget widget) {
                return new CoolThing(widget);
            }
        },
    };

    public static enum Things {
        COOL;

        private final Lineman lineman;

        Things() {
            lineman = LINEMEN[ordinal()];
        }

        public Thing create(final Widget widget) {
            return lineman.create(widget);
        }
    }
}

User code looks likes this:

final Thing thing = Factory.Things.COOL.create(widget);

Although overcomplicated-looking, it does has several useful points.

User code is constrained with enums as to the types of objects created by the factory. No business with class names or special strings. And modern editors have full code completion for the enums.

Secondly, code maintenance for the factory is simple. When you add a new type, add a new enum and a corresponding entry in the static array. This sort of work is straight-forward to automate with XDoclet or some custom build step.

UPDATE: I should point out that suitable imports simplify the user code further:

final Thing thing = COOL.create(widget);

And reflection can automate futher eliminating the need for a static array of factory methods if the classes follow some pattern in their naming, but with the caveats that go with reflection (ignoring exceptions):

public Thing create(final Widget widget) {
    return (Action) Class.forName(getThingClassName(name()))
            .getConstructor(Things.class, Widget.class)
            .newInstance(this, widget);
}

Let generics make your Java constructor cleaner

I often find myself writing Java constructors like this:

public SomeClass(final SomeType parameter) {
    super(parameter);

    if (parameter == null)
        throw new NullPointerException();
}

when what I really want to write is this:

public SomeClass(final SomeType parameter) {
    if (parameter == null) throw new NullPointerException();

    super(parameter);
}

which is, unfortunately, illegal. But there is a simple solution:

public SomeClass(final SomeType parameter) {
    super(asNotNull(parameter));
}

What is asNotNull(?)?

public static <T> T asNotNull(final T parameter) {
    if (parameter == null) throw new NullPointerException();

    return parameter;
}

As I generify the input, I am able to preserve the type on output so including calls to asNotNull(T) lose no type information and I need not write casts.

Of course, you can generalize this idea further and provide a family of tests or a more general method which takes an interface as a parameter or even an Exception parameter to change the thrown exception.

Ruby to Smalltalk

As part of working on Ruby on the Smalltalk VM, I am looking at ways of parsing Ruby in Ruby. My starting point is the fact that parse.y is by definition the most correct parsing of Ruby. So I thought, How could I turn parse.y into Ruby? Here is my idea:

1. Turn parse.y into parse.c — Already done for me in the stock Ruby distribution
2. Use GCC to turn parse.c into parse.rtl (where RTL is the intermediate representation of a program used by GCC) or parse.s (where S is some flavor of assembly)
3. Find or write a small RTL or Assembly interpreter in Ruby.

And there you have it. I have reduced a nasty problem (turning YACC/C source) into a less nasty one (interpreting in Ruby a made-to-interpret language).

Now to figure out step #3.

One to keep an eye on (or two)

Ryan Davis is someone to keep an eye on. His work on ruby parsers is letting a lot of interesting stuff flow into and through Ruby. And just as worth watching is Caleb Clausen and the Ruby Extended Grammar. These are interesting times to live in for Ruby.

How do I love thee?

It's official: Ruby is everybody's favorite sweetheart.

Rubyists in Houston unite with your CopyNight brethren!

Peter Suk and I are getting together at the The Stag's Head Pub in Shepherd Plaza at 2128 Portsmouth at 6pm Tuesday. All Houston Rubyists welcome. Pair Programming is in the offing.

AND: And as an extra special attraction bonus feature, Bobby Nagle organized the CopyNight folks to meet with us! Courtesies to the H-Town Blogs.

You have nothing to lose except some unsightly pounds or the loss of public domain works, whichever comes first.

VisualWorks, Smalltalk VM and image

Cincom Smalltalk's VisualWorks is a rich, portable Smalltalk VM and image suggested to me by Peter Suk as a target VM for porting Ruby. The software installs easily under Windows (well, you need to unpack it yourself and set up the Windows file assocation, but the instructions are clear) and runs beautifully. It makes me wistful for Smalltalk and happy to port Ruby to such a nice environment.

Glazed lists for Java

Glazed Lists is a clever Java API for list filtering. The swing intergration is particularly nice, and they even have a nice JNLP demo that works on live data from real projects rather than a canned fake like most JNLP demos. For example, the Glazed Lists data is the list of issues for the product itself. Great job!

I wish more demos were as realistic (and performant) as this one. To be honest, the demo is so excellent (look at the bug list for Looking Glass Core) it overshadows Glazed Lists. But this is a such a plus: an utility API should never get in the way of the GUI frontend, and Glazed Lists lives up to that expectation greatly.

Ruby hookup on Tuesday

Peter Suk and I are getting together at the The Stag's Head Pub in Shepherd Plaza at 2128 Portsmouth at 6pm Tuesday. All Houston Rubyists welcome. Pair Programming is in the offing.

Hani does ThoughtWorks

BileBlog likes to throw sideways squirts at ThoughtWorks (my former employer) once in a while. Friday's full-on firehose is entertaining and even insightful. And it's nice being called a young kid. Time to shake some dust off my USENET asbestos suit. uucp anyone?

Ruby revelation

I just wrote this letter to Paul Holser, a buddy of mine at ThoughtWorks. It explains pretty well the excitement I feel coming from Ruby:

I'm doing my best. I smell the Ruby-bean coffee brewing, and my caffeine cravings are kicking mighty hard.

I am (was) an expert in C++. But I long ago passed the 80/20 mark. To get more ooph out of C++, I became a template metaprogramming wizard. But the reward/effort ratio was low.

Then I became an export in Java. But again I have passed the 80/20 mark and am (was) exploring annotations and aspects to get more bang for the buck. Again the reward/effort ratio is too low.

So now I have a shiny new toy in front of me, Ruby. This is so much more fun than trying to squeeze those last few MPG out of my other programming engines.

Know what I mean, Earl?

Right now are those heady, young days again like when I first learned about programming and why the meta-thinking I enjoyed in college was actually useful. Shine on!

Obie does Ruby

Obie writes a bang-up piece in praise of Ruby. Coming from ThoughtWorks, I know just where he's speaking from when he says:

The nubys that do not have OO programming experience are being helped by Ruby old-timers and the other significant group of developers streaming into the Rails community: senior Java developers looking for something better that what we have to deal with now.

Yes, I am one of those senior Java developers. And where did I first hear of Ruby? At ThoughtWorks. If a long-time, hard-core, high-end shop like ThoughtWorks is preaching Ruby to clients like some vanguard of the proletariat, then the revolution is well underway.

Houston Rubyist hoedown

I just got off the horn with the excellent Peter Suk (he of Ruby to Smalltalk VM porting fame) and found a place for the Houston Rubyists to roost: Tuesdays at The Stag's Head Pub in Shepherd Plaza at 2128 Portsmouth. Be there, or be like a static programming language.

UPDATE: Peter pointed out the wiki for his VM project. However, it's timing out for me.

UPDATE: Well, I didn't make it. My date rang long (a better excuse than many), so I owe Peter a decent draft.

Higher-Order Perl

Now here's an interesting book title, Higher-Order Perl. The description:

Higher-Order Perl is about functional programming techniques in Perl. It's about how to write functions that can modify and manufacture other functions.

That's worth my Amazon wishlist.

Maven and JavaCC

I finally have a little time, so I'm writing a prototype build of PCGen using Maven as an alternative to the Ant build.

One piece to mind is DiceExpression.jj. I wrote it some time back to parse simple dice roll expressions such as 2d6+3. To wit, Maven provides a JavaCC plugin but the documentation is rather sparse. I can tease most of it out from the plugin.jelly for JavaCC, however a working example is always easier.

Happily, Howard Lewis Ship provides one ironically named Moving Away from Maven. Thank you, Howard.

Maven 2

Ah, yes. That favorite tool of many (especially Hani) is reappearing in a new incarnation. Maven 2: The Rewrite Simpler! Faster! Easier! All worthy goals. Of course, I have to try it.