Golang Dynamic Decision Tree

Overview

Go Report Card codecov Build Status Go Reference

DDT

Dynamic decision tree

DDT allows building custom decision trees based in a set of defined rules, programmatically or from json.

When making a decision, it allows adding a pre-processing stage to the input before comparing it with the following possible branches of the tree.

One of the default preprocessing functions in ddt is calling a method of a struct (CallStructMethod) and getting the attribute of a struct (GetStructAttribute) using reflection.

Examples

Create user tree

Use a struct as input of the tree and pre-process data before comparing with the next level of nodes. In this example we use some methods and attributes of the user struct.
alt text

package main

import (
	"fmt"
	"github.com/sgrodriguez/ddt"
	"github.com/sgrodriguez/ddt/compare"
	"github.com/sgrodriguez/ddt/function"
	"github.com/sgrodriguez/ddt/value"
)

type user struct {
	Age       int
	FirstName string
	LastName  string
}

func (u *user) UnderAge() bool {
	return u.Age < 18
}

func (u *user) FullName() string {
	return u.FirstName + " " + u.LastName
}

func main() {
	node6 := &ddt.Node{
		ID:             6,
		ParentID:       2,
		ValueToCompare: &value.Value{Type: value.Int, Value: 30},
		Result:         &value.Value{Type: value.String, Value: "node6"},
		Comparer:       &compare.Greater{},
	}
	node5 := &ddt.Node{
		ID:             5,
		ParentID:       2,
		ValueToCompare: &value.Value{Type: value.Int, Value: 30},
		Result:         &value.Value{Type: value.String, Value: "node5"},
		Comparer:       &compare.Lesser{Equal: true},
	}
	node3 := &ddt.Node{
		ID:             3,
		ParentID:       1,
		ValueToCompare: &value.Value{Type: value.String, Value: "SANTIAGO LUCIA"},
		Result:         &value.Value{Type: value.String, Value: "node3"},
		Comparer:       &compare.Equal{},
	}
	node4 := &ddt.Node{
		ID:             4,
		ParentID:       1,
		ValueToCompare: &value.Value{Type: value.String, Value: "LUCIA SANTIAGO"},
		Result:         &value.Value{Type: value.String, Value: "node4"},
		Comparer:       &compare.Equal{},
	}
	node1 := &ddt.Node{
		ID:             1,
		ParentID:       0,
		Children:       []*ddt.Node{node3, node4},
		ValueToCompare: &value.Value{Type: value.Bool, Value: true},
		PreProcessArgs: []*value.Value{{Type: value.String, Value: "FullName"}},
		PreProcessFn:   function.PreProcessFn{Function: function.CallStructMethod, Name: "CallStructMethod"},
		Comparer:       &compare.Equal{},
	}
	node2 := &ddt.Node{
		ID:             2,
		ParentID:       0,
		Children:       []*ddt.Node{node5, node6},
		ValueToCompare: &value.Value{Type: value.Bool, Value: false},
		Comparer:       &compare.Equal{},
		PreProcessArgs: []*value.Value{{Type: value.String, Value: "Age"}},
		PreProcessFn:   function.PreProcessFn{Function: function.GetStructAttribute, Name: "GetStructAttribute"},
	}
	root := &ddt.Node{
		Children:       []*ddt.Node{node1, node2},
		PreProcessArgs: []*value.Value{{Type: value.String, Value: "UnderAge"}},
		PreProcessFn:   function.PreProcessFn{Function: function.CallStructMethod, Name: "CallStructMethod"},
		ID:             0,
		ParentID:       -1,
	}
	userTree, err := ddt.NewTree("userTree", root)
	if err != nil {
		panic(err)
	}
	result, err := ddt.ResolveTree(userTree, &user{Age: 12, FirstName: "SANTIAGO", LastName: "LUCIA"})
	if err != nil {
		panic(err)
	}
	// result node3
	fmt.Println(result.(string))
}

