summaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
authordibyendumajumdar <mobile@majumdar.org.uk>2023-08-25 23:16:07 +0100
committerdibyendumajumdar <mobile@majumdar.org.uk>2023-08-25 23:16:07 +0100
commit9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39 (patch)
tree05dcb2c2b972538dba2da0429ba9705e09dc8e96 /src/main
parentb6098a9b9166da962676e33de31e93ace260d686 (diff)
downloadSimple-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.java11
-rw-r--r--src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java228
-rw-r--r--src/main/java/com/seaofnodes/simple/parser/Ast.java132
-rw-r--r--src/main/java/com/seaofnodes/simple/parser/Parser.java259
-rw-r--r--src/main/java/com/seaofnodes/util/Ary.java367
-rw-r--r--src/main/java/com/seaofnodes/util/AryInt.java203
-rw-r--r--src/main/java/com/seaofnodes/util/BitSetSparse.java41
-rw-r--r--src/main/java/com/seaofnodes/util/IBitSet.java164
-rw-r--r--src/main/java/com/seaofnodes/util/IHashMap.java34
-rw-r--r--src/main/java/com/seaofnodes/util/SB.java80
-rw-r--r--src/main/java/com/seaofnodes/util/Util.java151
-rw-r--r--src/main/java/com/seaofnodes/util/UtilUnsafe.java55
-rw-r--r--src/main/java/com/seaofnodes/util/VBitSet.java27
-rw-r--r--src/main/java/com/seaofnodes/util/Work.java79
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();
- }
-}