Package nl.tue.astar.impl

Class AbstractAStarThread<H extends Head,​T extends Tail>

    • Field Detail

      • trace

        protected final Trace trace

      • maxStates

        protected final int maxStates

      • queuedStateCount

        protected int queuedStateCount

      • traversedArcCount

        protected int traversedArcCount

      • computedEstimateCount

        protected int computedEstimateCount

      • poll

        protected int poll

      • i

        protected static int i

      • reliable

        protected boolean reliable

      • considered

        protected final gnu.trove.set.TLongSet considered

      • epsilon

        protected double epsilon

      • expectedLength

        protected double expectedLength

    • Constructor Detail

      • AbstractAStarThread

        public AbstractAStarThread​(Delegate<H,​T> delegate,
                           Trace trace,
                           int maxStates,
                           AbstractAStarThread.StorageHandler<H,​T> storageHandler)
        any implementation should, after calling this constructor, call initializeQueue(initialHead);
        Parameters:
        delegate -
        trace -
        maxStates -
        storageHandler -

    • Method Detail

      • getTrace

        public Trace getTrace()
        Description copied from interface: AStarThread
        Returns the trace for which this AStarThread was instantiated.
        Specified by:
        getTrace in interface AStarThread<H extends Head,​T extends Tail>
        Returns:

      • getDelegate

        public Delegate<H,​T> getDelegate()
        Description copied from interface: AStarThread
        returns the delegate used for determining the possible moves during replay.
        Specified by:
        getDelegate in interface AStarThread<H extends Head,​T extends Tail>
        Returns:

      • setPreferBreadth

        @Deprecated
