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);
}