Class ASTRRBTree

  • All Implemented Interfaces:
    edu.jas.structure.AbelianGroupElem<IExpr>, edu.jas.structure.Element<IExpr>, edu.jas.structure.GcdRingElem<IExpr>, edu.jas.structure.MonoidElem<IExpr>, edu.jas.structure.RingElem<IExpr>, Externalizable, Serializable, Cloneable, Comparable<IExpr>, Iterable<IExpr>, RandomAccess, org.hipparchus.CalculusFieldElement<IExpr>, org.hipparchus.FieldElement<IExpr>, IAST, IASTAppendable, IASTMutable, IExpr, ITensorAccess
    Direct Known Subclasses:
    ASTAssociation

    public class ASTRRBTree
    extends AbstractAST
    implements IASTAppendable, Externalizable, RandomAccess

    Immutable (A)bstract (S)yntax (T)ree of a given function implemented as an RRB Tree. The implmentation is based on the paper, "RRB-Trees: Efficient Immutable Vectors" by Phil Bagwell and Tiark Rompf, with the following differences:

    • the Relaxed nodes can be sized between n/3 and 2n/3 (Bagwell/Rompf specify n and n-1)
    • the Join operation sticks the shorter tree unaltered into the larger tree (except for verysmall trees which just get concatenated).

    In Symja, an abstract syntax tree (AST), is a tree representation of the abstract syntactic structure of the Symja source code. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it does not represent every detail that appears in the real syntax. For instance, grouping parentheses are implicit in the tree structure, and a syntactic construct such as a Sin[x] expression will be denoted by an AST with 2 nodes. One node for the header Sin and one node for the argument x. Internally an AST is represented as a java.util.List which contains

    • the operator of a function (i.e. the "header"-symbol: Sin, Cos, Inverse, Plus, Times,...) at index 0 and
    • the n arguments of a function in the index 1 to n
    See Abstract syntax tree.
    See Also:
    AST, Serialized Form
    • Field Detail

      • rrbTree

        protected org.organicdesign.fp.collections.RrbTree.MutRrbt<IExpr> rrbTree
        The underlying RRB Tree
    • Constructor Detail

      • ASTRRBTree

        public ASTRRBTree()
      • ASTRRBTree

        public ASTRRBTree​(int size,
                          boolean test)
      • ASTRRBTree

        public ASTRRBTree​(IAST ast)
        Copy constructor. Do a shallow copy of all ast elements to a new ASTRRBTree.
        Parameters:
        ast -
      • ASTRRBTree

        public ASTRRBTree​(org.organicdesign.fp.collections.RrbTree.MutRrbt<IExpr> list)
      • ASTRRBTree

        public ASTRRBTree​(org.organicdesign.fp.collections.RrbTree.ImRrbt<IExpr> list)
      • ASTRRBTree

        public ASTRRBTree​(IExpr[] array)
    • Method Detail

      • ensureCapacity

        public void ensureCapacity​(int size)
      • newInstance

        public static ASTRRBTree newInstance​(int initialCapacity,
                                             IExpr head)
      • arg1

        public IExpr arg1()
        Get the first argument (i.e. the second element of the underlying list structure) of the AST function (i.e. get(1) ).
        Example: for the AST representing the expression Sin(x), arg1() returns x.
        Specified by:
        arg1 in interface IAST
        Returns:
        the first argument of the function represented by this AST.
        See Also:
        IExpr.head()
      • arg2

        public IExpr arg2()
        Get the second argument (i.e. the third element of the underlying list structure) of the AST function (i.e. get(2) ).
        Example: for the AST representing the expression x^y (i.e. Power(x, y)), arg2() returns y.
        Specified by:
        arg2 in interface IAST
        Returns:
        the second argument of the function represented by this AST.
        See Also:
        IExpr.head()
      • arg3

        public IExpr arg3()
        Get the third argument (i.e. the fourth element of the underlying list structure) of the AST function (i.e. get(3) ).
        Example: for the AST representing the expression f(a, b, c), arg3() returns c.
        Specified by:
        arg3 in interface IAST
        Returns:
        the third argument of the function represented by this AST.
        See Also:
        IExpr.head()
      • arg4

        public IExpr arg4()
        Get the fourth argument (i.e. the fifth element of the underlying list structure) of the AST function (i.e. get(4) ).
        Example: for the AST representing the expression f(a, b ,c, d), arg4() returns d.
        Specified by:
        arg4 in interface IAST
        Returns:
        the fourth argument of the function represented by this AST.
        See Also:
        IExpr.head()
      • arg5

        public IExpr arg5()
        Get the fifth argument (i.e. the sixth element of the underlying list structure) of the AST function (i.e. get(5) ).
        Example: for the AST representing the expression f(a, b ,c, d, e), arg5() returns e .
        Specified by:
        arg5 in interface IAST
        Returns:
        the fifth argument of the function represented by this AST.
        See Also:
        IExpr.head()
      • argSize

        public int argSize()
        Returns the number of arguments in this IAST. The number of arguments equals size() - 1 (i.e. the number of elements minus 1). If this is an atom return size -1.
        Specified by:
        argSize in interface IAST
        Specified by:
        argSize in interface IExpr
        Returns:
        the number of arguments in this IAST.
        See Also:
        IExpr.size()
      • asSet

        public Set<IExpr> asSet()
        Description copied from interface: IAST
        Collect all arguments of this AST in a new set.
        Specified by:
        asSet in interface IAST
        Overrides:
        asSet in class AbstractAST
        Returns:
        null if a set couldn't be created
      • clone

        public IAST clone()
        Returns a new HMArrayList with the same elements, the same size and the same capacity as this HMArrayList.
        Overrides:
        clone in class Object
        Returns:
        a shallow copy of this ArrayList
        See Also:
        Cloneable
      • copy

        public ASTRRBTree copy()

        Returns a shallow copy of this IAST instance (the elements themselves are not copied). In contrast to the IAST.copyAppendable() method, this method returns exactly the same type for AST0, AST1, AST2, AST3 and tries to transform AST objects to AST0, AST1, AST2, AST3 if possible.

        Because it's not allowed to set the header object (offset 0) to an arbitrary expression after a copy(), this method should only be used if the arguments (offset 1..argSize) should be set to new expressions.

        Specified by:
        copy in interface edu.jas.structure.Element<IExpr>
        Specified by:
        copy in interface IAST
        Returns:
        a copy of this IAST instance.
      • copyAppendable

        public IASTAppendable copyAppendable()
        Description copied from interface: IAST

        Returns a shallow copy of this IAST instance (the elements themselves are not copied). In contrast to the IAST.copy() method, this method doesn't return exactly the same type for a given AST0, AST1, AST2, AST3... object but transforms it into a new AST object, so that additional arguments could be appended at the end.

        This also allows to set the header object to an arbitrary expression.

        Specified by:
        copyAppendable in interface IAST
        Returns:
        a copy of this IAST instance.
      • copyAppendable

        public IASTAppendable copyAppendable​(int additionalCapacity)
        Description copied from interface: IAST

        Returns a shallow copy of this IAST instance (the elements themselves are not copied). In contrast to the IAST.copy() method, this method doesn't return exactly the same type for a given AST0, AST1, AST2, AST3... object but transforms it into a new AST object, so that additional arguments could be appended at the end.

        This also allows to set the header object to an arbitrary expression.

        Specified by:
        copyAppendable in interface IAST
        Returns:
        a copy of this IAST instance.
      • equals

        public boolean equals​(Object obj)
        Specified by:
        equals in interface edu.jas.structure.Element<IExpr>
        Overrides:
        equals in class AbstractAST
      • exists

        public boolean exists​(ObjIntPredicate<? super IExpr> predicate,
                              int startOffset)
        Check all elements by applying the predicate to each argument in this AST and return true if one of the arguments starting from index startOffset satisfy the predicate.
        Specified by:
        exists in interface IAST
        Overrides:
        exists in class AbstractAST
        Parameters:
        predicate - the predicate which filters each argument in this AST
        startOffset - start offset from which the element have to be tested
        Returns:
        the true if the predicate is true the first time or false otherwise
      • exists

        public boolean exists​(Predicate<? super IExpr> predicate,
                              int startOffset)
        Check all elements by applying the predicate to each argument in this AST and return true if one of the arguments starting from index startOffset satisfy the predicate.
        Specified by:
        exists in interface IAST
        Overrides:
        exists in class AbstractAST
        Parameters:
        predicate - the predicate which filters each argument in this AST
        startOffset - start offset from which the element have to be tested
        Returns:
        the true if the predicate is true the first time or false otherwise
      • forAll

        public boolean forAll​(ObjIntPredicate<? super IExpr> predicate,
                              int startOffset)
        Check all elements by applying the predicate to each argument in this AST and return true if all of the arguments starting from index startOffset satisfy the predicate.

        Note: If this is an IAssociation the rule at the position will be returned.

        Specified by:
        forAll in interface IAST
        Overrides:
        forAll in class AbstractAST
        Parameters:
        predicate - the predicate which filters each argument in this AST
        startOffset - start offset from which the element have to be tested
        Returns:
        true if the predicate is true for all elements or false otherwise
      • forAll

        public boolean forAll​(Predicate<? super IExpr> predicate,
                              int startOffset)
        Check all elements by applying the predicate to each argument in this AST and return true if all of the arguments starting from index startOffset satisfy the predicate.

        Note: If this is an IAssociation the rule at the position will be returned.

        Specified by:
        forAll in interface IAST
        Overrides:
        forAll in class AbstractAST
        Parameters:
        predicate - the predicate which filters each argument in this AST
        startOffset - start offset from which the element have to be tested
        Returns:
        true if the predicate is true for all elements or false otherwise
      • forEach

        public void forEach​(int start,
                            int end,
                            ObjIntConsumer<? super IExpr> action)
        Description copied from interface: IAST
        Consume all value-elements generated by the given function from index start inclusive to end exclusive.
        Specified by:
        forEach in interface IAST
      • forEach

        public void forEach​(int start,
                            int end,
                            Consumer<? super IExpr> action)
        Description copied from interface: IAST
        Consume all value-elements generated by the given function from index start inclusive to end exclusive.
        Specified by:
        forEach in interface IAST
        Parameters:
        start - start index (inclusive)
        end - end index (exclusive)
        action - function which accepts the elements
      • get

        public IExpr get​(int location)
        Description copied from interface: IAST
        Returns the element at the specified location in this IAST. If this is an IAssociation return the value of the rule at the specified location.
        Specified by:
        get in interface IAST
        Specified by:
        get in interface ITensorAccess
        Specified by:
        get in class AbstractAST
        Parameters:
        location - the index of the element to return.
        Returns:
        the element at the specified location.
      • getItems

        public IAST getItems​(int[] items,
                             int length)
        Description copied from interface: IAST
        Returns length number of elements specified in the items position array in this IAST.
        Specified by:
        getItems in interface IAST
        Parameters:
        items - ascending ordered array of positions which should be selected from this IAST.
        length - the end position (exclusive) to which the items array is filled with valid element positions
        Returns:
      • head

        public IExpr head()
        Description copied from interface: IExpr
        If this object is an instance of IAST get the first element (offset 0) of the IAST list (i.e. #get(0) ). Otherwise return the specific header, i.e. for integer number type => S.Integer, fraction number type => S.Rational, complex number type => S.Complex, ...
        Specified by:
        head in interface IExpr
        Returns:
        the head of the expression, which must not be null.
      • isAST0

        public boolean isAST0()
        Test if this expression is an IAST function, which contains a header element (i.e. the function name) at index position 0 and no argument elements.
        Therefore this expression is no atomic expression.
        Specified by:
        isAST0 in interface IExpr
        Overrides:
        isAST0 in class AbstractAST
        Returns:
        See Also:
        IExpr.isAtom()
      • isAST1

        public boolean isAST1()
        Test if this expression is an IAST function, which contains a header element (i.e. the function name) at index position 0 and one argument element at the index position 1.
        Therefore this expression is no atomic expression.
        Specified by:
        isAST1 in interface IExpr
        Overrides:
        isAST1 in class AbstractAST
        Returns:
        See Also:
        IExpr.isAtom()
      • isAST2

        public boolean isAST2()
        Test if this expression is an IAST function, which contains a header element (i.e. the function name) at index position 0 and two argument elements at the index positions 1, 2.
        Therefore this expression is no atomic expression.
        Specified by:
        isAST2 in interface IExpr
        Overrides:
        isAST2 in class AbstractAST
        Returns:
        See Also:
        IExpr.isAtom()
      • isAST3

        public boolean isAST3()
        Test if this expression is an IAST function, which contains a header element (i.e. the function name) at index position 0 and three argument elements at the index positions 1, 2, 3.
        Therefore this expression is no atomic expression.
        Specified by:
        isAST3 in interface IExpr
        Overrides:
        isAST3 in class AbstractAST
        Returns:
        See Also:
        IExpr.isAtom()
      • isList

        public boolean isList()
        Test if this expression is a list (i.e. an AST with head List)
        Specified by:
        isList in interface IExpr
        Overrides:
        isList in class AbstractAST
        Returns:
      • isSameHead

        public boolean isSameHead​(ISymbol head)
        Check if the object at index 0 (i.e. the head of the list) is the same object as head
        Overrides:
        isSameHead in class AbstractAST
        Parameters:
        head - object to compare with element at location 0
        Returns:
      • isSameHead

        public boolean isSameHead​(ISymbol head,
                                  int length)
        Check if the object at index 0 (i.e. the head of the list) is the same object as head and if the size of the list equals length.
        Overrides:
        isSameHead in class AbstractAST
        Parameters:
        head - object to compare with element at location 0
        Returns:
      • isSameHead

        public boolean isSameHead​(ISymbol head,
                                  int minLength,
                                  int maxLength)
        Check if the object at index 0 (i.e. the head of the list) is the same object as head and if the size of the list is between minLength and maxLength .
        Overrides:
        isSameHead in class AbstractAST
        Parameters:
        head - object to compare with element at location 0
        minLength - minimum length of list elements.
        maxLength - maximum length of list elements.
        Returns:
      • isSameHeadSizeGE

        public boolean isSameHeadSizeGE​(ISymbol head,
                                        int length)
        Check if the object at index 0 (i.e. the head of the list) is the same object as head and if the size of the list is greater or equal length.
        Specified by:
        isSameHeadSizeGE in interface IAST
        Specified by:
        isSameHeadSizeGE in interface IExpr
        Parameters:
        head - object to compare with element at location 0
        Returns:
      • set

        public IExpr set​(int location,
                         IExpr object)
        Replaces the element at the specified location in this ArrayList with the specified object. Internally the hashValue will be reset to 0.
        Specified by:
        set in interface IASTMutable
        Parameters:
        location - the index at which to put the specified object.
        object - the object to add.
        Returns:
        the previous element at the index.
        Throws:
        IndexOutOfBoundsException - when location < 0 || >= size()
      • setAtCopy

        public IASTMutable setAtCopy​(int i,
                                     IExpr expr)
        Description copied from interface: IAST
        Create a shallow copy of this IAST instance (the elements themselves are not copied) and set the expr at the given position. In contrast to the setAtClone() method, this method returns exactly the same type for AST0, AST1, AST2, AST3.
        Specified by:
        setAtCopy in interface IAST
        Returns:
        a copy with element set to expr at the given position.
      • sortInplace

        public void sortInplace​(Comparator<IExpr> comparator)
        Description copied from interface: IASTMutable
        Sort this in place using function comparator#compare(a, b). Example: suppose the Symbol f has the attribute ISymbol.ORDERLESS f(z,d,a,b) ==> f(a,b,d,z)

        Warning only call this method in certain steps of the evaluation chain (for example for evaluating attribute ISymbol.ORDERLESS)

        Specified by:
        sortInplace in interface IASTMutable
        Overrides:
        sortInplace in class AbstractAST
        Parameters:
        comparator - the comparator used for sorting inplace.
      • size

        public final int size()
        Returns the number of elements in this ArrayList.
        Specified by:
        size in interface IAST
        Specified by:
        size in interface IExpr
        Returns:
        the number of elements in this ArrayList.
        See Also:
        IAST.argSize()
      • toArray

        public IExpr[] toArray()
        Description copied from interface: IAST
        Returns an array containing all elements contained in this List.
        Specified by:
        toArray in interface IAST
        Returns:
        an array of the elements from this List.
      • append

        public boolean append​(IExpr expr)
        Description copied from interface: IASTAppendable
        Adds the specified expression at the end of this.
        Specified by:
        append in interface IASTAppendable
        Parameters:
        expr - the object to add.
        Returns:
        always true.
      • append

        public void append​(int location,
                           IExpr expr)
        Description copied from interface: IASTAppendable
        Inserts the specified object into this List at the specified location. The object is inserted before the current element at the specified location. If the location is equal to the size of this List, the object is added at the end. If the location is smaller than the size of this List, then all elements beyond the specified location are moved by one position towards the end of the List.
        Specified by:
        append in interface IASTAppendable
        Parameters:
        location - the index at which to insert.
        expr - the object to add.
      • appendAll

        public boolean appendAll​(Collection<? extends IExpr> collection)
        Description copied from interface: IASTAppendable
        Adds the objects in the specified collection to the end of this List. The objects are added in the order in which they are returned from the collection's iterator.
        Specified by:
        appendAll in interface IASTAppendable
        Parameters:
        collection - the collection of objects.
        Returns:
        true if this List is modified, false otherwise (i.e. if the passed collection was empty).
      • appendAll

        public boolean appendAll​(Map<? extends IExpr,​? extends IExpr> map)
        Description copied from interface: IASTAppendable
        Adds the mappings in the specified map as Rule(...) to the end of this List. The objects are added in the order in which they are returned from the map's iterator.
        Specified by:
        appendAll in interface IASTAppendable
        Returns:
      • appendAll

        public boolean appendAll​(IAST ast,
                                 int startPosition,
                                 int endPosition)
        Description copied from interface: IASTAppendable
        Appends all elements from offset startPosition to endPosition in the specified AST to the end of this AST.
        Specified by:
        appendAll in interface IASTAppendable
        Parameters:
        ast - AST containing elements to be added to this AST
        startPosition - the start position, inclusive.
        endPosition - the ending position, exclusive.
        Returns:
        true if this AST changed as a result of the call
      • appendAll

        public boolean appendAll​(int location,
                                 Collection<? extends IExpr> collection)
        Description copied from interface: IASTAppendable
        Inserts the objects in the specified collection at the specified location in this AST. The objects are added in the order they are returned from the collection's iterator.
        Specified by:
        appendAll in interface IASTAppendable
        Parameters:
        location - the index at which to insert.
        collection - the collection of objects.
        Returns:
        true if this ArrayList is modified, false otherwise.
      • appendAll

        public boolean appendAll​(List<? extends IExpr> list,
                                 int startPosition,
                                 int endPosition)
        Description copied from interface: IASTAppendable
        Appends all elements from offset startPosition to endPosition in the specified list to the end of this AST.
        Specified by:
        appendAll in interface IASTAppendable
        Parameters:
        list - list containing elements to be added to this AST
        startPosition - the start position, inclusive.
        endPosition - the ending position, exclusive.
        Returns:
        true if this AST changed as a result of the call
      • appendAll

        public boolean appendAll​(IExpr[] args,
                                 int startPosition,
                                 int endPosition)
        Description copied from interface: IASTAppendable
        Appends all elements from offset startPosition to endPosition in the specified list to the end of this AST.
        Specified by:
        appendAll in interface IASTAppendable
        Parameters:
        args - array containing elements to be added to this AST
        startPosition - the start position, inclusive.
        endPosition - the ending position, exclusive.
        Returns:
        true if this AST changed as a result of the call
      • appendArgs

        public boolean appendArgs​(IAST ast)
        Description copied from interface: IASTAppendable
        Appends all of the arguments (starting from offset 1) in the specified ast to the end of this AST.
        Specified by:
        appendArgs in interface IASTAppendable
        Parameters:
        ast - AST containing elements to be added to this AST
        Returns:
        true if this AST changed as a result of the call
      • appendArgs

        public boolean appendArgs​(IAST ast,
                                  int untilPosition)
        Description copied from interface: IASTAppendable
        Appends all of the arguments (starting from offset 1) in the specified AST up to position untilPosition exclusive.
        Specified by:
        appendArgs in interface IASTAppendable
        Parameters:
        ast - AST containing elements to be added to this AST
        untilPosition - append all argumments of ast up to position untilPosition exclusive.
        Returns:
        true if this AST changed as a result of the call
      • appendOneIdentity

        public IAST appendOneIdentity​(IAST value)
        Description copied from interface: IASTAppendable
        Append an subAST with attribute OneIdentity for example Plus[] or Times[].
        Specified by:
        appendOneIdentity in interface IASTAppendable
        Parameters:
        value - an ast with attribute OneIdentity.
        Returns:
        this ast after adding the subAST
      • clear

        public void clear()
        Description copied from interface: IASTAppendable
        Removes all elements from this IAST, leaving it empty (optional).
        Specified by:
        clear in interface IASTAppendable
      • remove

        public IExpr remove​(int location)
        Description copied from interface: IASTAppendable
        Removes the object at the specified location from this IAST.
        Specified by:
        remove in interface IASTAppendable
        Parameters:
        location - the index of the object to remove.
        Returns:
        the removed object.
      • removeRange

        public void removeRange​(int start,
                                int end)
        Description copied from interface: IASTAppendable
        Removes the objects in the specified range from the start to the end, but not including the end index.
        Specified by:
        removeRange in interface IASTAppendable
        Parameters:
        start - the index at which to start removing.
        end - the index one after the end of the range to remove. * @throws UnsupportedOperationException if removing from this IAST is not supported.