public void setPreferBreadth​(boolean preferBreadth)
        Deprecated.
        Use setQueueingModel() or setQueue instead;
        Specified by:
        setPreferBreadth in interface AStarThread<H extends Head,​T extends Tail>

      • setASynchronousMoveSorting

        public void setASynchronousMoveSorting​(AStarThread.ASynchronousMoveSorting sorting)
        Description copied from interface: AStarThread
        When aligning a trace with a model, any moves between two synchronous moves can be sorted. When sorting is set to LOGMOVEFIRST, then no logMove can ever follow a modelMove. If sorting is set to ModelMoveFirst, then no modelMove can ever follow a logMove. The default is LOGMOVEFIRST;
        Specified by:
        setASynchronousMoveSorting in interface AStarThread<H extends Head,​T extends Tail>

      • getOptimalRecord

        public Record getOptimalRecord​(AStarThread.Canceller c)
                        throws AStarException
        Description copied from interface: AStarThread
        Returns a Record for an optimal alignment. If no optimal alignment exists, or if none is found in time, a "best guess" is returned. To check whether the returned alignment is optimal, the method isReliable() can be used. To make sure you investigated the entire graph from which the (a) final node is reachable, keep calling the method getOptimalRecord(c, stopAt) with the stopAt cost equal to the total cost of the first record. When doing so until the first unreliable result, the entire search space is covered.
        Specified by:
        getOptimalRecord in interface AStarThread<H extends Head,​T extends Tail>
        Returns:
        Throws:
        AStarException

      • getOptimalRecord

        public Record getOptimalRecord​(AStarThread.Canceller c,
                               int stopAt)
                        throws AStarException
        Description copied from interface: AStarThread
        Returns a Record for an optimal alignment. If no optimal alignment exists, if none is found in time or if the cost of an optimal alignment is higher than stopAt a "best guess" is returned. To check whether the returned alignment is optimal, the method isReliable() can be used. To make sure you investigated the entire graph from which the (a) final node is reachable, keep calling the method getOptimalRecord(c, stopAt) with the stopAt cost equal to the total cost of the first record. When doing so until the first unreliable result, the entire search space is covered.
        Specified by:
        getOptimalRecord in interface AStarThread<H extends Head,​T extends Tail>
        Returns:
        Throws:
        AStarException

      • poll

        protected Record poll()

      • getOptimalRecord

        public Record getOptimalRecord​(AStarThread.Canceller c,
                               int stopAt,
                               double timeLimit)
                        throws AStarException
        gets the optimal record. The search stops and returns the best prefix so far if either the stopAt value is reached in terms of cost, or if the timeLimit in seconds is reached. If the timelimit is negative, then time is unlimited.
        Parameters:
        c -
        stopAt -
        timeLimit -
        Returns:
        Throws:
        AStarException

      • processMovesForRecord

        protected void processMovesForRecord​(Record rec,
                                     H head,
                                     T tail,
                                     int stopAt,
                                     double timeLimit,
                                     long endTime)
                              throws AStarException
        Throws:
        AStarException

      • processMovesForRecordWithUpToDateTail

        protected void processMovesForRecordWithUpToDateTail​(Record rec,
                                                     H head,
                                                     T tail,
                                                     int stopAt,
                                                     double timeLimit,
                                                     long endTime)
                                              throws AStarException
        Throws:
        AStarException

      • setConsidered

        protected void setConsidered​(Record record)

      • isValidMoveOnModel

        protected boolean isValidMoveOnModel​(Record rec,
                                     gnu.trove.TIntCollection nextEvents,
                                     int activity,
                                     gnu.trove.list.TIntList modelMoves)

      • isValidMoveOnLog

        protected boolean isValidMoveOnLog​(Record rec,
                                   int nextEvent,
                                   int activity,
                                   gnu.trove.list.TIntList modelMoves,
                                   gnu.trove.list.TIntList syncMoves)

      • allowMove

        protected boolean allowMove​(Record rec,
                            int modelMove,
                            int logMove)
                     throws AStarException
        This method handles the filtering of moves in the situation the total ordering is implied. We assume a total ordering > on all moves (l,m) is the requested move (l',m') is the preceeding move (l'm') blocks the occurrence of (l,m) if and only if: 1) (l,m) was enabled before, i.e. no token flow 2) (l'm') > (l,m) Assume T(model) > T(log) > T(sync) Interpretation is: You can only do model or log moves with the intent to enable sync moves and among them, model and log moves are scheduled log move first
        Parameters:
        rec -
        nextEvent -
        modelMove -
        Returns:
        Throws:
        AStarException

      • wasReliable

        public boolean wasReliable()
        Description copied from interface: AStarThread
        After a call to run(), this method returns true if the returned Record yields the optimal result. If this method returns false, then the returned Record was subOptimal, for example because the maximum state count was reached, of because no solution was found. The Record returned by the previous call to run should be considered as a best guess.
        Specified by:
        wasReliable in interface AStarThread<H extends Head,​T extends Tail>
        Returns:

      • computeNextHead

        protected H computeNextHead​(Record rec,
                            H head,
                            int modelMove,
                            int movedEvent,
                            int activity)

      • computeNewTail

        protected T computeNewTail​(Record newRec,
                           T tail,
                           H newHead,
                           int modelMove,
                           int movedEvent,
                           int activity)

      • getQueuedStateCount

        public int getQueuedStateCount()
        Description copied from interface: AStarThread
        Returns the number of nodes queueud. This is at least the number of nodes visisted, but can be higher due to updates.
        Specified by:
        getQueuedStateCount in interface AStarThread<H extends Head,​T extends Tail>
        Returns:

      • getTraversedArcCount

        public int getTraversedArcCount()
        Description copied from interface: AStarThread
        Returns the number of arcs that were traversed in the statespace.
        Specified by:
        getTraversedArcCount in interface AStarThread<H extends Head,​T extends Tail>
        Returns:

      • getComputedEstimateCount

        public int getComputedEstimateCount()

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • setType

        public void setType​(AStarThread.Type type)
        Description copied from interface: AStarThread
        Sets the type of the AStar algorithm. Can be changed during execution, however if type is set to any weighted variant, the epsilon and expected length should be set.
        Specified by:
        setType in interface AStarThread<H extends Head,​T extends Tail>

      • setEpsilon

        public void setEpsilon​(double epsilon)
        Set epsilon for the weighted variants of A Star
        Specified by:
        setEpsilon in interface AStarThread<H extends Head,​T extends Tail>
        Parameters:
        epsilon -

      • setExpectedLength

        public void setExpectedLength​(int length)
        Set expected length for the dynamic weighted variant of A Star
        Specified by:
        setExpectedLength in interface AStarThread<H extends Head,​T extends Tail>
        Parameters:
        length -