Is there a map comparator that simply retains the order of insertion?

MartinDelVecchio commented

2017-05-23 16:56:03 +00:00

(Migrated from github.com)

I am using code that collects KV pairs in a map[string]interface{}. Because it's Go, when json.Unmarshal() iterates over the keys, they come out in a random order. This does not work for my purposes; I need the keys to iterate in the same order in which they were inserted.

Your TreeMap maintains an ordered set of keys, based on a comparator. Does a comparator exist, or can one be built, that sorts the keys based on the order of their insertion? And if so, would the JSON interface then serialize these keys in the insertion order?

Thank you.

I am using code that collects KV pairs in a map[string]interface{}. Because it's Go, when json.Unmarshal() iterates over the keys, they come out in a random order. This does not work for my purposes; I need the keys to iterate in the same order in which they were inserted. Your TreeMap maintains an ordered set of keys, based on a comparator. Does a comparator exist, or can one be built, that sorts the keys based on the order of their insertion? And if so, would the JSON interface then serialize these keys in the insertion order? Thank you.

ghost commented

2017-05-23 18:50:32 +00:00

(Migrated from github.com)

In short: no. If you use a comparator that orders by insertion time then you would have to look up by insertion time as well.

I would use a slice or a doubly linked list to store the items ordered by insertion in a queue-like fashion. You could then use a map to to store indices into the slice or a pointer to the linked list node. You can then do constant time lookup and in the case of the linked list constant time removal. You iterate through the slice or linked list to get an insertion ordered loop.

In short: no. If you use a comparator that orders by insertion time then you would have to look up by insertion time as well. I would use a slice or a doubly linked list to store the items ordered by insertion in a queue-like fashion. You could then use a map to to store indices into the slice or a pointer to the linked list node. You can then do constant time lookup and in the case of the linked list constant time removal. You iterate through the slice or linked list to get an insertion ordered loop.

👍 1

MartinDelVecchio commented

2017-05-23 19:09:53 +00:00

(Migrated from github.com)

My problem is that I don't do the insertions; json.Unmarshal() does. As currently written, the struct it unmarshals into uses a map[string]interface{}, which is ordered. So I need to replace that with a type that 1) supports json.Unmarshal() (and json.Marshal() ) transparently, and 2) maintains insertion order.

I see that the gods map types fully support the JSON interface, so that seems promising. I was hoping that one already spuported maintaining the insertion order, but that does not appear to be the case. I will take a look at the source to see how difficult it would be to adapt HashMap to do this.

Thanks.

My problem is that I don't do the insertions; json.Unmarshal() does. As currently written, the struct it unmarshals into uses a map[string]interface{}, which is ordered. So I need to replace that with a type that 1) supports json.Unmarshal() (and json.Marshal() ) transparently, and 2) maintains insertion order. I see that the gods map types fully support the JSON interface, so that seems promising. I was hoping that one already spuported maintaining the insertion order, but that does not appear to be the case. I will take a look at the source to see how difficult it would be to adapt HashMap to do this. Thanks.

emirpasic commented

2017-05-24 11:01:58 +00:00

(Migrated from github.com)

@MartinDelVecchio

As @spewspews mentioned, that structure hasn't yet been implemented and I think it would be a nice addition to GoDS. It's fairly easy to implement and, once implemented, the JSON serialization/deserialization would be in that (insertion) order.

I hope to have it ready this weekend, i.e. LinkedHashMap and LinkedHashSet that maintain the insertion order.

@MartinDelVecchio As @spewspews mentioned, that structure hasn't yet been implemented and I think it would be a nice addition to GoDS. It's fairly easy to implement and, once implemented, the JSON serialization/deserialization would be in that (insertion) order. I hope to have it ready this weekend, i.e. LinkedHashMap and LinkedHashSet that maintain the insertion order.

MartinDelVecchio commented

2017-05-24 11:06:09 +00:00

(Migrated from github.com)

That would be awesome for me. And based on my week of searching for "golang ordered map JSON marshal unmarshal", I think it would be awesome for a lot of other people as well.

Thank you!

That would be awesome for me. And based on my week of searching for "golang ordered map JSON marshal unmarshal", I think it would be awesome for a lot of other people as well. Thank you!

👍 5

MartinDelVecchio commented

2017-06-05 23:55:00 +00:00

(Migrated from github.com)

Have you made any progress on this? I'd love to try out anything that you have.

Thanks again!

Have you made any progress on this? I'd love to try out anything that you have. Thanks again!

chrischris292 commented

2018-06-13 14:30:31 +00:00

(Migrated from github.com)

any progress?

emirpasic commented

2018-06-13 15:40:39 +00:00

(Migrated from github.com)

@chrischris292 unfortunately not, i'm time-limited due to recent fatherhood. i have to take a day or two one of these weekends to clean up pull requests and implement requested features.

emirpasic commented

2018-09-21 03:39:51 +00:00

(Migrated from github.com)

@MartinDelVecchio @chrischris292 sorry it took so long, but I finally found some time for this

Map data structure preserving the insertion-order. LinkedHashMap

Set data structure preserving the insertion-order. LinkedHashSet

@MartinDelVecchio @chrischris292 sorry it took so long, but I finally found some time for this Map data structure preserving the insertion-order. [LinkedHashMap](https://github.com/emirpasic/gods#linkedhashmap) Set data structure preserving the insertion-order. [LinkedHashSet](https://github.com/emirpasic/gods#linkedhashset)

Rows
Columns

Is there a map comparator that simply retains the order of insertion? #58