27974749198

Committed 22 Jun 2026 06:25PM UTC coverage: 41.032% (-40.0%) from 81.081%

Build # 27974749198

Build Type

Pull #38

github

Committed by

web-flow

Commit Message

Merge 5879a1978 into a31e3fb33

Pull Request Pull Request #38: Add Data Visualisation

Coverage Stats

98 of 298 branches covered (32.89%)

Branch coverage included in aggregate %.

214 of 488 new or added lines in 20 files covered. (43.85%)

236 of 516 relevant lines covered (45.74%)

1.33 hits per line

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

51.32

/src/web/data-display/src/dataVisualizer.tsx

import type { Data } from "./dataVisualizerTypes";
import { Config } from "./Config";
import type { Step } from "./dataVisualizerTypes";
import { Tree } from "./tree/Tree";
import { DataTreeNode } from "./tree/TreeNode";

/**
 * The data visualizer class.
 * Exposes three function: init, drawData, and clear.
 *
 * init is used by SideContentDataVisualizer as a hook.
 * drawData is the draw_data function in source.
 * clear is used by WorkspaceSaga to reset the visualizer after every "Run" button press
 */
export default class DataVisualizer {
  private static empty() {}
  private static setSteps: (step: Step[]) => void = DataVisualizer.empty;
  public static dataRecords: Data[] = [];
  public static isRedraw = false;
  private static _instance = new DataVisualizer();
  public static treeMode = false;
  public static BinTreeMode = false;
  public static normalMode = true;
  public static TreeDepth = 0;
  public static isBinTree = false;
  public static isGenTree = false;
  public static nodeCount: number[] = [];
  public static nodeColor: number[] = [];
  public static longestNodePos: number = 0;
  public static colorMap: WeakMap<Array<Data>, number> = new WeakMap();
  public static posMap: WeakMap<Data[], number> = new WeakMap();

  private steps: Step[] = [];
  private nodeLabel = 0;
  private nodeToLabelMap: Map<DataTreeNode, number> = new Map();

  private constructor() {}

  public static isBinaryTree(structures: Data[], data: unknown): boolean {
    if (structures == null) {
      return true;
    }
    if (!(structures instanceof Array)) {
      return false;
    }
    if (structures[0] === null) {
      return true;
    }
    if (structures.length != 2 || !(structures[1] instanceof Array)) {
      return false;
    }
    if (data != null && !(structures[0] instanceof Array) && typeof structures[0] != typeof data) {
      return false;
    }
    let next = structures[1];
    data = structures[0];

    let ans = false;
    let count = 0;
    while (next instanceof Array) {
      if (!(next[0] instanceof Array) && typeof next[0] == typeof structures[0]) {
        return false;
      }
      count++;
      next = next[1];
    }
    if (count == 2) {
      ans = true;
    }
    // further checks to ensure that the left and right subtrees are also binary trees and structures can be accessed
    const left = structures[1];
    const right = structures[1][1];
    if (left instanceof Array && right instanceof Array) {
      return ans && this.isBinaryTree(left[0], data) && this.isBinaryTree(right[0], data);
    } else {
      return false;
    }
  }

  public static isGeneralTree(structures: Data[], data: unknown): boolean {
    if (structures == null) {
      return true;
    }
    if (
      data != null &&
      !(structures[0] instanceof Array) &&
      typeof structures[0] != typeof data &&
      structures[0] != null
    ) {
      return false;
    }
    if (structures.length == 2 && structures[1] == null) {
      if (structures[0] instanceof Array) {
        return this.isGeneralTree(structures[0], data);
      }
      return true;
    }
    if (!(structures[0] instanceof Array) && structures[1] != null) {
      data = structures[0];
      return this.isGeneralTree(structures[1], data);
    }
    if (structures.length != 2 || (!(structures[1] instanceof Array) && structures[1] != null)) {
      return false;
    }
    return this.isGeneralTree(structures[1], data) && this.isGeneralTree(structures[0], data);
  }

