Non-deterministic enumeration of weights in OverlappingModel

[nanodeath]

While porting this over to Kotlin (whee), I discovered what I think is the root cause of my troubles: when populating the patterns and stationary arrays in OverlappingModel, the keys of weight are iterated over. The order of this enumeration is non-deterministic, and the patterns and stationary can vary significantly based on the ordering.

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey, TValue> structure representing a value and its key. The order in which the items are returned is undefined.
https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

The affected code is here:

        foreach (int w in weights.Keys)
        {
            patterns[counter] = patternFromIndex(w);
            stationary[counter] = weights[w];
            counter++;
        }

[nanodeath]

I'm not really sure what the full ramifications of this are, BUT appending .OrderBy(x => x) to Keys still seems to work, and doing the equivalent enables the Kotlin/JVM version to function as well. You don't have to do this, but the order should be well-defined one way or another.

---

Update: correction, it always works for some of them (like City), but not for others (like Flowers). With this change, Flowers always yields CONTRADICTION in both this repo and my Kotlin version. So blindly sorting is apparently not the solution 😸

[nanodeath]

Yeah pretty sure messing with the weights order also messes up the foundation index value. The output of Platform looks messed up (almost as if there's no foundation set at all; multiple strata instead of just the one), and as semi-mentioned before, the given foundation value doesn't work for Flowers anymore.

[nanodeath]

Sorry for all the updates, but on the JVM side, using LinkedHashMap (which preserves insertion order as iteration order) to store the weights seemed to do the trick -- foundation is working and all the samples are working. I tried switching your C# version over to OrderedDictionary, but frankly was having some trouble getting the thing to cooperate, due to using integers as keys (it has an Item[Int32] method in addition to Item[Object] -- go figure).

---

Update: OrderedDictionary works fine if you cast all your lookup indexes to object to force it to use Item[Object], i.e.

if (weights.Contains(ind)) weights[(object)ind] = (int)weights[(object)ind] + 1;
else weights.Add(ind, 1);

Granted, it's quite the eyesore, but it works and I'm not sure there's another way while using the (non-generic) OrderedDictionary.

[nanodeath]

I think this is a pretty serious issue, so I'll send a pull request your way tonight. I'll try to wrap the OrderedDictionary ugliness in extension methods so as not to pollute the code.

[tomprogrammer]

The C# code actually returns the patterns and stationary weights in a deterministic order (on Mono Stable 4.6.1.3/abb06f1, LLVM disabled).

I discovered, that the foundation pattern just describes the bottom boundary.
Examples from the C# code:

City:   Flowers:   Platformer:   Platformer:
4 4 4    3 3 3         3 3          3 3 3
0 0 0    0 0 0         0 0          0 0 0
0 0 0    0 0 0                      0 0 0

I use that to calculate the pattern from the sample using the coordinates (0, SMY - 1) and finding the index of this pattern in the pattern/stationary list. This keeps the implementation details (the indices) internal to OverlappingModel and frees the caller from supplying the correct foundation value.

[nanodeath]

Yes, "foundation" as in, the bottom. It's been renamed to "ground" just today, actually, which is a bit clearer.

And that's a good idea -- you're passing in the coordinates that you want to be the ground, and then this gets mapped back into the index transparently, right? For completeness, you might also allow the caller to provide reflection and rotation information, symmetry-providing.

---

It's still iterating over keys of an unsorted dictionary and inserting them into an array -- that that works with any amount of predictability is a bit miraculous. So this still needs to be fixed 😅

[mxgmn]

@nanodeath Somehow I always assumed that foreach for dict.Keys goes through it in the order of filling, and it has always worked. But yeah, it's risky. I can change it to List<Tuple<int, int>>, or you already prepared a PR?

[mxgmn]

@tomprogrammer Nice change for foundation, but it's almost always -1 anyways, and if your sample has flower roots near (0, SMY - 1), then this method won't work. So I'll leave it as it is.

[nanodeath]

I still think OrderedDictionary might be better -- if it's a list, you have to scan through it a lot to see if that subimage has already been detected. On the other hand, OrderedDictionary's API is pretty rough 😉

I haven't started on a PR, but I was just about to. I can hold off if you'd rather do it yourself.

[mxgmn]

@nanodeath Yeah, I'll do it. I prefer sticking to basic data types when possible.

[mxgmn]

@nanodeath There was a simpler solution =).

[nanodeath]

@mxgmn Ah, glad to hear it.