Create the user tree from json

package main


import (
	"encoding/json"
	"fmt"
	"github.com/sgrodriguez/ddt"
)

type user struct {
	Age       int
	FirstName string
	LastName  string
}

func (u *user) UnderAge() bool {
	return u.Age < 18
}

func (u *user) FullName() string {
	return u.FirstName + " " + u.LastName
}

func main() {
	// define empty tree
	tree, err := ddt.NewTree("newTree", &ddt.Node{ID: 0, ParentID: -1})
	if err != nil {
		panic(err)
	}
	treeFromJson := []byte(`
{
   "nodes":[
      {
         "preProcessFnName":"CallStructMethod",
         "id":0,
         "parentId":-1,
         "preProcessFnArgs":[
            {
               "Value":"UnderAge",
               "Type":"string"
            }
         ]
      },
      {
         "preProcessFnName":"CallStructMethod",
         "id":1,
         "parentId":0,
         "preProcessFnArgs":[
            {
               "Value":"FullName",
               "Type":"string"
            }
         ],
         "comparer":{
            "type":"eq"
         },
         "valueToCompare":{
            "Value":true,
            "Type":"bool"
         }
      },
      {
         "preProcessFnName":"GetStructAttribute",
         "id":2,
         "parentId":0,
         "preProcessFnArgs":[
            {
               "Value":"Age",
               "Type":"string"
            }
         ],
         "comparer":{
            "type":"eq"
         },
         "valueToCompare":{
            "Value":false,
            "Type":"bool"
         }
      },
      {
         "preProcessFnName":"",
         "id":3,
         "parentId":1,
         "comparer":{
            "type":"eq"
         },
         "valueToCompare":{
            "Value":"SANTIAGO LUCIA",
            "Type":"string"
         },
         "result":{
            "Value":"node3",
            "Type":"string"
         }
      },
      {
         "preProcessFnName":"",
         "id":4,
         "parentId":1,
         "comparer":{
            "type":"eq"
         },
         "valueToCompare":{
            "Value":"LUCIA SANTIAGO",
            "Type":"string"
         },
         "result":{
            "Value":"node4",
            "Type":"string"
         }
      },
      {
         "preProcessFnName":"",
         "id":5,
         "parentId":2,
         "comparer":{
            "type":"lt",
            "equal":true
         },
         "valueToCompare":{
            "Value":30,
            "Type":"int"
         },
         "result":{
            "Value":"node5",
            "Type":"string"
         }
      },
      {
         "preProcessFnName":"",
         "id":6,
         "parentId":2,
         "comparer":{
            "type":"gt",
            "equal":false
         },
         "valueToCompare":{
            "Value":30,
            "Type":"int"
         },
         "result":{
            "Value":"node6",
            "Type":"string"
         }
      }
   ],
   "name":"userTree"
}`)
	err = json.Unmarshal(treeFromJson, tree)
	if err != nil {
		panic(err)
	}
	result, err := ddt.ResolveTree(tree, &user{Age: 12, FirstName: "SANTIAGO", LastName: "LUCIA"})
	if err != nil {
		panic(err)
	}
	// result node3
	fmt.Println(result.(string))
	treeByte, err := json.Marshal(tree)
	fmt.Println(string(treeByte))
}

Create simple tree

Create a simple tree using only basic types. alt text

package main

import (
	"fmt"
	"github.com/sgrodriguez/ddt"
	"github.com/sgrodriguez/ddt/compare"
	"github.com/sgrodriguez/ddt/value"
)