  public static initializeTreeMetaData(
    structures: Data[],
    depth: number,
    nodePos: number,
    newNode: boolean,
  ): number {
    if (!(structures instanceof Array)) {
      return 0;
    }
    // nodeCount keeps track of the current index of nodes at each depth
    if (this.getTreeMode()) {
      if (this.nodeCount[depth] === undefined) {
        this.nodeCount[depth] = 0;
      }
      this.posMap.set(structures, this.nodeCount[depth]);
      if (this.nodeCount[depth] > this.longestNodePos) {
        this.longestNodePos = this.nodeCount[depth];
      }
      this.nodeCount[depth]++;
    }
    if (this.getBinTreeMode() || this.getTreeMode()) {
      if (this.nodeColor[depth] === undefined) {
        this.nodeColor[depth] = depth;
      }
      if (newNode) {
        this.nodeColor[depth]++;
      }
      this.colorMap.set(structures, this.nodeColor[depth]);
    }

    this.TreeDepth = Math.max(this.TreeDepth, depth);
    this.initializeTreeMetaData(structures[0], depth + 1, 0, true);
    this.initializeTreeMetaData(structures[1], depth, nodePos + 1, false);
    return depth;
  }

  public static init(setSteps: (step: Step[]) => void): void {
    DataVisualizer.setSteps = setSteps;
    setSteps(DataVisualizer._instance.steps);
  }

  /**
   * Set the visualization mode. This ensures only one mode is active at a time.
   * @param mode - 'normal' for original view, 'binTree' for binary tree, 'tree' for general tree
   */
  public static setMode(mode: "normal" | "binTree" | "tree"): void {
    DataVisualizer.normalMode = mode === "normal";
    DataVisualizer.BinTreeMode = mode === "binTree";
    DataVisualizer.treeMode = mode === "tree";
  }

  // RenderBinaryTree
  public static toggleBinTreeMode(): void {
    DataVisualizer.BinTreeMode = !DataVisualizer.BinTreeMode;
  }

  // RenderGeneralTree
  public static toggleTreeMode(): void {
    DataVisualizer.treeMode = !DataVisualizer.treeMode;
  }

  // OriginalView
  public static toggleNormalMode(): void {
    DataVisualizer.normalMode = !DataVisualizer.normalMode;
  }

  public static getBinTreeMode(): boolean {
    return DataVisualizer.BinTreeMode;
  }

  public static getTreeMode(): boolean {
    return DataVisualizer.treeMode;
  }

  public static getNormalMode(): boolean {
    return DataVisualizer.normalMode;
  }

  public static hasCycle(structures: Data, visited: WeakSet<object> = new WeakSet()): boolean {
    if (!(structures instanceof Array)) {
      return false;
    }
    if (visited.has(structures)) {
      return true;
    }
    visited.add(structures);
    return this.hasCycle(structures[0], visited) || this.hasCycle(structures[1], visited);
  }

  public static drawData(structures: Data[]): void {
    if (!DataVisualizer.setSteps) {
      throw new Error("Data visualizer not initialized");
    }
    if (!DataVisualizer.isRedraw) {
      this.dataRecords.push(structures);
    }
    const root = structures[0];
    const isCyclic = this.hasCycle(root);
    DataVisualizer.nodeCount = [];
    DataVisualizer.nodeColor = [];
    this.nodeColor[0] = -1;
    DataVisualizer.longestNodePos = 0;
    DataVisualizer.TreeDepth = 0;
    if (isCyclic) {
      DataVisualizer.isBinTree = false;
      DataVisualizer.isGenTree = false;
    } else {
      DataVisualizer.isBinTree = this.isBinaryTree(root, null);
      DataVisualizer.isGenTree = this.isGeneralTree(root, null);
      if (DataVisualizer.isBinTree || DataVisualizer.isGenTree) {
        this.initializeTreeMetaData(root, 0, 0, false);
      }
    }
    DataVisualizer._instance.addStep(structures);

    DataVisualizer.setSteps(DataVisualizer._instance.steps);
  }

  public static clearWithData(): void {
    DataVisualizer.longestNodePos = 0;
    DataVisualizer.dataRecords = [];
    DataVisualizer.isRedraw = false;
    DataVisualizer.clear();
  }

  public static clear(): void {
    DataVisualizer._instance = new DataVisualizer();
    this.nodeCount = [];
    this.TreeDepth = 0;
    DataVisualizer.setSteps(DataVisualizer._instance.steps);
  }

  public static displaySpecialContent(dataNode: DataTreeNode): number {
    return DataVisualizer._instance.displaySpecialContent(dataNode);
  }

