commit 91fd3fa6eb8a9076f9ed820a8d77cfc62ed4d6ba
Author: Vaclav Honzik <vaclavhonzik98@gmail.com>
Date:   Fri May 6 22:17:42 2022 +0200

    Nonrecursive algorithm for path building + path rendering on map
    
    re #9629

diff --git a/frontend/src/features/TrackingTool/TrackingTool.tsx b/frontend/src/features/TrackingTool/TrackingTool.tsx
index 8569b61..0fe1ad3 100644
--- a/frontend/src/features/TrackingTool/TrackingTool.tsx
+++ b/frontend/src/features/TrackingTool/TrackingTool.tsx
@@ -8,7 +8,7 @@ import {
     Stack,
     Typography,
 } from '@mui/material'
-import { Fragment, useState } from 'react'
+import { Fragment, useEffect, useState } from 'react'
 import AddIcon from '@mui/icons-material/Add'
 import { MapContainer, Marker, Polyline, Popup, TileLayer } from 'react-leaflet'
 import mapConfig from '../../config/mapConfig'
@@ -19,61 +19,85 @@ import L from 'leaflet'
 import DeleteIcon from '@mui/icons-material/Delete'
 import { PathDto } from '../../swagger/data-contracts'
 import { formatHtmlStringToReactDom } from '../../utils/formatting/HtmlUtils'
