linkedhashmap maintaining order only on first level? Is there any data structure that holds order in nested maps also?

punithck commented

2021-08-31 11:30:08 +00:00

(Migrated from github.com)

https://play.golang.org/p/AIAkjs_TELp If we see above example. linkedhashmap is maintaining the order only on firsl level of keys. It is not maintaining the same for nested keys or maps. Do we have any data structure that holds order in nested keys also?

Input:

{"pulse_in_sec":60,"pulse_count":1,"rate":1.0,"slabs":["1-50"],"billplan_hierarchy":{"direction":"outgoing","legType":"pstn","callType":"trans","endUserCircleMask":"intra"}}

Expected:

map[pulse_in_sec:60 pulse_count:1 rate:1 slabs:[1-50] billplan_hierarchy:map[direction:outgoing legType:pstn  callType:trans endUserCircleMask:intra]]

Ouput:

map[pulse_in_sec:60 pulse_count:1 rate:1 slabs:[1-50] billplan_hierarchy:map[callType:trans direction:outgoing endUserCircleMask:intra legType:pstn]]

https://play.golang.org/p/AIAkjs_TELp If we see above example. linkedhashmap is maintaining the order only on firsl level of keys. It is not maintaining the same for nested keys or maps. Do we have any data structure that holds order in nested keys also? Input: ``` {"pulse_in_sec":60,"pulse_count":1,"rate":1.0,"slabs":["1-50"],"billplan_hierarchy":{"direction":"outgoing","legType":"pstn","callType":"trans","endUserCircleMask":"intra"}} ``` Expected: ``` map[pulse_in_sec:60 pulse_count:1 rate:1 slabs:[1-50] billplan_hierarchy:map[direction:outgoing legType:pstn callType:trans endUserCircleMask:intra]] ``` Ouput: ``` map[pulse_in_sec:60 pulse_count:1 rate:1 slabs:[1-50] billplan_hierarchy:map[callType:trans direction:outgoing endUserCircleMask:intra legType:pstn]] ```

👍 2

emirpasic commented

2022-04-12 13:16:54 +00:00

(Migrated from github.com)

@punithck unfortunately there is no data structure that can go beyond the first level simply due to the randomness in iteration order of maps when unmarshalling JSON to map in Golang.

The only way to achieve this is to write GoDS own unmarshaler as was done in json/decode

Given this would be a cool feature to have in GoDS as there is nothing out there that can anything similar on the web in Golang, it would give GoDS more value.

Hence, I will keep this issue open until GoDS JSON decode is implemented to unmarshal JSON into GoDS' data structures.

@punithck unfortunately there is no data structure that can go beyond the first level simply due to the randomness in iteration order of maps when unmarshalling JSON to map in Golang. The only way to achieve this is to write GoDS own unmarshaler as was done in [json/decode](https://cs.opensource.google/go/go/+/go1.18:src/encoding/json/decode.go) Given this would be a cool feature to have in GoDS as there is nothing out there that can anything similar on the web in Golang, it would give GoDS more value. Hence, I will keep this issue open until GoDS JSON decode is implemented to unmarshal JSON into GoDS' data structures.

retrodaredevil commented

2024-03-06 02:51:53 +00:00

(Migrated from github.com)

FromJSON is actually more problematic than described above:

Take this unit test:

func TestGodsLinkedHashMapRetainsOrderWithComplexJSON(t *testing.T) {
	jsonString := `
{
  "a": 1,
  "c": {
    "b": 1,
    "a": 2,
    "c": 3
  },
  "d": 3,
  "b": 4
}
`
	data := linkedhashmap.New[string, any]()
	err := json.Unmarshal([]byte(jsonString), &data)
	if err != nil {
		t.Fatal("Could not unmarshal json", err)
		return
	}
	it := data.Iterator()
	it.Next()
	if it.Key() != "a" {
		t.Error("First key not a")
	}
	it.Next()
	if it.Key() != "c" {
		t.Error("Second key not c")
	}

	it.Next()
	if it.Key() != "d" {
		t.Error("Third key not d") // IT FAILS HERE
	}
	it.Next()
	if it.Key() != "b" {
		t.Error("Forth key not b") // And also here
	}
}

@punithck points out that the object won't have sorted fields (its value is of the type map[string]interface{}). However, this test shows that the keys d and b are put in the wrong order because the key b is present in nested JSON.

github.com/emirpasic/gods@14f714261f/maps/linkedhashmap/serialization.go (L84) shows that the logic works by finding the index of the key in the JSON itself, which seems messy.

I bumped this issue because one of the reasons I looked into GoDS is because it's one of the few libraries with a linked hash map implementation that seems standard enough to use in production code. I was hoping it could be my solution to parsing arbitrary JSON and keeping the fields in the order they were in the JSON. So, I was wondering if there were any plans to implement a JSON parser so that the order would be correct for complex JSON objects like I showed in the above unit test, and so that nested JSON objects can have their fields ordered correctly.

FromJSON is actually more problematic than described above: Take this unit test: ```go func TestGodsLinkedHashMapRetainsOrderWithComplexJSON(t *testing.T) { jsonString := ` { "a": 1, "c": { "b": 1, "a": 2, "c": 3 }, "d": 3, "b": 4 } ` data := linkedhashmap.New[string, any]() err := json.Unmarshal([]byte(jsonString), &data) if err != nil { t.Fatal("Could not unmarshal json", err) return } it := data.Iterator() it.Next() if it.Key() != "a" { t.Error("First key not a") } it.Next() if it.Key() != "c" { t.Error("Second key not c") } it.Next() if it.Key() != "d" { t.Error("Third key not d") // IT FAILS HERE } it.Next() if it.Key() != "b" { t.Error("Forth key not b") // And also here } } ``` @punithck points out that the object won't have sorted fields (its value is of the type `map[string]interface{}`). However, this test shows that the keys `d` and `b` are put in the wrong order because the key `b` is present in nested JSON. https://github.com/emirpasic/gods/blob/14f714261f50e6d3e4af1cd29e4ae11ffdedab94/maps/linkedhashmap/serialization.go#L84 shows that the logic works by finding the index of the key in the JSON itself, which seems messy. I bumped this issue because one of the reasons I looked into GoDS is because it's one of the few libraries with a linked hash map implementation that seems standard enough to use in production code. I was hoping it could be my solution to parsing arbitrary JSON and keeping the fields in the order they were in the JSON. So, I was wondering if there were any plans to implement a JSON parser so that the order would be correct for complex JSON objects like I showed in the above unit test, and so that nested JSON objects can have their fields ordered correctly.

mort666 closed this issue

2026-09-07 17:04:13 +00:00

Rows
Columns

linkedhashmap maintaining order only on first level? Is there any data structure that holds order in nested maps also? #171