5086275713

Build Type

push

github

Committed by Daybrush

Commit Message

chore(release): Release 1.14.1

Run Details

599 of 689 branches covered (86.94%)

Branch coverage included in aggregate %.

1330 of 1362 relevant lines covered (97.65%)

1076.12 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.67

/src/grids/lib/dijkstra.ts

/* eslint-disable */
/******************************************************************************
 * Created 2008-08-19.
 *
 * Dijkstra path-finding functions. Adapted from the Dijkstar Python project.
 *
 * Copyright (C) 2008
 *   Wyatt Baldwin <self@wyattbaldwin.com>
 *   All rights reserved
 *
 * Licensed under the MIT license.
 *
 *   http://www.opensource.org/licenses/mit-license.php
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *****************************************************************************/
function single_source_shortest_paths(
        graph: (x: string) => ({ [key: string]: number }),
        s: string,
        d: string,
) {
        // Predecessor map for each node that has been encountered.
        // node ID => predecessor node ID
        const predecessors: { [key: string]: string } = {};
        // Costs of shortest paths from s to all nodes encountered.
        // node ID => cost
        const costs: { [key: string]: number } = {};
        costs[s] = 0;

        // Costs of shortest paths from s to all nodes encountered; differs from
        // `costs` in that it provides easy access to the node that currently has
        // the known shortest path from s.
        // XXX: Do we actually need both `costs` and `open`?
        const open = new BinaryHeap<{ value: string, cost: number }>(x => x.cost);
        open.push({ value: s, cost: 0 });

        let closest;
        let u;
        let cost_of_s_to_u;
        let adjacent_nodes;
        let cost_of_e;
        let cost_of_s_to_u_plus_cost_of_e;
        let cost_of_s_to_v;
        let first_visit: boolean;

        while (open.size()) {
                // In the nodes remaining in graph that have a known cost from s,
                // find the node, u, that currently has the shortest path from s.
                closest = open.pop();
                u = closest.value;
                cost_of_s_to_u = closest.cost;

                // Get nodes adjacent to u...
                adjacent_nodes = graph(u) || {};

                // ...and explore the edges that connect u to those nodes, updating
                // the cost of the shortest paths to any or all of those nodes as
                // necessary. v is the node across the current edge from u.
                for (const v in adjacent_nodes) {
                        // Get the cost of the edge running from u to v.
                        cost_of_e = adjacent_nodes[v];

                        // Cost of s to u plus the cost of u to v across e--this is *a*
                        // cost from s to v that may or may not be less than the current
                        // known cost to v.
                        cost_of_s_to_u_plus_cost_of_e = cost_of_s_to_u + cost_of_e;

                        // If we haven't visited v yet OR if the current known cost from s to
                        // v is greater than the new cost we just found (cost of s to u plus
                        // cost of u to v across e), update v's cost in the cost list and
                        // update v's predecessor in the predecessor list (it's now u).
                        cost_of_s_to_v = costs[v];
                        first_visit = (typeof costs[v] === "undefined");
                        if (first_visit || cost_of_s_to_v > cost_of_s_to_u_plus_cost_of_e) {
                                costs[v] = cost_of_s_to_u_plus_cost_of_e;
                                open.push({ value: v, cost: cost_of_s_to_u_plus_cost_of_e });
                                predecessors[v] = u;
                        }
                }
        }

        if (typeof costs[d] === "undefined") {
                const msg = ["Could not find a path from ", s, " to ", d, "."].join("");
                throw new Error(msg);
        }

        return predecessors;
}
function extract_shortest_path_from_predecessor_list(
        predecessors: { [key: string]: string },
        d: string,
) {
        const nodes: string[] = [];
        let u = d;

        while (u) {
                nodes.push(u);
                u = predecessors[u];
        }
        nodes.reverse();
        return nodes;
}
function find_path(
        graph: (x: string) => ({ [key: string]: number }),
        s: string,
        d: string,
) {
        const predecessors = single_source_shortest_paths(graph, s, d);

        return extract_shortest_path_from_predecessor_list(predecessors, d);
}

class BinaryHeap<T> {
        private content: T[];
        private scoreFunction: (x: T) => number;