+import buildPathVariants, { PathVariant } from './buildPathVariants'
 
 // Page with tracking tool
 const TrackingTool = () => {
     // Path response from the API
     const [pathDto, setPathDto] = useState<PathDto | undefined>(undefined)
 
-    const createDummyPathCoords = () => {
-        // Sample dummy path to display
-        const dummyPath = []
-        for (let i = 0; i < 10; i += 1) {
-            dummyPath.push({
-                latitude:
-                    mapConfig.defaultCoordinates[0] +
-                    i * 0.1 +
-                    Math.random() * 0.1,
-                longitude:
-                    mapConfig.defaultCoordinates[1] +
-                    i * 0.1 +
-                    Math.random() * 0.1,
-            })
-        }
-        return dummyPath
-    }
+    // Whether the path variants are building
+    const [buildingPathVariants, setBuildingPathVariants] =
+        useState<boolean>(false)
 
-    const createDummyPath = () => {
-        const coords = createDummyPathCoords()
-        const polylines: any[] = []
+    // List of all computed path variants
+    const [pathVariants, setPathVariants] = useState<PathVariant[] | undefined>(
+        undefined
+    )
 
-        if (coords.length < 2) {
-            return []
-        }
+    // List of all rendered paths to display
+    const [renderedPaths, setRenderedPaths] = useState<any[]>([])
 
-        for (let i = 0; i < coords.length - 1; i += 1) {
-            polylines.push(
-                <TextPath
-                    positions={[
-                        [coords[i].latitude, coords[i].longitude],
-                        [coords[i + 1].latitude, coords[i + 1].longitude],
-                    ]}
-                    text="►"
-                    attributes={{
-                        'font-size': 25,
-                        fill: 'blue',
-                    }}
-                    repeat
-                    center
-                    weight={10}
-                ></TextPath>
-            )
-        }
+    const [mapCenter, setMapCenter] = useState<number[]>([
+        mapConfig.defaultCoordinates[0],
+        mapConfig.defaultCoordinates[1],
+    ])
+
+    // Returns tuple of average latitude and longitude
+    const calculateMapCenter = (pathVariant: PathVariant) => [
+        pathVariant
+            .map((item) => item.latitude ?? 0)
+            .reduce((a, b) => a + b, 0) / pathVariant.length,
+        pathVariant
+            .map((item) => item.longitude ?? 0)
+            .reduce((a, b) => a + b, 0) / pathVariant.length,
+    ]
 
-        return [polylines, coords]
-    }
+    useEffect(() => {
+        if (!pathDto) {
+            return
+        }
 
-    const [polylines, coords] = createDummyPath()
+        setBuildingPathVariants(true)
+        buildPathVariants(pathDto).then((pathVariants) => {
+            setPathVariants(pathVariants)
+            setBuildingPathVariants(false)
+            const paths: any[] = []
+            let first = true
+            pathVariants?.forEach((pathVariant) => {
+                if (first) {
+                    setMapCenter(calculateMapCenter(pathVariant))
+                }
+                for (let i = 0; i < pathVariant.length - 1; i++) {
+                    paths.push(
+                        <TextPath
+                            positions={[
+                                [
+                                    pathVariant[i].latitude,
+                                    pathVariant[i].longitude,
+                                ],
+                                [
+                                    pathVariant[i + 1].latitude,
+                                    pathVariant[i + 1].longitude,
+                                ],
+                            ]}
+                            text="►"
+                            attributes={{
+                                'font-size': 25,
+                                fill: first ? 'blue' : 'gray',
+                            }}
+                            repeat
+                            center
+                            weight={10}
+                        />
+                    )
+                }
+                first = false
+            })
+            console.log(paths)
+            setRenderedPaths(paths)
+        })
+    }, [pathDto])
 
     return (
         <Fragment>
@@ -146,10 +170,7 @@ const TrackingTool = () => {
                     }}
                 >
                     <MapContainer
-                        center={[
-                            mapConfig.defaultCoordinates[0],
-                            mapConfig.defaultCoordinates[1],
-                        ]}
+                        center={[mapCenter[0], mapCenter[1]]}
                         zoom={mapConfig.defaultZoom}
                         style={{ height: '100%', minHeight: '100%' }}
                     >
@@ -157,10 +178,7 @@ const TrackingTool = () => {
                             attribution={mapConfig.attribution}
                             url={mapConfig.url}
                         />
-                        {coords.map(({ latitude, longitude }, idx) => (
-                            <Marker position={[latitude, longitude]} />
-                        ))}
-                        {polylines}
+                        {renderedPaths}
                     </MapContainer>
                 </Grid>
             </Grid>
diff --git a/frontend/src/features/TrackingTool/buildPathVariants.ts b/frontend/src/features/TrackingTool/buildPathVariants.ts
new file mode 100644
index 0000000..09a8111
--- /dev/null
+++ b/frontend/src/features/TrackingTool/buildPathVariants.ts
@@ -0,0 +1,30 @@
+// Business logic for tracking tool
+
+import { CatalogItemDto, PathDto } from '../../swagger/data-contracts'
+
+// For more comprehensive code alias CatalogItemDto[] as path variant
+export type PathVariant = CatalogItemDto[]
+
+const cartesianProduct = (sets: CatalogItemDto[][]): CatalogItemDto[][] =>
+    sets.reduce<CatalogItemDto[][]>(
+        (results, ids) =>
+            results
+                .map((result) => ids.map((id) => [...result, id]))
+                .reduce((nested, result) => [...nested, ...result]),
+        [[]]
+    )
+
+export const buildPathVariants = async (pathDto: PathDto): Promise<PathVariant[]> => {
+    if (!pathDto.foundCatalogItems) {
+        return []
+    }
+
+    const catalogItems = pathDto.foundCatalogItems
+    if (catalogItems.length === 1) {
+        return catalogItems
+    }
+
+    return cartesianProduct(catalogItems)
+}
+
+export default buildPathVariants
diff --git a/frontend/src/features/TrackingTool/trackingTool.ts b/frontend/src/features/TrackingTool/trackingTool.ts
deleted file mode 100644
index 32a7e2b..0000000
--- a/frontend/src/features/TrackingTool/trackingTool.ts
+++ /dev/null
@@ -1,53 +0,0 @@
-// Business logic for tracking tool
-
-import { CatalogItemDto, PathDto } from '../../swagger/data-contracts'
-
-// For more comprehensive code alias CatalogItemDto[] as path variant
-export type PathVariant = CatalogItemDto[]
-
-const getPathItemVariants = (
-    catalogItems: CatalogItemDto[][],
-    currentIdx: number,
-    itemIdx: number
-): PathVariant[] => {
-    if (currentIdx < 0) {
-        return []
-    }
-
-    const variants: PathVariant[] = []
-    const nextIdx = currentIdx - 1
-    const currentItem = catalogItems[currentIdx][itemIdx]
-    for (let i = 0; i < catalogItems[nextIdx].length; i += 1) {
-        const itemPaths = getPathItemVariants(catalogItems, nextIdx, i)
-        // Push current item at the end
-        itemPaths.forEach((variant) => {
-            variant.push(currentItem)
-        })
-    }
-
-    return variants
-}
-
-const buildPathVariants = (pathDto: PathDto) => {
-    const catalogItems = pathDto.foundCatalogItems
-    const pathVariants: PathVariant[] = []
-    // If there are no items or list is empty return
-    if (!catalogItems || catalogItems.length === 0) {
-        return []
-    }
-
-    if (catalogItems.length === 1) {
-        return catalogItems[0]
-    }
-
-    // Get items in the last idx since we start from the end
-    const currentIdx = catalogItems.length - 1
-    // For each of the items get all path variants
-    for (let i = 0; i < catalogItems[currentIdx].length; i += 1) {
-        pathVariants.concat(getPathItemVariants(catalogItems, currentIdx, i))
-    }
-
-    return pathVariants
-}
-
-export default buildPathVariants
