I tried to make Trie data structures by Go Language, but somehow it stuck with References problem, Here it is. http://play.golang.org/p/ASSGF5Oe9R
// Package main provides ...
package main
import "fmt"
type RootTrie []Trie
type Trie struct {
subtrie []Trie
index byte
}
func (trie *Trie) Insert(data string) *Trie {
if data != "" {
if trie.index == 0 {
trie.index = data[0]
}
if next := trie.containsIndex(data[1:]); next != nil {
//Problem Point
fmt.Println(string(data[1]), "found follwing", string(data[0]))
next.Insert(data[1:])
} else {
nt := &Trie{}
trie.subtrie = append(trie.subtrie, *nt.Insert(data[1:]))
}
}
return trie
}
func (trie *Trie) containsIndex(next string) *Trie {
if next != "" {
for _, st := range trie.subtrie {
if st.index == next[0] {
return &st
}
}
}
return nil
}
func main() {
t := &Trie{}
t = t.Insert("hanyang")
fmt.Println("result:", t)
t = t.Insert("hanyKk")
fmt.Println("result:", t)
t.Insert("hanyK")
}
The following problems happen in second "Insert",
the where I put, //Problem Point
I made containsIndex
method for searching next linked trie, and it searched well actually.
But when I updated next
property which containsIndex
given, its not affected its mother struct trie
though.
What I don't understand is I gave it reference type when returning containsIndex
, but its still
act liked 'value copied', Why does it not affected its mother structure(trie
)?
Thanks!
The problem is in method containsIndex. Golang range
by default creates copy each element in slice and assigns copy of this value to st
(in your example). Usually to preserve reference to element in slice you should use original slice and its index. In you case method containsIndex should look something like this:
func (trie *Trie) containsIndex(next string) *Trie {
if next != "" {
for i, st := range trie.subtrie {
if st.index == next[0] {
return &trie.subtrie[i]
}
}
}
return nil
}