001package jmri.jmrit.display.layoutEditor;
002
003import java.util.ArrayList;
004import java.util.HashMap;
005import java.util.List;
006import java.util.Set;
007import jmri.*;
008import jmri.jmrit.display.EditorManager;
009import org.slf4j.Logger;
010import org.slf4j.LoggerFactory;
011import org.slf4j.MDC;
012
013/**
014 * These are a series of layout block connectivity tools that can be used when
015 * the advanced layout block routing has been enabled. These tools can determine
016 * if a path from a source to destination bean is valid. If a route between two
017 * layout blocks is usable and free.
018 *
019 * @author Kevin Dickerson Copyright (C) 2011
020 * @author George Warner Copyright (c) 2017-2018
021 */
022final public class LayoutBlockConnectivityTools {
023
024    public LayoutBlockConnectivityTools() {
025    }
026
027    public enum Routing {
028        /**
029         * Constant used in the getLayoutBlocks to represent a path from one Signal
030         * Mast to another and that no mast should be in the path.
031         */
032        MASTTOMAST,
033
034        /**
035         * Constant used in the getLayoutBlocks to represent a path from one Signal
036         * Head to another and that no head should be in the path.
037         */
038        HEADTOHEAD,
039
040        /**
041         * Constant used in the getLayoutBlocks to represent a path from one Sensor
042         * to another and that no sensor should be in the path.
043         */
044        SENSORTOSENSOR,
045
046        /**
047         * Constant used in the getLayoutBlocks to represent a path from either a
048         * Signal Mast or Head to another Signal Mast or Head and that no mast of
049         * head should be in the path.
050         */
051        ANY,
052
053        /**
054         * Constant used in the getLayoutBlocks to indicate that the system
055         * should not check for signal masts or heads on the path.
056         */
057        NONE
058    }
059
060    public enum Metric {
061        HOPCOUNT,
062        METRIC,
063        DISTANCE
064    }
065    
066    private static final int ttlSize = 50;
067    
068
069    /**
070     * Determines if a pair of NamedBeans (Signalhead, Signalmast or Sensor)
071     * assigned to a block boundary are reachable.<br>
072     * Called by {@link jmri.jmrit.signalling.SignallingPanel} using MASTTOMAST.
073     * <p>
074     * Search all of the layout editor panels to find the facing and protecting
075     * layout blocks for each bean.  Call the 3 block+list version of checkValidDest() to finish the checks.
076     *
077     * @param sourceBean The source bean.
078     * @param destBean   The destination bean.
079     * @param pathMethod Indicates the type of path:  Signal head, signal mast or sensor.
080     * @return true if source and destination beans are reachable.
081     * @throws jmri.JmriException if no blocks can be found that related to the
082     *                            named beans.
083     */
084    public boolean checkValidDest(NamedBean sourceBean, NamedBean destBean, Routing pathMethod) throws jmri.JmriException {
085        if (log.isDebugEnabled()) {
086            log.debug("checkValidDest with source/dest bean {} {}", sourceBean.getDisplayName(), destBean.getDisplayName());
087        }
088        LayoutBlock facingBlock = null;
089        LayoutBlock protectingBlock = null;
090        LayoutBlock destFacingBlock = null;
091        List<LayoutBlock> destProtectBlock = null;
092        Set<LayoutEditor> layout = InstanceManager.getDefault(EditorManager.class).getAll(LayoutEditor.class);
093        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
094        for (LayoutEditor layoutEditor : layout) {
095            if (log.isDebugEnabled()) {
096                log.debug("Layout name {}", layoutEditor.getLayoutName());
097            }
098            if (facingBlock == null) {
099                facingBlock = lbm.getFacingBlockByNamedBean(sourceBean, layoutEditor);
100            }
101            if (protectingBlock == null) {
102                protectingBlock = lbm.getProtectedBlockByNamedBean(sourceBean, layoutEditor);
103            }
104            if (destFacingBlock == null) {
105                destFacingBlock = lbm.getFacingBlockByNamedBean(destBean, layoutEditor);
106            }
107            if (destProtectBlock == null) {
108                destProtectBlock = lbm.getProtectingBlocksByNamedBean(destBean, layoutEditor);
109            }
110            if ((destFacingBlock != null) && (facingBlock != null) && (protectingBlock != null)) {
111                /*Destination protecting block list is allowed to be empty, as the destination signalmast
112                 could be assigned to an end bumper */
113                // A simple to check to see if the remote signal/sensor is in the correct direction to ours.
114                try {
115                    return checkValidDest(facingBlock, protectingBlock, destFacingBlock, destProtectBlock, pathMethod);
116                } catch (JmriException e) {
117                    log.debug("Rethrowing exception from checkValidDest(..)");
118                    throw e;
119                }
120            } else {
121                log.debug("blocks not found");
122            }
123        }
124        if (log.isDebugEnabled()) {
125            log.debug("No valid route from {} to {}", sourceBean.getDisplayName(), destBean.getDisplayName());
126        }
127        throw new jmri.JmriException("Blocks Not Found");
128    }
129
130    /**
131     * The is used in conjunction with the layout block routing protocol, to
132     * discover a clear path from a source layout block through to a destination
133     * layout block. By specifying the sourceLayoutBlock and
134     * protectingLayoutBlock or sourceLayoutBlock+1, a direction of travel can
135     * then be determined, eg east to west, south to north etc.
136     * @param sourceBean    The source bean (SignalHead, SignalMast or Sensor)
137     *                     assigned to a block boundary that we are starting
138     *                     from.
139     * @param destBean      The destination bean.
140     * @param validateOnly  When set false, the system will not use layout
141     *                     blocks that are set as either reserved(useExtraColor
142     *                     set) or occupied, if it finds any then it will try to
143     *                     find an alternative path When set false, no block
144     *                     state checking is performed.
145     * @param pathMethod    Performs a check to see if any signal heads/masts
146     *                     are in the path, if there are then the system will
147     *                     try to find an alternative path. If set to NONE, then
148     *                     no checking is performed.
149     * @return an List of all the layoutblocks in the path.
150     * @throws jmri.JmriException if it can not find a valid path or the routing
151     *                            has not been enabled.
152     */
153    public List<LayoutBlock> getLayoutBlocks(NamedBean sourceBean, NamedBean destBean, boolean validateOnly, Routing pathMethod) throws jmri.JmriException {
154        Set<LayoutEditor> layout = InstanceManager.getDefault(EditorManager.class).getAll(LayoutEditor.class);
155        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
156        LayoutBlock facingBlock = null;
157        LayoutBlock protectingBlock = null;
158        LayoutBlock destFacingBlock = null;
159        for (LayoutEditor layoutEditor : layout) {
160            if (log.isDebugEnabled()) {
161                log.debug("Layout name {}", layoutEditor.getLayoutName());
162            }
163            if (facingBlock == null) {
164                facingBlock = lbm.getFacingBlockByNamedBean(sourceBean, layoutEditor);
165            }
166            if (protectingBlock == null) {
167                protectingBlock = lbm.getProtectedBlockByNamedBean(sourceBean, layoutEditor);
168            }
169            if (destFacingBlock == null) {
170                destFacingBlock = lbm.getFacingBlockByNamedBean(destBean, layoutEditor);
171            }
172            if ((destFacingBlock != null) && (facingBlock != null) && (protectingBlock != null)) {
173                try {
174                    return getLayoutBlocks(facingBlock, destFacingBlock, protectingBlock, validateOnly, pathMethod);
175                } catch (JmriException e) {
176                    log.debug("Rethrowing exception from getLayoutBlocks()");
177                    throw e;
178                }
179            } else {
180                log.debug("blocks not found");
181            }
182        }
183        if (log.isDebugEnabled()) {
184            log.debug("No valid route from {} to {}", sourceBean.getDisplayName(), destBean.getDisplayName());
185        }
186        throw new jmri.JmriException("Blocks Not Found");
187    }
188
189    /**
190     * Returns a list of NamedBeans (Signalhead, Signalmast or Sensor) that are
191     * assigned to block boundaries in a given list.
192     *
193     * @param blocklist The list of block in order that need to be checked.
194     * @param panel     (Optional) panel that the blocks need to be checked
195     *                  against
196     * @param T         (Optional) the class that we want to check against,
197     *                  either Sensor, SignalMast or SignalHead, set null will
198     *                  return any.
199     * @return the list of NamedBeans
200     */
201    public List<NamedBean> getBeansInPath(List<LayoutBlock> blocklist, LayoutEditor panel, Class<?> T) {
202        List<NamedBean> beansInPath = new ArrayList<>();
203        if (blocklist.size() >= 2) {
204            LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
205            for (int x = 1; x < blocklist.size(); x++) {
206                LayoutBlock facingBlock = blocklist.get(x - 1);
207                LayoutBlock protectingBlock = blocklist.get(x);
208                NamedBean nb = null;
209                if (T == null) {
210                    nb = lbm.getFacingNamedBean(facingBlock.getBlock(), protectingBlock.getBlock(), panel);
211                } else if (T.equals(jmri.SignalMast.class)) {
212                    nb = lbm.getFacingSignalMast(facingBlock.getBlock(), protectingBlock.getBlock(), panel);
213                } else if (T.equals(jmri.Sensor.class)) {
214                    nb = lbm.getFacingSensor(facingBlock.getBlock(), protectingBlock.getBlock(), panel);
215                } else if (T.equals(jmri.SignalHead.class)) {
216                    nb = lbm.getFacingSignalHead(facingBlock.getBlock(), protectingBlock.getBlock());
217                }
218                if (nb != null) {
219                    beansInPath.add(nb);
220                }
221            }
222        }
223        return beansInPath;
224    }
225
226    /**
227     * Determines if one set of blocks is reachable from another set of blocks
228     * based upon the directions of the set of blocks.
229     * <ul>
230     * <li>Called by {@link jmri.implementation.DefaultSignalMastLogic} using MASTTOMAST.</li>
231     * <li>Called by {@link jmri.jmrit.entryexit.DestinationPoints} using SENSORTOSENSOR.</li>
232     * <li>Called by {@link jmri.jmrit.entryexit.EntryExitPairs} using SENSORTOSENSOR.</li>
233     * </ul>
234     * Convert the destination protected block to an array list.
235     * Call the 3 block+list version of checkValidDest() to finish the checks.
236     * @param currentBlock The facing layout block for the source signal or sensor.
237     * @param nextBlock    The protected layout block for the source signal or sensor.
238     * @param destBlock    The facing layout block for the destination signal mast or sensor.
239     * @param destProBlock The protected destination block.
240     * @param pathMethod   Indicates the type of path:  Signal head, signal mast or sensor.
241     * @return true if a path to the destination is valid.
242     * @throws jmri.JmriException if any Block is null;
243     */
244    public boolean checkValidDest(LayoutBlock currentBlock, LayoutBlock nextBlock, LayoutBlock destBlock, LayoutBlock destProBlock, Routing pathMethod) throws jmri.JmriException {
245
246        List<LayoutBlock> destList = new ArrayList<>();
247        if (destProBlock != null) {
248            destList.add(destProBlock);
249        }
250        try {
251            return checkValidDest(currentBlock, nextBlock, destBlock, destList, pathMethod);
252        } catch (jmri.JmriException e) {
253            throw e;
254        }
255
256    }
257
258    /**
259     * Determines if one set of blocks is reachable from another set of blocks
260     * based upon the directions of the set of blocks.
261     * <p>
262     * This is used to help with identifying items such as signalmasts located
263     * at positionable points or turnouts are facing in the same direction as
264     * other given signalmasts.
265     * <p>
266     * Given the current block and the next block we can work out the direction
267     * of travel. Given the destBlock and the next block on, we can determine
268     * the whether the destBlock comes before the destBlock+1.
269     * <p>
270     * Note: This version is internally called by other versions that
271     * pre-process external calls.
272     * @param currentBlock The facing layout block for the source signal or
273     *                     sensor.
274     * @param nextBlock    The protected layout block for the source signal or
275     *                     sensor.
276     * @param destBlock    The facing layout block for the destination signal
277     *                     mast or sensor.
278     * @param destBlockn1  A list of protected destination blocks. Can be empty
279     *                     if the destination is at an end bumper.
280     * @param pathMethod   Indicates the type of path: Signal head, signal mast
281     *                     or sensor.
282     * @return true if a path to the destination is valid.
283     * @throws jmri.JmriException if any layout block is null or advanced
284     *                            routing is not enabled.
285     */
286    public boolean checkValidDest(LayoutBlock currentBlock, LayoutBlock nextBlock, LayoutBlock destBlock, List<LayoutBlock> destBlockn1, Routing pathMethod) throws jmri.JmriException {
287        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
288        if (!lbm.isAdvancedRoutingEnabled()) {
289            log.debug("Advanced routing has not been enabled therefore we cannot use this function");
290            throw new jmri.JmriException("Advanced routing has not been enabled therefore we cannot use this function");
291        }
292
293        if (log.isDebugEnabled()) {
294            try {
295                log.debug("faci {}", currentBlock.getDisplayName());
296                log.debug("next {}", nextBlock.getDisplayName());
297                log.debug("dest {}", destBlock.getDisplayName());
298                for (LayoutBlock dp : destBlockn1) {
299                    log.debug("dest + 1 {}", dp.getDisplayName());
300                }
301            } catch (java.lang.NullPointerException e) {
302
303            }
304        }
305        if ((destBlock != null) && (currentBlock != null) && (nextBlock != null)) {
306            if (!currentBlock.isRouteToDestValid(nextBlock.getBlock(), destBlock.getBlock())) {
307                log.debug("Route to dest not valid");
308                return false;
309            }
310            if (log.isDebugEnabled()) {
311                log.debug("dest {}", destBlock.getDisplayName());
312                /*if(destBlockn1!=null)
313                 log.debug("remote prot " + destBlockn1.getDisplayName());*/
314            }
315            if (!destBlockn1.isEmpty() && currentBlock == destBlockn1.get(0) && nextBlock == destBlock) {
316                log.debug("Our dest protecting block is our current block and our protecting block is the same as our destination block");
317                return false;
318            }
319            // Do a simple test to see if one is reachable from the other.
320            int proCount = 0;
321            int desCount = 0;
322            if (!destBlockn1.isEmpty()) {
323                desCount = currentBlock.getBlockHopCount(destBlock.getBlock(), nextBlock.getBlock());
324                proCount = currentBlock.getBlockHopCount(destBlockn1.get(0).getBlock(), nextBlock.getBlock());
325                if (log.isDebugEnabled()) {
326                    log.debug("dest {} protecting {}", desCount, proCount);
327                }
328            }
329
330            if ((proCount == -1) && (desCount == -1)) {
331                // The destination block and destBlock+1 are both directly connected
332                log.debug("Dest and dest+1 are directly connected");
333                return false;
334            }
335
336            if (proCount > desCount && (proCount - 1) == desCount) {
337                // The block that we are protecting should be one hop greater than the destination count.
338                log.debug("Protecting is one hop away from destination and therefore valid.");
339                return true;
340            }
341
342            /*Need to do a more advanced check in this case as the destBlockn1
343             could be reached via a different route and therefore have a smaller
344             hop count we need to therefore step through each block until we reach
345             the end.
346             The advanced check also covers cases where the route table is inconsistent.
347             We also need to perform a more advanced check if the destBlockn1
348             is null as this indicates that the destination signal mast is assigned
349             on an end bumper*/
350
351            if (pathMethod == Routing.SENSORTOSENSOR && destBlockn1.size() == 0) {
352                // Change the pathMethod to accept the NX sensor at the end bumper.
353                pathMethod = Routing.NONE;
354            }
355
356            List<LayoutBlock> blockList = getLayoutBlocks(currentBlock, destBlock, nextBlock, true, pathMethod); // Was MASTTOMAST
357            if (log.isDebugEnabled()) {
358                log.debug("checkValidDest blockList for {}", destBlock.getDisplayName());
359                blockList.forEach(blk -> log.debug("  block = {}", blk.getDisplayName()));
360            }
361            for (LayoutBlock dp : destBlockn1) {
362                log.debug("dp = {}", dp.getDisplayName());
363                if (blockList.contains(dp) && currentBlock != dp) {
364                    log.debug("Signal mast in the wrong direction");
365                    return false;
366                }
367            }
368                /*Work on the basis that if you get the blocks from source to dest
369                 then the dest+1 block should not be included*/
370            log.debug("Signal mast in the correct direction");
371            return true;
372
373        } else if (destBlock == null) {
374            throw new jmri.JmriException("Block in Destination Field returns as invalid");
375        } else if (currentBlock == null) {
376            throw new jmri.JmriException("Block in Facing Field returns as invalid");
377        } else if (nextBlock == null) {
378            throw new jmri.JmriException("Block in Protecting Field returns as invalid");
379        }
380        throw new jmri.JmriException("BlockIsNull");
381    }
382
383    /**
384     * This uses the layout editor to check if the destination location is
385     * reachable from the source location.<br>
386     * Only used internally to the class.
387     * <p>
388     * @param facing     Layout Block that is considered our first block
389     * @param protecting Layout Block that is considered first block +1
390     * @param dest       Layout Block that we want to get to
391     * @param pathMethod the path method
392     * @return true if valid
393     * @throws JmriException during nested getProtectingBlocks operation
394     */
395    private boolean checkValidDest(LayoutBlock facing, LayoutBlock protecting, FacingProtecting dest, Routing pathMethod) throws JmriException {
396        if (facing == null || protecting == null || dest == null) {
397            return false;
398        }
399        if (log.isDebugEnabled()) {
400            log.debug("facing : {} protecting : {} dest {}", protecting.getDisplayName(), dest.getBean().getDisplayName(), facing.getDisplayName());
401        }
402
403        // In this instance it doesn't matter what the destination protecting block is so we get the first
404        /*LayoutBlock destProt = null;
405         if(!dest.getProtectingBlocks().isEmpty()){
406         destProt = InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(dest.getProtectingBlocks().get(0));
407         // log.info(dest.getProtectingBlocks());
408         }*/
409         
410        List<LayoutBlock> destList = new ArrayList<>();
411
412         // may throw JmriException here
413        dest.getProtectingBlocks().forEach((b) -> {
414            destList.add(InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(b));
415        });
416        return checkValidDest(facing, protecting, InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(dest.getFacing()), destList, pathMethod);
417    }
418
419    /**
420     * This used in conjunction with the layout block routing protocol, to
421     * discover a clear path from a source layout block through to a destination
422     * layout block. By specifying the sourceLayoutBlock and
423     * protectingLayoutBlock or sourceLayoutBlock+1, a direction of travel can
424     * then be determined, eg east to west, south to north etc.
425     *
426     * @param sourceLayoutBlock      The layout block that we are starting from,
427     *                               can also be considered as the block facing
428     *                               a signal.
429     * @param destinationLayoutBlock The layout block that we want to get to
430     * @param protectingLayoutBlock  The next layout block connected to the
431     *                               source block, this can also be considered
432     *                               as the block being protected by a signal
433     * @param validateOnly           When set false, the system will not use
434     *                               layout blocks that are set as either
435     *                               reserved(useExtraColor set) or occupied, if
436     *                               it finds any then it will try to find an
437     *                               alternative path When set true, no block
438     *                               state checking is performed.
439     * @param pathMethod             Performs a check to see if any signal
440     *                               heads/masts are in the path, if there are
441     *                               then the system will try to find an
442     *                               alternative path. If set to NONE, then no
443     *                               checking is performed.
444     * @return an List of all the layoutblocks in the path.
445     * @throws jmri.JmriException if it can not find a valid path or the routing
446     *                            has not been enabled.
447     */
448    public List<LayoutBlock> getLayoutBlocks(LayoutBlock sourceLayoutBlock, LayoutBlock destinationLayoutBlock, LayoutBlock protectingLayoutBlock, boolean validateOnly, Routing pathMethod) throws jmri.JmriException {
449        lastErrorMessage = "Unknown Error Occured";
450        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
451        
452        if (!lbm.isAdvancedRoutingEnabled()) {
453            log.debug("Advanced routing has not been enabled therefore we cannot use this function");
454            throw new jmri.JmriException("Advanced routing has not been enabled therefore we cannot use this function");
455        }
456
457        int directionOfTravel = sourceLayoutBlock.getNeighbourDirection(protectingLayoutBlock);
458        Block currentBlock = sourceLayoutBlock.getBlock();
459
460        Block destBlock = destinationLayoutBlock.getBlock();
461        log.debug("Destination Block {} {}", destinationLayoutBlock.getDisplayName(), destBlock);
462
463        Block nextBlock = protectingLayoutBlock.getBlock();
464        if (log.isDebugEnabled()) {
465            log.debug("s:{} p:{} d:{}", sourceLayoutBlock.getDisplayName(), protectingLayoutBlock.getDisplayName(), destinationLayoutBlock.getDisplayName());
466        }
467        List<BlocksTested> blocksInRoute = new ArrayList<>();
468        blocksInRoute.add(new BlocksTested(sourceLayoutBlock));
469
470        if (!validateOnly) {
471            if (canLBlockBeUsed(protectingLayoutBlock)) {
472                blocksInRoute.add(new BlocksTested(protectingLayoutBlock));
473            } else {
474                lastErrorMessage = "Block we are protecting is already occupied or reserved";
475                log.debug("will throw {}", lastErrorMessage);
476                throw new jmri.JmriException(lastErrorMessage);
477            }
478            if (!canLBlockBeUsed(destinationLayoutBlock)) {
479                lastErrorMessage = "Destination Block is already occupied or reserved";
480                log.debug("will throw {}", lastErrorMessage);
481                throw new jmri.JmriException(lastErrorMessage);
482            }
483        } else {
484            blocksInRoute.add(new BlocksTested(protectingLayoutBlock));
485        }
486        if (destinationLayoutBlock == protectingLayoutBlock) {
487            List<LayoutBlock> returnBlocks = new ArrayList<>();
488            blocksInRoute.forEach((blocksTested) -> {
489                returnBlocks.add(blocksTested.getBlock());
490            });
491            return returnBlocks;
492        }
493
494        BlocksTested bt = blocksInRoute.get(blocksInRoute.size() - 1);
495
496        int ttl = 1;
497        List<Integer> offSet = new ArrayList<>();
498        while (ttl < ttlSize) { // value should be higher but low for test!
499            log.debug("===== Ttl value = {} ======", ttl);
500            log.debug("Looking for next block");
501            int nextBlockIndex = findBestHop(currentBlock, nextBlock, destBlock, directionOfTravel, offSet, validateOnly, pathMethod);
502            if (nextBlockIndex != -1) {
503                bt.addIndex(nextBlockIndex);
504                if (log.isDebugEnabled()) {
505                    log.debug("block index returned {} Blocks in route size {}", nextBlockIndex, blocksInRoute.size());
506                }
507                // Sets the old next block to be our current block.
508                LayoutBlock currentLBlock = InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(nextBlock);
509                if (currentLBlock == null) {
510                    log.error("Unable to get block :{}: from instancemanager", nextBlock);
511                    continue;
512                }
513                offSet.clear();
514
515                directionOfTravel = currentLBlock.getRouteDirectionAtIndex(nextBlockIndex);
516
517                //allow for routes that contain more than one occurrence of a block in a route to allow change of direction.
518                Block prevBlock = currentBlock;
519                LayoutBlock prevLBlock = InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(prevBlock);
520                currentBlock = nextBlock;
521                nextBlock = currentLBlock.getRouteNextBlockAtIndex(nextBlockIndex);
522                LayoutBlock nextLBlock = InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(nextBlock);
523                if (log.isDebugEnabled()) {
524                    log.debug("Blocks in route size {}", blocksInRoute.size());
525                    log.debug("next: {} dest: {}", nextBlock.getDisplayName(), destBlock.getDisplayName());
526                }
527                if (nextBlock == currentBlock) {
528                    nextBlock = currentLBlock.getRouteDestBlockAtIndex(nextBlockIndex);
529                    log.debug("the next block to our destination we are looking for is directly connected to this one");
530                } else if (!((protectingLayoutBlock == prevLBlock)&&(protectingLayoutBlock == nextLBlock))) {
531                    if (nextLBlock != null) {
532                        log.debug("Add block {}", nextLBlock.getDisplayName());
533                    }
534                    bt = new BlocksTested(nextLBlock);
535                    blocksInRoute.add(bt);
536                }
537                if (nextBlock == destBlock) {
538                    if (!validateOnly && !checkForLevelCrossing(destinationLayoutBlock)) {
539                        throw new jmri.JmriException("Destination block is in conflict on a crossover");
540                    }
541                    List<LayoutBlock> returnBlocks = new ArrayList<>();
542                    blocksInRoute.forEach((blocksTested) -> {
543                        returnBlocks.add(blocksTested.getBlock());
544                    });
545                    returnBlocks.add(destinationLayoutBlock);
546                    if (log.isDebugEnabled()) {
547                        log.debug("Adding destination Block {}", destinationLayoutBlock.getDisplayName());
548                        log.debug("arrived at destination block");
549                        log.debug("{} Return as Long", sourceLayoutBlock.getDisplayName());
550                        returnBlocks.forEach((returnBlock) -> {
551                            log.debug("  return block {}", returnBlock.getDisplayName());
552                        });
553                        log.debug("Finished List");
554                    }
555                    return returnBlocks;
556                }
557            } else {
558                //-1 is returned when there are no more valid besthop valids found
559                // Block index is -1, so we need to go back a block and find another way.
560
561                // So we have gone back as far as our starting block so we better return.
562                int birSize = blocksInRoute.size();
563                log.debug("block in route size {}", birSize);
564                if (birSize <= 2) {
565                    log.debug("drop out here with ttl");
566                    ttl = ttlSize + 1;
567                } else {
568                    if (log.isDebugEnabled()) {
569                        for (int t = 0; t < blocksInRoute.size(); t++) {
570                            log.debug("index {} block {}", t, blocksInRoute.get(t).getBlock().getDisplayName());
571                        }
572                        log.debug("To remove last block {}", blocksInRoute.get(birSize - 1).getBlock().getDisplayName());
573                    }
574
575                    currentBlock = blocksInRoute.get(birSize - 3).getBlock().getBlock();
576                    nextBlock = blocksInRoute.get(birSize - 2).getBlock().getBlock();
577                    offSet = blocksInRoute.get(birSize - 2).getTestedIndexes();
578                    bt = blocksInRoute.get(birSize - 2);
579                    blocksInRoute.remove(birSize - 1);
580                    ttl--;
581                }
582            }
583            ttl++;
584        }
585        if (ttl == ttlSize) {
586            lastErrorMessage = "ttlExpired";
587        }
588        // we exited the loop without either finding the destination or we had error.
589        throw new jmri.JmriException(lastErrorMessage);
590    }
591
592    static class BlocksTested {
593
594        LayoutBlock block;
595        List<Integer> indexNumber = new ArrayList<>();
596
597        BlocksTested(LayoutBlock block) {
598            this.block = block;
599        }
600
601        void addIndex(int x) {
602            indexNumber.add(x);
603        }
604
605        int getLastIndex() {
606            return indexNumber.get(indexNumber.size() - 1); // get the last one in the list
607        }
608
609        List<Integer> getTestedIndexes() {
610            return indexNumber;
611        }
612
613        LayoutBlock getBlock() {
614            return block;
615        }
616    }
617
618    private boolean canLBlockBeUsed(LayoutBlock lBlock) {
619        if (lBlock == null) {
620            return true;
621        }
622        if (lBlock.getUseExtraColor()) {
623            return false;
624        }
625        if (lBlock.getBlock().getPermissiveWorking()) {
626            return true;
627        }
628        return (lBlock.getState() != Block.OCCUPIED);
629    }
630
631    String lastErrorMessage = "Unknown Error Occured";
632
633    // We need to take into account if the returned block has a signalmast attached.
634    int findBestHop(final Block preBlock, final Block currentBlock, Block destBlock, int direction, List<Integer> offSet, boolean validateOnly, Routing pathMethod) {
635        int result = 0;
636
637        LayoutBlock currentLBlock = InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(currentBlock);
638        if (currentLBlock == null) {
639            return -1;
640        }
641        List<Integer> blkIndexTested = new ArrayList<>(5);
642        if (log.isDebugEnabled()) {
643            log.debug("In find best hop current {} previous {}", currentLBlock.getDisplayName(), preBlock.getDisplayName());
644        }
645        Block block;
646        while (result != -1) {
647            if (currentBlock == preBlock) {
648                // Basically looking for the connected block, which there should only be one of!
649                log.debug("At get ConnectedBlockRoute");
650                result = currentLBlock.getConnectedBlockRouteIndex(destBlock, direction);
651                log.trace("getConnectedBlockRouteIndex returns result {} with destBlock {}, direction {}", result, destBlock, direction);
652            } else {
653                if (log.isDebugEnabled()) {
654                    log.debug("Off Set {}", offSet);
655                }
656                result = currentLBlock.getNextBestBlock(preBlock, destBlock, offSet, Metric.METRIC);
657                log.trace("getNextBestBlock returns result {} with preBlock {}, destBlock {}", result, preBlock, destBlock);
658            }
659            if (result != -1) {
660                block = currentLBlock.getRouteNextBlockAtIndex(result);
661                LayoutBlock lBlock = InstanceManager.getDefault(LayoutBlockManager.class).getLayoutBlock(block);
662
663                Block blocktoCheck = block;
664                if (block == currentBlock) {
665                    log.debug("current block matches returned block therefore the next block is directly connected");
666                    blocktoCheck = destBlock;
667                }
668
669                if ((block == currentBlock) && (currentLBlock.getThroughPathIndex(preBlock, destBlock) == -1)) {
670                    lastErrorMessage = "block " + block.getDisplayName() + " is directly attached, however the route to the destination block " + destBlock.getDisplayName() + " can not be directly used";
671                    log.debug("continue after {}", lastErrorMessage);
672                } else if ((validateOnly) || ((checkForDoubleCrossover(preBlock, currentLBlock, blocktoCheck) && checkForLevelCrossing(currentLBlock)) && canLBlockBeUsed(lBlock))) {
673                    if (log.isDebugEnabled()) {
674                        log.debug("{} not occupied & not reserved but we need to check if the anchor point between the two contains a signal or not", block.getDisplayName());
675                        log.debug("  current {} {}", currentBlock.getDisplayName(), block.getDisplayName());
676                    }
677
678                    jmri.NamedBean foundBean = null;
679                    /* We change the logging level to fatal in the layout block manager as we are testing to make sure that no signalhead/mast exists
680                     this would generate an error message that is expected.*/
681                    MDC.put("loggingDisabled", LayoutBlockManager.class.getName());
682                    log.trace(" current pathMethod is {}", pathMethod, new Exception("traceback"));
683                    switch (pathMethod) {
684                        case MASTTOMAST:
685                            foundBean = InstanceManager.getDefault(LayoutBlockManager.class).getFacingSignalMast(currentBlock, blocktoCheck);
686                            break;
687                        case HEADTOHEAD:
688                            foundBean = InstanceManager.getDefault(LayoutBlockManager.class).getFacingSignalHead(currentBlock, blocktoCheck);
689                            break;
690                        case SENSORTOSENSOR:
691                            foundBean = InstanceManager.getDefault(LayoutBlockManager.class).getFacingSensor(currentBlock, blocktoCheck, null);
692                            break;
693                        case NONE:
694                            break;
695                        default:
696                            foundBean = InstanceManager.getDefault(LayoutBlockManager.class).getFacingNamedBean(currentBlock, blocktoCheck, null);
697                            break;
698                    }
699                    MDC.remove("loggingDisabled");
700                    if (foundBean == null) {
701                        log.debug("No object found so okay to return");
702                        return result;
703                    } else {
704                        lastErrorMessage = "Signal " + foundBean.getDisplayName() + " already exists between blocks " + currentBlock.getDisplayName() + " and " + blocktoCheck.getDisplayName() + " in the same direction on this path";
705                        log.debug("continue after {}", lastErrorMessage);
706                    }
707                } else {
708                    lastErrorMessage = "block " + block.getDisplayName() + " found not to be not usable";
709                    log.debug("continue after {}", lastErrorMessage);
710                }
711                if (blkIndexTested.contains(result)) {
712                    lastErrorMessage = ("No valid free path found");
713                    return -1;
714                }
715                blkIndexTested.add(result);
716                offSet.add(result);
717            } else {
718                log.debug("At this point the getNextBextBlock() has returned a -1");
719            }
720        }
721        return -1;
722    }
723
724    private boolean checkForDoubleCrossover(Block prevBlock, LayoutBlock curBlock, Block nextBlock) {
725        LayoutEditor le = curBlock.getMaxConnectedPanel();
726        ConnectivityUtil ct = le.getConnectivityUtil();
727        List<LayoutTrackExpectedState<LayoutTurnout>> turnoutList = ct.getTurnoutList(curBlock.getBlock(), prevBlock, nextBlock);
728        for (LayoutTrackExpectedState<LayoutTurnout> layoutTurnoutLayoutTrackExpectedState : turnoutList) {
729            LayoutTurnout lt = layoutTurnoutLayoutTrackExpectedState.getObject();
730            if (lt.getTurnoutType() == LayoutTurnout.TurnoutType.DOUBLE_XOVER) {
731                if (layoutTurnoutLayoutTrackExpectedState.getExpectedState() == jmri.Turnout.THROWN) {
732                    jmri.Turnout t = lt.getTurnout();
733                    if (t.getKnownState() == jmri.Turnout.THROWN) {
734                        if (lt.getLayoutBlock() == curBlock || lt.getLayoutBlockC() == curBlock) {
735                            if (!canLBlockBeUsed(lt.getLayoutBlockB()) && !canLBlockBeUsed(lt.getLayoutBlockD())) {
736                                return false;
737                            }
738                        } else if (lt.getLayoutBlockB() == curBlock || lt.getLayoutBlockD() == curBlock) {
739                            if (!canLBlockBeUsed(lt.getLayoutBlock()) && !canLBlockBeUsed(lt.getLayoutBlockC())) {
740                                return false;
741                            }
742                        }
743                    }
744                }
745            }
746        }
747        return true;
748    }
749
750    private boolean checkForLevelCrossing(LayoutBlock curBlock) {
751        LayoutEditor lay = curBlock.getMaxConnectedPanel();
752        for (LevelXing lx : lay.getLevelXings()) {
753            if (lx.getLayoutBlockAC() == curBlock
754                    || lx.getLayoutBlockBD() == curBlock) {
755                if ((lx.getLayoutBlockAC() != null)
756                        && (lx.getLayoutBlockBD() != null)
757                        && (lx.getLayoutBlockAC() != lx.getLayoutBlockBD())) {
758                    if (lx.getLayoutBlockAC() == curBlock) {
759                        if (!canLBlockBeUsed(lx.getLayoutBlockBD())) {
760                            return false;
761                        }
762                    } else if (lx.getLayoutBlockBD() == curBlock) {
763                        if (!canLBlockBeUsed(lx.getLayoutBlockAC())) {
764                            return false;
765                        }
766                    }
767                }
768            }
769        }
770        return true;
771    }
772
773    /**
774     * Discovers valid pairs of beans type T assigned to a layout editor. If no
775     * bean type is provided, then either SignalMasts or Sensors are discovered
776     * If no editor is provided, then all editors are considered
777     *
778     * @param editor     the layout editor panel
779     * @param T          the type
780     * @param pathMethod Determine whether or not we should reject pairs if
781     *                   there are other beans in the way. Constant values of
782     *                   NONE, ANY, MASTTOMAST, HEADTOHEAD
783     * @return the valid pairs
784     */
785    public HashMap<NamedBean, List<NamedBean>> discoverValidBeanPairs(LayoutEditor editor, Class<?> T, Routing pathMethod) {
786        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
787        HashMap<NamedBean, List<NamedBean>> retPairs = new HashMap<>();
788        List<FacingProtecting> beanList = generateBlocksWithBeans(editor, T);
789        beanList.forEach((fp) -> {
790            fp.getProtectingBlocks().stream().map((block) -> {
791                if (log.isDebugEnabled()) {
792                    try {
793                        log.debug("\nSource {}", fp.getBean().getDisplayName());
794                        log.debug("facing {}", fp.getFacing().getDisplayName());
795                        log.debug("protecting {}", block.getDisplayName());
796                    } catch (java.lang.NullPointerException e) {
797                        // Can be considered normal if the signalmast is assigned to an end bumper.
798                    }
799                }
800                return block;
801            }).forEachOrdered((block) -> {
802                LayoutBlock lFacing = lbm.getLayoutBlock(fp.getFacing());
803                LayoutBlock lProtecting = lbm.getLayoutBlock(block);
804                NamedBean source = fp.getBean();
805                try {
806                    retPairs.put(source, discoverPairDest(source, lProtecting, lFacing, beanList, pathMethod));
807                } catch (JmriException ex) {
808                    log.error("exception in retPairs.put", ex);
809                }
810            });
811        });
812        return retPairs;
813    }
814
815    /**
816     * Returns a list of valid destination beans reachable from a given source
817     * bean.
818     *
819     * @param source     Either a SignalMast or Sensor
820     * @param editor     The layout editor that the source is located on, if
821     *                   null, then all editors are considered
822     * @param T          The class of the remote destination, if null, then both
823     *                   SignalMasts and Sensors are considered
824     * @param pathMethod Determine whether or not we should reject pairs if
825     *                   there are other beans in the way. Constant values of
826     *                   NONE, ANY, MASTTOMAST, HEADTOHEAD
827     * @return A list of all reachable NamedBeans
828     * @throws jmri.JmriException occurring during nested readAll operation
829     */
830    public List<NamedBean> discoverPairDest(NamedBean source, LayoutEditor editor, Class<?> T, Routing pathMethod) throws JmriException {
831        if (log.isDebugEnabled()) {
832            log.debug("discover pairs from source {}", source.getDisplayName());
833        }
834        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
835        LayoutBlock lFacing = lbm.getFacingBlockByNamedBean(source, editor);
836        List<LayoutBlock> lProtecting = lbm.getProtectingBlocksByNamedBean(source, editor);
837        List<NamedBean> ret = new ArrayList<>();
838        List<FacingProtecting> beanList = generateBlocksWithBeans(editor, T);
839        
840        // may throw JmriException here
841        for (LayoutBlock lb : lProtecting) {
842            ret.addAll(discoverPairDest(source, lb, lFacing, beanList, pathMethod));
843        }
844        return ret;
845    }
846
847    List<NamedBean> discoverPairDest(NamedBean source, LayoutBlock lProtecting, LayoutBlock lFacing, List<FacingProtecting> blockList, Routing pathMethod) throws JmriException {
848        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
849        if (!lbm.isAdvancedRoutingEnabled()) {
850            throw new JmriException("advanced routing not enabled");
851        }
852        if (!lbm.routingStablised()) {
853            throw new JmriException("routing not stabilised");
854        }
855        List<NamedBean> validDestBean = new ArrayList<>();
856        for (FacingProtecting facingProtecting : blockList) {
857            if (facingProtecting.getBean() != source) {
858                NamedBean destObj = facingProtecting.getBean();
859                if (log.isDebugEnabled()) {
860                    log.debug("looking for pair {} {}", source.getDisplayName(), destObj.getDisplayName());
861                }
862                try {
863                    if (checkValidDest(lFacing, lProtecting, facingProtecting, pathMethod)) {
864                        if (log.isDebugEnabled()) {
865                            log.debug("Valid pair {} {}", source.getDisplayName(), destObj.getDisplayName());
866                        }
867                        LayoutBlock ldstBlock = lbm.getLayoutBlock(facingProtecting.getFacing());
868                        try {
869                            List<LayoutBlock> lblks = getLayoutBlocks(lFacing, ldstBlock, lProtecting, true, pathMethod);
870                            if (log.isDebugEnabled()) {
871                                log.debug("Adding block {} to paths, current size {}", destObj.getDisplayName(), lblks.size());
872                            }
873                            validDestBean.add(destObj);
874                        } catch (JmriException e) {  // Considered normal if route not found.
875                            log.debug("not a valid route through {} - {}", source.getDisplayName(), destObj.getDisplayName());
876                        }
877                    }
878                } catch (JmriException ex) {
879                    log.debug("caught exception in discoverPairsDest", ex);
880                }
881            }
882        }
883        return validDestBean;
884    }
885
886    List<FacingProtecting> generateBlocksWithBeans(LayoutEditor editor, Class<?> T) {
887        LayoutBlockManager lbm = InstanceManager.getDefault(LayoutBlockManager.class);
888        List<FacingProtecting> beanList = new ArrayList<>();
889
890        for (LayoutBlock curLblk : lbm.getNamedBeanSet()) {
891            Block curBlk = curLblk.getBlock();
892            LayoutEditor useEdit = editor;
893            if (editor == null) {
894                useEdit = curLblk.getMaxConnectedPanel();
895            }
896            if (curBlk != null) {
897                int noNeigh = curLblk.getNumberOfNeighbours();
898                for (int x = 0; x < noNeigh; x++) {
899                    Block blk = curLblk.getNeighbourAtIndex(x);
900                    List<Block> proBlk = new ArrayList<>();
901                    NamedBean bean = null;
902                    if (T == null) {
903                        proBlk.add(blk);
904                        bean = lbm.getFacingNamedBean(curBlk, blk, useEdit);
905                    } else if (T.equals(SignalMast.class)) {
906                        bean = lbm.getFacingSignalMast(curBlk, blk, useEdit);
907                        if (bean != null) {
908                            if (log.isDebugEnabled()) {
909                                log.debug("Get list of protecting blocks for {} facing {}", bean.getDisplayName(), curBlk.getDisplayName());
910                            }
911                            List<LayoutBlock> lProBlk = lbm.getProtectingBlocksByNamedBean(bean, useEdit);
912                            for (LayoutBlock lb : lProBlk) {
913                                if (lb != null) {
914                                    proBlk.add(lb.getBlock());
915                                }
916                            }
917                        }
918                    } else if (T.equals(Sensor.class)) {
919                        bean = lbm.getFacingSensor(curBlk, blk, useEdit);
920                        if (bean != null) {
921                            if (log.isDebugEnabled()) {
922                                log.debug("Get list of protecting blocks for {}", bean.getDisplayName());
923                            }
924                            List<LayoutBlock> lProBlk = lbm.getProtectingBlocksByNamedBean(bean, useEdit);
925                            for (LayoutBlock lb : lProBlk) {
926                                if (lb != null) {
927                                    proBlk.add(lb.getBlock());
928                                }
929                            }
930                        }
931                    } else {
932                        log.error("Past bean type is unknown {}", T);
933                    }
934                    if (bean != null) {
935                        FacingProtecting toadd = new FacingProtecting(curBlk, proBlk, bean);
936                        boolean found = false;
937                        for (FacingProtecting fp : beanList) {
938                            if (fp.equals(toadd)) {
939                                found = true;
940                                break;
941                            }
942                        }
943                        if (!found) {
944                            beanList.add(toadd);
945                        }
946                    }
947                }
948                if (noNeigh == 1) {
949                    NamedBean bean = null;
950                    if (log.isDebugEnabled()) {
951                        log.debug("We have a dead end {}", curBlk.getDisplayName());
952                    }
953                    if (T == null) {
954                        bean = lbm.getNamedBeanAtEndBumper(curBlk, useEdit);
955                    } else if (T.equals(SignalMast.class)) {
956                        bean = lbm.getSignalMastAtEndBumper(curBlk, useEdit);
957                    } else if (T.equals(Sensor.class)) {
958                        bean = lbm.getSensorAtEndBumper(curBlk, useEdit);
959                    } else {
960                        log.error("Past bean type is unknown {}", T);
961                    }
962                    if (bean != null) {
963                        FacingProtecting toadd = new FacingProtecting(curBlk, null, bean);
964                        boolean found = false;
965                        for (FacingProtecting fp : beanList) {
966                            if (fp.equals(toadd)) {
967                                found = true;
968                                break;
969                            }
970                        }
971                        if (!found) {
972                            beanList.add(toadd);
973                        }
974                    }
975                }
976            }
977        }
978        return beanList;
979    }
980
981    static class FacingProtecting {
982
983        Block facing;
984        List<Block> protectingBlocks;
985        NamedBean bean;
986
987        FacingProtecting(Block facing, List<Block> protecting, NamedBean bean) {
988            this.facing = facing;
989            if (protecting == null) {
990                this.protectingBlocks = new ArrayList<>(0);
991            } else {
992                this.protectingBlocks = protecting;
993            }
994            this.bean = bean;
995        }
996
997        Block getFacing() {
998            return facing;
999        }
1000
1001        List<Block> getProtectingBlocks() {
1002            return protectingBlocks;
1003        }
1004
1005        NamedBean getBean() {
1006            return bean;
1007        }
1008
1009        @Override
1010        public boolean equals(Object obj) {
1011
1012            if (obj == this) {
1013                return true;
1014            }
1015            if (obj == null) {
1016                return false;
1017            }
1018
1019            if (!(getClass() == obj.getClass())) {
1020                return false;
1021            } else {
1022                FacingProtecting tmp = (FacingProtecting) obj;
1023                if (tmp.getBean() != this.bean) {
1024                    return false;
1025                }
1026                if (tmp.getFacing() != this.facing) {
1027                    return false;
1028                }
1029                if (!tmp.getProtectingBlocks().equals(this.protectingBlocks)) {
1030                    return false;
1031                }
1032            }
1033            return true;
1034        }
1035
1036        @Override
1037        public int hashCode() {
1038            int hash = 7;
1039            hash = 37 * hash + (this.bean != null ? this.bean.hashCode() : 0);
1040            hash = 37 * hash + (this.facing != null ? this.facing.hashCode() : 0);
1041            hash = 37 * hash + (this.protectingBlocks != null ? this.protectingBlocks.hashCode() : 0);
1042            return hash;
1043        }
1044    }
1045
1046    private final static Logger log
1047            = LoggerFactory.getLogger(LayoutBlockConnectivityTools.class);
1048}