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    WarrantRoute _caller;
014    BlockOrder _originBlockOrder;
015    BlockOrder _destBlockOrder;
016    BlockOrder _viaBlockOrder;
017    BlockOrder _avoidBlockOrder;
018    ArrayList<DefaultMutableTreeNode> _destNodes;
019    DefaultTreeModel _tree;
020
021    OBlock _destBlock;
022    String _dPathName;
023    String _dEntryName;
024    OBlock _viaBlock;
025    String _vPathName;
026    OBlock _avoidBlock;
027    String _aPathName;
028
029    int _maxBlocks;
030    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            if (log.isDebugEnabled()) {
103                log.debug("level {} has {} nodes. quit= {}", level, nodes.size(), _quit);
104            }
105            level++;
106        }
107        jmri.util.ThreadingUtil.runOnLayout(() -> {
108            if (_destNodes.isEmpty()) {
109                _caller.debugRoute(_tree, _originBlockOrder, _destBlockOrder);
110            } else {
111                _caller.pickRoute(_destNodes, _tree);
112            }
113        });
114    }
115
116    /**
117     * Examines list of nodes at a given level for the destination node and
118     * makes a list of nodes of the next level.
119     * @param nodes list of route nodes
120     * @param level level of the nodes
121     * @return list of  route nodes at level
122     */
123    @SuppressFBWarnings(value="BC_UNCONFIRMED_CAST_OF_RETURN_VALUE", justification="OBlock extends Block")
124    ArrayList<RouteNode> makeLevel(ArrayList<RouteNode> nodes, int level) {
125
126        ArrayList<RouteNode> children = new ArrayList<>();
127        for (int i = 0; i < nodes.size(); i++) {
128            RouteNode node = nodes.get(i);
129            BlockOrder pOrder = (BlockOrder) node.getUserObject();
130            OBlock pBlock = pOrder.getBlock();
131            String pName = pOrder.getExitName();    // is entryName of next block
132            Portal exitPortal = pBlock.getPortalByName(pName);
133            if (exitPortal != null) {
134                OBlock nextBlock = exitPortal.getOpposingBlock(pBlock);
135                List<OPath> paths = exitPortal.getPathsFromOpposingBlock(pBlock);
136                if (log.isTraceEnabled()) {
137                    log.debug("makeLevel {} block= {}, path= {} meets {} portal paths",
138                            level, pBlock.getDisplayName(), pOrder.getPathName(), paths.size());
139                }
140                if (paths.isEmpty()) {
141                    if (nextBlock == null) {
142                        log.error("Portal \"{}\" is malformed! \"{}\" not connected to another block!", 
143                                pName, pBlock.getDisplayName());
144                    } else {
145                        log.error("Portal \"{}\" does not have any paths from \"{}\" to \"{}\"",
146                                pName, pBlock.getDisplayName(), nextBlock.getDisplayName());
147                    }
148                }
149                // walk all paths
150                for (int k = 0; k < paths.size(); k++) {
151                    OPath path = paths.get(k);
152                    if (_avoidBlock != null && _avoidBlock.equals(nextBlock)) {
153                        if (_aPathName.equals(path.getName())) {
154                            continue;
155                        }
156                    }
157                    String exitName = path.getOppositePortalName(pName);
158                    OBlock pathBlock = (OBlock) path.getBlock();
159                    BlockOrder nOrder = new BlockOrder(pathBlock, path.getName(), pName, exitName);
160                    RouteNode child = new RouteNode(nOrder, node.needsViaAncestor());
161                    _tree.insertNodeInto(child, node, node.getChildCount());
162                    if (_viaBlock != null && _viaBlock.equals(nextBlock)) {
163                        if (_vPathName.equals(path.getName())) {
164                            child.hasViaAncestor(true);
165                        }
166                    }
167                    if (!node.needsViaAncestor()) {
168                        if (log.isTraceEnabled()) {
169                            log.debug("Test= \"{}\" Path= {} Exit= {}",  nOrder.getBlock().getDisplayName(),
170                                    path.getName(),pName);
171                        }
172                        if (_destBlock == nOrder.getBlock() && _dPathName.equals(path.getName())
173                                && _dEntryName.equals(pName)) {
174                            _destNodes.add(child);
175                        }
176                    }
177                    children.add(child);
178                    if (_quit) {
179                        break;
180                    }
181                }
182            } else {
183                if (log.isDebugEnabled()) {
184                    log.debug("Dead branch: block= \"{}\" has no exit portal", pBlock.getDisplayName());
185                }
186            }
187            if (_quit) {
188                break;
189            }
190        }
191        return children;
192    }
193
194    private static final Logger log = LoggerFactory.getLogger(RouteFinder.class);
195}