func main() {
	leaf1 := ddt.Node{
		ID:             1,
		ParentID:       0,
		ValueToCompare: &value.Value{Value: int64(60), Type: value.Int64},
		Comparer:       &compare.Greater{},
		Result:         &value.Value{Value: "prize1", Type: value.String},
	}
	leaf11 := ddt.Node{
		ID:             3,
		ParentID:       2,
		ValueToCompare: &value.Value{Value: int64(30), Type: value.Int64},
		Comparer:       &compare.Equal{},
		Result:         &value.Value{Value: "prize2", Type: value.String},
	}
	leaf12 := ddt.Node{
		ID:             4,
		ParentID:       2,
		ValueToCompare: &value.Value{Value: int64(30), Type: value.Int64},
		Comparer:       &compare.Greater{},
		Result:         &value.Value{Value: "prize3", Type: value.String},
	}
	leaf13 := ddt.Node{
		ID:             5,
		ParentID:       2,
		ValueToCompare: &value.Value{Value: int64(30), Type: value.Int64},
		Comparer:       &compare.Lesser{},
		Result:         &value.Value{Value: "prize4", Type: value.String},
	}
	node1 := ddt.Node{
		Children:       []*ddt.Node{&leaf11, &leaf12, &leaf13},
		ID:             2,
		ParentID:       0,
		ValueToCompare: &value.Value{Value: int64(60), Type: value.Int64},
		Comparer:       &compare.Lesser{Equal: true},
	}
	root := ddt.Node{
		ID:       0,
		ParentID: -1,
		Children: []*ddt.Node{&node1, &leaf1},
	}
	simpleTree, err := ddt.NewTree("simpleTree", &root)
	if err != nil {
		panic(err)
	}
	result, err := ddt.ResolveTree(simpleTree,int64(15))
	if err != nil {
		panic(err)
	}
	fmt.Println(result.(string))
}

Create simple tree from json

Create or modify the simple tree from json

package main

import (
	"encoding/json"
	"fmt"
	"github.com/sgrodriguez/ddt"
)

func main() {
	// define empty tree
	tree, err := ddt.NewTree("newTree", &ddt.Node{ID: 0, ParentID: -1})
	if err != nil {
		panic(err)
	}
	treeFromJson := []byte(`
{
   "nodes":[
      {
         "preProcessFnName":"",
         "id":0,
         "parentId":-1
      },
      {
         "preProcessFnName":"",
         "id":2,
         "parentId":0,
         "comparer":{
            "type":"lt",
            "equal":true
         },
         "valueToCompare":{
            "Value":60,
            "Type":"int64"
         }
      },
      {
         "preProcessFnName":"",
         "id":1,
         "parentId":0,
         "comparer":{
            "type":"gt",
            "equal":false
         },
         "valueToCompare":{
            "Value":60,
            "Type":"int64"
         },
         "result":{
            "Value":"prize1",
            "Type":"string"
         }
      },
      {
         "preProcessFnName":"",
         "id":3,
         "parentId":2,
         "comparer":{
            "type":"eq"
         },
         "valueToCompare":{
            "Value":30,
            "Type":"int64"
         },
         "result":{
            "Value":"prize2",
            "Type":"string"
         }
      },
      {
         "preProcessFnName":"",
         "id":4,
         "parentId":2,
         "comparer":{
            "type":"gt",
            "equal":false
         },
         "valueToCompare":{
            "Value":30,
            "Type":"int64"
         },
         "result":{
            "Value":"prize3",
            "Type":"string"
         }
      },
      {
         "preProcessFnName":"",
         "id":5,
         "parentId":2,
         "comparer":{
            "type":"lt",
            "equal":false
         },
         "valueToCompare":{
            "Value":30,
            "Type":"int64"
         },
         "result":{
            "Value":"prize4",
            "Type":"string"
         }
      }
   ],
   "name":"simpleTree"
}`)
	err = json.Unmarshal(treeFromJson, tree)
	if err != nil {
		panic(err)
	}
	result, err := ddt.ResolveTree(tree, int64(15))
	if err != nil {
		panic(err)
	}
	// result prize4
	fmt.Println(result.(string))
	// change some property of the tree for example the result of prize4
	modifiedTree := []byte(`{"nodes":[{"preProcessFnName":"","id":0,"parentId":-1},{"preProcessFnName":"","id":2,"parentId":0,"comparer":{"type":"lt","equal":true},"valueToCompare":{"Value":60,"Type":"int64"}},{"preProcessFnName":"","id":1,"parentId":0,"comparer":{"type":"gt","equal":false},"valueToCompare":{"Value":60,"Type":"int64"},"result":{"Value":"prize1","Type":"string"}},{"preProcessFnName":"","id":3,"parentId":2,"comparer":{"type":"eq"},"valueToCompare":{"Value":30,"Type":"int64"},"result":{"Value":"prize2","Type":"string"}},{"preProcessFnName":"","id":4,"parentId":2,"comparer":{"type":"gt","equal":false},"valueToCompare":{"Value":30,"Type":"int64"},"result":{"Value":"prize3","Type":"string"}},{"preProcessFnName":"","id":5,"parentId":2,"comparer":{"type":"lt","equal":false},"valueToCompare":{"Value":30,"Type":"int64"},"result":{"Value": 420,"Type":"int64"}}],"name":"simpleTree"}`)
	err = json.Unmarshal(modifiedTree, tree)
	if err != nil {
		panic(err)
	}
	result, err = ddt.ResolveTree(tree, int64(15))
	if err != nil {
		panic(err)
	}
	// result 420
	fmt.Println(result.(int64))
}

