Comments (12)
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.
from gods.
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:
fmt.Println(m)
hangs on Go 1.7.1 64-bit on Windows after making a change to one of theTreeSet
s:
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)
}
- Wasn't able to test this out due to the issue I ran into above, however, if I make a change to a
TreeSet
, says1
, I would have to remove it then add it back to get it to sort correctly right? How expensive would this be?
from gods.
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]
from gods.
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.
from gods.
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?
from gods.
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.
from gods.
Ah, I see! In my case, I would need to be able to add and remove ip addresses after initialisation.
from gods.
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?
from gods.
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.
from gods.
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.
from gods.
Wow, thanks! That's very helpful! π
from gods.
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!
from gods.
Related Issues (20)
- Add to Go official wiki? HOT 3
- generic upgrade request HOT 3
- RedBlackTree: Iterators become invalid after removing an element. HOT 2
- DS which can give element if present or next greater if not present, elements should be stored in sorted order HOT 2
- LinkedHashMap Sort? HOT 3
- Multiset support HOT 1
- deque support
- hashset should support NewWith Comparator
- Add method of Set lack info about the insert take place or not
- treesetοΌThe names of each element are not equal, why is second_8 disappearing? HOT 1
- godslist.js refrence in chrome 120.0.6099.225 console
- Add elements of a slice [] T
- Red black tree: Unresolved reference 'NewWithIntComparator'
- Red black tree: package cmp is not in GOROOT (/usr/lib/golang/src/cmp)
- Interfaces support any types HOT 5
- Why cannot index priorityqueue.NewWith (value of type func(comparator utils.Comparator) *priorityqueue.Queue)? HOT 1
- A issue In BinaryHeap
- linkedhashmap json.Marshal error HOT 1
- treeset json.Unmarshal error HOT 1
- Update documention to use V2 version of generics
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. πππ
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google β€οΈ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from gods.