        constructor(scoreFunction: (x: T) => number) {
                this.content = [];
                this.scoreFunction = scoreFunction;
        }
        public push(element: T) {
                // Add the new element to the end of the array.
                this.content.push(element);
                // Allow it to bubble up.
                this.bubbleUp(this.content.length - 1);
        }
        public pop() {
                // Store the first element so we can return it later.
                const result = this.content[0];
                // Get the element at the end of the array.
                const end = this.content.pop()!;
                // If there are any elements left, put the end element at the
                // start, and let it sink down.
                if (this.content.length > 0) {
                        this.content[0] = end;
                        this.sinkDown(0);
                }
                return result;
        }
        public size() {
                return this.content.length;
        }
        public bubbleUp(_n: number) {
                let n = _n;
                // Fetch the element that has to be moved.
                const element = this.content[n];
                // When at 0, an element can not go up any further.
                while (n > 0) {
                        // Compute the parent element's index, and fetch it.
                        const parentN = Math.floor((n + 1) / 2) - 1;
                        const parent = this.content[parentN];

                        // Swap the elements if the parent is greater.
                        if (this.scoreFunction(element) < this.scoreFunction(parent)) {
                                this.content[parentN] = element;
                                this.content[n] = parent;
                                // Update 'n' to continue at the new position.
                                n = parentN;
                        } else {
                                // Found a parent that is less, no need to move it further.
                                break;
                        }
                }
        }
        public sinkDown(n: number) {
                // Look up the target element and its score.
                const length = this.content.length;
                const element = this.content[n];
                const elemScore = this.scoreFunction(element);
                let child1Score;

                while (true) {
                        // Compute the indices of the child elements.
                        const child2N = (n + 1) * 2;
                        const child1N = child2N - 1;
                        // This is used to store the new position of the element,
                        // if any.
                        let swap: number | null = null;
                        // If the first child exists (is inside the array)...
                        if (child1N < length) {
                                // Look it up and compute its score.
                                const child1 = this.content[child1N];
                                child1Score = this.scoreFunction(child1);
                                // If the score is less than our element's, we need to swap.
                                if (child1Score < elemScore) {
                                        swap = child1N;
                                }
                        }
                        // Do the same checks for the other child.
                        if (child2N < length) {
                                const child2 = this.content[child2N];
                                const child2Score = this.scoreFunction(child2);

                                if (child2Score < (swap == null ? elemScore : child1Score)) {
                                        swap = child2N;
                                }
                        }

                        // If the element needs to be moved, swap it, and continue.
                        if (swap !== null) {
                                this.content[n] = this.content[swap];
                                this.content[swap] = element;
                                n = swap;
                        } else {
                                // Otherwise, we are done.
                                break;
                        }
                }
        }
}

export { find_path };

