1.0.2 • Published 3 years ago
declarative-tree v1.0.2
Table of contents
- Table of contents
- Installation
- Description
- Code coverage
- Examples
- Documentation
- Motivation
- Contributing
- Changelog
- License
Installation
npm install declarative-treeDescription
Generalized way to convert a string to tree, and vice versa. Useful for creating declarative tree tests.
Code coverage
The testing code coverage is around 90%.
Examples
The following examples deal with converting an AVL tree string representation to tree data structure and vice versa. Here is the code that defines the AVL tree:
class AvlTreeBaseNode {
left: null | AvlTreeNode;
right: null | AvlTreeNode;
id: number;
constructor(_: AvlTreeBaseNode) {
const { id, left, right } = _;
this.id = id;
this.left = left;
this.right = right;
}
}
export class AvlTreeRootNode extends AvlTreeBaseNode {
parent: null;
constructor(_: AvlTreeRootNode) {
const { id, left, right } = _;
super({
id,
left,
right,
});
this.parent = null;
}
}
export class AvlTreeNode extends AvlTreeBaseNode {
parent: AvlTreeNode | AvlTreeRootNode;
constructor(_: AvlTreeNode) {
const { parent, right, left, id } = _;
super({
id,
left,
right,
});
this.parent = parent;
}
}
export class AvlTree {
root: AvlTreeRootNode;
constructor(_: { root: AvlTreeRootNode }) {
const { root } = _;
this.root = root;
}
}
/**
* @description
* The tree looks like this:
* ```
* 20
* |_ 25
* |_ 10
* |_ 5
* ```
*/
export const mockAvlTree: AvlTree = (() => {
const root: AvlTreeRootNode = new AvlTreeRootNode({
id: 20,
left: null, //lazy setted
parent: null,
right: null, //lazy setted
});
const tree: AvlTree = new AvlTree({
root,
});
const left: AvlTreeNode = new AvlTreeNode({
id: 10,
left: null, //lazy setted
parent: root,
right: null,
});
const leftLeft: AvlTreeNode = new AvlTreeNode({
id: 5,
left: null,
parent: left,
right: null,
});
const right: AvlTreeNode = new AvlTreeNode({
id: 25,
left: null,
parent: root,
right: null,
});
root.left = left;
root.right = right;
left.left = leftLeft;
return tree;
})();tree to string
import { treeToStringHorizontalFactory } from "..";
import { AvlTree, AvlTreeNode, AvlTreeRootNode, mockAvlTree } from "./mockTree";
describe(treeToStringHorizontalFactory.name, () => {
it(`
returns a function that converts a tree to string, according to the
instructions the factory has been provided
`, () => {
const avlTreeToString = treeToStringHorizontalFactory<
AvlTreeNode | AvlTreeRootNode,
AvlTree
>({
getChildren: ({ treeNode }) => {
const children: AvlTreeNode[] = [];
const { left, right } = treeNode;
if (left !== null) children.push(left);
if (right !== null) children.push(right);
return children.reverse();
},
getRoot: ({ tree }) => tree.root,
nodeToString: ({ treeNodeMetadata }) =>
String(treeNodeMetadata.treeNode.id),
});
//prettier-ignore
expect(avlTreeToString({ tree: mockAvlTree })).toBe(
`20\n`+
`|_ 25\n`+
`|_ 10\n`+
` |_ 5`
);
});
});string to tree horizontal
import { stringToTreeHorizontalFactory } from "..";
import { AvlTree, AvlTreeNode, AvlTreeRootNode, mockAvlTree } from "./mockTree";
describe(stringToTreeHorizontalFactory.name, () => {
it(`
returns a function that converts a string to tree, according to the
instructions the factory has been provided
`, () => {
const stringToAVLTree = stringToTreeHorizontalFactory<
number,
AvlTreeNode | AvlTreeRootNode,
AvlTree
>({
strategy: (parameters) => {
const root: AvlTreeRootNode = new AvlTreeRootNode({
id: parameters.treeNodeMetadataInLevelOrder[0]
.placeholderValue,
left: null,
parent: null,
right: null,
});
const avlTree: AvlTree = new AvlTree({ root });
/**
* @description
* The main idea here is to iterate the tree node metadata, and
* use the information they provide to create the tree nodes.
* When you create a tree node, set it as the `treeNode`
* property of the tree node metadata it corresponds. The sole
* reason for that is that maybe you will need to access that
* node from other nodes.
*/
parameters.treeNodeMetadataInLevelOrder.forEach(
(treeNodeMetadata, i) => {
if (i === 0) {
treeNodeMetadata.treeNode = root;
return;
}
if (i !== 0) {
const parentTreeNodeMetadata =
treeNodeMetadata.parent;
if (parentTreeNodeMetadata === null) {
throw Error(
"only the parent tree node metadata of" +
"the root node can be null"
);
}
const parent = parentTreeNodeMetadata.treeNode;
const currentNode: AvlTreeNode = new AvlTreeNode({
id: treeNodeMetadata.placeholderValue,
left: null,
right: null,
parent,
});
treeNodeMetadata.treeNode = currentNode;
/**
* @description
* Here I connect the parent node with its child
* node. The only way to understand whether the
* child node is a left or right child, is through
* the brach that connects them.
* You are free to use the character that you see
* fit for branches. In this example I choose to use
* `⏝` for left branch and `⏜` for right branch.
* The branch character that you use has to be used
* in the tag function that is returned by the
* factory. Take a look at the test assertion a few
* lines bellow where the tag function is used.
*/
if (treeNodeMetadata.branchTop === "⏝") {
parent.left = currentNode;
return;
}
if (treeNodeMetadata.branchTop === "⏜") {
parent.right = currentNode;
return;
}
throw Error(
`encountered branch that is not "⏝" or "⏜"`
);
}
throw Error("case not accounted for");
}
);
return avlTree;
},
});
expect(stringToAVLTree`
${20}
|⏜ ${25}
|⏝ ${10}
|⏝ ${5}
`).toEqual(mockAvlTree);
});
});string to tree vertical
import { stringToTreeVerticalFactory } from "..";
import { AvlTree, AvlTreeNode, AvlTreeRootNode, mockAvlTree } from "./mockTree";
describe(stringToTreeVerticalFactory.name, () => {
it(`
returns a function that converts a string to tree, according to the
instructions the factory has been provided
`, () => {
const stringToAvlTree = stringToTreeVerticalFactory<
number,
AvlTreeNode | AvlTreeRootNode,
AvlTree
>({
strategy: (parameters) => {
const root: AvlTreeRootNode = new AvlTreeRootNode({
id: parameters.treeNodeMetadataInLevelOrder[0]
.placeholderValue,
left: null,
parent: null,
right: null,
});
const avlTree: AvlTree = new AvlTree({ root });
/**
* @description
* The main idea here is to iterate the tree node metadata, and
* use the information they provide to create the tree nodes.
* When you create a tree node, set it as the `treeNode`
* property of the tree node metadata it corresponds. The sole
* reason for that is that maybe you will need to access that
* node from other nodes.
*/
parameters.treeNodeMetadataInLevelOrder.forEach(
(treeNodeMetadata, i) => {
if (i === 0) {
treeNodeMetadata.treeNode = root;
return;
}
if (i !== 0) {
const parentTreeNodeMetadata =
treeNodeMetadata.parent;
if (parentTreeNodeMetadata === null) {
throw Error(
"only the parent tree node metadata of " +
"the root node can be null"
);
}
const parent = parentTreeNodeMetadata.treeNode;
const currentNode: AvlTreeNode = new AvlTreeNode({
id: treeNodeMetadata.placeholderValue,
left: null,
right: null,
parent,
});
treeNodeMetadata.treeNode = currentNode;
/**
* @description
* Here I connect the parent node with its child
* node. The only way to understand whether the
* child node is a left or right child, is through
* the brach that connects them.
* You are free to use the character that you see
* fit for branches. In this example I choose to use
* `(` for left branch and `)` for right branch. The
* branch character that you use has to be used in
* the tag function that is returned by the factory.
* Take a look at the test assertion a few lines
* bellow where the tag function is used.
*/
if (treeNodeMetadata.branchTop === "(") {
parent.left = currentNode;
return;
}
if (treeNodeMetadata.branchTop === ")") {
parent.right = currentNode;
return;
}
throw Error(
`encountered branch that is not "(" or ")"`
);
}
throw Error("case not accounted for");
}
);
return avlTree;
},
});
/**
* @description
* You have to add dots. They define where the children group ends. You
* do no need to do that in the last row of the tree. For example in the
* following tree the tree node with id `20` has `10` and `25` as
* children group. The group ends at `25` and hence the dot in the
* branch above `25`. The tree node with id `10` has children group that
* consist only of the tree node with id `5` and hence the dot on its
* branch. The tree node with id `25` has no children so it has a dot
* with no branches.
*/
expect(stringToAvlTree`
${20}
( ).
${10} ${25}
(. .
${5}
`).toEqual(mockAvlTree);
});
});Documentation
/**
* @description
* Returns a tag function that converts template literals to tree data
* structures, in accordance to the instructions you have provided to the
* factory.
*/
export declare const stringToTreeHorizontalFactory: IStringToTreeFactory;/**
* @description
* Returns a tag function that converts template literals to tree data
* structures, in accordance to the instructions you have provided to the
* factory.
*/
export declare const stringToTreeVerticalFactory: IStringToTreeFactory;/**
* @description
* Returns a function that converts tree data structures to horizontal tree
* string representations, in accordance to the instructions you have provided
* to the factory.
*/
export declare const treeToStringHorizontalFactory: ITreeToStringHorizontalFactory;Motivation
I just wanted to create declarative tree tests for any kind of tree. No packages in npm could do that, so I decided to create my own.
Contributing
I am open to suggestions/pull request to improve this program.
You will find the following commands useful:
Clones the github repository of this project:
git clone https://github.com/lillallol/declarative-treeInstalls the node modules (nothing will work without them):
npm installTests the code and generates code coverage:
npm run testThe generated code coverage is saved in
./coverage.Lints the source folder using typescript and eslint:
npm run lintBuilds the typescript code from the
./srcfolder to javascript code in./dist:npm run build-tsInjects in place the generated toc and imported files to
README.md:npm run build-mdChecks the project for spelling mistakes:
npm run spell-checkTake a look at the related configuration
./cspell.json.Checks
./srcfor dead typescript files:npm run dead-filesTake a look at the related configuration
./unimportedrc.json.Logs which node modules can be updated:
npm run check-updatesUpdates the node modules to their latest version (even if they introduce breaking changes):
npm run updateFormats all the typescript files in the
./srcfolder:npm run format
Changelog
1.0.2
Bugs fixed
Placeholders groups were being over flattened. For example the following template literal:
` ${""} |_ ${"p"} |_ ${"a"} |_ ${"t"} |_ ${"h"} |_ ${["prop1", -1, "=>", 1]} `would wrongly have as placeholders:
["","p","a","t","h",...["prop1", -1, "=>", 1]]instead of:
["","p","a","t","h",["prop1", -1, "=>", 1]]
1.0.1
- Fixed some mistakes in the examples.
- Minor internal changes.
1.0.0
- Published the package.
License
MIT