2
\$\begingroup\$

This is an implementation of tree data structure using Ballerina's table collection and query expressions. The implementation allows bi-directional traversal.

The two free traversing functions walk1() and walk2() demonstrate the usage.

I'm especially looking a guidance how to make the implementation more generic. I see the only non-generic part here is the TreeNode.value field. But any other comments and implementation alternatives as long as they allow bi-directional traversal are welcome too.

This is Ballerina 2201.2.0 (Swan Lake Update 2).

import ballerina/io;

public type TreeNode record {|
    readonly int id;
    string value;
    int parentId;
    int[] childIds = [];
|};

type TreeTable table<TreeNode> key(id);

class Tree {
    private TreeTable tree = table [];
    // TODO: might run out of numbers -> run-time panic
    // but we're not allowing removal yet so will do for now
    private int currentId = 1;

    public function init(string rootNodeValue) {
        self.tree.add({
            id: self.currentId,
            value: rootNodeValue,
            parentId: 0
        });
        self.currentId += 1;
    }

    public function add1(int parentId, string nodeValue) returns int {
        return self.add2(parentId, nodeValue)[0];
    }

    public function add2(int parentId, string... nodeValues) returns int[] {
        TreeNode parent = (
            from TreeNode item in self.tree
            where item.id == parentId
            limit 1
            select item
        )[0]; // <- TODO: might panic run-time but will do for now
        int [] ids = [];
        foreach string nodeValue in nodeValues {
            ids.push(self.currentId);
            self.tree.add({
                id: self.currentId,
                value: nodeValue,
                parentId: parentId
            });
            self.currentId += 1;
        }
        parent.childIds.push(...ids);
        return ids;
    }

    public function getRoot() returns TreeNode {
        return <TreeNode>self.getNodeById(1);
    }

    public function getNodeById(int id) returns TreeNode? {
        if id < 1 {
            return ();
        }
        TreeNode[] nodes = 
            from TreeNode item in self.tree
            where item.id == id
            limit 1
            select item
        ;
        if nodes.length() > 0 {
            return nodes[0];
        } else {
            return ();
        }
    }

    public function getNodeByValue(string nodeValue) returns TreeNode? {
        TreeNode[] nodes = 
            from TreeNode item in self.tree
            where item.value == nodeValue
            limit 1
            select item
        ;
        if nodes.length() > 0 {
            return nodes[0];
        } else {
            return ();
        }
    }

    public function toString() returns string {
        return self.tree.toString();
    }
}

function walk1(Tree tree, TreeNode? startNode) {
    if startNode !is () {
        io:print(startNode.value); io:print(" ");
        foreach var childId in startNode.childIds {
            TreeNode child = <TreeNode>tree.getNodeById(childId);
            walk1(tree, startNode = child);
        }
    }
}

function walk2(Tree tree, TreeNode? startNode) {
    if startNode !is () {
        io:print(startNode.value); io:print(" ");
        TreeNode? parent = tree.getNodeById(startNode.parentId);
        if parent is TreeNode {
            walk2(tree, parent);
        }
    }
}

//       A
//  B    C     D
// E F  G H  I J K
public function main() {
    Tree tree = new("A");
    
    int[] bc = tree.add2(1, "B", "C");
    int d = tree.add1(1, "D");
 
    _ = tree.add2(bc[0], "E", "F");
    _ = tree.add2(bc[1], "G", "H");
    _ = tree.add2(d, "I", "J", "K");
 
    // io:println(tree);

    walk1(tree, startNode = tree.getRoot()); io:println();
    walk1(tree, startNode = tree.getNodeByValue("C")); io:println();

    walk2(tree, startNode = tree.getNodeByValue("J")); io:println();
}

When the program is executed it prints:

A B E F C G H D I J K 
C G H 
J D A 

as expected.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.