v77a - EachIn loop broken for extended Map class

Monkey Forums/Monkey Programming/v77a - EachIn loop broken for extended Map class

itto(Posted 2014) [#1]
Hi there, I've been trying to create a custom map class but it looks like something's wrong...

Simple Unit class and relative UnitMap

Class Unit
	Field foo
End

Class UnitMap<V> Extends Map<Unit, V>
	
	Method Compare(a:Unit, b:Unit)
		If a.foo > b.foo Return 1
		If a.foo = b.foo Return 0
		Return -1
	End

End


Now let's create three units and add them to the UnitMap

Function Main()

	Local map:= New UnitMap<Int>

	For Local x = 1 To 3
		map.Set(New Unit(), Rnd(1000))
	Next
	
	Print "Map elements: " + map.Count()

	For Local node := EachIn map
		Print node.Value()
	Next

End 


With the above code only one unit gets added to the map instead of three! BUT if you change the Compare method to always return 1 or -1, the three units are correctly added to the map! o.O

Class UnitMap<V> Extends Map<Unit, V>
	
	Method Compare(a:Unit, b:Unit)
		Return 1 ' same with -1 but not with 0
	End

End


Why is it working like this, and why is the Compare method needed for a simple Set and EachIn loop by the way? I thought that would matter only when sorting the map or such.


muddy_shoes(Posted 2014) [#2]
The way your code is written all your Units will have the same zero foo value. This, along with your original comparator, means that you're adding three values with effectively the same Unit key. Maps only accept one value per key, so you end up with one entry in the map. Your second comparator doesn't compare at all and will always say the Unit keys are different so you get three entries but you'll never find them again.

Are you sure you want to use Units as keys and Ints as values anyway? Seems like you might have them reversed.


itto(Posted 2014) [#3]
What I'm trying to do is having a map which store units object references and relate a value to them, so the <Unit, V> map is what I need.

The way your code is written all your Units will have the same zero foo value.


How can they have zero value, and especially how is it that I'm storing the same reference to the map if I'm creating a new Unit instance every time I call the Map.Set method?

For Local x = 1 To 3
	map.Set(New Unit(), Rnd(1000))
Next


I'm calling New Unit() each time... either the value set as a key to the map is not the unique reference to the Unit instance, or I'm missing something.

Besides, as I wrote if you change the Compare method to always return either 1 or -1 the code magically works, so I don't think it's a problem with the stored Unit key.


muddy_shoes(Posted 2014) [#4]
The Unit foo values are zero because you never set them, at least according to the code you've provided. "New Unit()" doesn't give foo a value.

The code may well "work" in that it prints out three values but the Map isn't working. The Map's purpose is to allow you to set a value against a key and also to get a value for a given key. You won't be able to retrieve any value for a Unit because your comparator doesn't actually inform the Map of the ordering.

Try changing your test loop to this and see what happens:

    For Local x = 1 To 3
		Local key:Unit = New Unit()
		Local value:Int = Rnd(1000)
		map.Set(key, value)
		If map.Get(key) <> value
			Print "Value not found"
		Else
			Print "Value found"
		End
	Next


Then revert the comparator to what you had originally and add this after the key is constructed:

    key.foo = x



itto(Posted 2014) [#5]
I already tried what you wrote, although I didn't state it previously (my bad!). Anyway I changed the for loop to your version, like this:

Function Main()

	Local map:= New UnitMap<Int>

	For Local x = 1 To 3
		Local key:Unit = New Unit()
		Local value:Int = Rnd(1000)
		map.Set(key, value)
		If map.Get(key) <> value
			Print "Value not found"
		Else
			Print "Value found: " + value
		End
	Next
	
	Print "Map elements: " + map.Count()

	For Local node := Eachin map
		Print node.Value()
	Next
End 


Now the values are being correctly stored in the map and retrieved from it. Nevertheless, map.Count() still prints 1 instead of 3, and the EachIn loop prints only one value, how can I fix that?


muddy_shoes(Posted 2014) [#6]
You haven't added the last bit I posted.


itto(Posted 2014) [#7]
With key.foo = x it works, but what's the point of storing the value in the map if I necessarily have to store it on the Unit class also? Of course if I store the value on the unit class directly I can avoid the map, but this exactly what I want to avoid, that's why I need the map... basically what I don't understand is why the behavior of the Compare method is determinant in the EachIn loop, does the EachIn loop call the Compare method to loop the map elements in a sorted order or what?

I guess I could just have the Compare method always return 1 and that's it, since I don't need to compare these values anyway, if that won't break something else at least.


muddy_shoes(Posted 2014) [#8]
X isn't the value. The value is some random number. X is just being used to uniquely identify the Unit so it can be ordered and found again by the Map.

As I said previously, if your compare function always returns a value that says the keys are different you won't be able to retrieve anything. If all you want is to add units and loop over them then you may as well use a list or an array.


itto(Posted 2014) [#9]
Ok now I understand it better. Basically the Compare method wants a value associated with each key to work. I can use whatever number I want, not necessarily the value actually stored by the map for the given key. I still don't understand why if this number is not present the map won't even be able to count the elements it stored or retrieve them within a loop (doesn't the map already have the key-value pair? why does it need another number?).

Anyway, since we need this number to use in the Compare method, is it possible to retrieve it from the object stored as a key (but not from one of its fields). For example

Method Compare(a:Unit, b:Unit)
	If a > b Return 1
	If a = b Return 0
	Return -1
End


or some field available to all Object instances I'm unaware of? perhaps an internal ID?

By the way I don't only need to loop the map elements, I need to retrieve them singularly by reference, that's why I really want to use a map.


muddy_shoes(Posted 2014) [#10]
I think somewhere along you line you're not quite joining the dots here.

A Map has one definitive function -- it allows you to store and retrieve values by association with keys. In your case you want to use your Unit instances as keys. That's fine but you need to understand some requirements/properties of Monkey's maps/keys.

* Key-value pairs are considered unique. Only one value can be stored against one key.
* Keys are required to be orderable and the compare method must reveal that order through its return value.

So, as I said above, your first problem was that you created Unit with an integer field "foo", wrote a compare method for it and then didn't ever set the value of foo so it was zero for every instance. This meant that when you wrote "Map.Set(New Unit(), Rnd(1000))" as far as the Map was concerned you were giving it the same key every time. The result is that you just replaced the value stored against that key resulting in what you saw as three values being added and only one being found in the loop. There is no problem there with the "EachIn", you actually only have one value in the Map.

What may be throwing you is that languages like Java offer map/dictionary implementations where all objects can inherently be used as keys. Unfortunately Monkey's base Object doesn't have this property. The code did at one point have commented out stubs for Equals and (I think) HashCode methods that would have allowed this but they were never implemented.


itto(Posted 2014) [#11]

your first problem was that you created Unit with an integer field "foo", wrote a compare method for it and then didn't ever set the value of foo so it was zero for every instance.


the VALUE of foo was zero for every instance


This meant that when you wrote "Map.Set(New Unit(), Rnd(1000))" as far as the Map was concerned you were giving it the same key every time.


Key? the key is not "foo", but the reference of the unit instance. Why can't I place a thousands of different key-value pairs in a map, each with value zero? How's this not possible?
I'm storing different object references in a map as keys, each one with an assigned value of zero. What's strange about this? Beside, the value was set as a random number, not zero.

I expect "Map.Set(New Unit(), Rnd(1000))" to store a new and different key every time, along with a random number, because I'm creating a new instance every time, and instances of objects should obviously all have a different reference otherwise it wouldn't be possible to pass them by reference at all anywhere... that code is all but misleading, because it's not doing what there's written. Did I not create a New Unit every time I called the Set method? Did I not call the Set method every time for each created unit? Did I not passed the reference of a new and different unit as a first parameter of the Set method every time I called it?

If, instead, monkey is under the hood using the "foo" value as a key (???) then this is even more awkward.

I would like to know why the following code is behaving like this: the map contains only one element, but if you change the compare method to return a value other than zero, then it correctly contains 1000 elements. There are no method at all in the class, so how am I supposed to "compare" them?

Class Unit
End

Class UnitMap<V> Extends Map<Unit, V>
	Method Compare(a:Unit, b:Unit)
		Return 1 ' if you change this with 1 or -1 the code works as expected
	End
End

Function Main()
	Local map:= New UnitMap<Int>
	For Local x = 1 To 1000
		map.Set(New Unit(), 200)
	Next
	Print "Map elements: " + map.Count()
End 


What value can I use to compare them if they have no methods? Can I get an internal id they use, or their reference number converted to int, or what?


muddy_shoes(Posted 2014) [#12]
I've answered all of this already but I'll try once more.

Monkey isn't choosing to use anything as a key. You're using foo as the ordering value for your Unit instance in compare so you've chosen it as the key. Your Compare method defines the key ordering. Monkey knows nothing about the nature of your key objects which is the very reason you have to write a compare method. When you add a key-value or try to retrieve a value by the key the Map internally calls the compare function to test against the keys it has stored.

If your compare function looks at the foo values and they're both zero then as far as the Map is concerned it's the same key. It looks at the first key, calls the compare method and the compare method says "They're the same". You could add a million entries with new Unit instances and you're just replacing the same entry. On the other hand if you do the same with this:

Class UnitMap<V> Extends Map<Unit, V>
	Method Compare(a:Unit, b:Unit)
		Return 1 ' if you change this with 1 or -1 the code works as expected
	End
End


Then compare method is effectively saying "No matter what Unit instances you give me, they are always different". You could pass the exact same Unit instance in for both a and b and it would say they are different. This means that every new Unit is a different key and you get as many entries as times you call Set but it also means that when you try to retrieve a value the Map calls compare and gets told "It's lower" or "It's higher" every time and therefore never finds a match.


itto(Posted 2014) [#13]
Ok, so the Compare method is the heart of the Map and it has to work correctly even for simple setting and retrieving of key-value pairs. My initial code was broken because I was comparing the foo fields of the objects, which were all set to zero. I decided to use the foo field in the compare method and that was obviously not what I wanted to do. The problem still persists though: I don't want to use an object field for the comparison (I didn't want to use foo for that matter), I already have the unique object reference and that should be enough, so it's the object reference value I want to compare, how can I achieve this?

Class Unit
End

Class UnitMap<V> Extends Map<Unit, V>
	Method Compare(a:Unit, b:Unit)
		' magic code to compare a with b here
                            ' Object(a).GetMagicID() ?
	End
End

Function Main()
	Local map:= New UnitMap<Int>
	For Local x = 1 To 1000
		map.Set(New Unit(), 200)
	Next
	Print "Map elements: " + map.Count()
End



muddy_shoes(Posted 2014) [#14]
You can't. See the last paragraph in post 10.


marksibly(Posted 2014) [#15]
You can only compare object references in Monkey for equality, not less than, greater than etc.

There is no 'MagicID' or 'hashCode' in Monkey either, as not all languages support this and I was uncomfortable with the extra per-object 'baggage' a custom implementation of this would entail.

So if you want to 'identify' a reference, you will need to add your own 'ID' field, eg:

Global _nextId

Funciton AllocId;Int()
  _nextId+=1
  Return _nextId
End

Class MyObject
    Field Id:=AllocId()
End



itto(Posted 2014) [#16]
Ok now I think I got the whole picture, thank you for your support and sorry muddy_shoes if I drove you nuts :P