Access value in key comparator

[F21]

I want to implement a structure base on TreeMap where I have IP addresses as the key and a TreeSet as the value. I want to be able to sort the TreeMap using the size() of the TreeSet. This is currently impossible because the comparator can only access either the keys or values.

For example:

m := treemap.NewWith(myComparator)

s1 := treeset.NewWithIntComparator()
s1.Add(2, 2, 3, 4, 5) 

s2 := treeset.NewWithIntComparator()
s2.Add(7, 8, 9) 

m.Put("server1", s1)
m.Put("server2", s2)

Unfortunately, the myComparator can only access the keys:

func myComparator(a, b interface{}) int {
    // a and b are the keys
}

What do you think about adding access to the values for key comparators used by maps?

[emirpasic]

If you do it in that order that you gave in your example, i.e. create the sets and then insert them thereafter into the map, then you could do something like this (keep the reference to the value in the key):

package main

import (
    "github.com/emirpasic/gods/maps/treemap"
    "github.com/emirpasic/gods/sets/treeset"
    "fmt"
    "github.com/emirpasic/gods/utils"
)

type RefKey struct {
    ip  uint32
    ref *treeset.Set
}

func bySize(a, b interface{}) int {
    aK := a.(*RefKey)
    bK := b.(*RefKey)
    return utils.IntComparator(aK.ref.Size(), bK.ref.Size()) // just put a "-" after "return" in case you need descending order
}

func main() {
    m := treemap.NewWith(bySize)

    s1 := treeset.NewWithIntComparator()
    s1.Add(1, 2, 3, 4)

    s2 := treeset.NewWithIntComparator()
    s2.Add(1, 2, 3)

    s3 := treeset.NewWithIntComparator()
    s3.Add(1)

    s4 := treeset.NewWithIntComparator()
    s4.Add(1, 2)

    m.Put(&RefKey{634199692, s1}, s1) // 37.205.30.140
    m.Put(&RefKey{634199693, s2}, s2) // 37.205.30.141
    m.Put(&RefKey{634199694, s3}, s3) // 37.205.30.142
    m.Put(&RefKey{634199695, s4}, s4) // 37.205.30.143

    fmt.Println(m)
}

Obviously the order is important here, since the map won't be sorted automatically if you add/remove from the sets after insertion into the map.

Another problem with the above solution is that you can't lookup the map by IP address anymore in case you need that and I suppose you do.

[F21]

Hey,

Thanks for your help! Haven't thought of setting the TreeSet as the key, which was really smart! However, I ran into a few problems:

1. fmt.Println(m) hangs on Go 1.7.1 64-bit on Windows after making a change to one of the TreeSets:

package main

import (
    "fmt"
    "github.com/emirpasic/gods/maps/treebidimap"
    "github.com/emirpasic/gods/sets/treeset"
    "github.com/emirpasic/gods/utils"
)

func bySize(a, b interface{}) int {
    return utils.IntComparator(a.(*treeset.Set).Size(), b.(*treeset.Set).Size())
}

// TODO I will add these comparators for all builtin types soon to GoDS
func UInt32Comparator(a, b interface{}) int {
    aUInt32 := a.(uint32)
    bUInt32 := b.(uint32)
    switch {
    case aUInt32 > bUInt32:
        return 1
    case aUInt32 < bUInt32:
        return -1
    default:
        return 0
    }
}

func main() {
    m := treebidimap.NewWith(bySize, UInt32Comparator)

    s1 := treeset.NewWithIntComparator()
    s1.Add(1, 2, 3, 4)

    s2 := treeset.NewWithIntComparator()
    s2.Add(1, 2, 3)

    s3 := treeset.NewWithIntComparator()
    s3.Add(1)

    s4 := treeset.NewWithIntComparator()
    s4.Add(1, 2)

    m.Put(s1, uint32(634199692))
    m.Put(s2, uint32(634199693))
    m.Put(s3, uint32(634199694))
    m.Put(s4, uint32(634199695))

    fmt.Println(m)

    // e.g. to lookup now the set of values for an IP address:
    fmt.Println(m.GetKey(uint32(634199692)))

    s3.Add(6, 7, 8, 9, 10, 11)
    fmt.Println(m.GetKey(uint32(634199694)))
    fmt.Println(m)
}

1. Wasn't able to test this out due to the issue I ran into above, however, if I make a change to a TreeSet, say s1, I would have to remove it then add it back to get it to sort correctly right? How expensive would this be?

[F21]

If I change the last 3 times of the code in my comment, it seems to lose entries in the map.

Code:

s4.Add(6, 7, 8, 9, 10, 11)
fmt.Println(m.GetKey(uint32(634199694)))
fmt.Println(m)

Result:

