View
99 src/ccm/lib/lca/lca.go
@@ -0,0 +1,99 @@
package lca
type node struct {
name string
children []*node
ancestor *node
rank int
color int
parent *node
}
type Data struct {
Name string
Children []*Data
}
var root, target_node_1, target_node_2 *node
func makeset(n *node) {
n.parent = n
n.rank = 1
}
func union(nodex, nodey *node) {
xroot := find(nodex)
yroot := find(nodey)
if xroot.rank > yroot.rank {
yroot.parent = xroot
} else if xroot.rank < yroot.rank {
xroot.parent = yroot
} else if xroot.rank == yroot.rank {
yroot.parent = xroot
xroot.rank += 1
}
}
func find(node *node) *node {
if node.parent != node {
node.parent = find(node.parent)
}
return node.parent
}
func lca(node *node) (*node, bool) {
makeset(node)
node.ancestor = node
for _, child := range node.children {
return_value, found := lca(child)
if found == true {
return return_value, found
}
union(node, child)
this_node := find(node)
this_node.ancestor = node
}
node.color = 1
if node.name == target_node_2.name && target_node_2.color == 1 && target_node_1.color == 1 {
return_val := find(target_node_1).ancestor
return return_val, true
} else if node.name == target_node_1.name && target_node_2.color == 1 && target_node_1.color == 1 {
return_val := find(target_node_2).ancestor
return return_val, true
} else {
return nil, false
}
}
func find_node_by_name(name string, parent *node) (*node, bool) {
if parent.name == name {
return parent, true
}
for _, child := range parent.children {
node, found := find_node_by_name(name, child)
if found == true {
return node, true
}
}
return nil, false
}
func build_tree(data *Data) *node {
node := &node{name: data.Name}
for _,child := range data.Children {
child_node := build_tree(child)
node.children = append(node.children, child_node)
}
return node
}
func Search(name1, name2 string) string {
target_node_1, _ = find_node_by_name(name1, root)
target_node_2, _ = find_node_by_name(name2, root)
ancestor, _ := lca(root)
return ancestor.name
}
func Init(data *Data) {
root = build_tree(data)
}
View
39 src/ccm/lib/lca/lca_test.go
@@ -0,0 +1,39 @@
package lca
import "testing"
func TestSearch(t *testing.T) {
var one, two, three, four, five, six, seven *Data
one = &Data{Name: "1"}
two = &Data{Name: "2"}
three = &Data{Name: "3"}
four = &Data{Name: "4"}
five = &Data{Name: "5"}
six = &Data{Name: "6"}
seven = &Data{Name: "7"}
one.Children = append(one.Children, two)
one.Children = append(one.Children, three)
two.Children = append(two.Children, four)
two.Children = append(two.Children, five)
three.Children = append(three.Children, six)
three.Children = append(three.Children, seven)
Init(one)
ancestor := Search("3", "4")
if ancestor != "1" {
t.Errorf("Search was incorrect, got: %s, want %s", ancestor, "1")
}
Init(one)
ancestor = Search("5", "4")
if ancestor != "2" {
t.Errorf("Search was incorrect, got: %s, want %s", ancestor, "2")
}
Init(one)
ancestor = Search("7", "1")
if ancestor != "1" {
t.Errorf("Search was incorrect, got: %s, want %s", ancestor, "1")
}
}
View
82 src/ccm/model/employee_model/employee.go
@@ -0,0 +1,82 @@
package employee_model
import (
"ccm/datastore/memory" //should have been an interface rather
"ccm/lib/lca"
"strconv"
)
type Employee struct {
Id int
Name string
Manages []*Employee
}
func Create(name string) *Employee {
employee := &Employee{Name: name}
return employee
}
func (employee_obj *Employee) Save() *Employee {
var data map[string]interface{}
data = make(map[string]interface{})
data["name"] = employee_obj.Name //Not checking if names are duplicates
manages_employee_id := []int{}
for _, employee := range employee_obj.Manages {
manages_employee_id = append(manages_employee_id, employee.Id)
}
data["manages_employee_id"] = manages_employee_id
if employee_obj.Id == 0 {
saved_data := memory.Set(data)
employee_obj.Id = saved_data.Id
} else {
memory.Update(employee_obj.Id, data)
}
return employee_obj
}
func (manager_obj *Employee) Link_employee(employee_obj *Employee) {
manager_obj.Manages = append(manager_obj.Manages, employee_obj)
manager_obj.Save()
}
func build_data(data *Employee) *lca.Data {
//this should be elsewhere
employee_node := &lca.Data{Name: data.Name}
for _, employee := range data.Manages {
employee_child_node := build_data(employee)
employee_node.Children = append(employee_node.Children, employee_child_node)
}
return employee_node
}
func Search_common_manager (ceo, employee1, employee2 *Employee) *Employee {
data := build_data(ceo)
lca.Init(data)
common_manager := lca.Search(employee1.Name, employee2.Name)
common_manager_obj := Find_by_name(common_manager)
return common_manager_obj
}
func Delete() {}
func Find() {}
func build_employee_obj(data *memory.Entry) *Employee {
employee_obj := &Employee{Id: data.Id, Name: data.Data["name"].(string)}
for _, id := range data.Data["manages_employee_id"].([]int) {
me_entry := memory.Get("Id", strconv.Itoa(id))
me_obj := build_employee_obj(me_entry)
employee_obj.Manages = append(employee_obj.Manages, me_obj)
}
return employee_obj
}
func Find_by_name(name string) *Employee{
employee := memory.Get("name", name)
employee_obj := build_employee_obj(employee)
return employee_obj
}
View
39 src/ccm/model/employee_model/employee_test.go
@@ -0,0 +1,39 @@
package employee_model
import "testing"
func TestCreate(t *testing.T) {
employee := Create("Claire")
if employee.Name != "Claire" {
t.Errorf("Create was incorrect, got: %s, want %s", employee.Name, "Claire")
}
}
func TestSave(t *testing.T) {
employee := Create("Claire")
employee_obj := employee.Save()
if employee_obj.Id != 1 {
t.Errorf("Save failed. id got: %d, want: %d", employee_obj.Id, 1)
}
employee2 := Create("Claire 2")
employee_obj = employee2.Save()
if employee_obj.Id != 2 {
t.Errorf("Save failed. id got: %d, want: %d", employee_obj.Id, 2)
}
}
func TestLink_employee(t *testing.T) {
employee := Create("Claire")
employee_obj := employee.Save()
employee2 := Create("Claire 2")
employee2_obj := employee2.Save()
employee_obj.Link_employee(employee2_obj)
if len(employee_obj.Manages) != 1 {
t.Errorf("Link failed. lenght got: %d, want: %d", len(employee_obj.Manages), 1)
}
}
View
3 src/ccm/repository/employee/employee.go
@@ -0,0 +1,3 @@
package employee_repo
import "ccm/model/employee_model"