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