{"version":3,"file":"index.cjs","sources":["../src/utils.ts","../src/find-shortest-path.ts","../src/index.ts"],"sourcesContent":["import { IAspectRatioList } from './types';\n\nexport const calcLimitNodeSearch = (\n containerWidth: number,\n targetRowHeight: number,\n) =>\n containerWidth > 500\n ? Math.round(containerWidth / targetRowHeight / 1.5) + 8\n : 5;\n\ninterface IGetCommonHeightOptions {\n aspectRatioList: IAspectRatioList;\n containerWidth: number;\n horizontalBoxSpacing: number;\n}\n\nexport const calcCommonHeight = ({\n aspectRatioList,\n containerWidth,\n horizontalBoxSpacing,\n}: IGetCommonHeightOptions) => {\n const rowWidth =\n containerWidth - aspectRatioList.length * horizontalBoxSpacing;\n\n const totalAspectRatio = aspectRatioList.reduce(\n (acc, ratio) => acc + ratio,\n 0,\n );\n // return Math.ceil(rowWidth / totalAspectRatio);\n return rowWidth / totalAspectRatio;\n};\n\ninterface ICostOptions {\n aspectRatioList: IAspectRatioList;\n start: number;\n end: number;\n containerWidth: number;\n targetRowHeight: number;\n horizontalBoxSpacing: number;\n}\n\n// calculate the cost of breaking at this node (edge weight)\nexport const calcCost = ({\n aspectRatioList,\n start,\n end,\n containerWidth,\n targetRowHeight,\n horizontalBoxSpacing,\n}: ICostOptions) => {\n const row = aspectRatioList.slice(start, end);\n const commonHeight = calcCommonHeight({\n aspectRatioList: row,\n containerWidth,\n horizontalBoxSpacing,\n });\n return Math.pow(Math.abs(commonHeight - targetRowHeight), 2);\n};\n","import TinyQueue from 'tinyqueue';\n\nimport { IGraphBuilder, INode } from './types';\n\nconst buildPrecedentsMap = (\n graphBuilder: IGraphBuilder,\n startNode: number,\n endNode: number,\n) => {\n // store the previous vertex of the shortest path of arrival\n const precedentsMap = new Map();\n\n // store nodes already visited\n const visited = new Set();\n\n // store/update only the shortest edge weights measured\n // the purpose of this is object is constant time lookup vs. binary heap lookup O(n)\n const storedShortestPaths: Record = {};\n storedShortestPaths[startNode] = 0;\n\n // priority queue of ALL nodes and storedShortestPaths\n // don't bother to delete them because it's faster to look at visited?\n const pQueue = new TinyQueue(undefined, (a, b) => a.weight - b.weight);\n pQueue.push({ id: startNode, weight: 0 });\n\n while (pQueue.length !== 0) {\n // pop node with shortest total weight from start node\n const shortestNode = pQueue.pop();\n if (!shortestNode) continue;\n\n const shortestNodeId = shortestNode.id;\n\n // if already visited, continue\n if (visited.has(shortestNodeId)) continue;\n\n // visit neighboring nodes\n const neighboringNodes = graphBuilder(shortestNodeId) || new Map();\n visited.add(shortestNodeId);\n\n // meet the neighbors, looking for shorter paths\n for (const [neighbor, neighborValue] of neighboringNodes) {\n // weight of path from startNode to this neighbor\n const newTotalWeight = shortestNode.weight + neighborValue;\n\n // if this is the first time meeting the neighbor OR if the new total weight from\n // start node to this neighbor node is greater than the old weight path, update it,\n // and update precedent node\n if (\n typeof storedShortestPaths[neighbor] === 'undefined' ||\n storedShortestPaths[neighbor] > newTotalWeight\n ) {\n storedShortestPaths[neighbor] = newTotalWeight;\n pQueue.push({ id: neighbor, weight: newTotalWeight });\n precedentsMap.set(neighbor, shortestNodeId);\n }\n }\n }\n\n if (typeof storedShortestPaths[endNode] === 'undefined') {\n throw new Error(`There is no path from ${startNode} to ${endNode}`);\n }\n\n return precedentsMap;\n};\n\n// build the route from precedent node vertices\nconst getPathFromPrecedentsMap = (\n precedentsMap: Map,\n endNode: number,\n) => {\n let n = endNode;\n const nodes = [n];\n while (n) {\n n = precedentsMap.get(n)!;\n nodes.push(n);\n }\n return nodes.reverse();\n};\n\n// build the precedentsMap and find the shortest path from it\nexport const findShortestPath = (\n graph: IGraphBuilder,\n startNode: number,\n endNode: number,\n) => {\n const precedentsMap = buildPrecedentsMap(graph, startNode, endNode);\n\n return getPathFromPrecedentsMap(precedentsMap, endNode);\n};\n","export * from './types';\n\nimport {\n IPhotoFlexLayoutOptions,\n IAspectRatioList,\n ILayoutBox,\n IPhotoFlexLayoutResult,\n} from './types';\nimport { calcLimitNodeSearch, calcCost, calcCommonHeight } from './utils';\nimport { findShortestPath } from './find-shortest-path';\n\ninterface IMakeGetNeighborsOptions {\n aspectRatioList: IAspectRatioList;\n containerWidth: number;\n targetRowHeight: number;\n horizontalBoxSpacing: number;\n limitNodeSearch: number;\n}\n\n// return function that gets the neighboring nodes of node and returns costs\nconst makeGetNeighbors =\n ({\n aspectRatioList,\n targetRowHeight,\n containerWidth,\n limitNodeSearch,\n horizontalBoxSpacing,\n }: IMakeGetNeighborsOptions) =>\n (start: number) => {\n const results = new Map();\n // start = +start;\n results.set(start, 0);\n for (let i = start + 1; i < aspectRatioList.length + 1; ++i) {\n if (i - start > limitNodeSearch) break;\n results.set(\n i,\n calcCost({\n aspectRatioList,\n start,\n end: i,\n containerWidth,\n targetRowHeight,\n horizontalBoxSpacing,\n }),\n );\n }\n return results;\n };\n\nexport const photoFlexLayout = ({\n items,\n containerWidth,\n targetRowHeight,\n boxSpacing,\n}: IPhotoFlexLayoutOptions): IPhotoFlexLayoutResult => {\n const aspectRatioList = items.map((x) => x.width / x.height);\n\n // containerWidth =\n // containerWidth % 2 === 0 ? containerWidth : containerWidth - 1;\n\n const limitNodeSearch = calcLimitNodeSearch(containerWidth, targetRowHeight);\n\n const horizontalBoxSpacing =\n typeof boxSpacing === 'number' ? boxSpacing : boxSpacing.horizontal;\n const verticalBoxSpacing =\n typeof boxSpacing === 'number' ? boxSpacing : boxSpacing.vertical;\n\n const getNeighbors = makeGetNeighbors({\n targetRowHeight,\n containerWidth,\n aspectRatioList,\n limitNodeSearch,\n horizontalBoxSpacing,\n });\n\n const path = findShortestPath(getNeighbors, 0, aspectRatioList.length);\n\n const result: ILayoutBox[] = [];\n\n let containerHeight = 0;\n\n for (let rowId = 0; rowId < path.length - 1; ++rowId) {\n const row = aspectRatioList.slice(path[rowId], path[rowId + 1]);\n\n let height = calcCommonHeight({\n aspectRatioList: row,\n containerWidth,\n horizontalBoxSpacing,\n });\n\n if (rowId === path.length - 2 && height > targetRowHeight * 1.3) {\n height = targetRowHeight;\n }\n\n let left = 0;\n\n for (\n let aspectRatioId = path[rowId];\n aspectRatioId < path[rowId + 1];\n ++aspectRatioId\n ) {\n const aspectRatio = aspectRatioList[aspectRatioId];\n\n const width = Math.round(height * aspectRatio * 100) / 100;\n\n result.push({\n width,\n height,\n aspectRatio: aspectRatio,\n top: containerHeight,\n left,\n rowId,\n });\n\n left += width + horizontalBoxSpacing;\n }\n containerHeight += Math.ceil(height + verticalBoxSpacing);\n }\n\n return {\n containerHeight: containerHeight,\n boxes: result,\n };\n};\n"],"names":["calcLimitNodeSearch","containerWidth","targetRowHeight","Math","round","calcCommonHeight","param","aspectRatioList","horizontalBoxSpacing","rowWidth","length","totalAspectRatio","reduce","acc","ratio","calcCost","start","end","row","slice","commonHeight","pow","abs","buildPrecedentsMap","graphBuilder","startNode","endNode","precedentsMap","Map","visited","Set","storedShortestPaths","pQueue","TinyQueue","undefined","a","b","weight","push","id","shortestNode","pop","shortestNodeId","has","neighboringNodes","add","neighbor","neighborValue","newTotalWeight","set","Error","getPathFromPrecedentsMap","n","nodes","get","reverse","findShortestPath","graph","makeGetNeighbors","limitNodeSearch","results","i","photoFlexLayout","items","boxSpacing","map","x","width","height","horizontal","verticalBoxSpacing","vertical","getNeighbors","path","result","containerHeight","rowId","left","aspectRatioId","aspectRatio","top","ceil","boxes"],"mappings":"gDAEO,MAAMA,oBAAsB,CACjCC,eACAC,kBAEAD,eAAiB,IACbE,KAAKC,MAAMH,eAAiBC,gBAAkB,KAAO,EACrD,EAQC,MAAMG,iBAAmB,AAAAC,QAAC,GAAA,CAC/BC,eAAe,CACfN,cAAc,CACdO,qBACwB,CAAAF,MACxB,MAAMG,SACJR,eAAiBM,gBAAgBG,OAASF,qBAE5C,MAAMG,iBAAmBJ,gBAAgBK,OACvC,CAACC,IAAKC,QAAUD,IAAMC,MACtB,GAGF,OAAOL,SAAWE,gBACpB,EAYO,MAAMI,SAAW,AAAAT,WAAC,CACvBC,eAAAA,CACAS,KAAAA,CACAC,GAAAA,CACAhB,cAAAA,CACAC,eAAAA,CACAM,oBAAAA,CACa,CAAAF,MACb,MAAMY,IAAMX,gBAAgBY,MAAMH,MAAOC,KACzC,MAAMG,aAAef,iBAAiB,CACpCE,gBAAiBW,IACjBjB,eACAO,oBACF,GACA,OAAOL,KAAKkB,IAAIlB,KAAKmB,IAAIF,aAAelB,iBAAkB,EAC5D,ECrDA,MAAMqB,mBAAqB,CACzBC,aACAC,UACAC,WAGA,MAAMC,cAAgB,IAAIC,IAG1B,MAAMC,QAAU,IAAIC,IAIpB,MAAMC,oBAA8C,CAAA,CACpDA,CAAAA,mBAAmB,CAACN,UAAU,CAAG,EAIjC,MAAMO,OAAS,IAAIC,UAAiBC,UAAW,CAACC,EAAGC,IAAMD,EAAEE,OAASD,EAAEC,QACtEL,OAAOM,KAAK,CAAEC,GAAId,UAAWY,OAAQ,CAAE,GAEvC,MAAOL,OAAOtB,SAAW,EAAG,CAE1B,MAAM8B,aAAeR,OAAOS,MAC5B,GAAI,CAACD,aAAc,SAEnB,MAAME,eAAiBF,aAAaD,GAGpC,GAAIV,QAAQc,IAAID,gBAAiB,SAGjC,MAAME,iBAAmBpB,aAAakB,iBAAmB,IAAId,IAC7DC,QAAQgB,IAAIH,gBAGZ,IAAK,KAAM,CAACI,SAAUC,cAAc,GAAIH,iBAAkB,CAExD,MAAMI,eAAiBR,aAAaH,OAASU,cAK7C,GACE,OAAOhB,mBAAmB,CAACe,SAAS,GAAK,aACzCf,mBAAmB,CAACe,SAAS,CAAGE,eAChC,CACAjB,mBAAmB,CAACe,SAAS,CAAGE,eAChChB,OAAOM,KAAK,CAAEC,GAAIO,SAAUT,OAAQW,cAAe,GACnDrB,cAAcsB,IAAIH,SAAUJ,eAC9B,CACF,CACF,CAEA,GAAI,OAAOX,mBAAmB,CAACL,QAAQ,GAAK,YAAa,CACvD,MAAM,IAAIwB,MAAM,CAAC,sBAAsB,EAAEzB,UAAU,IAAI,EAAEC,QAAQ,CAAC,CACpE,CAEA,OAAOC,aACT,EAGA,MAAMwB,yBAA2B,CAC/BxB,cACAD,WAEA,IAAI0B,EAAI1B,QACR,MAAM2B,MAAQ,CAACD,EAAE,CACjB,MAAOA,EAAG,CACRA,EAAIzB,cAAc2B,IAAIF,GACtBC,MAAMf,KAAKc,EACb,CACA,OAAOC,MAAME,SACf,EAGO,MAAMC,iBAAmB,CAC9BC,MACAhC,UACAC,WAEA,MAAMC,cAAgBJ,mBAAmBkC,MAAOhC,UAAWC,SAE3D,OAAOyB,yBAAyBxB,cAAeD,QACjD,ECpEA,MAAMgC,iBACJ,AAAApD,WAAC,CACCC,eAAAA,CACAL,eAAe,CACfD,eACA0D,eAAAA,CACAnD,oBAAAA,CACyB,CAAAF,aAC3B,AAACU,QACC,MAAM4C,QAAU,IAAIhC,IAEpBgC,QAAQX,IAAIjC,MAAO,GACnB,IAAK,IAAI6C,EAAI7C,MAAQ,EAAG6C,EAAItD,gBAAgBG,OAAS,EAAG,EAAEmD,EAAG,CAC3D,GAAIA,EAAI7C,MAAQ2C,gBAAiB,MACjCC,QAAQX,IACNY,EACA9C,SAAS,CACPR,gBACAS,MACAC,IAAK4C,EACL5D,eACAC,gBACAM,oBACF,GAEJ,CACA,OAAOoD,OACT,CAAA,QAEWE,gBAAkB,AAAAxD,QAAC,GAAA,CAC9ByD,MACA9D,cAAAA,CACAC,eAAe,CACf8D,WACwB,CAAA1D,MACxB,MAAMC,gBAAkBwD,MAAME,IAAI,AAACC,GAAMA,EAAEC,MAAQD,EAAEE,QAKrD,MAAMT,gBAAkB3D,oBAAoBC,eAAgBC,iBAE5D,MAAMM,qBACJ,OAAOwD,aAAe,SAAWA,WAAaA,WAAWK,WAC3D,MAAMC,mBACJ,OAAON,aAAe,SAAWA,WAAaA,WAAWO,SAE3D,MAAMC,aAAed,iBAAiB,CACpCxD,gBACAD,eACAM,gBACAoD,gBACAnD,oBACF,GAEA,MAAMiE,KAAOjB,iBAAiBgB,aAAc,EAAGjE,gBAAgBG,QAE/D,MAAMgE,OAAuB,EAAE,CAE/B,IAAIC,gBAAkB,EAEtB,IAAK,IAAIC,MAAQ,EAAGA,MAAQH,KAAK/D,OAAS,EAAG,EAAEkE,MAAO,CACpD,MAAM1D,IAAMX,gBAAgBY,MAAMsD,IAAI,CAACG,MAAM,CAAEH,IAAI,CAACG,MAAQ,EAAE,EAE9D,IAAIR,OAAS/D,iBAAiB,CAC5BE,gBAAiBW,IACjBjB,eACAO,oBACF,GAEA,GAAIoE,QAAUH,KAAK/D,OAAS,GAAK0D,OAASlE,gBAAkB,IAAK,CAC/DkE,OAASlE,eACX,CAEA,IAAI2E,KAAO,EAEX,IACE,IAAIC,cAAgBL,IAAI,CAACG,MAAM,CAC/BE,cAAgBL,IAAI,CAACG,MAAQ,EAAE,CAC/B,EAAEE,cACF,CACA,MAAMC,YAAcxE,eAAe,CAACuE,cAAc,CAElD,MAAMX,MAAQhE,KAAKC,MAAMgE,OAASW,YAAc,KAAO,IAEvDL,OAAOpC,KAAK,CACV6B,MACAC,OACAW,YAAaA,YACbC,IAAKL,gBACLE,KACAD,KACF,GAEAC,MAAQV,MAAQ3D,oBAClB,CACAmE,iBAAmBxE,KAAK8E,KAAKb,OAASE,mBACxC,CAEA,MAAO,CACLK,gBAAiBA,gBACjBO,MAAOR,MACT,CACF"}