GM's Data Structures

[polygone]

OK I've done all of GM's data structures now. I haven't fully tested all of the functions so let me know if anything doesn't work, doesn't mimic GM's behaviour or of course can be made more efficient.

There is a small incompatibility from GM that when a data structure is destroyed in GM it leaves a gap in the index value (this is replicated), but then when GM creates a new data structure afterwards it fills in the gaps of the indexes (which has not been replicated because it seems retarded). This shouldn't cause any problems though unless people are calling data structure indexes as literals or something.

And there is a also slight incompatibility with ds_queues when you have multiple priorities of the same value. The way I have handled it, it will always return the lowest value with multiple the priorities the same. The way GM handles it, is it returns the value which was first added to the priority queue. This should unlikely cause any issues though as you shouldn't be setting priorities the same anyway.

Anyway code posted on pastebin (because I'm way over the forum character limit): http://pastebin.com/earWGw8Z

[TheExDeus]

They are pretty short so I doubt there is much room for optimization. Just check if they all work, and if they do, then feel free to commit. Just want to know if this will be as an extension or built in. I don't actually get how ENIGMAS extensions function right now, because you cant actually select which ones you want and which you don't want. My curve and spline drawing functions also were meant as an extension, but it ended up in the main build.

[Rusky]

You should free the arrays you allocate in the grid class- C++ isn't garbage collected and heap-allocated memory doesn't get freed when it goes out of scope. Just "delete[] grid_array;" in the destructor and when you resize it.

I'm not entirely sure why you would choose multimap over map or unordered_map for ds_map. It just seems to add complexity in this case.

You shouldn't erase and re-insert for ds_*_replace()- it's redundant and in the case of vector (where it has to copy the other elements over and then back) very slow.

For ds_map_find_next() you could just get an iterator to the key and increment it instead of doing a linear search through the map.

GM's behavior with regard to priority queues is the point of priority queues. There's no problem with adding multiple things that have the same priority- in that case it should simply act as the queue that its name implies and return the first one inserted.

[polygone]

You should free the arrays you allocate in the grid class- C++ isn't garbage collected and heap-allocated memory doesn't get freed when it goes out of scope. Just "delete[] grid_array;" in the destructor and when you resize it.

I tried that when I was writing it and it didn't work, so I just left it for Josh to sort.

I'm not entirely sure why you would choose multimap over map or unordered_map for ds_map. It just seems to add complexity in this case.

To mimic GM's behaviour, it allows you to set two keys the same.

You shouldn't erase and re-insert for ds_*_replace()- it's redundant and in the case of vector (where it has to copy the other elements over and then back) very slow.

What do you use instead?

For ds_map_find_next() you could just get an iterator to the key and increment it instead of doing a linear search through the map.

Doesn't work with multimap in the case where two keys have been set the same.

GM's behavior with regard to priority queues is the point of priority queues. There's no problem with adding multiple things that have the same priority- in that case it should simply act as the queue that its name implies and return the first one inserted.

That behaviour was annoying to replicate so I didn't bother. I don't think it makes too much difference.

[luiscubal]

Code: [Select]

        ds_lists[id].erase(ds_lists[id].begin() + pos);
        ds_lists[id].insert(ds_lists[id].begin() + pos, val);
Wouldn't just:

Code: [Select]

ds_lists[id] = val;work?

[IsmAvatar]

I don't see how that would even work. 1) You lose the reference to the ds_list, 2) You try to store a non-ds_list object in a ds_list variable, 3) That doesn't even touch the ds_list, let alone perform a replace on it.
You must be missing something. ds_lists[id][size] = val maybe.

[luiscubal]

@IsmAvatar - Yes, I meant ds_lists[id][pos]

[polygone]

Yes that would work.

[Rusky]

You should free the arrays you allocate in the grid class- C++ isn't garbage collected and heap-allocated memory doesn't get freed when it goes out of scope. Just "delete[] grid_array;" in the destructor and when you resize it.

I tried that when I was writing it and it didn't work, so I just left it for Josh to sort.

What exactly didn't work? It's just a simple insertion in two places.

I'm not entirely sure why you would choose multimap over map or unordered_map for ds_map. It just seems to add complexity in this case.

To mimic GM's behaviour, it allows you to set two keys the same.

For ds_map_find_next() you could just get an iterator to the key and increment it instead of doing a linear search through the map.

Doesn't work with multimap in the case where two keys have been set the same.

GM allows you to ds_map_add() twice with the same key, but you can only ever access the first one you added so it seems more like a bug than anything useful. There's really no reason keep that behavior.

GM's behavior with regard to priority queues is the point of priority queues. There's no problem with adding multiple things that have the same priority- in that case it should simply act as the queue that its name implies and return the first one inserted.

That behaviour was annoying to replicate so I didn't bother. I don't think it makes too much difference.

"My car's engine is broken but it was annoying to fix so I didn't bother. The wheels still turn, right?"

[polygone]

What exactly didn't work? It's just a simple insertion in two places.

I can't remember, I was going to go back to it at the end but I forgot so I just left it for josh to add when he moved everything into .cpp (however I see now that he didn't add it or actually change anything that was talked about in the irc).

GM allows you to ds_map_add() twice with the same key, but you can only ever access the first one you added so it seems more like a bug than anything useful. There's really no reason keep that behavior.

You can't reference it directly but if you delete a key then you are able to reference the one next which had the same key.

"My car's engine is broken but it was annoying to fix so I didn't bother. The wheels still turn, right?"

This is a very minor inconsistency with a behaviour that shouldn't be relied on anyway and is also unlikely to cause any detrimental inconsistency with anybody's game, fixing it will cost on efficiency I deemed it not worth doing.

[Rusky]

I'm a bit confused here. You want to keep the weird, undocumented behavior in ds_map that most people probably have never noticed, but get rid of the useful behavior in ds_priority required by several real-world algorithms?

[TheExDeus]

Stop fighting over nothing. It works and works great. If somebody does have problems with the few inconsistencies, then we will look into fixing that. Until then - speed and efficiency over compatibility.

[Josh @ Dreamland]

Well, they're missing speed and efficiency, too. But I'm going for "working" with those functions--they're kind of unusable.

[Rusky]

ds_priority works the way it does because that's how priority queues work. It's not just a compatibility issue- it's required by real algorithms that use priority queues. If you change it, it's not a priority queue. It's a priority sorted list.

I did find the data structure stuff I wrote- it's horrible, horrible code but it may be helpful with the ds_*_write/read() formats. http://dl.dropbox.com/u/22998312/EnigmaDataStructures.zip

[The 11th plague of Egypt]

Sorry for the late reply but...

I'm writing a Qt project right now, and I assure you that C++ data structures are WAY more difficult to learn and use than the GM's counterpart.

I think there's a chance that these simple structures will be the most used, at least for starters.

What Enigma is trying to do is merging a complex but consistent language (C++) with a simple but inconsistent language (GML), while keeping compatibility.

In the face of the recent news (Python3, C++11, Java7) showing us how difficult and problematic it is to just to keep compatibility between two version of the SAME language, reaching Engima's objective seems to me like a damn development nightmare.

I think it's better to break compatibility between GM8 and Enigma1 now, than breaking it between Enigma1 and Enigma2 later.