ENIGMA Forums

Contributing to ENIGMA => Function Peer Review => Topic started by: polygone on July 16, 2011, 12:05:09 PM

Title: GM's Data Structures
Post by: polygone on July 16, 2011, 12:05:09 PM
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
Title: Re: GM's Data Structures
Post by: TheExDeus on July 17, 2011, 11:01:53 AM
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.
Title: Re: GM's Data Structures
Post by: Rusky on July 26, 2011, 07:19:24 PM
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.
Title: Re: GM's Data Structures
Post by: polygone on July 27, 2011, 06:46:42 AM
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.

Quote
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.

Quote
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?

Quote
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.

Quote
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.
Title: Re: GM's Data Structures
Post by: luiscubal on July 27, 2011, 08:22:07 AM
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?
Title: Re: GM's Data Structures
Post by: IsmAvatar on July 27, 2011, 11:49:50 AM
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.
Title: Re: GM's Data Structures
Post by: luiscubal on July 27, 2011, 11:58:31 AM
@IsmAvatar - Yes, I meant ds_lists[id][pos]
Title: Re: GM's Data Structures
Post by: polygone on July 27, 2011, 01:46:20 PM
Yes that would work.
Title: Re: GM's Data Structures
Post by: Rusky on July 31, 2011, 07:15:20 PM
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.

Quote
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.

Quote
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.

Quote
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?"
Title: Re: GM's Data Structures
Post by: polygone on August 01, 2011, 09:02:58 AM
Quote
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).

Quote
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.

Quote
"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.
Title: Re: GM's Data Structures
Post by: Rusky on August 01, 2011, 09:30:18 AM
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?
Title: Re: GM's Data Structures
Post by: TheExDeus on August 01, 2011, 10:12:03 AM
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.
Title: Re: GM's Data Structures
Post by: Josh @ Dreamland on August 01, 2011, 11:28:30 AM
Well, they're missing speed and efficiency, too. But I'm going for "working" with those functions--they're kind of unusable.
Title: Re: GM's Data Structures
Post by: Rusky on August 01, 2011, 03:21:43 PM
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 (http://dl.dropbox.com/u/22998312/EnigmaDataStructures.zip)
Title: Re: GM's Data Structures
Post by: The 11th plague of Egypt on August 31, 2011, 07:13:13 AM
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.
Title: Re: GM's Data Structures
Post by: RetroX on September 01, 2011, 01:38:42 PM
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.
Um.

I literally see no difference.  Instead of:
Code: [Select]
var l = list_create();
list_add(l, 1);
you have:
Code: [Select]
vector<variant> l;
l.add(1);
Which is a whole lot easier to understand, in my opinion.  The only difference is an OO API versus a functional API, and an OO API makes a whole lot more sense in this instance.
Title: Re: GM's Data Structures
Post by: Josh @ Dreamland on September 01, 2011, 11:09:21 PM
Actually, you don't need the <variant>. You can use vector, vector<>, or vector<variant>; they're all the same.

But I can see how functions, technically using no types, could be easier for the GM crowd to understand. Even if they're far too verbose for the rest of us.

I will keep that in mind, though, plague.
Title: Re: GM's Data Structures
Post by: The 11th plague of Egypt on September 02, 2011, 08:25:04 AM
I'm just saying I can handle both GML and C++ synthax, but a mix of the two could be tricky and counter-intuitive if rushed through.

Thank you for caring.
Title: Re: GM's Data Structures
Post by: RetroX on September 02, 2011, 10:23:24 AM
But I can see how functions, technically using no types, could be easier for the GM crowd to understand. Even if they're far too verbose for the rest of us.
In all honesty, I think that they're easier for the advanced GM users, who know how to use them well, but not as much for the newer users that haven't used data structures before.  Either way, I suppose that it's good to have a functional API as well as an OO one.
Title: Re: GM's Data Structures
Post by: Rusky on September 02, 2011, 01:20:22 PM
It's really not very functional when you update the data structures in-place. I'd call it procedural.