From 9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Fri, 25 Aug 2023 23:16:07 +0100 Subject: Reorganized the project as multi-maven module Updated README Added language module with grammar Split the code into common and chapter01 modules. Removed a number of utility classes that were imported from AA. Added github workflow file. --- src/main/java/com/seaofnodes/util/Ary.java | 367 --------------------- src/main/java/com/seaofnodes/util/AryInt.java | 203 ------------ .../java/com/seaofnodes/util/BitSetSparse.java | 41 --- src/main/java/com/seaofnodes/util/IBitSet.java | 164 --------- src/main/java/com/seaofnodes/util/IHashMap.java | 34 -- src/main/java/com/seaofnodes/util/SB.java | 80 ----- src/main/java/com/seaofnodes/util/Util.java | 151 --------- src/main/java/com/seaofnodes/util/UtilUnsafe.java | 55 --- src/main/java/com/seaofnodes/util/VBitSet.java | 27 -- src/main/java/com/seaofnodes/util/Work.java | 79 ----- 10 files changed, 1201 deletions(-) delete mode 100644 src/main/java/com/seaofnodes/util/Ary.java delete mode 100644 src/main/java/com/seaofnodes/util/AryInt.java delete mode 100644 src/main/java/com/seaofnodes/util/BitSetSparse.java delete mode 100644 src/main/java/com/seaofnodes/util/IBitSet.java delete mode 100644 src/main/java/com/seaofnodes/util/IHashMap.java delete mode 100644 src/main/java/com/seaofnodes/util/SB.java delete mode 100644 src/main/java/com/seaofnodes/util/Util.java delete mode 100644 src/main/java/com/seaofnodes/util/UtilUnsafe.java delete mode 100644 src/main/java/com/seaofnodes/util/VBitSet.java delete mode 100644 src/main/java/com/seaofnodes/util/Work.java (limited to 'src/main/java/com/seaofnodes/util') diff --git a/src/main/java/com/seaofnodes/util/Ary.java b/src/main/java/com/seaofnodes/util/Ary.java deleted file mode 100644 index 36654a7f..00000000 --- a/src/main/java/com/seaofnodes/util/Ary.java +++ /dev/null @@ -1,367 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.lang.reflect.Array; -import java.util.*; -import java.util.function.Function; -import java.util.function.Predicate; - -// ArrayList with saner syntax -public class Ary implements Iterable { - 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 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; } - /** @param i element index - * @return element being returned; throws if OOB - * @exception ArrayIndexOutOfBoundsException if !(0 <= i < _len) - */ - public E at( int i ) { - range_check(i); - return _es[i]; - } - /** @param i element index - * @return element being returned, or null if OOB */ - public E atX( int i ) { - return i < _len ? _es[i] : null; - } - /** @return last element */ - public E last( ) { - range_check(0); - return _es[_len-1]; - } - public void last(int i) { - range_check(i); - E tmp = _es[i]; - _es[i] = _es[_len-1]; - _es[_len-1] = tmp; - } - - /** @return remove and return last element */ - public E 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 Ary add( E e ) { - if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); - _es[_len++] = e; - return this; - } - - /** 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); - } - - /** Slow, linear-time, element insert. Preserves order. - * @param i index to insert at, between 0 and _len inclusive. - * @param e Element to insert - */ - public void insert( int i, E 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 E del( int i ) { - range_check(i); - E tmp = _es[i]; - _es[i]=_es[--_len]; - return tmp; - } - - /** Element removal, using '=='. Does not preserve order. - * @param e element to be removed - * @return element removed */ - public E del( E e ) { - for( int i=0; i<_len; i++ ) { - E tmp = _es[i]; - if( tmp==e ) { - _es[i]=_es[--_len]; - return tmp; - } - } - return null; - } - - /** Slow, linear-time, element removal. Preserves order. - * @param i element to be removed - * @return element removed */ - public E remove( int i ) { - range_check(i); - E e = _es[i]; - System.arraycopy(_es,i+1,_es,i,(--_len)-i); - return e; - } - - /** Remove all elements */ - public void clear( ) { _len=0; } - - public void fill( E e ) { Arrays.fill(_es,0,_len,e); } - - /** Extend and set. null fills as needed and does not throw AIOOBE. - * @param i element to set - * @param e value to set - * @return old value - */ - public E setX( int i, E e ) { - if( i >= _len ) Arrays.fill(_es,_len,_es.length,null); - while( i>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); - if( i >= _len ) _len = i+1; - return (_es[i] = e); - } - - /** Clear element. Does nothing if element is OOB, since these are clear by - * default. - * @param i element to clear - */ - public void clear( int i ) { if( i<_len ) _es[i]=null; } - - /** 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; - } - - // Increment length, revealing the E behind the _len, or null - public E inc_len( ) { - if( _len >= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); - return _es[_len++]; - } - public Ary 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); - Arrays.fill(_es,len,_es.length,null); - return this; - } - - /** @param c Collection to be added */ - public Ary addAll( Collection c ) { if( c!=null ) for( E e : c ) add(e); return this; } - - /** @param es Array to be added */ - public Ary 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 addAll( Ary 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); } - - /** @param f function to apply to each element. Updates in-place. */ - public Ary map_update( Function f ) { for( int i = 0; i<_len; i++ ) _es[i] = f.apply(_es[i]); return this; } - /** @param P filter out elements failing to pass the predicate; updates in - * place and shuffles list. - * @return this, for flow-coding */ - public Ary filter_update( Predicate P ) { - for( int i=0; i<_len; i++ ) - if( !P.test(_es[i]) ) - del(i--); - return this; - } - /** Sorts in-place - * @param c Comparator to sort by */ - public void sort_update(Comparator c ) { Arrays.sort(_es, 0, _len, c); } - /** 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; - } - /** Find the first element matching predicate P, or -1 if none. Note that - * most del calls shuffle the list, so the first element might be random. - * @param P Predicate to match - * @return index of first matching element, or -1 if none */ - public int find( Predicate P ) { - for( int i=0; i<_len; i++ ) if( P.test(_es[i]) ) return i; - return -1; - } - /** Find and replace the first matching element using ==. - * @param old Element to find - * @param nnn Element replacing old - * @return true if replacement happened */ - public boolean replace( E old, E nnn ) { - for( int i=0; i<_len; i++ ) if( _es[i]==old ) { _es[i]=nnn; return true; } - return false; - } - - - /** Merge-Or. Merge 2 sorted Arys, tossing out duplicates. Return a new - * sorted Ary with the merged list. Undefined if the original arrays are - * not sorted. Error if they are not of the same type. Elements must - * implement Comparable. - * @param a0 Sorted Ary to merge - * @param a1 Sorted Ary to merge - * @return A new sorted merged Ary - */ - public static > Ary merge_or( Ary a0, Ary a1 ) { - int i=0, j=0; - Ary res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); - - while( i0 ) { res.add(y); j++; } - else { res.add(x); i++; j++; } - } - while( i Ary merge_or( Ary a0, Ary a1, Comparator cmpr, Predicate filter) { - int i=0, j=0; - Ary res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); - - while( i0 ) { res.add(y); j++; } - else { res.add(x); i++; j++; } - } - while( i> Ary merge_and( Ary a0, Ary a1 ) { - int i=0, j=0; - Ary res = new Ary<>(Arrays.copyOf(a0._es,Math.min(a0._len,a1._len)),0); - while( i0 ) { j++; } - else { res.add(x); i++; j++; } - } - return res; - } - - /** @return an iterator */ - @Override public Iterator iterator() { return new Iter(); } - private class Iter implements Iterator { - int _i=0; - @Override public boolean hasNext() { return _i<_len; } - @Override public E next() { return _es[_i++]; } - } - - @Override public String toString() { - SB sb = new SB().p('{'); - for( int i=0; i<_len; i++ ) { - if( i>0 ) sb.p(','); - if( _es[i] != null ) sb.p(_es[i].toString()); - } - return sb.p('}').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; - } - - public Ary deepCopy() { - return new Ary<>(_es.clone(),_len); - } -} diff --git a/src/main/java/com/seaofnodes/util/AryInt.java b/src/main/java/com/seaofnodes/util/AryInt.java deleted file mode 100644 index 000f4809..00000000 --- a/src/main/java/com/seaofnodes/util/AryInt.java +++ /dev/null @@ -1,203 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.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( ) { - range_check(0); - return _es[_len-1]; - } - - /** @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 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; - } - - 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) ) return false; - AryInt ary = (AryInt)o; - 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/src/main/java/com/seaofnodes/util/BitSetSparse.java b/src/main/java/com/seaofnodes/util/BitSetSparse.java deleted file mode 100644 index 09d2f039..00000000 --- a/src/main/java/com/seaofnodes/util/BitSetSparse.java +++ /dev/null @@ -1,41 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import org.jctools.maps.NonBlockingHashMapLong; - -// Simple sparse bitset, with a test-and-set. -public class BitSetSparse { - NonBlockingHashMapLong _set = new NonBlockingHashMapLong<>(); - public boolean tset(int b0, int b1) { return tset(((long)b0<<32)|b1); } - public boolean clr (int b0, int b1) { return clr (((long)b0<<32)|b1); } - public boolean tset(long b) { return _set.put(b,"")!=null; } - public boolean clr (long b) { return _set.remove(b)!=null; } - public boolean test(long b) { return _set.get(b)!=null; } - public BitSetSparse clear() { _set.clear(true); return this; } - public int size() { return _set.size(); } - public int cardinality() { return _set.size(); } - @Override public String toString() { - if( _set.size()==0 ) return "[]"; - SB sb = new SB().p('['); - for( long i : _set.keySetLong() ) - if( i >= (1L<<32) ) sb.p('(').p(i>>32).p(',').p(i&0xFFFFFFFFL).p(')').p(','); - else sb.p(i).p(','); - return sb.unchar().p(']').toString(); - } -} diff --git a/src/main/java/com/seaofnodes/util/IBitSet.java b/src/main/java/com/seaofnodes/util/IBitSet.java deleted file mode 100644 index d0d97585..00000000 --- a/src/main/java/com/seaofnodes/util/IBitSet.java +++ /dev/null @@ -1,164 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.util.Iterator; - -// Standard bit-set but supports the notion of an 'infinite extension' of 1. -// i.e. all bits past the end are either 0 or 1. -// Supports update-in-place, mutable, NOT hash-consed -public class IBitSet implements Iterable { - private boolean _sign; // false=infinite zeros, true=infinite ones - private final AryInt _bits = new AryInt(); - - // Since mutable, please do not mutate these - public static final IBitSet EMPTY = new IBitSet(); - public static final IBitSet FULL = new IBitSet().flip(); - - private static int idx (int i) { return i>>5; } - private static int mask(int i) { return 1<<(i&31); } - - // Test; returns the value - public boolean tst(int idx) { return _sign != _tst(idx); } - private boolean _tst(int idx) { return (_bits.atX(idx(idx)) & mask(idx)) != 0; } - - // Test and set; returns the old value - public boolean set(int idx) { return _sign ? !_clr(idx) : _set(idx); } - public boolean clr(int idx) { return _sign ? !_set(idx) : _clr(idx); } - - private boolean _set(int idx) { - int widx = idx (idx); - int mask = mask(idx); - int bits = _bits.atX(widx); - _bits.setX(widx, bits | mask); - return (bits&mask)!=0; - } - private boolean _clr(int idx) { - int widx = idx (idx); - int mask = mask(idx); - int bits = _bits.atX(widx); - _bits.setX(widx, bits & ~mask); - while( _bits._len>0 && _bits.last()==0 ) _bits.pop(); // Shrink - return (bits&mask)!=0; - } - // Constant-time, invert all bits - public IBitSet flip() { _sign=!_sign; return this; } - - public int bitCount() { - assert !_sign; // Infinite if sign is set - int sum=0; - for( int i=0; i<_bits._len; i++ ) - sum += Integer.bitCount(_bits._es[i]); - return sum; - } - public int max( ) { - assert !_sign; // Infinite if sign is set - if( _bits._len==0 ) return 0; - return (31 - Integer.numberOfLeadingZeros(_bits.last()))+((_bits._len-1)<<5); - } - - private int wd(int x) { return _bits._es[x]; } - private int xd(int x) { - int b = _bits.atX(x); // zero extend if off end - return _sign ? ~b : b;// adjust for sign - } - - public IBitSet clear() { - _sign=false; - _bits.clear(); - return this; - } - - // OR-into-this - public IBitSet or( IBitSet bs ) { - _sign |= bs._sign; - for( int i=0; i bs._bits._len ) { min=bs; bs=this; } // max in bs - if( min._sign && min._bits._len < bs._bits._len ) return false; // Extension in min overlaps last bits in max - for( int i=0; i iterator() { return new Iter(); } - private class Iter implements Iterator { - int _i=-1; - @Override public boolean hasNext() { - int idx; - while( (idx=idx(++_i)) < _bits._len ) - if( (_bits._es[idx]&mask(_i)) != 0 ) - return true; - return false; - } - @Override public Integer next() { - if( idx(_i) < _bits._len ) return _i; - throw new java.util.NoSuchElementException(); - } - } -} diff --git a/src/main/java/com/seaofnodes/util/IHashMap.java b/src/main/java/com/seaofnodes/util/IHashMap.java deleted file mode 100644 index 2f1a1d12..00000000 --- a/src/main/java/com/seaofnodes/util/IHashMap.java +++ /dev/null @@ -1,34 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import org.jctools.maps.NonBlockingHashMap; - -import java.util.Set; - -@SuppressWarnings("unchecked") -public class IHashMap { - private final NonBlockingHashMap _map = new NonBlockingHashMap(); - public T put(T kv) { _map.put(kv,kv); return kv; } - public T put(T k, T v) { _map.put(k,v); return v; } - public T get(T key) { return (T)_map.get(key); } - public void remove(Object key) { _map.remove(key); } - public void clear() { _map.clear(); } - public boolean isEmpty() { return _map.isEmpty(); } - public Set keySet() { return _map.keySet(); } -} diff --git a/src/main/java/com/seaofnodes/util/SB.java b/src/main/java/com/seaofnodes/util/SB.java deleted file mode 100644 index 4481ce71..00000000 --- a/src/main/java/com/seaofnodes/util/SB.java +++ /dev/null @@ -1,80 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.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( Type t ) { _sb.append(t.toString()); 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; } - // 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 int find( E[] es, E e ) { - for( int i=0; i>>(64-k)); } - private static long a,b,c; - private static int x; - static public void add_hash( long h ) { - switch( x ) { - case 0: a+=h; x++; return; - case 1: b+=h; x++; return; - case 2: c+=h; - a -= c; a ^= rot(c, 4); c += b; - b -= a; b ^= rot(a, 6); a += c; - c -= b; c ^= rot(b, 8); b += a; - a -= c; a ^= rot(c,16); c += b; - b -= a; b ^= rot(a,19); a += c; - c -= b; c ^= rot(b, 4); b += a; - x=0; - } - } - // Return the resulting hash, which is never 0 - static public long get_hash() { - if( x!=0 ) { - c ^= b; c -= rot(b,14); - a ^= c; a -= rot(c,11); - b ^= a; b -= rot(a,25); - c ^= b; c -= rot(b,16); - a ^= c; a -= rot(c, 4); - b ^= a; b -= rot(a,14); - c ^= b; c -= rot(b,24); - } - long hash=c; - if( hash==0 ) hash=b; - if( hash==0 ) hash=a; - if( hash==0 ) hash=0xcafebabe; - a=b=c=x=0; - return hash; - } - // Single-use hash spreader - static public long mix_hash(long h0) { - add_hash(h0); - return get_hash(); - } - static public long mix_hash( long h0, long h1 ) { - add_hash(h0); - add_hash(h1); - return get_hash(); - } - static public long mix_hash( long h0, long h1, long h2 ) { - add_hash(h0); - add_hash(h1); - add_hash(h2); - return get_hash(); - } - static public long mix_hash( long h0, long h1, long h2, long h3 ) { - add_hash(h0); - add_hash(h1); - add_hash(h2); - add_hash(h3); - return get_hash(); - } - static public long mix_hash( long h0, long h1, long h2, long h3, long h4 ) { - add_hash(h0); - add_hash(h1); - add_hash(h2); - add_hash(h3); - add_hash(h4); - return get_hash(); - } - - static public int gcd(int x, int y) { - if( x==0 || y== 0 ) return 0; - int a = Math.max(x,y), r; - int b = Math.min(x,y); - while((r=(a % b)) != 0) { a = b; b = r; } - return b; - } - - static public boolean isUpperCase( String s ) { - for( int i=0; ii && k>j; // Arrays were not equals, so at least one element from each copied to other - if( k < xs.length ) - throw new UnsupportedOperationException("Not implemented"); // Compact - return xs; - } - -} diff --git a/src/main/java/com/seaofnodes/util/UtilUnsafe.java b/src/main/java/com/seaofnodes/util/UtilUnsafe.java deleted file mode 100644 index c98f0d21..00000000 --- a/src/main/java/com/seaofnodes/util/UtilUnsafe.java +++ /dev/null @@ -1,55 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.lang.reflect.Field; - -import sun.misc.Unsafe; - -/** - * Simple class to obtain access to the {@link Unsafe} object. {@link Unsafe} - * is required to allow efficient CAS operations on arrays. Note that the - * versions in java.util.concurrent.atomic, such as {@link - * java.util.concurrent.atomic.AtomicLongArray}, require extra memory ordering - * guarantees which are generally not needed in these algorithms and are also - * expensive on most processors. - */ -public class UtilUnsafe { - private UtilUnsafe() { } // dummy private constructor - static final Unsafe UNSAFE = getUnsafe(); - /** Fetch the Unsafe. Use With Caution. */ - public static Unsafe getUnsafe() { - // Not on bootclasspath - if( UtilUnsafe.class.getClassLoader() == null ) - return Unsafe.getUnsafe(); - try { - final Field fld = Unsafe.class.getDeclaredField("theUnsafe"); - fld.setAccessible(true); - return (Unsafe) fld.get(UtilUnsafe.class); - } catch (Exception e) { - throw new RuntimeException("Could not obtain access to sun.misc.Unsafe", e); - } - } - - static final long fieldOffset( Class clz, String field ) { - Field f = null; - try { f = clz.getDeclaredField(field); } - catch( java.lang.NoSuchFieldException e ) { throw new RuntimeException(e); } - return UNSAFE.objectFieldOffset(f); - } -} diff --git a/src/main/java/com/seaofnodes/util/VBitSet.java b/src/main/java/com/seaofnodes/util/VBitSet.java deleted file mode 100644 index 5d00a9e4..00000000 --- a/src/main/java/com/seaofnodes/util/VBitSet.java +++ /dev/null @@ -1,27 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.util.BitSet; - -public class VBitSet extends BitSet { - // Cannot override 'set' to return a value... :-P - public boolean tset(int idx) { boolean b = get(idx); set(idx); return b; } - public boolean test(int idx) { return get(idx); } - public VBitSet clr() { clear(); return this; } -} diff --git a/src/main/java/com/seaofnodes/util/Work.java b/src/main/java/com/seaofnodes/util/Work.java deleted file mode 100644 index 4f34ed21..00000000 --- a/src/main/java/com/seaofnodes/util/Work.java +++ /dev/null @@ -1,79 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.util.function.IntSupplier; - -// Simple worklist. Filters dups on a add. -// Constant-time remove until empty. -// Supports psuedo random pop. -@SuppressWarnings("unchecked") -public class Work extends BitSetSparse { - private final Ary _work = new Ary(new Object[1],0); - private int _rseed; // Psuedo-random draw - private int _idx; // Next item to get - public Work() { this(123); } // Default seed - public Work(int rseed) { _rseed = rseed; } - public int len() { return _work._len; } - public boolean isEmpty() { return _work.isEmpty(); } - public E add(E e) { // Add, filtering dups - if( e!=null && !tset(e.getAsInt()) ) - _work.push(e); - return e; - } - public void setSeed(int rseed ) { - assert _work.isEmpty(); - _rseed = rseed; - _idx = 0; - } - @Override public Work clear() { - super.clear(); - _work.clear(); - return this; - } - // Bulk adders - public void add(E[] es) { if(es!=null) for( E e : es ) add(e); } - public void addAll(Ary es) { if( es!=null ) for( E e : es ) add(e); } - public void addAll(Work work) { for( Object o : work._work ) add((E)o); } - public boolean on(E e) { return test(e.getAsInt()); } - // Pull a psuedo-random element. Order depends on rseed. - public E pop() { - if( _work._len==0 ) return null; - _idx = (_idx+_rseed)&((1<<30)-1); - E e = _work.del( _idx % _work._len ); - clr(e.getAsInt()); - return e; - } - public E pop_last() { - if( _work._len==0 ) return null; - E e = _work.pop(); - clr(e.getAsInt()); - return e; - } - // Get/delete "idx"th elements; error if OOB. - public E at(int idx) { return _work.at(idx); } - public void del(int idx) { clr((_work.del(idx)).getAsInt()); } - public String print_work() { return _work.toString(); } - @Override public String toString() { - if( _set.size()==0 ) return "[]"; - SB sb = new SB().p('['); - for( E e : _work ) - sb.p(e.getAsInt()).p(','); - return sb.unchar().p(']').toString(); - } -} -- cgit v1.2.3