6145886764

Committed 11 Sep 2023 11:42AM UTC coverage: 80.25% (-0.2%) from 80.427%

Build # 6145886764

Build Type

push

github

Committed by

iddan

Commit Message

Improve docs and interface

Run Details

392 of 538 branches covered (0.0%)

Branch coverage included in aggregate %.

4 of 4 new or added lines in 1 file covered. (100.0%)

957 of 1143 relevant lines covered (83.73%)

36.78 hits per line

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

88.16

/src/engine/point-graph.ts

import { Point } from "../point";
import * as pointHash from "./point-hash";
import { PointSet } from "./point-set";

/**
 * Immutable directed graph of points, where each point can have multiple
 * edges to other points.
 */
export class PointGraph {
  private constructor(private forwards = new Map<string, PointSet>()) {}

  /** Creates a new PointGraph instance from an array-like or iterable object */
  static from(pairs: Iterable<[Point, PointSet]>): PointGraph {
    const adjacencyList = new Map<string, PointSet>();
    for (const [node, edges] of pairs) {
      adjacencyList.set(pointHash.toString(node), edges);
    }
    return new PointGraph(adjacencyList);
  }

  set(node: Point, edges: PointSet): PointGraph {
    const newGraph = new PointGraph(new Map(this.forwards));
    if (edges.size() === 0) {
      newGraph.forwards.delete(pointHash.toString(node));
      return newGraph;
    }
    newGraph.forwards.set(pointHash.toString(node), edges);
    return newGraph;
  }

  get(node: Point): PointSet {
    return this.forwards.get(pointHash.toString(node)) || PointSet.from([]);
  }

  getBackwards(node: Point): PointSet {
    let result = PointSet.from([]);
    for (const [key, value] of this.forwards) {
      if (value.has(node)) {
        result = result.add(pointHash.fromString(key));
      }
    }
    return result;
  }

  getBackwardsRecursive(
    node: Point,
    visited: PointSet = PointSet.from([])
  ): PointSet {
    let result = this.getBackwards(node);
    let newVisited = visited;
    for (const point of result) {
      if (newVisited.has(point)) {
        continue;
      }
      newVisited = newVisited.add(point);
      result = result.union(this.getBackwardsRecursive(point, newVisited));
    }
    return result;
  }

  /** Determine whether the graph has a circular dependency, starting from given start point */
  hasCircularDependency(startPoint: Point): boolean {
    let visited = PointSet.from([]);
    const stack: Point[] = [startPoint];

    while (stack.length > 0) {
      const current = stack.pop();
      if (!current) {
        continue;
      }

      if (visited.has(current)) {
        return true;
      }

      visited = visited.add(current);

      const dependents = this.get(current);

      if (!dependents) {
        continue;
      }

      for (const dependent of dependents) {
        stack.push(dependent);
      }
    }

    return false;
  }

  /** Get the points in the graph in a breadth-first order */
  *traverseBFS(): Generator<Point> {
    // Create a Set to store the points that have been visited
    let visited = PointSet.from([]);

    // Create a queue to store the points that still need to be visited
    const queue: Point[] = [];

    // Iterate over all the points and add the ones with no dependencies to the queue
    for (const key of this.forwards.keys()) {
      const point = pointHash.fromString(key);
      if (this.getBackwards(point).size() === 0) {
        queue.push(point);
        visited = visited.add(point);
      }
    }

    // While there are points in the queue, remove the first one and yield it
    while (queue.length > 0) {
      const point = queue.shift();
      if (!point) {
        continue;
      }
      yield point;

      // Get the set of points that depend on the current point
      const dependents = this.get(point);

      // If there are no dependents, skip to the next iteration
      if (!dependents) {
        continue;
      }

      // Otherwise, add the dependents to the queue if they have not yet been visited
      for (const dependent of dependents) {
        if (!visited.has(dependent)) {
          queue.push(dependent);
          visited = visited.add(dependent);
        }
      }
    }
  }
}

