Golang: How to create unknown (dynamic) Map length

Question

I can create a "static" map via

type m map[int]map[int]map[int]bool

but the length of "keys" will be dynamic:

 |---unknown len--|
m[1][2][3][4][2][0] = true

or

|---unk len--|
m[1][2][3][4] = true

How I can create this map in Go? Or any way exists?

Added: Hierarchical is IMPORTANT

Thanks in advance!

Answer 1

The map type:

A map is an unordered group of elements of one type, called the element type, indexed by a set of unique keys of another type, called the key type.

A map type must have a specific value type and a specific key type. What you want does not qualify for this: you want a map where the value is sometimes another map (of the same type), and sometimes it's a bool.

Your options:

1. With a wrapper value type

The idea here is to not use just a simple (bool) value type, but a wrapper which holds both of your potential values: both a map and the simple value (bool):

type Value struct {
    Children MapType
    V        bool
}

type MapType map[int]*Value

var m MapType

This is basically what user3591723 suggested, so I won't detail it further.

2. With a tree

This is a variant of #1, but this way we clearly communicate it's a tree.

The cleanest way to implement your hierarchical structure would be to use a tree, where a node could look like this:

type KeyType int
type ValueType string

type Node struct {
    Children map[KeyType]*Node
    Value    ValueType
}

This has the advantage that you may choose the value type (which is bool in your case, but you can change it to whatever type - I used string for presentation).

For easily build / manage your tree, we can add some methods to our Node type:

func (n *Node) Add(key KeyType, v ValueType) {
    if n.Children == nil {
        n.Children = map[KeyType]*Node{}
    }
    n.Children[key] = &Node{Value: v}
}

func (n *Node) Get(keys ...KeyType) *Node {
    for _, key := range keys {
        n = n.Children[key]
    }
    return n
}

func (n *Node) Set(v ValueType, keys ...KeyType) {
    n = n.Get(keys...)
    n.Value = v
}

And using it: 1. build a tree, 2. query some values, 3. change a value:

root := &Node{Value: "root"}
root.Add(0, "first")
root.Get(0).Add(9, "second")
root.Get(0, 9).Add(3, "third")
root.Get(0).Add(4, "fourth")

fmt.Println(root)
fmt.Println(root.Get(0, 9, 3))
fmt.Println(root.Get(0, 4))

root.Set("fourthMod", 0, 4)
fmt.Println(root.Get(0, 4))

Output (try it on the Go Playground):

&{map[0:0x104382f0] root}
&{map[] third}
&{map[] fourth}
&{map[] fourthMod}

3. With a recursive type definition

It may be surprising but it is possible to define a map type in Go which has unlimited or dynamic "depth", using a recursive definition:

type X map[int]X

It is what it says: it's a map with int keys, and values of the same type as the map itself.

The big downside of this recursive type is that it can't store any "useful" data in the value type. It can only store the "fact" whether a value is present which is identical to a bool-like information (bool type: true or false), which may be enough in rare cases, but not in most.

Let's see an example building a "tree":

var x X
x = map[int]X{}
x[0] = map[int]X{}
x[0][9] = map[int]X{}
x[0][9][3] = map[int]X{}
x[0][4] = map[int]X{}
fmt.Println(x)

Output:

map[0:map[9:map[3:map[]] 4:map[]]]

If we want to test if there is a "value" based on a series of keys, we have 2 options: either use the special v, ok := m[i] indexing (which reports if a value for the specified key exists), or test if the value is not nil, e.g. m[i] != nil.

Let's see some examples testing the above built map:

var ok bool
_, ok = x[0][9][3]
fmt.Println("x[0][9][3] exists:", ok, "; alternative way:", x[0][9][3] != nil)
_, ok = x[0][9][4]
fmt.Println("x[0][9][4] exists:", ok, "; alternative way:", x[0][9][4] != nil)
_, ok = x[0][4]
fmt.Println("x[0][4] exists:", ok, "; alternative way:", x[0][4] != nil)
_, ok = x[0][4][9][9][9]
fmt.Println("x[0][4][9][9][9] exists:", ok, "; alternative way:", x[0][4][9][9][9] != nil)

Output:

x[0][9][3] exists: true ; alternative way: true
x[0][9][4] exists: false ; alternative way: false
x[0][4] exists: true ; alternative way: true
x[0][4][9][9][9] exists: false ; alternative way: false

Try these on the Go Playground.

Note: Even though x[0][4] is the last "leaf", indexing further like x[0][4][9][9][9] will not cause a panic as a nil map can be indexed and yields the zero value of the value type (which is nil in case the value type is a map type).

Answer 2

Ok I had some fun playing with this a bit. Here is a much better implementation than what I did before:

type mymap map[int]*myentry

type myentry struct {
    m mymap
    b bool
}

func (mm mymap) get(idx ...int) *myentry {
    if len(idx) == 0 {
        return nil
    }
    entry, ok := mm[idx[0]]
    if !ok {
        return nil
    } else if len(idx) == 1 {
        return entry
    }
    for i := 1; i < len(idx); i++ {
        if entry == nil || entry.m == nil {
            return nil
        }
        entry = entry.m[idx[i]]
    }
    return entry
}

func (mm mymap) setbool(v bool, idx ...int) {
    if len(idx) == 0 {
        return
    }
    if mm[idx[0]] == nil {
        mm[idx[0]] = &myentry{m: make(mymap), b: false}
    } else if mm[idx[0]].m == nil {
        mm[idx[0]].m = make(mymap)
    }
    if len(idx) == 1 {
        mm[idx[0]].b = v
        return
    }
    entry := mm[idx[0]]
    for i := 1; i < len(idx); i++ {
        if entry.m == nil {
            entry.m = make(mymap)
            entry.m[idx[i]] = &myentry{m: make(mymap), b: false}
        } else if entry.m[idx[i]] == nil {
            entry.m[idx[i]] = &myentry{m: make(mymap), b: false}
        }
        entry = entry.m[idx[i]]
    }
    entry.b = v
}

func (m mymap) getbool(idx ...int) bool {
    if val := m.get(idx...); val != nil {
        return val.b
    }
    return false
}

func (m mymap) getmap(idx ...int) mymap {
    if val := m.get(idx...); val != nil {
        return val.m
    }
    return nil
}

Playground link

Something like that ought to get you started

Answer 3

You cannot do this as this sort of type is not representable in Go's type system.

You will have to redesign.

E.g. a type arbitrarilyKeyedMapwith a method lookup(vals ...int) bool. Probably you'll need methods for setting and deletion too.

Answer 4

If you don't need the hierarchical map structure and just want to use keys with variable length one approach could be to simply use strings as keys and one single map.

m := make(map[string]bool)
k := fmt.Sprintf("%v_%v_%v", 1, 2, 3)

m[k] = true

fmt.Println(m[k])