diff options
Diffstat (limited to 'chapter29/src/main/java/com/seaofnodes/simple/util')
6 files changed, 822 insertions, 0 deletions
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); } +} |