diff options
| author | dibyendumajumdar <mobile@majumdar.org.uk> | 2023-08-25 23:16:07 +0100 |
|---|---|---|
| committer | dibyendumajumdar <mobile@majumdar.org.uk> | 2023-08-25 23:16:07 +0100 |
| commit | 9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39 (patch) | |
| tree | 05dcb2c2b972538dba2da0429ba9705e09dc8e96 /src/main | |
| parent | b6098a9b9166da962676e33de31e93ace260d686 (diff) | |
| download | Simple-9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39.tar.gz Simple-9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39.zip | |
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.
Diffstat (limited to 'src/main')
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/common/CompilerException.java | 11 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java | 228 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/parser/Ast.java | 132 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/parser/Parser.java | 259 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/Ary.java | 367 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/AryInt.java | 203 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/BitSetSparse.java | 41 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/IBitSet.java | 164 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/IHashMap.java | 34 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/SB.java | 80 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/Util.java | 151 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/UtilUnsafe.java | 55 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/VBitSet.java | 27 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/Work.java | 79 |
14 files changed, 0 insertions, 1831 deletions
diff --git a/src/main/java/com/seaofnodes/simple/common/CompilerException.java b/src/main/java/com/seaofnodes/simple/common/CompilerException.java deleted file mode 100644 index 518dcde6..00000000 --- a/src/main/java/com/seaofnodes/simple/common/CompilerException.java +++ /dev/null @@ -1,11 +0,0 @@ -package com.seaofnodes.simple.common; - -public class CompilerException extends RuntimeException { - public CompilerException(String message) { - super(message); - } - - public CompilerException(String message, Throwable cause) { - super(message, cause); - } -} diff --git a/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java b/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java deleted file mode 100644 index 162cdea1..00000000 --- a/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java +++ /dev/null @@ -1,228 +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.simple.lexer.aa; - -import com.seaofnodes.util.AryInt; -import com.seaofnodes.util.SB; - -import java.text.NumberFormat; -import java.text.ParsePosition; - -public class Lexer { - private final String _srcName; // Source for error messages; usually a file name - private final byte[] _buf; - private int _x; // Parser index - private int _lastNWS; // Index of last non-white-space char - private final AryInt _lines; // char offset of each line - - private final NumberFormat _nf; - private final ParsePosition _pp; - private final String _str; - - public Lexer(String srcName, String source) - { - _srcName = srcName; - _buf = source.getBytes(); - _x = 0; - - // Set fields strictly for Java number parsing - _nf = NumberFormat.getInstance(); - _nf.setGroupingUsed(false); - _pp = new ParsePosition(0); - _str = source; // Keep a complete string copy for java number parsing - _lines = new AryInt();// - _lines.push(0); // Line 0 at offset 0 - } - - // Skip WS, return true&skip if match, false & do not skip if miss. - public boolean peek( char c ) { return peek1(skipWS(),c); } - public boolean peek_noWS( char c ) { return peek1(_x >= _buf.length ? -1 : _buf[_x],c); } - // Already skipped WS & have character; - // return true & skip if a match, false& do not skip if a miss. - public boolean peek1( byte c0, char c ) { - assert c0==-1 || c0== _buf[_x]; - if( c0!=c ) return false; - _x++; // Skip peeked character - return true; - } - // Already skipped WS & have character; - // return true&skip if match, false & do not skip if miss. - public boolean peek2( byte c0, String s2 ) { - if( c0 != s2.charAt(0) ) return false; - if( _x+1 >= _buf.length || _buf[_x+1] != s2.charAt(1) ) return false; - _x+=2; // Skip peeked characters - return true; - } - public boolean peek( String s ) { - if( !peek(s.charAt(0)) ) return false; - if( !peek_noWS(s.charAt(1)) ) { _x--; return false; } - return true; - } - // Peek 'c' and NOT followed by 'no' - public boolean peek_not( char c, char no ) { - byte c0 = skipWS(); - if( c0 != c || (_x+1 < _buf.length && _buf[_x+1] == no) ) return false; - _x++; - return true; - } - // Match any of these, and return the match or null - public String peek(String[] toks) { - for( String tok : toks ) if( peek1(tok) ) return tok; - return null; - } - public boolean peek1(String tok) { - for( int i=0; i<tok.length(); i++ ) - if( _x+i >= _buf.length || _buf[_x+i] != tok.charAt(i) ) - return false; - return true; - } - - - /** Advance parse pointer to the first non-whitespace character, and return - * that character, -1 otherwise. */ - public byte skipWS() { - int oldx = _x; - while( _x < _buf.length ) { - byte c = _buf[_x]; - if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='/' ) { skipEOL() ; continue; } - if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='*' ) { skipBlock(); continue; } - if( c=='\n' && _x+1 > _lines.last() ) _lines.push(_x+1); - if( !isWS(c) ) { - if( oldx-1 > _lastNWS && !isWS(_buf[oldx-1]) ) _lastNWS = oldx-1; - return c; - } - _x++; - } - return -1; - } - public void skipEOL () { while( _x < _buf.length && _buf[_x] != '\n' ) _x++; } - public void skipBlock() { throw new UnsupportedOperationException("Block comments not yet implemented"); } - // Advance parse pointer to next WS. Used for parser syntax error recovery. - public void skipNonWS() { - while( _x < _buf.length && !isWS(_buf[_x]) ) _x++; - } - - /** Return true if `c` passes a test */ - public static boolean isWS (byte c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; } - public static boolean isAlpha0(byte c) { return ('a'<=c && c <= 'z') || ('A'<=c && c <= 'Z') || (c=='_'); } - public static boolean isAlpha1(byte c) { return isAlpha0(c) || ('0'<=c && c <= '9'); } - public static boolean isJava (byte c) { return isAlpha1(c) || (c=='$') || (c=='.'); } - public static boolean isDigit (byte c) { return '0' <= c && c <= '9'; } - - public String token() { skipWS(); return token0(); } - // Lexical tokens. Any alpha, followed by any alphanumerics is a alpha- - // token; alpha-tokens end with WS or any operator character. Any collection - // of the classic operator characters are a token, except that they will break - // un-ambiguously. - public String token0() { - if( _x >= _buf.length ) return null; - byte c=_buf[_x]; int x = _x; - if( isOp0(c) || (c=='_' && _x+1 < _buf.length && isOp0(_buf[_x+1])) ) - while( _x < _buf.length && isOp1(_buf[_x]) ) _x++; - else if( isAlpha0(c) ) - while( _x < _buf.length && isAlpha1(_buf[_x]) ) _x++; - else return null; // Not a token; specifically excludes e.g. all bytes >= 128, or most bytes < 32 - if( (c==':' || c==',') && _x-x==1 ) // Disallow bare ':' as a token; ambiguous with ?: and type annotations; same for ',' - { _x=x; return null; } // Unwind, not a token - if( c=='-' && _x-x>2 && _buf[x+1]=='>' ) // Disallow leading "->", confusing with function parameter list end; eg "not={x->!x}" - _x=x+2; // Just return the "->" - return new String(_buf,x,_x-x); - } - public boolean isOp(String s) { - if( s==null || s.isEmpty() ) return false; - byte c = (byte)s.charAt(0); - if( !isOp0(c) && (c!='_' || !isOp0((byte)s.charAt(1))) ) return false; - for( int i=1; i<s.length(); i++ ) - if( !isOp1((byte)s.charAt(i)) ) return false; - return true; - } - - // Parse a number; WS already skipped and sitting at a digit. Relies on - // Javas number parsing. - public Number number() { - _pp.setIndex(_x); - Number n = _nf.parse(_str,_pp); - _x = _pp.getIndex(); - if( n instanceof Long ) { - if( _buf[_x-1]=='.' ) _x--; // Java default parser allows "1." as an integer; pushback the '.' - } - return n; - } - - public int field_number() { - byte c = _buf[_x]; - if( !isDigit(c) ) return -1; - _x++; - int sum = c-'0'; - while( _x < _buf.length && isDigit(c=_buf[_x]) ) { - _x++; - sum = sum*10+c-'0'; - } - return sum; - } - - /** Parse a String; _x is at '"'. - * str = [.\%]* // String contents; \t\n\r\% standard escapes - * str = %[num]?[.num]?fact // Percent escape embeds a 'fact' in a string; "name=%name\n" - */ - public String string() { - int oldx = ++_x; - byte c; - while( (c=_buf[_x++]) != '"' ) { - if( c=='%' ) throw new UnsupportedOperationException("Not implemented"); - if( c=='\\' ) throw new UnsupportedOperationException("Not implemented"); - if( _x == _buf.length ) return null; - } - return new String(_buf,oldx,_x-oldx-1).intern(); - } - - public static boolean isOp0(byte c) { return "!#$%*+-=<>^[]~/&|".indexOf(c) != -1; } - public static boolean isOp1(byte c) { return isOp0(c) || ":?_{}".indexOf(c) != -1; } - - public String errLocMsg(String s) { - if( s.charAt(0)=='\n' ) return s; - // find line start - int a=_x; - while( a > 0 && _buf[a-1] != '\n' ) --a; - if( _buf[a]=='\r' ) a++; // do not include leading \n or \n\r - // find line end - int b=_x; - while( b < _buf.length && _buf[b] != '\n' ) b++; - if( b < _buf.length ) b--; // do not include trailing \n or \n\r - // Find line number. Bin-search returns the insertion-point, which is the NEXT - // line unless _x is exactly a line start. - int line = _lines.binary_search(_x); // Find zero-based line insertion point - if( line == _lines._len || _lines.at(line)>_x ) line--; - // error message using 1-based line - SB sb = new SB().p(_srcName).p(':').p(line+1).p(':').p(s).nl(); - sb.p(new String(_buf,a,b-a)).nl(); - int line_start = a; - for( int i=line_start; i<_x; i++ ) - sb.p(' '); - return sb.p('^').nl().toString(); - } - - @Override public String toString() { return new String(_buf,_x,_buf.length-_x); } - @Override public boolean equals(Object loc) { - if( this==loc ) return true; - if( !(loc instanceof Lexer p) ) return false; - return _x==p._x && _srcName.equals(p._srcName); - } - @Override public int hashCode() { - return _srcName.hashCode()+_x; - } -} diff --git a/src/main/java/com/seaofnodes/simple/parser/Ast.java b/src/main/java/com/seaofnodes/simple/parser/Ast.java deleted file mode 100644 index a93b230f..00000000 --- a/src/main/java/com/seaofnodes/simple/parser/Ast.java +++ /dev/null @@ -1,132 +0,0 @@ -package com.seaofnodes.simple.parser; - -import com.seaofnodes.simple.common.CompilerException; -import com.seaofnodes.simple.lexer.ecstasy.Token; - -import java.util.ArrayList; -import java.util.List; - -public abstract class Ast { - - public static class Node { - } - - public static class Expr extends Node { - public final Token op; - - public Expr(Token op) { - this.op = op; - } - } - - public static class Identifier extends Expr { - public final String name; - public Identifier(Token op) { - super(op); - name = op.getValueText(); - } - } - - public static class Symbol extends Expr { - public final String name; - public Symbol(Token op) { - super(op); - name = op.getValueText(); - } - } - - public static class Binary extends Expr { - public final Expr expr1, expr2; - - public Binary(Token op, Expr expr1, Expr expr2) { - super(op); - this.expr1 = expr1; - this.expr2 = expr2; - } - } - - public static class Unary extends Expr { - public final Expr expr; - - public Unary(Token op, Expr expr) { - super(op); - this.expr = expr; - } - } - - public static class Constant extends Expr { - public Constant(Token op) { - super(op); - } - } - - public static class Statement extends Node { - } - - public static class IfElse extends Statement { - public final Expr expr; - public final Statement ifStmt, elseStmt; - - public IfElse(Expr expr, Statement ifStmt, Statement elseStmt) { - this.expr = expr; - this.ifStmt = ifStmt; - this.elseStmt = elseStmt; - } - } - - public static class While extends Statement { - public Expr expr; - public Statement stmt; - - public While() { - } - public void init(Expr expr, Statement stmt) { - this.expr = expr; - this.stmt = stmt; - } - } - - public static class Break extends Statement { - public final Statement stmt; - - public Break(Statement stmt) { - if (stmt == null) - { - throw new CompilerException("uneclosed break"); - } - this.stmt = stmt; - } - } - - public static class Assign extends Statement { - public final Identifier identifier; - public final Expr expr; - - public Assign(Identifier identifier, Expr expr) { - this.identifier = identifier; - this.expr = expr; - } - } - - public static class Type extends Node { - public final Token.Id typeId; - - public Type(Token.Id typeId) { - this.typeId = typeId; - } - } - - public static class Declare extends Statement { - public final Type type; - public final Identifier identifier; - - public Declare(Type type, Identifier identifier) { - this.type = type; - this.identifier = identifier; - } - } - - public static class Block extends Statement { - public final List<Statement> stmtList = new ArrayList<>(); - } -} diff --git a/src/main/java/com/seaofnodes/simple/parser/Parser.java b/src/main/java/com/seaofnodes/simple/parser/Parser.java deleted file mode 100644 index f7b29f40..00000000 --- a/src/main/java/com/seaofnodes/simple/parser/Parser.java +++ /dev/null @@ -1,259 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Dibyendu Majumdar. - * - * 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.simple.parser; - -import com.seaofnodes.simple.common.CompilerException; -import com.seaofnodes.simple.lexer.ecstasy.Lexer; -import com.seaofnodes.simple.lexer.ecstasy.Token; -import com.seaofnodes.util.Severity; - -public class Parser { - final Lexer lexer; - Token look; - Ast.Statement statementEnclosing; - - public Parser(Lexer lexer) { - this.lexer = lexer; - } - - Token nextOrEof() { - if (lexer.hasNext()) - return lexer.next(); - return new Token(look.getStartPosition(), look.getEndPosition(), Token.Id.EOF); - } - - void nextToken() { - look = nextOrEof(); - while (look.isComment()) { - look = nextOrEof(); - } - if (look.isContextSensitive() && - look.getId() == Token.Id.IDENTIFIER) { - look = look.convertToKeyword(); - } - } - - void error(Token t, String errorMessage) { - lexer.log(Severity.ERROR, errorMessage, t.getStartPosition(), t.getEndPosition()); - throw new CompilerException(errorMessage + ": " + t.toDebugString()); - } - - void match(Token.Id tag) { - if (look.getId() == tag) { - nextToken(); - } else { - error(look, "syntax error, expected " + tag); - } - } - - public Ast.Node parse() { - nextToken(); - return parseProgram(); - } - - Ast.Statement parseProgram() { - var block = new Ast.Block(); - parseDeclarations(block); - parseStatements(block); - return block; - } - - void parseDeclarations(Ast.Block block) { - while (look.getId() == Token.Id.VAR) { - nextToken(); - var tok = look; - match(Token.Id.IDENTIFIER); - match(Token.Id.COLON); - var type = parseType(); - match(Token.Id.SEMICOLON); - var identifier = new Ast.Identifier(tok); - block.stmtList.add(new Ast.Declare(type, identifier)); - } - } - - Ast.Type parseType() { - if (look.getId() == Token.Id.LIT_INTA) { - nextToken(); - return new Ast.Type(look.getId()); - } - error(look, "syntax error: unsupported type (at present only Int type is allowed)"); - return null; - } - - void parseStatements(Ast.Block block) { - while (look.getId() != Token.Id.EOF && - look.getId() != Token.Id.R_CURLY) { - block.stmtList.add(parseStatement()); - } - } - - Ast.Statement parseStatement() { - Ast.Expr x; - Ast.Statement s1; - Ast.Statement s2; - - switch (look.getId()) { - case IF -> { - match(Token.Id.IF); - match(Token.Id.L_PAREN); - x = parseBool(); - match(Token.Id.R_PAREN); - s1 = parseStatement(); - if (look.getId() != Token.Id.ELSE) { - return new Ast.IfElse(x, s1, null); - } - s2 = parseStatement(); - return new Ast.IfElse(x, s1, s2); - } - case WHILE -> { - var whilenode = new Ast.While(); - var savedStmt = statementEnclosing; - statementEnclosing = whilenode; - match(Token.Id.WHILE); - match(Token.Id.L_PAREN); - x = parseBool(); - match(Token.Id.R_PAREN); - s1 = parseStatement(); - whilenode.init(x, s1); - statementEnclosing = savedStmt; - return whilenode; - } - case BREAK -> { - match(Token.Id.BREAK); - match(Token.Id.SEMICOLON); - return new Ast.Break(statementEnclosing); - } - case L_CURLY -> { - return parseBlock(); - } - default -> { - return parseAssign(); - } - } - } - - Ast.Statement parseBlock() { - match(Token.Id.L_CURLY); - var block = new Ast.Block(); - parseDeclarations(block); - parseStatements(block); - match(Token.Id.R_CURLY); - return block; - } - - Ast.Statement parseAssign() { - match(Token.Id.IDENTIFIER); - Ast.Identifier identifier = new Ast.Identifier(look); - match(Token.Id.ASN); - var s = new Ast.Assign(identifier, parseBool()); - match(Token.Id.SEMICOLON); - return s; - } - - Ast.Expr parseBool() { - var x = parseAnd(); - while (look.getId() == Token.Id.COND_OR) { - var tok = look; - nextToken(); - x = new Ast.Binary(tok, x, parseAnd()); - } - return x; - } - - Ast.Expr parseAnd() { - var x = parseRelational(); - while (look.getId() == Token.Id.COND_AND) { - var tok = look; - nextToken(); - x = new Ast.Binary(tok, x, parseRelational()); - } - return x; - } - - Ast.Expr parseRelational() { - var x = parseAddition(); - while (look.getId() == Token.Id.COMP_EQ || - look.getId() == Token.Id.COMP_NEQ || - look.getId() == Token.Id.COMP_LT || - look.getId() == Token.Id.COMP_GT || - look.getId() == Token.Id.COMP_GTEQ || - look.getId() == Token.Id.COMP_LTEQ) { - var tok = look; - nextToken(); - x = new Ast.Binary(tok, x, parseAddition()); - } - return x; - } - - Ast.Expr parseAddition() { - var x = parseMultiplication(); - while (look.getId() == Token.Id.ADD || - look.getId() == Token.Id.SUB) { - var tok = look; - nextToken(); - x = new Ast.Binary(tok, x, parseMultiplication()); - } - return x; - } - - Ast.Expr parseMultiplication() { - var x = parseUnary(); - while (look.getId() == Token.Id.MUL || - look.getId() == Token.Id.DIV) { - var tok = look; - nextToken(); - x = new Ast.Binary(tok, x, parseUnary()); - } - return x; - } - - Ast.Expr parseUnary() { - if (look.getId() == Token.Id.SUB || - look.getId() == Token.Id.NOT) { - var tok = look; - nextToken(); - return new Ast.Unary(tok, parseUnary()); - } else { - return parsePrimary(); - } - } - - Ast.Expr parsePrimary() { - switch (look.getId()) { - case L_PAREN -> { - nextToken(); - var x = parseBool(); - match(Token.Id.R_PAREN); - return x; - } - case LIT_INT -> { - var x = new Ast.Constant(look); - nextToken(); - return x; - } - case IDENTIFIER -> { - var x = new Ast.Symbol(look); - nextToken(); - return x; - } - default -> { - error(look, "syntax error, expected nested expr, integer value or variable"); - return null; - } - } - } -} 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<E> implements Iterable<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; } - /** @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<E> 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<E> 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<E> addAll( Collection<? extends E> c ) { if( c!=null ) for( E e : c ) 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); } - - /** @param f function to apply to each element. Updates in-place. */ - public Ary<E> map_update( Function<E,E> 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<E> filter_update( Predicate<E> 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<? super E> 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<E> 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 <X extends Comparable<X>> Ary<X> merge_or( Ary<X> a0, Ary<X> a1 ) { - int i=0, j=0; - Ary<X> res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); - - while( i<a0._len && j<a1._len ) { - X x = a0._es[i]; - X y = a1._es[j]; - int cmp = x.compareTo(y); - if( cmp<0 ) { res.add(x); i++; } - else if( cmp>0 ) { res.add(y); j++; } - else { res.add(x); i++; j++; } - } - while( i<a0._len ) res.add(a0._es[i++]); - while( j<a1._len ) res.add(a1._es[j++]); - return res; - } - - /** Merge-Or. Merge two sorted Arys, tossing out duplicates and elements not - * passing the filter. 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 - * @param cmpr Comparator - * @param filter Predicate, null means no filter - * @return A new sorted merged Ary - */ - public static <X> Ary<X> merge_or( Ary<X> a0, Ary<X> a1, Comparator<X> cmpr, Predicate<X> filter) { - int i=0, j=0; - Ary<X> res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); - - while( i<a0._len && j<a1._len ) { - X x = a0._es[i]; if( !filter.test(x) ) { i++; continue; } - X y = a1._es[j]; if( !filter.test(y) ) { j++; continue; } - int cmp = cmpr.compare(x,y); - if( cmp<0 ) { res.add(x); i++; } - else if( cmp>0 ) { res.add(y); j++; } - else { res.add(x); i++; j++; } - } - while( i<a0._len ) if( filter.test(a0._es[i++]) ) res.add(a0._es[i-1]); - while( j<a1._len ) if( filter.test(a1._es[j++]) ) res.add(a1._es[j-1]); - return res; - } - - - /** Merge-And. Merge 2 sorted Arys, keeping only 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 <X extends Comparable<X>> Ary<X> merge_and( Ary<X> a0, Ary<X> a1 ) { - int i=0, j=0; - Ary<X> res = new Ary<>(Arrays.copyOf(a0._es,Math.min(a0._len,a1._len)),0); - while( i<a0._len && j<a1._len ) { - X x = a0._es[i]; - X y = a1._es[j]; - int cmp = x.compareTo(y); - if( cmp<0 ) { i++; } - else if( cmp>0 ) { j++; } - else { res.add(x); i++; j++; } - } - return res; - } - - /** @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() { - 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<E> 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<? 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; - } - - 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<String> _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<Integer> { - 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; i++ ) - _bits.setX(i,_bits.atX(i)|bs.wd(i)); - return this; - } - // SUBTRACT-from-this - public void subtract( IBitSet bs ) { - for( int i=0; i<bs._bits._len; i++ ) - _bits.setX(i,_bits.atX(i)&~bs.wd(i)); - } - // True if set is empty. The flipped set is never empty. - public boolean is_empty() { return _bits._len==0 && !_sign; } - - // False if any bits in common - public boolean disjoint( IBitSet bs ) { - if( is_empty() ) return true; // Empty set must be disjoint - if( bs.is_empty() ) return true; // Empty set must be disjoint - if( _sign && bs._sign ) return false; // Both extensions are set - IBitSet min = this; - if( _bits._len > 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<min._bits._len; i++ ) - if( (min.wd(i)&bs.wd(i))!= 0 ) - return false; - return true; - } - - // Does 'this' subset 'bs'? - // True if all bits in common: "bs== this.OR (bs)". - public boolean subsetsX( IBitSet bs ) { - assert !bs.is_empty(); // Undefined - int max=Math.max(_bits._len,bs._bits._len); - for( int i=0; i<max; i++ ) - if( (xd(i)|bs.xd(i)) != bs.xd(i) ) // All bits in common - return false; - return true; - } - - @Override public String toString() { return toString(new SB()).toString(); } - public SB toString(SB sb) { - if( _bits._len==0 ) return sb.p(_sign?"[...]":"[]"); - int x = -1; // No range-in-process - sb.p('['); - for( int i=0; i<_bits._len*32+1; i++ ) { - if( tst(i) ) { - if( x==-1 ) x=i; // Start a range - } else { - if( x!=-1 ) { // End a range - if( x+1==i ) sb.p(x).p(','); - else if( x+2==i ) sb.p(x).p(',').p(i-1).p(','); - else sb.p(x).p("...").p(i-1).p(','); - x = -1; - } - } - } - if( x != -1 ) sb.p(x).p("...,"); // Close open range - return sb.unchar().p(']'); - } - - /** @return an iterator */ - @Override public Iterator<Integer> iterator() { return new Iter(); } - private class Iter implements Iterator<Integer> { - 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> T put(T kv) { _map.put(kv,kv); return kv; } - public <T> T put(T k, T v) { _map.put(k,v); return v; } - public <T> 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 <T> Set<T> 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<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; } - // Decrease indentation - public SB di( int i) { _indent -= i; return this; } - - public SB nl( ) { return p(System.lineSeparator()); } - - // Delete last char. Useful when doing string-joins and JSON printing and an - // extra seperater 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 clear() { _sb.setLength(0); return this; } - public int len() { return _sb.length(); } - @Override public String toString() { return _sb.toString(); } -} diff --git a/src/main/java/com/seaofnodes/util/Util.java b/src/main/java/com/seaofnodes/util/Util.java deleted file mode 100644 index e559a799..00000000 --- a/src/main/java/com/seaofnodes/util/Util.java +++ /dev/null @@ -1,151 +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; - -public class Util { - // Fast linear scan for a hit, returns index or -1 - public static int find( int[] es, int e ) { - for( int i=0; i<es.length; i++ ) if( es[i]==e ) return i; - return -1; - } - // Fast linear scan for a hit, returns index or -1 - public static <E> int find( E[] es, E e ) { - for( int i=0; i<es.length; i++ ) if( es[i]==e ) return i; - return -1; - } - - // String-equals, with expected interned strings - public static boolean eq( String s0, String s1 ) { - if( s0==s1 ) return true; - if( s0==null || s1==null ) return false; - assert !s0.equals(s1) : "Not interned: "+s0; - return false; - } - - - // Copied from http://burtleburtle.net/bob/c/lookup3.c - // Call add_hash as many times as you like, then get_hash at the end. - // Uses global statics, does not nest. - public static long rot(long x, int k) { return (x<<k) | (x>>>(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; i<s.length() ; i++ ) - if( !Character.isUpperCase(s.charAt(i)) ) - return false; - return true; - } - - // Return a merged sorted array from two sorted arrays, removing dups. - // If the merge is the same as either array, return that array. - // If the merge is the same as BOTH arrays, return the array with the smaller - // hashCode (goal: canonicalize identical arrays, so the fast == check works - // more often, and we do not make lots of equals-not-== arrays). - static public short[] merge_sort( short[] es0, short[] es1 ) { - if( es0==es1 ) return es0; - if( Arrays.equals(es0,es1) ) - throw new UnsupportedOperationException("Not implemented"); - short[] xs = new short[es0.length+es1.length]; - int i=0, j=0, k=0; - while( i<es0.length || j<es1.length ) { - short s0 = i<es0.length ? es0[i] : Short.MAX_VALUE, s1 = j<es1.length ? es1[j] : Short.MAX_VALUE, s2=s0; - if( s0<=s1 ) { i++; s2=s0; } - if( s1<=s0 ) { j++; s2=s1; } - xs[k++] = s2; - } - assert k>i && 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<E extends IntSupplier> extends BitSetSparse { - private final Ary<E> _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<? extends E> es) { if( es!=null ) for( E e : es ) add(e); } - public void addAll(Work<E> 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(); - } -} |
