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