  private displaySpecialContent(dataNode: DataTreeNode): number {
    if (this.nodeToLabelMap.has(dataNode)) {
      return this.nodeToLabelMap.get(dataNode) ?? 0;
    } else {
      this.nodeToLabelMap.set(dataNode, this.nodeLabel);
      return this.nodeLabel++;
    }
  }

  private addStep(structures: Data[]) {
    const step = structures.map((xs, index) => this.createDrawing(xs, index));
    this.steps.push(step);
  }

  private createDrawing(xs: Data, key: number): React.ReactElement {
    const treeDrawer = Tree.fromSourceStructure(xs).draw();

    // To account for overflow to the left side due to a backward arrow
    const leftMargin = Config.StrokeWidth / 2;

    // To account for overflow to the top due to a backward arrow
    const topMargin = Config.StrokeWidth / 2;

    return treeDrawer.draw(leftMargin, topMargin, key);
  }

  static redraw() {
    this.isRedraw = true;
    this.clear();
    try {
      return DataVisualizer.dataRecords.map(structures => this.drawData(structures));
    } finally {
      this.isRedraw = false;
    }
  }
}

1	import type { Data } from "./dataVisualizerTypes";
2	import { Config } from "./Config";
3	import type { Step } from "./dataVisualizerTypes";
4	import { Tree } from "./tree/Tree";
5	import { DataTreeNode } from "./tree/TreeNode";
6
7	/**
8	* The data visualizer class.
9	* Exposes three function: init, drawData, and clear.
10	*
11	* init is used by SideContentDataVisualizer as a hook.
12	* drawData is the draw_data function in source.
13	* clear is used by WorkspaceSaga to reset the visualizer after every "Run" button press
14	*/
15	export default class DataVisualizer {
16	private static empty() {}
17	private static setSteps: (step: Step[]) => void = DataVisualizer.empty;	1✔
18	public static dataRecords: Data[] = [];	1✔
19	public static isRedraw = false;	1✔
20	private static _instance = new DataVisualizer();	1✔
21	public static treeMode = false;	1✔
22	public static BinTreeMode = false;	1✔
23	public static normalMode = true;	1✔
24	public static TreeDepth = 0;	1✔
25	public static isBinTree = false;	1✔
26	public static isGenTree = false;	1✔
27	public static nodeCount: number[] = [];	1✔
28	public static nodeColor: number[] = [];	1✔
29	public static longestNodePos: number = 0;	1✔
30	public static colorMap: WeakMap<Array<Data>, number> = new WeakMap();	1✔
31	public static posMap: WeakMap<Data[], number> = new WeakMap();	1✔
32
33	private steps: Step[] = [];	1✔
34	private nodeLabel = 0;	1✔
35	private nodeToLabelMap: Map<DataTreeNode, number> = new Map();	1✔
36
37	private constructor() {}
38
39	public static isBinaryTree(structures: Data[], data: unknown): boolean {
40	if (structures == null) {	2!
NEW 41	return true;	×
42	}
43	if (!(structures instanceof Array)) {	2!
NEW 44	return false;	×
45	}
46	if (structures[0] === null) {	2✔
47	return true;	1✔
48	}
49	if (structures.length != 2 \|\| !(structures[1] instanceof Array)) {	1!
50	return false;	1✔
51	}
NEW 52	if (data != null && !(structures[0] instanceof Array) && typeof structures[0] != typeof data) {	×
NEW 53	return false;	×
54	}
NEW 55	let next = structures[1];	×
NEW 56	data = structures[0];	×
57
NEW 58	let ans = false;	×
NEW 59	let count = 0;	×
NEW 60	while (next instanceof Array) {	×
NEW 61	if (!(next[0] instanceof Array) && typeof next[0] == typeof structures[0]) {	×
NEW 62	return false;	×
63	}
NEW 64	count++;	×
NEW 65	next = next[1];	×
66	}
NEW 67	if (count == 2) {	×
NEW 68	ans = true;	×
69	}
70	// further checks to ensure that the left and right subtrees are also binary trees and structures can be accessed
NEW 71	const left = structures[1];	×
NEW 72	const right = structures[1][1];	×
NEW 73	if (left instanceof Array && right instanceof Array) {	×
NEW 74	return ans && this.isBinaryTree(left[0], data) && this.isBinaryTree(right[0], data);	×
75	} else {
NEW 76	return false;	×
77	}
78	}
79
80	public static isGeneralTree(structures: Data[], data: unknown): boolean {
81	if (structures == null) {	3!
NEW 82	return true;	×
83	}
84	if (	3!
85	data != null &&	5!
86	!(structures[0] instanceof Array) &&
87	typeof structures[0] != typeof data &&
88	structures[0] != null
89	) {
NEW 90	return false;	×
91	}
92	if (structures.length == 2 && structures[1] == null) {	3!
NEW 93	if (structures[0] instanceof Array) {	×
NEW 94	return this.isGeneralTree(structures[0], data);	×
95	}
NEW 96	return true;	×
97	}
98	if (!(structures[0] instanceof Array) && structures[1] != null) {	3✔
99	data = structures[0];	1✔
100	return this.isGeneralTree(structures[1], data);	1✔
101	}
102	if (structures.length != 2 \|\| (!(structures[1] instanceof Array) && structures[1] != null)) {	2!
103	return false;	2✔
104	}
NEW 105	return this.isGeneralTree(structures[1], data) && this.isGeneralTree(structures[0], data);	×
106	}
107
108	public static initializeTreeMetaData(
109	structures: Data[],
110	depth: number,
111	nodePos: number,
112	newNode: boolean,
113	): number {
114	if (!(structures instanceof Array)) {	3✔
115	return 0;	2✔
116	}
117	// nodeCount keeps track of the current index of nodes at each depth
118	if (this.getTreeMode()) {	1!
NEW 119	if (this.nodeCount[depth] === undefined) {	×
NEW 120	this.nodeCount[depth] = 0;	×
121	}
NEW 122	this.posMap.set(structures, this.nodeCount[depth]);	×
NEW 123	if (this.nodeCount[depth] > this.longestNodePos) {	×
NEW 124	this.longestNodePos = this.nodeCount[depth];	×
125	}
NEW 126	this.nodeCount[depth]++;	×
127	}
128	if (this.getBinTreeMode() \|\| this.getTreeMode()) {	1!
NEW 129	if (this.nodeColor[depth] === undefined) {	×
NEW 130	this.nodeColor[depth] = depth;	×
131	}
NEW 132	if (newNode) {	×
NEW 133	this.nodeColor[depth]++;	×
134	}
NEW 135	this.colorMap.set(structures, this.nodeColor[depth]);	×
136	}
137
138	this.TreeDepth = Math.max(this.TreeDepth, depth);	1✔
139	this.initializeTreeMetaData(structures[0], depth + 1, 0, true);	1✔
140	this.initializeTreeMetaData(structures[1], depth, nodePos + 1, false);	1✔
141	return depth;	1✔
142	}
143
144	public static init(setSteps: (step: Step[]) => void): void {
145	DataVisualizer.setSteps = setSteps;	2✔
146	setSteps(DataVisualizer._instance.steps);	2✔
147	}
148
149	/**
150	* Set the visualization mode. This ensures only one mode is active at a time.
151	* @param mode - 'normal' for original view, 'binTree' for binary tree, 'tree' for general tree
152	*/
153	public static setMode(mode: "normal" \| "binTree" \| "tree"): void {
NEW 154	DataVisualizer.normalMode = mode === "normal";	×
NEW 155	DataVisualizer.BinTreeMode = mode === "binTree";	×
NEW 156	DataVisualizer.treeMode = mode === "tree";	×
157	}
158
159	// RenderBinaryTree
160	public static toggleBinTreeMode(): void {
NEW 161	DataVisualizer.BinTreeMode = !DataVisualizer.BinTreeMode;	×
162	}
163
164	// RenderGeneralTree
165	public static toggleTreeMode(): void {
NEW 166	DataVisualizer.treeMode = !DataVisualizer.treeMode;	×
167	}
168
169	// OriginalView
170	public static toggleNormalMode(): void {
NEW 171	DataVisualizer.normalMode = !DataVisualizer.normalMode;	×
172	}
173
174	public static getBinTreeMode(): boolean {
175	return DataVisualizer.BinTreeMode;	7✔
176	}
177
178	public static getTreeMode(): boolean {
179	return DataVisualizer.treeMode;	8✔
180	}
181
182	public static getNormalMode(): boolean {
NEW 183	return DataVisualizer.normalMode;	×
184	}
185
186	public static hasCycle(structures: Data, visited: WeakSet<object> = new WeakSet()): boolean {	3✔
187	if (!(structures instanceof Array)) {	9✔
188	return false;	5✔
189	}
190	if (visited.has(structures)) {	4✔
191	return true;	1✔
192	}
193	visited.add(structures);	3✔
194	return this.hasCycle(structures[0], visited) \|\| this.hasCycle(structures[1], visited);	3✔
195	}
196
197	public static drawData(structures: Data[]): void {
198	if (!DataVisualizer.setSteps) {	3!
NEW 199	throw new Error("Data visualizer not initialized");	×
200	}
201	if (!DataVisualizer.isRedraw) {	3!
202	this.dataRecords.push(structures);	3✔
203	}
204	const root = structures[0];	3✔
205	const isCyclic = this.hasCycle(root);	3✔
206	DataVisualizer.nodeCount = [];	3✔
207	DataVisualizer.nodeColor = [];	3✔
208	this.nodeColor[0] = -1;	3✔
209	DataVisualizer.longestNodePos = 0;	3✔
210	DataVisualizer.TreeDepth = 0;	3✔
211	if (isCyclic) {	3✔
212	DataVisualizer.isBinTree = false;	1✔
213	DataVisualizer.isGenTree = false;	1✔
214	} else {
215	DataVisualizer.isBinTree = this.isBinaryTree(root, null);	2✔
216	DataVisualizer.isGenTree = this.isGeneralTree(root, null);	2✔
217	if (DataVisualizer.isBinTree \|\| DataVisualizer.isGenTree) {	2✔
218	this.initializeTreeMetaData(root, 0, 0, false);	1✔
219	}
220	}
221	DataVisualizer._instance.addStep(structures);	3✔
222
223	DataVisualizer.setSteps(DataVisualizer._instance.steps);	3✔
224	}
225
226	public static clearWithData(): void {
NEW 227	DataVisualizer.longestNodePos = 0;	×
NEW 228	DataVisualizer.dataRecords = [];	×
NEW 229	DataVisualizer.isRedraw = false;	×
NEW 230	DataVisualizer.clear();	×
231	}
232
233	public static clear(): void {
NEW 234	DataVisualizer._instance = new DataVisualizer();	×
NEW 235	this.nodeCount = [];	×
NEW 236	this.TreeDepth = 0;	×
NEW 237	DataVisualizer.setSteps(DataVisualizer._instance.steps);	×
238	}
239
240	public static displaySpecialContent(dataNode: DataTreeNode): number {
NEW 241	return DataVisualizer._instance.displaySpecialContent(dataNode);	×
242	}
243
244	private displaySpecialContent(dataNode: DataTreeNode): number {
NEW 245	if (this.nodeToLabelMap.has(dataNode)) {	×
NEW 246	return this.nodeToLabelMap.get(dataNode) ?? 0;	×
247	} else {
NEW 248	this.nodeToLabelMap.set(dataNode, this.nodeLabel);	×
NEW 249	return this.nodeLabel++;	×
250	}
251	}
252
253	private addStep(structures: Data[]) {
254	const step = structures.map((xs, index) => this.createDrawing(xs, index));	3✔
255	this.steps.push(step);	3✔
256	}
257
258	private createDrawing(xs: Data, key: number): React.ReactElement {
259	const treeDrawer = Tree.fromSourceStructure(xs).draw();	3✔
260
261	// To account for overflow to the left side due to a backward arrow
262	const leftMargin = Config.StrokeWidth / 2;	3✔
263
264	// To account for overflow to the top due to a backward arrow
265	const topMargin = Config.StrokeWidth / 2;	3✔
266
267	return treeDrawer.draw(leftMargin, topMargin, key);	3✔
268	}
269
270	static redraw() {
NEW 271	this.isRedraw = true;	×
NEW 272	this.clear();	×
NEW 273	try {	×
NEW 274	return DataVisualizer.dataRecords.map(structures => this.drawData(structures));	×
275	} finally {
NEW 276	this.isRedraw = false;	×
277	}
278	}
279	}

source-academy / plugins / 27974749198

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