1	/* eslint-disable */
2	/******************************************************************************
3	* Created 2008-08-19.
4	*
5	* Dijkstra path-finding functions. Adapted from the Dijkstar Python project.
6	*
7	* Copyright (C) 2008
8	* Wyatt Baldwin <self@wyattbaldwin.com>
9	* All rights reserved
10	*
11	* Licensed under the MIT license.
12	*
13	* http://www.opensource.org/licenses/mit-license.php
14	*
15	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18	* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20	* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21	* THE SOFTWARE.
22	*****************************************************************************/
23	function single_source_shortest_paths(	1✔
24	graph: (x: string) => ({ [key: string]: number }),
25	s: string,
26	d: string,
27	) {
28	// Predecessor map for each node that has been encountered.
29	// node ID => predecessor node ID
30	const predecessors: { [key: string]: string } = {};	13✔
31	// Costs of shortest paths from s to all nodes encountered.
32	// node ID => cost
33	const costs: { [key: string]: number } = {};	13✔
34	costs[s] = 0;	13✔
35
36	// Costs of shortest paths from s to all nodes encountered; differs from
37	// `costs` in that it provides easy access to the node that currently has
38	// the known shortest path from s.
39	// XXX: Do we actually need both `costs` and `open`?
40	const open = new BinaryHeap<{ value: string, cost: number }>(x => x.cost);	2,382✔
41	open.push({ value: s, cost: 0 });	13✔
42
43	let closest;	13✔
44	let u;	13✔
45	let cost_of_s_to_u;	13✔
46	let adjacent_nodes;	13✔
47	let cost_of_e;	13✔
48	let cost_of_s_to_u_plus_cost_of_e;	13✔
49	let cost_of_s_to_v;	13✔
50	let first_visit: boolean;	13✔
51
52	while (open.size()) {	13✔
53	// In the nodes remaining in graph that have a known cost from s,
54	// find the node, u, that currently has the shortest path from s.
55	closest = open.pop();	287✔
56	u = closest.value;	287✔
57	cost_of_s_to_u = closest.cost;	287✔
58
59	// Get nodes adjacent to u...
60	adjacent_nodes = graph(u) \|\| {};	287!
61
62	// ...and explore the edges that connect u to those nodes, updating
63	// the cost of the shortest paths to any or all of those nodes as
64	// necessary. v is the node across the current edge from u.
65	for (const v in adjacent_nodes) {	287✔
66	// Get the cost of the edge running from u to v.
67	cost_of_e = adjacent_nodes[v];	1,148✔
68
69	// Cost of s to u plus the cost of u to v across e--this is a
70	// cost from s to v that may or may not be less than the current
71	// known cost to v.
72	cost_of_s_to_u_plus_cost_of_e = cost_of_s_to_u + cost_of_e;	1,148✔
73
74	// If we haven't visited v yet OR if the current known cost from s to
75	// v is greater than the new cost we just found (cost of s to u plus
76	// cost of u to v across e), update v's cost in the cost list and
77	// update v's predecessor in the predecessor list (it's now u).
78	cost_of_s_to_v = costs[v];	1,148✔
79	first_visit = (typeof costs[v] === "undefined");	1,148✔
80	if (first_visit \|\| cost_of_s_to_v > cost_of_s_to_u_plus_cost_of_e) {	1,148✔
81	costs[v] = cost_of_s_to_u_plus_cost_of_e;	274✔
82	open.push({ value: v, cost: cost_of_s_to_u_plus_cost_of_e });	274✔
83	predecessors[v] = u;	274✔
84	}
85	}
86	}
87
88	if (typeof costs[d] === "undefined") {	13!
89	const msg = ["Could not find a path from ", s, " to ", d, "."].join("");	×
90	throw new Error(msg);	×
91	}
92
93	return predecessors;	13✔
94	}
95	function extract_shortest_path_from_predecessor_list(	1✔
96	predecessors: { [key: string]: string },
97	d: string,
98	) {
99	const nodes: string[] = [];	13✔
100	let u = d;	13✔
101
102	while (u) {	13✔
103	nodes.push(u);	59✔
104	u = predecessors[u];	59✔
105	}
106	nodes.reverse();	13✔
107	return nodes;	13✔
108	}
109	function find_path(	1✔
110	graph: (x: string) => ({ [key: string]: number }),
111	s: string,
112	d: string,
113	) {
114	const predecessors = single_source_shortest_paths(graph, s, d);	13✔
115
116	return extract_shortest_path_from_predecessor_list(predecessors, d);	13✔
117	}
118
119	class BinaryHeap<T> {	1✔
120	private content: T[];
121	private scoreFunction: (x: T) => number;
122
123	constructor(scoreFunction: (x: T) => number) {	1✔
124	this.content = [];	13✔
125	this.scoreFunction = scoreFunction;	13✔
126	}
127	public push(element: T) {	1✔
128	// Add the new element to the end of the array.
129	this.content.push(element);	287✔
130	// Allow it to bubble up.
131	this.bubbleUp(this.content.length - 1);	287✔
132	}
133	public pop() {	1✔
134	// Store the first element so we can return it later.
135	const result = this.content[0];	287✔
136	// Get the element at the end of the array.
137	const end = this.content.pop()!;	287✔
138	// If there are any elements left, put the end element at the
139	// start, and let it sink down.
140	if (this.content.length > 0) {	287✔
141	this.content[0] = end;	243✔
142	this.sinkDown(0);	243✔
143	}
144	return result;	287✔
145	}
146	public size() {	1✔
147	return this.content.length;	300✔
148	}
149	public bubbleUp(_n: number) {	1✔
150	let n = _n;	287✔
151	// Fetch the element that has to be moved.
152	const element = this.content[n];	287✔
153	// When at 0, an element can not go up any further.
154	while (n > 0) {	287✔
155	// Compute the parent element's index, and fetch it.
156	const parentN = Math.floor((n + 1) / 2) - 1;	447✔
157	const parent = this.content[parentN];	447✔
158
159	// Swap the elements if the parent is greater.
160	if (this.scoreFunction(element) < this.scoreFunction(parent)) {	447✔
161	this.content[parentN] = element;	250✔
162	this.content[n] = parent;	250✔
163	// Update 'n' to continue at the new position.
164	n = parentN;	250✔
165	} else {
166	// Found a parent that is less, no need to move it further.
167	break;	197✔
168	}
169	}
170	}
171	public sinkDown(n: number) {	1✔
172	// Look up the target element and its score.
173	const length = this.content.length;	243✔
174	const element = this.content[n];	243✔
175	const elemScore = this.scoreFunction(element);	243✔
176	let child1Score;	243✔
177
178	while (true) {	243✔
179	// Compute the indices of the child elements.
180	const child2N = (n + 1) * 2;	820✔
181	const child1N = child2N - 1;	820✔
182	// This is used to store the new position of the element,
183	// if any.
184	let swap: number \| null = null;	820✔
185	// If the first child exists (is inside the array)...
186	if (child1N < length) {	820✔
187	// Look it up and compute its score.
188	const child1 = this.content[child1N];	642✔
189	child1Score = this.scoreFunction(child1);	642✔
190	// If the score is less than our element's, we need to swap.
191	if (child1Score < elemScore) {	642✔
192	swap = child1N;	515✔
193	}
194	}
195	// Do the same checks for the other child.
196	if (child2N < length) {	820✔
197	const child2 = this.content[child2N];	603✔
198	const child2Score = this.scoreFunction(child2);	603✔
199
200	if (child2Score < (swap == null ? elemScore : child1Score)) {	603✔
201	swap = child2N;	272✔
202	}
203	}
204
205	// If the element needs to be moved, swap it, and continue.
206	if (swap !== null) {	820✔
207	this.content[n] = this.content[swap];	577✔
208	this.content[swap] = element;	577✔
209	n = swap;	577✔
210	} else {
211	// Otherwise, we are done.
212	break;	243✔
213	}
214	}
215	}
216	}	1✔
217
218	export { find_path };	1✔

naver / egjs-grid / 5086275713

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous