From f4bd723d929e53475f7990374dca7b7dfcbbdc42 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Sun, 1 Nov 2026 10:33:55 -0800
Subject: Add Chapter 29 for tech debt cleanup with the parser split

Keep Chapter 28b intact and carry the grammar-oriented parser package, Var move, IterPeeps move, and parser regression tests into Chapter 29. Defer privacy and exclude its experimental tests and fixture changes.

Register the chapter in the indexes, IntelliJ modules and run configurations, Maven reactor, roadmap, and linear-history publisher. Windows and Linux each pass 573 tests, release builds, 199 allocation replays, and 29 native checks.
---
 .../main/java/com/seaofnodes/simple/util/Ary.java  | 229 +++++++++++++++++++++
 .../java/com/seaofnodes/simple/util/AryInt.java    | 192 +++++++++++++++++
 .../main/java/com/seaofnodes/simple/util/BAOS.java | 162 +++++++++++++++
 .../com/seaofnodes/simple/util/IntHashMap.java     |  87 ++++++++
 .../main/java/com/seaofnodes/simple/util/SB.java   |  99 +++++++++
 .../java/com/seaofnodes/simple/util/Utils.java     |  53 +++++
 6 files changed, 822 insertions(+)
 create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/util/Ary.java
 create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/util/AryInt.java
 create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/util/BAOS.java
 create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/util/IntHashMap.java
 create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/util/SB.java
 create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/util/Utils.java

(limited to 'chapter29/src/main/java/com/seaofnodes/simple/util')

diff --git a/chapter29/src/main/java/com/seaofnodes/simple/util/Ary.java b/chapter29/src/main/java/com/seaofnodes/simple/util/Ary.java
new file mode 100644
index 00000000..d67801c2
--- /dev/null
+++ b/chapter29/src/main/java/com/seaofnodes/simple/util/Ary.java
@@ -0,0 +1,229 @@
+package com.seaofnodes.simple.util;
+
+import java.lang.StringBuilder;
+import java.lang.reflect.Array;
+import java.util.*;
+
+// ArrayList with saner syntax
+public class Ary<E> extends AbstractList<E> implements List<E> {
+    public E[] _es;
+    public int _len;
+
+    public Ary(E[] es) { this(es,es.length); }
+    public Ary(E[] es, int len) { if( es.length==0 ) es=Arrays.copyOf(es,1); _es=es; _len=len; }
+    @SuppressWarnings("unchecked")
+    public Ary(Class<E> clazz) { this((E[]) Array.newInstance(clazz, 1),0); }
+
+    /** @return list is empty */
+    public boolean isEmpty() { return _len==0; }
+    /** @return active list length */
+    public int len() { return _len; }
+    public int size() { return len(); }
+
+    /** @param i element index
+     *  @return element being returned; throws if OOB
+     *  @exception AIOOBE if !(0 <= i < _len)
+     */
+    public E get( int i ) { return at(i); }
+    public E at( int i ) {
+        range_check(i);
+        return _es[i];
+    }
+    public E atX( int i ) {
+        if( i >= _len ) return null;
+        return _es[i];
+    }
+
+    /** @return last element */
+    public E last( ) { return at(_len-1); }
+    public E last(int x ) { return at(_len-1+x); }
+
+    /** Add element in amortized constant time
+     *  @param e Element to add at end of list
+     **/
+    public E push( E e ) {
+        if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1));
+        return (_es[_len++] = e);
+    }
+    /** @return remove and return last element */
+    public E pop( ) {
+        return _len==0 ? null : _es[--_len];
+    }
+    @Override public E removeLast() { return pop(); }
+
+
+    /** Add element in amortized constant time
+     *  @param e Element to add at end of list
+     *  @return true */
+    public boolean add( E e ) {
+        if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1));
+        _es[_len++] = e;
+        return true;
+    }
+
+    /** Fast, constant-time, element removal.  Does not preserve order
+     *  @param i element to be removed
+     *  @return element removed */
+    public E del( int i ) {
+        range_check(i);
+        E tmp = _es[i];
+        _es[i]=_es[--_len];
+        return tmp;
+    }
+
+    /** Slow, linear-time, element removal.  Preserves order.
+     *  @param i element to be removed
+     *  @return element removed */
+    @Override public E remove( int i ) {
+        range_check(i);
+        E e = _es[i];
+        System.arraycopy(_es,i+1,_es,i,(--_len)-i);
+        return e;
+    }
+
+    /** Slow, linear-time, element insertion.  Preserves order.
+     *  @param i where to insert
+     *  @return element inserted */
+    public E insert( E e, int i ) {
+        setLen(_len+1);
+        System.arraycopy(_es,i,_es,i+1,_len-i);
+        _es[i] = e;
+        return e;
+    }
+
+
+    /** Remove all elements */
+    public void clear( ) { _len=0; }
+
+    /** Set existing element
+     *  @param i element to set
+     *  @param e value to set
+     *  @return old value
+     *  @exception AIOOBE if !(0 <= i < _len)
+     */
+    public E set( int i, E e ) {
+        range_check(i);
+        E old = _es[i];
+        _es[i] = e;
+        return old;
+    }
+
+    /** Set existing element
+     *  @param i element to set
+     *  @param e value to set
+     *  @return old value
+     *  @exception AIOOBE if !(0 <= i < _len)
+     */
+    public E setX( int i, E e ) {
+        if( i >= _len ) {
+            while( i >= _es.length ) _es = Arrays.copyOf( _es, _es.length << 1 );
+            _len = i+1;
+        }
+        E old = _es[i];
+        _es[i] = e;
+        return old;
+    }
+
+    public Ary<E> setLen( int len ) {
+        if( len > _len )
+            while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+        _len = len;
+        while( _es.length > (len<<1) ) // Shrink if hugely too large
+            _es = Arrays.copyOf(_es,_es.length>>1);
+        Arrays.fill(_es,len,_es.length,null);
+        return this;
+    }
+
+    public E swap( int i, int j ) {
+        range_check(i);
+        range_check(j);
+        E tmp = _es[i];
+        if( i==j ) return tmp;
+        _es[i] = _es[j];
+        _es[j] = tmp;
+        return tmp;
+    }
+
+
+    /** @param c Collection to be added */
+    public boolean addAll( Collection<? extends E> c ) {
+        if( c==null ) return false;
+        for( E e : c ) add(e);
+        return true;
+    }
+    public Ary<E> addAll( Iterable<? extends E> it ) { for( E e : it ) add(e); return this; }
+
+    /** @param es Array to be added */
+    public <F extends E> Ary<E> addAll( F[] es ) {
+        if( es==null || es.length==0 ) return this;
+        while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+        System.arraycopy(es,0,_es,_len,es.length);
+        _len += es.length;
+        return this;
+    }
+
+    /** @param c Collection to be added */
+    public Ary<E> addAll( Ary<? extends E> c ) {
+        if( c==null || c._len==0 ) return this;
+        while( _len+c._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+        System.arraycopy(c._es,0,_es,_len,c._len);
+        _len += c._len;
+        return this;
+    }
+
+    /** @return compact array version */
+    public E[] asAry() { return Arrays.copyOf(_es,_len); }
+
+    /** Find the first matching element using ==, or -1 if none.  Note that
+     *  most del calls shuffle the list, so the first element might be random.
+     *  @param e Element to find
+     *  @return index of first matching element, or -1 if none */
+    public int find( E e ) {
+        for( int i=0; i<_len; i++ )  if( _es[i]==e )  return i;
+        return -1;
+    }
+
+
+    /** @return an iterator */
+    @Override public Iterator<E> iterator() { return new Iter(); }
+    private class Iter implements Iterator<E> {
+        int _i=0;
+        @Override public boolean hasNext() { return _i<_len; }
+        @Override public E next() { return _es[_i++]; }
+    }
+
+    @Override public String toString() {
+        StringBuilder sb = new StringBuilder().append('{');
+        for( int i=0; i<_len; i++ ) {
+            if( i>0 ) sb.append(',');
+            if( _es[i] != null ) sb.append(_es[i].toString());
+        }
+        return sb.append('}').toString();
+    }
+
+    private void range_check( int i ) {
+        if( i < 0 || i>=_len )
+            throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len);
+    }
+
+    // Note that the hashCode() and equals() are not invariant to changes in the
+    // underlying array.  If the hashCode() is used (e.g., inserting into a
+    // HashMap) and the then the array changes, the hashCode() will change also.
+    @Override public boolean equals( Object o ) {
+        if( this==o ) return true;
+        if( !(o instanceof Ary ary) ) return false;
+        if( _len != ary._len ) return false;
+        if( _es == ary._es ) return true;
+        for( int i=0; i<_len; i++ )
+            if( !(_es[i]==null ? (ary._es[i] == null) : _es[i].equals(ary._es[i])) )
+                return false;
+        return true;
+    }
+    @Override public int hashCode( ) {
+        int sum=_len;
+        for( int i=0; i<_len; i++ )
+            sum += _es[i]==null ? 0 : _es[i].hashCode();
+        return sum;
+    }
+
+}
diff --git a/chapter29/src/main/java/com/seaofnodes/simple/util/AryInt.java b/chapter29/src/main/java/com/seaofnodes/simple/util/AryInt.java
new file mode 100644
index 00000000..b498fd78
--- /dev/null
+++ b/chapter29/src/main/java/com/seaofnodes/simple/util/AryInt.java
@@ -0,0 +1,192 @@
+package com.seaofnodes.simple.util;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.function.IntUnaryOperator;
+
+// ArrayList with saner syntax
+public class AryInt {
+  public int[] _es;
+  public int _len;
+  public AryInt(int[] es) { this(es,es.length); }
+  public AryInt(int[] es, int len) { _es=es; _len=len; }
+  public AryInt() { this(new int[1],0); }
+
+  /** @return list is empty */
+  public boolean isEmpty() { return _len==0; }
+  /** @return active list length */
+  public int len() { return _len; }
+  /** @param i element index
+   *  @return element being returned; throws if OOB */
+  public int at( int i ) {
+    range_check(i);
+    return _es[i];
+  }
+  /** @param i element index
+   *  @return element being returned, or 0 if OOB */
+  public int atX( int i ) {
+    return i < _len ? _es[i] : 0;
+  }
+  /** @return last element */
+  public int last( ) { return at(_len-1); }
+  public int last(int x ) { return at(_len-1+x); }
+
+  /** @return remove and return last element */
+  public int pop( ) {
+    range_check(0);
+    return _es[--_len];
+  }
+
+  /** Add element in amortized constant time
+   *  @param e element to add at end of list
+   *  @return 'this' for flow-coding */
+  public AryInt push( int e ) {
+    if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1));
+    _es[_len++] = e;
+    return this;
+  }
+
+  /** Slow, linear-time, element insert.  Preserves order.
+   *  @param i index to insert at, between 0 and _len inclusive.
+   *  @param e intlement to insert
+   */
+  public void insert( int i, int e ) {
+    if( i < 0 || i>_len )
+      throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len);
+    if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1));
+    System.arraycopy(_es,i,_es,i+1,(_len++)-i);
+    _es[i] = e;
+  }
+
+  /** Fast, constant-time, element removal.  Does not preserve order
+   *  @param i element to be removed
+   *  @return element removed */
+  public int del( int i ) {
+    range_check(i);
+    int tmp = _es[i];
+    _es[i]=_es[--_len];
+    return tmp;
+  }
+
+  /** Slow, linear-time, element removal.  Preserves order.
+   *  @param i element to be removed
+   *  @return element removed */
+  public int remove( int i ) {
+    range_check(i);
+    int e = _es[i];
+    System.arraycopy(_es,i+1,_es,i,(--_len)-i);
+    return e;
+  }
+
+  /** Remove all elements */
+  public void clear( ) { Arrays.fill(_es,0,_len,0); _len=0; }
+
+  // Extend and set
+  public int setX( int i, int e ) {
+    while( i>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+    if( i >= _len ) _len = i+1;
+    return (_es[i] = e);
+  }
+
+  public int set( int i, int e ) {
+    range_check(i);
+    return (_es[i] = e);
+  }
+
+  public AryInt set_as( int e ) { _es[0] = e; _len=1; return this; }
+  public AryInt set_len( int len ) {
+    if( len > _len )
+      while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+    _len = len;
+    while( _es.length > (len<<1) ) // Shrink if hugely too large
+      _es = Arrays.copyOf(_es,_es.length>>1);
+    return this;
+  }
+
+  /** @param c Collection to be added */
+  public AryInt addAll( Collection<? extends Integer> c ) { for( int e : c ) push(e); return this; }
+
+  /** @param es Array to be added */
+  public AryInt addAll( int[] es ) {
+    if( es.length==0 ) return this;
+    while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+    System.arraycopy(es,0,_es,_len,es.length);
+    _len += es.length;
+    return this;
+  }
+
+  /** @param es Array to be added */
+  public AryInt addAll( AryInt ary ) {
+    if( ary._len==0 ) return this;
+    while( _len+ary._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1);
+    System.arraycopy(ary._es,0,_es,_len,ary._len);
+    _len += ary._len;
+    return this;
+  }
+
+  public AryInt map_update( IntUnaryOperator f ) { for( int i = 0; i<_len; i++ ) _es[i] = f.applyAsInt(_es[i]); return this; }
+
+  /** @return compact array version, using the internal base array where possible. */
+  public int[] asAry() { return _len==_es.length ? _es : Arrays.copyOf(_es,_len); }
+
+  /** Sorts in-place */
+  public void sort_update() { Arrays.sort(_es, 0, _len);  }
+  /** Find the first matching element using ==, or -1 if none.  Note that
+   *  most del calls shuffle the list, so the first element might be random.
+   *  @param e intlement to find
+   *  @return index of first matching element, or -1 if none */
+  public int find( int e ) {
+    for( int i=0; i<_len; i++ )  if( _es[i]==e )  return i;
+    return -1;
+  }
+
+  @Override public String toString() {
+    SB sb = new SB().p('[');
+    for( int i=0; i<_len; i++ )
+      sb.p(_es[i]).p(',');
+    return sb.unchar().p(']').toString();
+  }
+
+  private void range_check( int i ) {
+    if( i < 0 || i>=_len )
+      throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len);
+  }
+
+  // Binary search sorted _es.  Returns insertion point.
+  // Undefined results if _es is not sorted.
+  public int binary_search( int e ) {
+    int lo=0, hi=_len-1;
+    while( lo <= hi ) {
+      int mid = (hi + lo) >>> 1; // midpoint, rounded down
+      int mval = _es[mid];
+      if( e==mval ) {
+        // If dups, get to the first.
+        while( mid>0 && e==_es[mid-1] ) mid--;
+        return mid;
+      }
+      if( e >mval ) lo = mid+1;
+      else          hi = mid-1;
+    }
+    return lo;
+  }
+
+  // Note that the hashCode() and equals() are not invariant to changes in the
+  // underlying array.  If the hashCode() is used (e.g., inserting into a
+  // HashMap) and the then the array changes, the hashCode() will change also.
+  @Override public boolean equals( Object o ) {
+    if( this==o ) return true;
+    if( !(o instanceof AryInt ary) ) return false;
+    if( _len != ary._len ) return false;
+    if( _es == ary._es ) return true;
+    for( int i=0; i<_len; i++ )
+      if( _es[i] != ary._es[i] )
+        return false;
+    return true;
+  }
+  @Override public int hashCode( ) {
+    int sum=_len;
+    for( int i=0; i<_len; i++ )
+      sum += _es[i];
+    return sum;
+  }
+}
diff --git a/chapter29/src/main/java/com/seaofnodes/simple/util/BAOS.java b/chapter29/src/main/java/com/seaofnodes/simple/util/BAOS.java
new file mode 100644
index 00000000..61ce7387
--- /dev/null
+++ b/chapter29/src/main/java/com/seaofnodes/simple/util/BAOS.java
@@ -0,0 +1,162 @@
+package com.seaofnodes.simple.util;
+
+import java.util.HashMap;
+import java.util.Arrays;
+
+// "ByteArrayOutputStream", and Input Stream and not synchronized and has
+// matching pack/unpack strategies.
+public class BAOS {
+
+    private byte[] _buf;
+    private int _len;
+
+    public BAOS() { _buf = new byte[1]; }
+    public BAOS(byte[] buf) { _buf = buf; }
+    public BAOS(byte[] buf, int x) { _buf = buf; _len = x; }
+
+    public byte[] toByteArray() {
+        return Arrays.copyOf(_buf,_len);
+    }
+
+    public byte[] buf() { return _buf; }
+    public int size() { return _len; }
+    public void set( byte[] buf, int len ) { _buf=buf; _len=len; }
+    public void clear() { _len=0; }
+
+    // -----------------------------------------------------------------------
+    // Basic read, write (expand)
+
+    private void grow(int len) {
+        while( _len+len >= _buf.length )
+            _buf = Arrays.copyOf(_buf,_buf.length*2);
+    }
+
+    // Write a byte, grow as needed; silent chop
+    public BAOS write(int b) {
+        grow(1);
+        _buf[_len++] = (byte)b; // Silent chop
+        return this;
+    }
+
+    // Read an UNSIGNED bytes at INDEX, AIOOBE if off end
+    public int read1(int idx) { return _buf[idx] & 0xFF; }
+
+    // Read an UNSIGNED byte, AIOOBE if off end
+    public int read() { return read1(_len++); }
+
+    // write 2 bytes
+    public BAOS write2( int x ) {
+        grow(2);
+        _buf[_len++] = (byte)(x>> 0);
+        _buf[_len++] = (byte)(x>> 8);
+        return this;
+    }
+
+    // Read a u16 in 2 bytes
+    public int read2(int idx) { return read1(idx) | (read1(idx+1)<<8);  }
+    public int read2() { int rez = read2(_len); _len+=2; return rez; }
+
+    // write 4 bytes
+    public BAOS write4( int x ) {
+        grow(4);
+        _buf[_len++] = (byte)(x>> 0);
+        _buf[_len++] = (byte)(x>> 8);
+        _buf[_len++] = (byte)(x>>16);
+        _buf[_len++] = (byte)(x>>24);
+        return this;
+    }
+
+    // Read a i32 in 4 bytes
+    public int read4(int idx) { return read2(idx) | (read2(idx+2)<<16);  }
+    public int read4() { int rez = read4(_len); _len+=4; return rez; }
+
+    // write 8 bytes
+    public BAOS write8( long x ) {
+        write4((int) x     );
+        write4((int)(x>>32));
+        return this;
+    }
+
+    // Read a i64 in 8 bytes
+    public long read8(int idx) { return ((long)read4(idx) & 0xFFFFFFFFL) | ((long)read4(idx+4)<<32); }
+    public long read8() { long rez = read8(_len); _len+=8; return rez; }
+
+    // Write byte array
+    public void write( byte[] bs ) {
+        grow(bs.length);
+        System.arraycopy(bs,0,_buf,_len,bs.length);
+        _len += bs.length;
+    }
+
+    // Read/fill byte array
+    public byte[] read( byte[] bs ) {
+        System.arraycopy(_buf,_len,bs,0,bs.length);
+        _len += bs.length;
+        return bs;
+    }
+
+    // -----------------------------------------------------------------------
+    // Write a packed integer to the BAOS.  Track a histogram to make more
+    // intelligent choices in the future.
+    private static final HashMap<Long,Integer> PACKED_HISTOGRAM = new HashMap<>();
+    private BAOS histo(long x) {
+        Integer cnt = PACKED_HISTOGRAM.get(x);
+        PACKED_HISTOGRAM.put(x,cnt==null ? 1 : cnt+1);
+        return this;
+    }
+
+    // Write a u8 (checked)
+    public void packed1(int x) {
+        assert 0 <= x && x <= 255;
+        histo(x).write(x);
+    }
+
+    public int packed1() { return read(); }
+
+    // Write a u16 (checked)
+    public void packed2(int x) {
+        assert 0 <= x && x <= 65535;
+        (( x <= 254 ) ? write(x) : write(0xFF).write2(x)).histo(x);
+    }
+
+    // Read a packed u16
+    public int packed2() {
+        int x = read();
+        return x==0xFF ? read2() : x;
+    }
+
+    // Write a packed i32
+    public void packed4(int x) {
+        ((-127 <= x && x <= 127 ) ? write(x) : write(-128).write4(x)).histo(x);
+    }
+
+    // Read a packed i32
+    public int packed4() {
+        int x = _buf[_len++];   // Signed byte read
+        return x== -128 ? read4() : x;
+    }
+
+    // Write a packed i64
+    public void packed8(long x) {
+        ((-127 <= x && x <= 127 ) ? write((int)x) : write(-128).write8(x)).histo(x);
+    }
+
+    // Read a packed i64
+    public long packed8() {
+        int x = _buf[_len++];   // Signed byte read
+        return x== -128 ? read8() : x;
+    }
+
+    public void packedS(String s) {
+        packed4(s.length());
+        for( int i=0; i<s.length(); i++ )
+            packed4(s.charAt(i));
+    }
+
+    public String packedS() {
+        int len = packed4();
+        String s = new String(_buf,_len,len).intern();
+        _len += len;
+        return s;
+    }
+}
diff --git a/chapter29/src/main/java/com/seaofnodes/simple/util/IntHashMap.java b/chapter29/src/main/java/com/seaofnodes/simple/util/IntHashMap.java
new file mode 100644
index 00000000..b356ec31
--- /dev/null
+++ b/chapter29/src/main/java/com/seaofnodes/simple/util/IntHashMap.java
@@ -0,0 +1,87 @@
+package com.seaofnodes.simple.util;
+
+import java.util.Arrays;
+
+// Int-Int Hash Map
+public class IntHashMap {
+    private int[] _es;
+    private int _size;
+    private final int _sentinel;
+
+    // Pick a sentinel value; not allowed for keys or values.  Sentinel is
+    // returned on a miss.  Writing sentinel counts as a remove.
+    public IntHashMap(int sentinel) {
+        _sentinel = sentinel;
+        _es = new int[4];
+        Arrays.fill(_es,sentinel);
+    }
+
+    public int size() { return _size; }
+    public boolean isEmpty() { return _size==0; }
+    public void clear() {
+        _size = 0;
+        Arrays.fill(_es,_sentinel);
+    }
+
+    private int cap() { return _es.length>>1; }
+
+    public int put( int key, int val ) {
+        int slot = probe(key);
+        int old = _es[(slot<<1)+1];
+        if( old == _sentinel && val != _sentinel ) _size++;
+        if( old != _sentinel && val == _sentinel ) _size--;
+        // Check cap, resize at 3/4 full
+        if( _size > ((cap()>>1) + (cap()>>2)) ) {
+            grow();
+            slot = probe(key);
+        }
+
+        _es[ slot<<1   ] = key;
+        _es[(slot<<1)+1] = val;
+        return old;
+    }
+
+    public int get( int key ) {
+        int slot = probe(key);
+        return _es[(slot<<1)+1];
+    }
+
+    private int probe( int key ) {
+        int mask = cap()-1;
+        int slot = key & mask;
+        while( _es[slot<<1] != _sentinel && _es[slot<<1] != key )
+            slot = (slot + (key|1)) & mask;
+        return slot;
+    }
+
+    // Double underlying array size
+    private void grow() {
+        int[] old = _es;
+        _es = new int[_es.length<<1];
+        Arrays.fill(_es,_sentinel);
+        for( int i=0; i<old.length; i+=2 )
+            if( old[i] != _sentinel ) {
+                int slot = probe(old[i]);
+                _es[ slot<<1   ] = old[i  ];
+                _es[(slot<<1)+1] = old[i+1];
+            }
+    }
+
+    // Just all the keys
+    public int[] keySet() {
+        int[] keys = new int[_size];
+        int j=0;
+        for( int i=0; i<_es.length; i+=2 )
+            if( _es[i] != _sentinel )
+                keys[j++] = _es[i];
+        return keys;
+    }
+
+    @Override public String toString() {
+        SB sb = new SB().p("[ ");
+        for( int i=0; i<_es.length; i+=2 )
+            if( _es[i] != _sentinel )
+                sb.p('(').p(_es[i]).p(',').p(_es[i+1]).p(')').p(',');
+        return sb.unchar().p(']').toString();
+    }
+}
diff --git a/chapter29/src/main/java/com/seaofnodes/simple/util/SB.java b/chapter29/src/main/java/com/seaofnodes/simple/util/SB.java
new file mode 100644
index 00000000..cc59f2a6
--- /dev/null
+++ b/chapter29/src/main/java/com/seaofnodes/simple/util/SB.java
@@ -0,0 +1,99 @@
+package com.seaofnodes.simple.util;
+
+/** Tight/tiny StringBuilder wrapper.
+ *  Short short names on purpose; so they don't obscure the printing.
+ *  Can't believe this wasn't done long, long ago. */
+public final class SB {
+  private final StringBuilder _sb;
+  private int _indent = 0;
+  public SB(        ) { _sb = new StringBuilder( ); }
+  public SB(String s) { _sb = new StringBuilder(s); }
+  public SB p( String s ) { _sb.append(s); return this; }
+  public SB p( float  s ) {
+    if( Float.isNaN(s) )
+      _sb.append( "Float.NaN");
+    else if( Float.isInfinite(s) ) {
+      _sb.append(s > 0 ? "Float.POSITIVE_INFINITY" : "Float.NEGATIVE_INFINITY");
+    } else _sb.append(s);
+    return this;
+  }
+  public SB p( double s ) {
+    if( Double.isNaN(s) )
+      _sb.append("Double.NaN");
+    else if( Double.isInfinite(s) ) {
+      _sb.append(s > 0 ? "Double.POSITIVE_INFINITY" : "Double.NEGATIVE_INFINITY");
+    } else _sb.append(s);
+    return this;
+  }
+  public SB p( char   s ) { _sb.append(s); return this; }
+  public SB p( int    s ) { _sb.append(s); return this; }
+  public SB p( long   s ) { _sb.append(s); return this; }
+  public SB p( boolean s) { _sb.append(s); return this; }
+  // 1 byte, 2 hex digits, 8 bits
+  public SB hex1(int s) {
+    int digit = (s>>4) & 0xf;
+    _sb.append((char)((digit <= 9 ? '0' : ('A'-10))+digit));
+    digit = s & 0xf;
+    _sb.append((char)((digit <= 9 ? '0' : ('A'-10))+digit));
+    return this;
+  }
+  // 2 bytes, 4 hex digits, 16 bits, Big Endian
+  public SB hex2(int s) { return hex1(s>> 8).hex1(s); }
+  // 4 bytes, 8 hex digits, 32 bits, Big Endian
+  public SB hex4(int s) { return hex2(s>>16).hex2(s); }
+  // 8 bytes, 16 hex digits, 64 bits, Big Endian
+  public SB hex8(long s) { return hex4((int)(s>>32)).hex4((int)s); }
+
+  // Fixed width field
+  public SB fix( int sz, String s ) {
+    for( int i=0; i<sz; i++ )
+      _sb.append( i < s.length() ? s.charAt(i) : ' ');
+    return this;
+  }
+  public char at(int idx ) { return _sb.charAt(idx); }
+
+  // Not spelled "p" on purpose: too easy to accidentally say "p(1.0)" and
+  // suddenly call the autoboxed version.
+  public SB pobj( Object s ) { _sb.append(s.toString()); return this; }
+  public SB i( int d ) { for( int i=0; i<d+_indent; i++ ) p("  "); return this; }
+  public SB i( ) { return i(0); }
+  public SB ip(String s) { return i().p(s); }
+  public SB s() { _sb.append(' '); return this; }
+
+  // Increase indentation
+  public SB ii( int i) { _indent += i; return this; }
+  public SB ii() { return ii(1); }
+  // Decrease indentation
+  public SB di( int i) { _indent -= i; return this; }
+  public SB di() { return di(1); }
+
+  public SB nl( ) { return p(System.lineSeparator()); }
+  // Last printed a nl
+  public boolean was_nl() {
+    int len = _sb.length();
+    String nl = System.lineSeparator();
+    int nlen = nl.length();
+    if( len < nlen ) return false;
+    for( int i=0; i<nlen; i++ )
+      if( _sb.charAt(len-nlen+i)!=nl.charAt(i) )
+        return false;
+    return true;
+  }
+
+  // Delete last char.  Useful when doing string-joins and JSON printing and an
+  // extra separater char needs to be removed:
+  //
+  //   sb.p('[');
+  //   for( Foo foo : foos )
+  //     sb.p(foo).p(',');
+  //   sb.unchar().p(']');  // remove extra trailing comma
+  //
+  public SB unchar() { return unchar(1); }
+  public SB unchar(int x) { _sb.setLength(_sb.length()-x); return this; }
+  public SB setLen(int len) { _sb.setLength(len); return this; }
+  public String subString(int start, int end ) { return _sb.substring(start,end); }
+
+  public SB clear() { _sb.setLength(0); return this; }
+  public int len() { return _sb.length(); }
+  @Override public String toString() { return _sb.toString(); }
+}
diff --git a/chapter29/src/main/java/com/seaofnodes/simple/util/Utils.java b/chapter29/src/main/java/com/seaofnodes/simple/util/Utils.java
new file mode 100644
index 00000000..577a60af
--- /dev/null
+++ b/chapter29/src/main/java/com/seaofnodes/simple/util/Utils.java
@@ -0,0 +1,53 @@
+package com.seaofnodes.simple.util;
+
+import java.util.ArrayList;
+
+public class Utils {
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+
+    /**
+     *  Fast, constant-time, element removal.  Does not preserve order
+     *
+     *  @param array ArrayList to modify
+     *  @param i element to be removed
+     *  @return element removed
+     */
+    public static <E> void del(ArrayList<E> array, int i) {
+        E last = array.removeLast();
+        if (i < array.size()) array.set(i, last);
+    }
+
+    /**
+     * Search a list for an element by reference
+     *
+     * @param ary List to search in
+     * @param x Object to be searched
+     * @return >= 0 on success, -1 on failure
+     */
+    public static <E> int find( ArrayList<E> ary, E x ) {
+        for( int i=0; i<ary.size(); i++ )
+            if( ary.get(i)==x )
+                return i;
+        return -1;
+    }
+    /**
+     * Search a list for an element by reference
+     *
+     * @param ary List to search in
+     * @param x Object to be searched
+     * @return >= 0 on success, -1 on failure
+     */
+    public static <E> int find( E[] ary, E x ) {
+        for( int i=0; i<ary.length; i++ )
+            if( ary[i]==x )
+                return i;
+        return -1;
+    }
+
+    // Rotate a long, nice for hashes
+    public static long rot( long x, int n ) { return (x<<n) | (x>>>n); }
+
+    // Fold a 64bit hash into 32 bits
+    public static int fold( long x ) { return (int)((x>>32) ^ x); }
+}
-- 
cgit v1.2.3