Java filter iterator

Several separate Java projects have led to using the same simple Iterator implementation, AbstractFilterIterator. The idea is very simple: use a single method to filter an underlying Iterator and decide which subset of the data to reveal. Perhaps it is more easily shown than explained, at least for me:

/*
 * AbstractFilterIterator.java
 * Copyright 2003 (C) B. K. Oxley (binkley)
 * <binkley@alumni.rice.edu>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 *
 * Created on July 15, 2003.
 *
 * $Id: AbstractFilterIterator.java,v 1.1 2003/08/28 19:07:52 binkley Exp $
 */

package hm.binkley.util;

import java.util.Iterator;
import java.util.ListIterator;

/**
 * <code>AbstractFilterIterator</code> is a partial list iterator.
 *
 * @author <a href="mailto:binkley@alumni.rice.edu">B. K. Oxley (binkley)</a>
 * @version 1.0
 */
public abstract class AbstractFilterIterator
    implements Iterator {
    /** <code>ListIterator</code> through the elements. */
    protected ListIterator it;

    /** The current element after {@link #next()}. */
    protected Object cursor = null;

    /**
     * Construct an <code>AbstractFilterIterator</code> from an
     * underlying iterator over a range.
     *
     * @param it the underlying iterator
     *
     */
    protected AbstractFilterIterator(ListIterator it) {
	this.it = it;
    }

    /**
     * Match <var>element</var>.  If the match is
     * <code>true</code>, <code>AbstractFilterIterator</code> will
     * present <var>element</var> in the view of the underlying
     * iterator.
     *
     * @param element the element to match
     * @return <code>true</code> if the element matches
     */
    protected abstract boolean match(Object element);

    /**
     * Scroll the underlying iterator forward to find the next match.
     * Afterwards, use {@link #rewindNext(int)} to return the
     * underlying iterator to its original position.
     *
     * @return boolean <code>true</code> if there is a next match
     */
    protected boolean findNext() {
	while (it.hasNext())
	    if (match(it.next()))
		return true;

	return false;
    }

    /**
     * Return the underlying iterator to previous position after an
     * earlier call to {@link #findNext()}.
     *
     * @param current the previous position
     */
    protected void rewindNext(int current) {
	for (int next = it.nextIndex(); next > current; --next)
	    it.previous();
    }

    /** {@inheritDoc} */
    public boolean hasNext() {
	// We have do it this way so that you can use next()
	// independently of hasNext().
	int current = it.nextIndex();
	boolean hasNext = findNext();

	rewindNext(current);

	return hasNext;
    }

    /** {@inheritDoc} */
    public Object next() {
	while (!match(cursor = it.next()))
	    ; // nothing

	return cursor;
    }

    /** {@inheritDoc} */
    public void remove() {
	it.remove();
    }
}

As you might suspect, AbstractFilterListIterator is similar and extends AbstractFilterIterator to include methods from ListIterator. This is very straight-forward as AbstractFilterIterator already has a protected ListIterator member, it, to work with.

Duff's device

Periodically while my mind wanders I alight upon Duff's device, one of the cleverest pieces of C code I have ever seen. (Apparently Stroustrup thinks so as well; he included it in his book). I understand perfectly well what the code does, but somehow it still seems elusive every time I see it.

send(to, from, count)
	register short *to, *from;
	register count;
	{
		register n=(count+7)/8;
		switch(count%8){
		case 0:	do{	*to = *from++;
		case 7:		*to = *from++;
		case 6:		*to = *from++;
		case 5:		*to = *from++;
		case 4:		*to = *from++;
		case 3:		*to = *from++;
		case 2:		*to = *from++;
		case 1:		*to = *from++;
			}while(--n>0);
		}
	}

One of the best interview questions I have seen is a slightly obfuscated version of Duff's device with the variable names replaced and all comments unhelpfully removed. The questioner then asks a job applicant, What does this function do? Why? Familiarity with the literature is a great help here.

Magic, more magic

Template technology is advancing so quickly in C++ I sometimes wonder where it will all lead. The obvious answer is LISP:

for_each(a.begin(), a.end(), std::cout << _1 << ' ');

Naturally, one thinks of the Story about 'Magic'.

The joy of macros

C and C++ is two of my favorite languages, but the macro preprocessor can be unwieldy at times. Consider this:

#define STR_1(line)   #line
#define STR_2(line)   STR_1(line)
#define malloc(n)      \ 
    (debug_malloc(       \ 
         (n), __FILE__ ":" STR_2(__LINE__)))

What is this? It's the only way to convert the current line number into a string usable in program diagnostics: you have to use the double macro call to make it work. Nasty, isn't it? I'm glad Jon Jagger wrote about that so I wouldn't have to.

An STL-like array container for JNI

After some tinkering, I tried this for an STL-like container for JNI arrays. Tell me what you think:

// Emacs, this is -*- c++ -*- code.

#ifndef JVECTOR_H_
#define JVECTOR_H_

#include <jni.h>

#include <algorithm>
#include <vector>

#include <stdint.h>

template<typename T>
class jtype;

/**
 * Base class with specializations to hide type differences in the JNI
 * API.
 *
 * XXX - handle exceptions (e.g., NULL return from NewArray).
 *
 * XXX - should switch to Get<Type>ArrayRegion and use a scroll window
 * ala SQL result sets.
 */
template<>
struct jtype<jint>
{
  typedef int32_t value_type; // jint == int32_t
  typedef jintArray array_type;

  mutable JNIEnv* env;

  explicit jtype (JNIEnv* env) : env (env) { }
  jtype (const jtype& that) : env (that.env) { }
  jtype& operator= (const jtype& that)
  { jtype tmp (that); swap (tmp); return *this; }
  ~jtype ( ) { env = 0; }

  /*
   * jsize (JNICALL *GetArrayLength)
   *   (JNIEnv *env, jarray array);
   */
  jsize GetArrayLength (jarray jarr) const
  { return env->GetArrayLength (jarr); }

  /*
   * jintArray (JNICALL *NewIntArray)
   *   (JNIEnv *env, jsize len);
   */
  array_type NewArray (jsize len) const
  { return env->NewIntArray (len); }

  /*
   * jint * (JNICALL *GetIntArrayElements)
   *   (JNIEnv *env, jintArray array, jboolean *isCopy);
   */
  value_type* GetArrayElements (array_type jarr, bool& is_copy)
  {
    jboolean b = is_copy ? JNI_TRUE : JNI_FALSE;
    value_type* arr = env->GetIntArrayElements (jarr, &b);
    is_copy = b == JNI_TRUE ? true : false;
    return arr;
  }

  value_type* GetArrayElements (array_type jarr)
  { return env->GetIntArrayElements (jarr, 0); }

  /*
   * void (JNICALL *ReleaseIntArrayElements)
   *   (JNIEnv *env, jintArray array, jint *elems, jint mode);
   */
  void ReleaseArrayElements (array_type jarr, value_type* arr, jint mode)
  { env->ReleaseIntArrayElements (jarr, arr, mode); }

  void ReleaseArrayElements (array_type jarr, value_type* arr)
    // 0 --> copy back and free element buffer
  { env->ReleaseIntArrayElements (jarr, arr, 0); }

  /*
   * void (JNICALL *GetIntArrayRegion)
   *   (JNIEnv *env, jintArray array, jsize start, jsize len, jint buf);
   */
  void GetArrayRegion (array_type jarr, jsize start, jsize len,
		       value_type* arr)
  { env->GetIntArrayRegion (jarr, start, len, arr); }

  /*
   * void (JNICALL *SetIntArrayRegion)
   *   (JNIEnv *env, jintArray array, jsize start, jsize len, const jint *buf);
   */
  void SetArrayRegion (array_type jarr, jsize start, jsize len,
		       const value_type* arr)
    // Not const.  What gives?  XXX
  { env->SetIntArrayRegion (jarr, start, len, const_cast<value_type*> (arr)); }

  void swap (jtype& that) throw ( ) { std::swap (env, that.env); }
};

template<typename T>
void
std::swap (jtype<T>& lhs, jtype<T>& rhs)
{ lhs.swap (rhs); }

/**
 * jvector<T> is an STL-like wrapper for Java arrays.  Note that Java
 * arrays are immutable although the values can be changed.  Therefore
 * operations like clear, resize, max_size, etc., make no sense are
 * are not included.
 */
template<typename T>
class jvector
  : public jtype<T>
{
public:
  typedef typename jtype<T>::value_type value_type;
  typedef typename jtype<T>::array_type array_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;

  // Replace with checked versions.  XXX
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef jsize size_type;
  typedef std::ptrdiff_t difference_type;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::reverse_iterator<iterator> reverse_iterator;

private:
  array_type jarr;
  size_type len;
  pointer arr; // XXX counted_arr<T>
  bool changed;

public:
  jvector (JNIEnv* env, array_type jarr)
    : jtype<T> (env),
      jarr (jarr),
      len (GetArrayLength (jarr)),
      arr (GetArrayElements (jarr)),
      changed (false)
  { }

  jvector (const jvector& that)
    : jtype<T> (that),
      jarr (that.jarr),
      len (that.len),
      arr (that.arr),
      changed (that.changed)
  { }

  jvector operator= (const jvector& that)
  { jvector tmp (that); swap (tmp); return *this; }

  // Switching to a counted array for arr may remove the memory burden
  // on the JVM for the calls to {Get,Release}IntArrayElements past
  // the first one.  XXX
  ~jvector ( )
  { ReleaseArrayElements (jarr, arr, changed ? 0 : JNI_ABORT); }

  iterator begin ( )
  { changed = true; return arr; }
  const_iterator begin ( ) const
  { return arr; }
  iterator end ( )
  { changed = true; return arr + len; }
  const_iterator end ( ) const
  { return arr + len; }
  reverse_iterator rbegin ( )
  { changed = true; return reverse_iterator (end ( )); }
  const_reverse_iterator rbegin ( ) const
  { return const_reverse_iterator (end ( )); }
  reverse_iterator rend ( )
  { changed = true; return reverse_iterator (begin ( )); }
  const_reverse_iterator rend ( ) const
  { return const_reverse_iterator (begin ( )); }

  size_type size ( ) const
  { return size_type (end ( ) - begin ( )); }

  bool empty ( ) const
  { return begin ( ) == end ( ); }

  reference at (size_type n)
  { check_range (n); changed = true; return (*this)[n]; }
  const_reference at (size_type n) const
  { check_range (n); return (*this)[n]; }
  reference operator[](size_type n)
  { changed = true; return *(begin ( ) + n); }
  const_reference operator[](size_type n) const
  { return *(begin ( ) + n); }

  reference front ( )
  { changed = true; return *begin ( ); }
  const_reference front ( ) const
  { return *begin ( ); }

  reference back ( )
  { changed = true; return *(end ( ) - 1); }
  const_reference back ( ) const
  { return *(end ( ) - 1); }

  void swap (jvector& that)
  {
    std::swap (base, that.base);
    std::swap (jarr, that.jarr);
    std::swap (len, that.len);
    std::swap (arr, that.arr);
    std::swap (changed, that.changed);
  }

private:
  void check_range (size_type n) const
  { if (n > len) throw std::out_of_range ("jvector"); }
};

template<typename T>
void
std::swap (jvector<T>& lhs, jvector<T>& rhs)
{ lhs.swap (rhs); }

#endif // JVECTOR_H_

JNI and the STL

While looking through some JNI code I started thinking more about IntArray and friends. To write a non-mutating STL-like jvector<T> wrapper for the underlying JNI calls would not be much work. A quick Google search did not turn up the code I hoped to find. Perhaps I should look for a std::vector<T> adaptor implementation and host it onto the JNI calls such as GetArrayLength. The easy thing to do would be to specialize jvector<> on each native type in Java. For example, JNI jint would use GetIntArrayElements. Seem simple enough?

The old standby

I'm filling out a programming quiz and run into that old standby, reverse the words of a string in place in linear time. I've done this one at the whiteboard too many times so I did a quick Google search: lots of references to the problem but no reusable code^*. So, I write my own. To save some other person the trouble, I'm posting it here. Also, I'm hoping to get mail from someone pointing out how I could do it better. Good advice is a precious commodity.

* I am a big advocate of code reuse. I can't stand to see cut&paste coding and NIH (not invented here) syndrome drives me nuts.

#include <ctype.h>

/*
 * In C++ just use std::swap.  This macro uses the XOR hack to avoid
 * the stack and a temporary.
 */
#define SWAP(a,b) \ 
  do { (*a) ^= (*b); (*b) ^= (*a); (*a) ^= (*b); } while (0)

/* 
 * Although wordrev could be written using strtok(3), many
 * implementation of strtok run in quadratic time with respect to the
 * token string and strtok only expresses membership in the token
 * class rather than non-membership.  I contrast, most implementations
 * optimize isspace(3) very well usually using a table-driven macro
 * for contant time performance even avoiding the function call cost.
 *
 * If wordrev proves to be a hotspot, then unroll the loop:
 *
 *   switch (b - a) {
 *   case 0: case 1: break;
 *   case 2: SWAP(a[0], a[1]); break;
 *   case 3: SWAP(a[0], a[2]); break;
 *   case 4: SWAP(a[0], a[3]); SWAP(a[1], a[2]); break;
 *   case 5: SWAP(a[0], a[4]); SWAP(a[1], a[3]); break;
 *   default: // use the loop below
 *   }
 *
 * I prefer not to unroll it unless a profiler indicates that it
 * matters and that the unrolling makes a difference.
 */

int
wordrev (char* s, int len)
{
  char* m; /* word boundary marker */

  if (! s) return 0; /* protect against a null pointer */
  if (len < 0) return 0; /* nonsense argument */

  m = s;

  for (;;) {
    const char* X = s + len; /* end of search space */
    char* a, *b; /* pointers for reversing word */

    while (m < X && *m && isspace(*m))
      ++m; /* advance m to start of next word */

    a = m; /* word start */

    while (m < X && *m && ! isspace(*m))
      ++m; /* advance m to next word break */

    if (m == a)
      break; // EOS

    b = m - 1; /* word finish, skipping the space */

    for ( ; a < b; a++, --b)
      SWAP(a, b);
  }

  return m - s;
}

Blogging 1, Job boards 0

I just got an interesting phone call from a firm recruiting for software talent. How did the caller find me? This blog. I looked up the company, ThoughtWorks, and saw that it focuses on agile development which fits hand and glove with extreme programming practises. Good for them! The programming world need more companies like that.

Java 1.5 and generics

I've been experimenting with the new generics support in Java 1.5. One disappointment is a lack of mixins—you must still inherit from a single, fixed class; no generic superclasses. (For that you need to use Rice's NextGen.) But otherwise I'm having a great time. This will be an excellent feature when 1.5 is released.

Effective Java

Tim Bell, a Sun Java engineer, recommended to me Effective Java while discussing a feature report I made. He said:

And if I could put in a plug for Bloch's book, I will. I bought my copy out of my own pocket money. It is well worth it. It is full of lessons learned the hard way. Reading it will save you much of your own debugging time, and you will write better code.

That's how you praise a programming book!

My resume

Looking for a programmer in Austin or Houston? My overview says:

Senior programmer and Unix/Linux expert in all areas, including development, administration, configuration and kernel programming. Strong Windows development experience, and exposure to other operating systems. Knowledgeable in most networking areas with strong design background in systems, protocols, libraries and applications. Designed and implemented various client-server and N-tier architectures.

Successful record leading design and programming teams of various sizes, and bringing long-range projects to completion on-time and under-budget. Frequently found ways to save my company money by recommending existing solutions over in-house redevelopment. Designed and built reliable software where failure was not an option.

Seeking a principal-level programming, architecture, systems design or software management position in the software industry with a focus on Java, C/C++, SQL, Unix/Linux or other advanced systems and networking technologies. Thrive on variety, difficulty, tight deadlines and jobs no one else wants or can get done.

I also blog. :-)

First post

The new, non-toxic binkley's BLOG.