001package jmri.jmrit.logix;
002
003import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
004import java.util.ArrayList;
005import java.util.List;
006import javax.swing.tree.DefaultMutableTreeNode;
007import javax.swing.tree.DefaultTreeModel;
008import org.slf4j.Logger;
009import org.slf4j.LoggerFactory;
010
011public class RouteFinder implements Runnable {
012
013    private WarrantRoute _caller;
014    private BlockOrder _originBlockOrder;
015    private BlockOrder _destBlockOrder;
016    private BlockOrder _viaBlockOrder;
017    private BlockOrder _avoidBlockOrder;
018    private ArrayList<DefaultMutableTreeNode> _destNodes;
019    private DefaultTreeModel _tree;
020
021    private OBlock _destBlock;
022    private String _dPathName;
023    private String _dEntryName;
024    private OBlock _viaBlock;
025    private String _vPathName;
026    private OBlock _avoidBlock;
027    private String _aPathName;
028
029    private int _maxBlocks;
030    private volatile boolean _quit = false;
031    private volatile boolean _cancelled = false;
032
033    protected RouteFinder(WarrantRoute f, BlockOrder origin, BlockOrder dest,
034            BlockOrder via, BlockOrder avoid, int maxB) {
035        _caller = f;
036        _originBlockOrder = origin;
037        _destBlockOrder = dest;
038        _viaBlockOrder = via;
039        _avoidBlockOrder = avoid;
040        _maxBlocks = maxB;
041    }
042
043    protected synchronized void quit() {
044        log.debug("quit= {}", _quit);
045        _quit = true;
046    }
047
048    /**
049     * Stop the search without reporting any result, e.g. because a new
050     * search has replaced it.
051     */
052    protected synchronized void cancel() {
053        log.debug("cancel");
054        _cancelled = true;
055        _quit = true;
056    }
057
058    static class RouteNode extends DefaultMutableTreeNode {
059
060        boolean _needsViaAncestor = false;
061
062        RouteNode(Object userObject) {
063            super(userObject);
064        }
065
066        RouteNode(Object userObject, boolean needsViaAncestor) {
067            super(userObject);
068            _needsViaAncestor = needsViaAncestor;
069        }
070
071        void hasViaAncestor(boolean hasViaAncestor) {
072            _needsViaAncestor = !hasViaAncestor;
073        }
074
075        boolean needsViaAncestor() {
076            return _needsViaAncestor;
077        }
078
079    }
080
081    @Override
082    public void run() {
083        _destBlock = _destBlockOrder.getBlock();
084        _dPathName = _destBlockOrder.getPathName();
085        _dEntryName = _destBlockOrder.getEntryName();
086        _viaBlock = null;
087        _vPathName = null;
088        if (_viaBlockOrder != null) {
089            _vPathName = _viaBlockOrder.getPathName();
090            _viaBlock = _viaBlockOrder.getBlock();
091        }
092        _avoidBlock = null;
093        _aPathName = null;
094        if (_avoidBlockOrder != null) {
095            _aPathName = _avoidBlockOrder.getPathName();
096            _avoidBlock = _avoidBlockOrder.getBlock();
097        }
098
099        _destNodes = new ArrayList<>();
100        int level = 0;
101        if (log.isDebugEnabled()) {
102            log.debug("Origin= \"{}\" Path= \"{}\" Exit= \"{}\"",  _originBlockOrder.getBlock().getDisplayName(),
103                    _originBlockOrder.getPathName(), _originBlockOrder.getExitName());
104            log.debug("Destination= \"{}\" Path= \"{}\" Entry= \"{}\"",  _destBlock.getDisplayName(), _dPathName, _dEntryName);
105        }
106        RouteNode root = new RouteNode(_originBlockOrder, (_viaBlockOrder != null));
107        _tree = new DefaultTreeModel(root);
108        ArrayList<RouteNode> nodes = new ArrayList<>();
109        nodes.add(root);
110        while (level < _maxBlocks && !_quit) {
111            nodes = makeLevel(nodes, level);
112            log.debug("level {} has {} nodes. quit= {}", level, nodes.size(), _quit);
113            level++;
114        }
115        if (_cancelled) {
116            log.debug("search cancelled at level {}", level);
117            return;
118        }
119        jmri.util.ThreadingUtil.runOnLayout(() -> {
120            if (_cancelled) {    // cancelled while waiting to report
121                return;
122            }
123            if (_destNodes.isEmpty()) {
124                _caller.debugRoute(_tree, _originBlockOrder, _destBlockOrder);
125            } else {
126                _caller.pickRoute(_destNodes, _tree);
127            }
128        });
129    }
130
131    /**
132     * Examines list of nodes at a given level for the destination node and
133     * makes a list of nodes of the next level.
134     * @param nodes list of route nodes
135     * @param level level of the nodes
136     * @return list of  route nodes at level
137     */
138    @SuppressFBWarnings(value="BC_UNCONFIRMED_CAST_OF_RETURN_VALUE", justification="OBlock extends Block")
139    ArrayList<RouteNode> makeLevel(ArrayList<RouteNode> nodes, int level) {
140
141        ArrayList<RouteNode> children = new ArrayList<>();
142        for (int i = 0; i < nodes.size(); i++) {
143            RouteNode node = nodes.get(i);
144            BlockOrder pOrder = (BlockOrder) node.getUserObject();
145            OBlock pBlock = pOrder.getBlock();
146            String pName = pOrder.getExitName();    // is entryName of next block
147            Portal exitPortal = pBlock.getPortalByName(pName);
148            if (exitPortal != null) {
149                OBlock nextBlock = exitPortal.getOpposingBlock(pBlock);
150                List<OPath> paths = exitPortal.getPathsFromOpposingBlock(pBlock);
151                if (log.isTraceEnabled()) {
152                    log.debug("makeLevel {} block= {}, path= {} meets {} portal paths",
153                            level, pBlock.getDisplayName(), pOrder.getPathName(), paths.size());
154                }
155                if (paths.isEmpty()) {
156                    if (nextBlock == null) {
157                        log.error("Portal \"{}\" is malformed! \"{}\" not connected to another block!", 
158                                pName, pBlock.getDisplayName());
159                    } else {
160                        log.error("Portal \"{}\" does not have any paths from \"{}\" to \"{}\"",
161                                pName, pBlock.getDisplayName(), nextBlock.getDisplayName());
162                    }
163                }
164                // walk all paths
165                for (int k = 0; k < paths.size(); k++) {
166                    OPath path = paths.get(k);
167                    if (_avoidBlock != null && _avoidBlock.equals(nextBlock)) {
168                        if (_aPathName.equals(path.getName())) {
169                            continue;
170                        }
171                    }
172                    String exitName = path.getOppositePortalName(pName);
173                    OBlock pathBlock = (OBlock) path.getBlock();
174                    BlockOrder nOrder = new BlockOrder(pathBlock, path.getName(), pName, exitName);
175                    RouteNode child = new RouteNode(nOrder, node.needsViaAncestor());
176                    _tree.insertNodeInto(child, node, node.getChildCount());
177                    if (_viaBlock != null && _viaBlock.equals(nextBlock)) {
178                        if (_vPathName.equals(path.getName())) {
179                            child.hasViaAncestor(true);
180                        }
181                    }
182                    if (!node.needsViaAncestor()) {
183                        if (log.isTraceEnabled()) {
184                            log.debug("Test= \"{}\" Path= {} Exit= {}",  nOrder.getBlock().getDisplayName(),
185                                    path.getName(),pName);
186                        }
187                        if (_destBlock == nOrder.getBlock() && _dPathName.equals(path.getName())
188                                && _dEntryName.equals(pName)) {
189                            _destNodes.add(child);
190                        }
191                    }
192                    children.add(child);
193                    if (_quit) {
194                        break;
195                    }
196                }
197            } else {
198                log.debug("Dead branch: block= \"{}\" has no exit portal", pBlock.getDisplayName());
199            }
200            if (_quit) {
201                break;
202            }
203        }
204        return children;
205    }
206
207    private static final Logger log = LoggerFactory.getLogger(RouteFinder.class);
208}