1	import { Point } from "../point";
2	import * as pointHash from "./point-hash";	12✔
3	import { PointSet } from "./point-set";	12✔
4
5	/**
6	* Immutable directed graph of points, where each point can have multiple
7	* edges to other points.
8	*/
9	export class PointGraph {	12✔
10	private constructor(private forwards = new Map<string, PointSet>()) {}	84!
11
12	/** Creates a new PointGraph instance from an array-like or iterable object */
13	static from(pairs: Iterable<[Point, PointSet]>): PointGraph {
14	const adjacencyList = new Map<string, PointSet>();	73✔
15	for (const [node, edges] of pairs) {	73✔
16	adjacencyList.set(pointHash.toString(node), edges);	36✔
17	}
18	return new PointGraph(adjacencyList);	73✔
19	}
20
21	set(node: Point, edges: PointSet): PointGraph {
22	const newGraph = new PointGraph(new Map(this.forwards));	11✔
23	if (edges.size() === 0) {	11✔
24	newGraph.forwards.delete(pointHash.toString(node));	2✔
25	return newGraph;	2✔
26	}
27	newGraph.forwards.set(pointHash.toString(node), edges);	9✔
28	return newGraph;	9✔
29	}
30
31	get(node: Point): PointSet {
32	return this.forwards.get(pointHash.toString(node)) \|\| PointSet.from([]);	27✔
33	}
34
35	getBackwards(node: Point): PointSet {
36	let result = PointSet.from([]);	20✔
37	for (const [key, value] of this.forwards) {	20✔
38	if (value.has(node)) {	50✔
39	result = result.add(pointHash.fromString(key));	10✔
40	}
41	}
42	return result;	20✔
43	}
44
45	getBackwardsRecursive(
46	node: Point,
47	visited: PointSet = PointSet.from([])	6✔
48	): PointSet {
49	let result = this.getBackwards(node);	7✔
50	let newVisited = visited;	7✔
51	for (const point of result) {	7✔
52	if (newVisited.has(point)) {	2✔
53	continue;	1✔
54	}
55	newVisited = newVisited.add(point);	1✔
56	result = result.union(this.getBackwardsRecursive(point, newVisited));	1✔
57	}
58	return result;	7✔
59	}
60
61	/** Determine whether the graph has a circular dependency, starting from given start point */
62	hasCircularDependency(startPoint: Point): boolean {
63	let visited = PointSet.from([]);	10✔
64	const stack: Point[] = [startPoint];	10✔
65
66	while (stack.length > 0) {	10✔
67	const current = stack.pop();	22✔
68	if (!current) {	22!
69	continue;	×
70	}
71
72	if (visited.has(current)) {	22✔
73	return true;	4✔
74	}
75
76	visited = visited.add(current);	18✔
77
78	const dependents = this.get(current);	18✔
79
80	if (!dependents) {	18!
81	continue;	×
82	}
83
84	for (const dependent of dependents) {	18✔
85	stack.push(dependent);	12✔
86	}
87	}
88
89	return false;	6✔
90	}
91
92	/** Get the points in the graph in a breadth-first order */
93	*traverseBFS(): Generator<Point> {
94	// Create a Set to store the points that have been visited
95	let visited = PointSet.from([]);	51✔
96
97	// Create a queue to store the points that still need to be visited
98	const queue: Point[] = [];	51✔
99
100	// Iterate over all the points and add the ones with no dependencies to the queue
101	for (const key of this.forwards.keys()) {	51✔
102	const point = pointHash.fromString(key);	9✔
103	if (this.getBackwards(point).size() === 0) {	9✔
104	queue.push(point);	5✔
105	visited = visited.add(point);	5✔
106	}
107	}
108
109	// While there are points in the queue, remove the first one and yield it
110	while (queue.length > 0) {	51✔
111	const point = queue.shift();	9✔
112	if (!point) {	9!
113	continue;	×
114	}
115	yield point;	9✔
116
117	// Get the set of points that depend on the current point
118	const dependents = this.get(point);	9✔
119
120	// If there are no dependents, skip to the next iteration
121	if (!dependents) {	9!
122	continue;	×
123	}
124
125	// Otherwise, add the dependents to the queue if they have not yet been visited
126	for (const dependent of dependents) {	9✔
127	if (!visited.has(dependent)) {	5✔
128	queue.push(dependent);	4✔
129	visited = visited.add(dependent);	4✔
130	}
131	}
132	}
133	}
134	}

iddan / react-spreadsheet / 6145886764

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