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