Pages: 1 2 »
  Print  
Author Topic: GM's Data Structures  (Read 31659 times)
Offline (Male) polygone
Posted on: July 16, 2011, 12:05:09 pm

Contributor
Location: England
Joined: Mar 2009
Posts: 794

View Profile
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
« Last Edit: July 20, 2011, 05:34:53 am by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Unknown gender) TheExDeus
Reply #1 Posted on: July 17, 2011, 11:01:53 am

Developer
Joined: Apr 2008
Posts: 1860

View Profile
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.
Logged
Offline (Male) Rusky
Reply #2 Posted on: July 26, 2011, 07:19:24 pm

Resident Troll
Joined: Feb 2008
Posts: 954
MSN Messenger - rpjohnst@gmail.com
View Profile WWW Email
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.
Logged
Offline (Male) polygone
Reply #3 Posted on: July 27, 2011, 06:46:42 am

Contributor
Location: England
Joined: Mar 2009
Posts: 794

View Profile
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.
« Last Edit: July 27, 2011, 07:26:18 am by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Unknown gender) luiscubal
Reply #4 Posted on: July 27, 2011, 08:22:07 am
Member
Joined: Jun 2009
Posts: 452

View Profile Email
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?
Logged
Offline (Female) IsmAvatar
Reply #5 Posted on: July 27, 2011, 11:49:50 am

LateralGM Developer
LGM Developer
Location: Pennsylvania/USA
Joined: Apr 2008
Posts: 877

View Profile Email
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.
Logged
Offline (Unknown gender) luiscubal
Reply #6 Posted on: July 27, 2011, 11:58:31 am
Member
Joined: Jun 2009
Posts: 452

View Profile Email
@IsmAvatar - Yes, I meant ds_lists[id][pos]
Logged
Offline (Male) polygone
Reply #7 Posted on: July 27, 2011, 01:46:20 pm

Contributor
Location: England
Joined: Mar 2009
Posts: 794

View Profile
Yes that would work.
« Last Edit: July 27, 2011, 05:06:28 pm by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) Rusky
Reply #8 Posted on: July 31, 2011, 07:15:20 pm

Resident Troll
Joined: Feb 2008
Posts: 954
MSN Messenger - rpjohnst@gmail.com
View Profile WWW Email
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?"
Logged
Offline (Male) polygone
Reply #9 Posted on: August 01, 2011, 09:02:58 am

Contributor
Location: England
Joined: Mar 2009
Posts: 794

View Profile
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.
Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) Rusky
Reply #10 Posted on: August 01, 2011, 09:30:18 am

Resident Troll
Joined: Feb 2008
Posts: 954
MSN Messenger - rpjohnst@gmail.com
View Profile WWW Email
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?
Logged
Offline (Unknown gender) TheExDeus
Reply #11 Posted on: August 01, 2011, 10:12:03 am

Developer
Joined: Apr 2008
Posts: 1860

View Profile
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.
Logged
Offline (Male) Josh @ Dreamland
Reply #12 Posted on: August 01, 2011, 11:28:30 am

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2950

View Profile Email
Well, they're missing speed and efficiency, too. But I'm going for "working" with those functions--they're kind of unusable.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) Rusky
Reply #13 Posted on: August 01, 2011, 03:21:43 pm

Resident Troll
Joined: Feb 2008
Posts: 954
MSN Messenger - rpjohnst@gmail.com
View Profile WWW Email
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
Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #14 Posted on: August 31, 2011, 07:13:13 am
Member
Joined: Dec 2009
Posts: 274

View Profile
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.
Logged
Pages: 1 2 »
  Print