Overview

Node

  • ID: id of the node, root node must have 0.
  • ParentID: parent id, root node must have -1.
  • Result: if the node is leaf and is the next node of the tree, this is the result.
  • Comparer.
  • ValueToCompare: value
  • PreProcessFn: function to pre-process the input before comparing.
  • PreProcessArgs.

Value

Basic types available for comparing, result and as PreProcessArgs.

  • Int
  • Int64
  • Bool
  • String
  • Float64

Comparators

  • Greater (or Equal)
  • Lesser (or Equal)
  • Equal

Pre-Process Functions

Functions to pre-process the input before comparing with the next level of the tree.

  • CallStructMethod
  • GetStructAttribute
Releases(v0.1.0)
Owner
Santiago
Ms Computer Science Student and Software Engineer.
Santiago
Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Arun Shaji 3 Oct 6, 2021
Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Arthur Abeilice 0 Oct 14, 2021
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

web_developer 1 Oct 9, 2021
Dynamic object-oriented programming support for the Go language

Goop Description The Goop (Go Object-Oriented Programming) package provides support for dynamic object-oriented programming constructs in Go, much lik

Los Alamos National Laboratory 103 Dec 5, 2021
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 18 Aug 26, 2021
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 301 Jan 13, 2022
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 17 Dec 28, 2021
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

Michael Lore 26 Dec 8, 2021
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Yasushi Saito 19 Jan 2, 2020
an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Daniel Connelly 499 Jan 17, 2022
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 170 Jan 9, 2022
Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Josh Baker 93 Oct 8, 2021
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Amit Davidson 189 Jan 2, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 2 Sep 13, 2021
Segment tree for bytes in Go

bsegtree Segment tree for bytes in Go Based on Thomas Oberndörfer's int range segment tree with fixing/optimization/modification for bytes ranges. For

Temple3x 2 Dec 20, 2021
A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

Victor Zeddys 1 Nov 1, 2021
A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

null 0 Nov 24, 2021
publish a tree-like data structure from a backend to a front-end

tree-publish publish a tree-like data structure from a backend to a front-end. It needs to be a tree in order to publish the data as JSON document. If

Lutz Behnke 0 Dec 20, 2021
Mmpxmas-go - ModMyPi Programmable Christmas Tree examples written in Go with go-rpio

ModMyPi Programmable Christmas Tree examples in Go This small program contains examples similar to the examples provided by ModMyPi for interacting wi

Tyler Darnell 0 Jan 4, 2022