TreeBidiMap
map[TreeSet
1:634199694 TreeSet
1, 2, 6, 7, 8, 9, 10, 11:634199695]

[emirpasic]

Ah my bad, the bi-directional map won't work. Sorry, I was tired last night when I thought of this. The problem here is that the inverse key in the bidi-map example is the size of the set, which will override all other sets with the same size LOL. I edited the comment above to remove that piece of buggy code. Shame on me :)

I'll think of another way later of doing this in case you need lookups by IP, which I suppose you do. Also does this list have to be sorted automatically when you populate into the sets, even after you've added the set as the value to the map? There are many solutions to this, but it all depends on the requirements.

What I also suggest is to create a simple TreeMap where the key is IP and the value is the set. Then just dynamically sort (utils.Sort) all the values of the map based on its size. That way you have lookups by IP address and the sorting is performed when you need it and it's consistent. I'll write an example later, but it's pretty straight forward.

[F21]

Thanks for looking into it! 😄

In my case, I need to be able to look up by IP, so a TreeMap is probably a good fit here. The list must always be sorted by the number of items in each TreeSet. If I manually call utils.Sort everytime I update the TreeMap or any of the TreeSets, is it more inefficient than letting gods handle it itself?

Also, utils.Sort appears to only be able to sort either keys or values. Do you have an example on how it can be used to sort a TreeMap by its values?

[emirpasic]

If I manually call utils.Sort everytime I update the TreeMap or any of the TreeSets, is it more inefficient than letting gods handle it itself?

I understand that you need the lookup by IP address to get the set.

I understand that you need this to be sorted by the number of elements in the set.

However, I am not sure if you are going to add more IP addresses after you've initialized everything? Also I am not sure if you are going to add more elements to the set after the initialization? The solution really depends on those two questions.

I'll give you an example later of how to accomplish all of the above requirements if you need that.

[F21]

Ah, I see! In my case, I would need to be able to add and remove ip addresses after initialisation.

[emirpasic]

Ah, I see! In my case, I would need to be able to add and remove ip addresses after initialisation.

OK, but you won't need to add/remove values to the set?

[emirpasic]

fmt.Println(m) hangs on Go 1.7.1 64-bit on Windows after making a change to one of the TreeSets:

It hangs on all versions, because the key is modified internally, but that example doesn't work anyways. Below is the updated example that should work and you should not add/remove from the set once inserted into the map as stated at the bottom.

[emirpasic]

This is essentially the same example with the bi-directional map, just corrected to account for equal sized sets and added comparators for all builtin types. I hope this works this time:

package main

import (
    "fmt"
    "github.com/emirpasic/gods/maps/treebidimap"
    "github.com/emirpasic/gods/sets/treeset"
    "github.com/emirpasic/gods/utils"
)

// By size
func bySize(a, b interface{}) int {
    // prefix with zero-padded number for comparing int as a string
    // suffix with pointer address in case the size is same
    aTmp := fmt.Sprintf("%010d%p", a.(*treeset.Set).Size(), a)
    bTmp := fmt.Sprintf("%010d%p", b.(*treeset.Set).Size(), b)
    return utils.StringComparator(aTmp, bTmp)
}

func main() {
    m := treebidimap.NewWith(bySize, utils.UInt32Comparator)

    s1 := treeset.NewWithIntComparator()
    s1.Add(1, 2, 3, 4)

    s2 := treeset.NewWithIntComparator()
    s2.Add(1, 2, 3)

    s3 := treeset.NewWithIntComparator()
    s3.Add(1, 5)

    s4 := treeset.NewWithIntComparator()
    s4.Add(1, 2)

    m.Put(s1, uint32(634199692))
    m.Put(s2, uint32(634199693))
    m.Put(s3, uint32(634199694))
    m.Put(s4, uint32(634199695))

    // e.g. to lookup now the set of values for an IP address:
    s, _ := m.GetKey(uint32(634199692))
    fmt.Println(s.(*treeset.Set).Values()) // Output: [1 2 3 4]

    it := m.Iterator()
    for it.Next() {
        s, ip := it.Key().(*treeset.Set), it.Value().(uint32)
        fmt.Printf("IP %d has %d elements: %v\n", ip, s.Size(), s.Values())
    }
    // Output:
    // IP 634199694 has 2 elements: [1 5]
    // IP 634199695 has 2 elements: [1 2]
    // IP 634199693 has 3 elements: [1 2 3]
    // IP 634199692 has 4 elements: [1 2 3 4]
}

You can add more IP addresses in this example, but you can't add more values to the set once you've placed it in the bi-directional map.

[F21]

Wow, thanks! That's very helpful! 😄

[sudevkk]

I am looking at a similar problem, but in my case I also need to be able to modify the Value (the set in the above example) after it gets placed/added. Is there a way to achieve this? @emirpasic Thanks!