Bug - Fixed Unexpected behavior when using two items with name "rock" in KoL as keys in a map
- Thread starter chown
- Start date
It looks like there are also multiple versions of some quest items, too. For example the spookyraven library key is both items #1764 and #7302. It could be that Mafia has some logic that is intended to treat those as a single item (perhaps to provide backward compatibility with older scripts) but that also does this as an unintended consequence.
I have seen some interesting things that involve "rock" when iterating over $items and related maps. Did not bother to track it down further. Perhaps I should.
Value.java:
This was written back when items, effects, whatever, did not have ambiguous names, and a case-insensitive comparison of names was all that was mattered.
items and effects, at least, should use the id.
Code:
public int compareTo( final Value o )
{
if ( !( o instanceof Value ) )
{
throw new ClassCastException();
}
Value it = (Value) o;
if ( this.type == DataTypes.BOOLEAN_TYPE || this.type == DataTypes.INT_TYPE )
{
return this.contentLong < it.contentLong ? -1 : this.contentLong == it.contentLong ? 0 : 1;
}
if ( this.type == DataTypes.FLOAT_TYPE )
{
return Double.compare(
Double.longBitsToDouble( this.contentLong ),
Double.longBitsToDouble( it.contentLong ) );
}
if ( this.contentString != null && it.contentString != null )
{
return this.contentString.compareToIgnoreCase( it.contentString );
}
return -1;
}items and effects, at least, should use the id.
Like This?
For reasons I have never figured out I cannot commit to KoLmafia from this computer and it is clear that this IDE isn't handling whitespace according to convention but...
This looks weird, and is untested, but the first getType returns a Type and the second getType returns an int that identifies the Type.
I may be able to commit today but if anyone else is moving faster that's fine with me
Code:
public int compareTo( final Value o )
{
if ( !( o instanceof Value ) )
{
throw new ClassCastException();
}
Value it = (Value) o;
if ( this.type == DataTypes.BOOLEAN_TYPE || this.type == DataTypes.INT_TYPE )
{
return this.contentLong < it.contentLong ? -1 : this.contentLong == it.contentLong ? 0 : 1;
}
if ( this.type == DataTypes.FLOAT_TYPE )
{
return Double.compare(
Double.longBitsToDouble( this.contentLong ),
Double.longBitsToDouble( it.contentLong ) );
}
if (this.type == DataTypes.ITEM_TYPE)
{
return (this.getType().getType() - it.getType().getType());
}
if (this.type == DataTypes.EFFECT_TYPE)
{
return (this.getType().getType() - it.getType().getType());
}
if ( this.contentString != null && it.contentString != null )
{
return this.contentString.compareToIgnoreCase( it.contentString );
}
return -1;
}For reasons I have never figured out I cannot commit to KoLmafia from this computer and it is clear that this IDE isn't handling whitespace according to convention but...
This looks weird, and is untested, but the first getType returns a Type and the second getType returns an int that identifies the Type.
I may be able to commit today but if anyone else is moving faster that's fine with me
I assumed Veracity meant
although, really, I am not sure why that isn't just implemented as this.contentLong - it.contentLong.
Is it even possible in ASH to compare two objects of different types, or will that result in a compile-time error?
Code:
if ( this.type == DataTypes.BOOLEAN_TYPE || this.type == DataTypes.INT_TYPE || this.type == DataTypes.ITEM_TYPE || this.type == DataTypes.EFFECT_TYPE)
{
return this.contentLong < it.contentLong ? -1 : this.contentLong == it.contentLong ? 0 : 1;
}Is it even possible in ASH to compare two objects of different types, or will that result in a compile-time error?
Well, no. A Value has a contentLong (the integer value) and a contentString (the name). It might also have a content - which is an arbitrary object. Looking at Datatypes.java:
BOOLEAN, INT, FLOAT - all have a number in contentLong, but no contentString or content
ITEM - contentLong is itemId, contentString is name
EFFECT - contentLong is effectId, contentString is name
CLASS - contentLong is class #, contentString is name
SKILL - contentLong is skill #, contentString is name
FAMILIAR - contentLong is familiar #, contentString is name
SLOT - contentLong is slot #, contentString is name
MONSTER - contentLong is monster id#, contentString is name
THRALL - contentLong is thrall #, contentString is name
SERVANT - contentLong is servant #, contentString is name
Every one of those last types could simply use contentLong to compare - with one caveat: multiple monsters can have id = 0, which simply means "we don't know the id", in which case, we should comapre the names.
Edit: my response was to frono, not to heeheehee, who snuck in while I was composing the response. His response is correct. Although mine lists additional types.
BOOLEAN, INT, FLOAT - all have a number in contentLong, but no contentString or content
ITEM - contentLong is itemId, contentString is name
EFFECT - contentLong is effectId, contentString is name
CLASS - contentLong is class #, contentString is name
SKILL - contentLong is skill #, contentString is name
FAMILIAR - contentLong is familiar #, contentString is name
SLOT - contentLong is slot #, contentString is name
MONSTER - contentLong is monster id#, contentString is name
THRALL - contentLong is thrall #, contentString is name
SERVANT - contentLong is servant #, contentString is name
Every one of those last types could simply use contentLong to compare - with one caveat: multiple monsters can have id = 0, which simply means "we don't know the id", in which case, we should comapre the names.
Edit: my response was to frono, not to heeheehee, who snuck in while I was composing the response. His response is correct. Although mine lists additional types.
Learned something. Thanks.
The method returns an int and the difference between two longs can overflow an int. Java gives an error about "possible loss of precision" if you try it.
OK, fascinating. When I have this code:
Apparently we are ending up with certain monsters comparing as the same - with bad results when used as keys in maps, as shown in missingManuel. I commented out the "return" statement and all is well again. And so, 16121 disables that line and $monster comparisons are always done using the name, for now.
I don't have time to investigate what the problem is, but it doesn't seem to affect items, the point of this bug report...
Code:
if ( this.type == DataTypes.MONSTER_TYPE )
{
// If we know the monster ID, compare it
if ( this.contentLong != 0 && it.contentLong != 0 )
{
return this.contentLong < it.contentLong ? -1 : this.contentLong == it.contentLong ? 0 : 1;
}
// Otherwise, must compare names
}I don't have time to investigate what the problem is, but it doesn't seem to affect items, the point of this bug report...
OK, changing:
to
fixes it. With that code, all monsters with ID=0 sort alphabetically in front of all monsters with non-zero IDs, which sort by ID.
With the previous code, if either monster had ID=0, we'd sort those two by name, but the one with a non-zero ID would be sorted by ID relative to other such monsters, so, we'd have ID=0 monsters intermingled with non-zero ID monsters. This was making TreeMaps of monster Values not work correctly, depending on the order of insertion of various monsters. In other words, it was violating the contract of compareTo. Somehow.
Code:
if ( this.contentLong != 0 && it.contentLong != 0 )
Code:
if ( this.contentLong != 0 || it.contentLong != 0 )With the previous code, if either monster had ID=0, we'd sort those two by name, but the one with a non-zero ID would be sorted by ID relative to other such monsters, so, we'd have ID=0 monsters intermingled with non-zero ID monsters. This was making TreeMaps of monster Values not work correctly, depending on the order of insertion of various monsters. In other words, it was violating the contract of compareTo. Somehow.
Here is an example of how the TreeMap could get screwed up.
TreeMaps are implemented as balanced trees: for any node, the number of children to the left (almost) equals the number to the right. That way, when you want to search the tree for a key, you start at the root and go left or right, making log n comparisons.
As you iteratively add nodes, it rebalances the tree - and the node at the root can change.
Consider adding the following nodes with id/name as given:
0/a
1/d
2/b
3/f
4/g
That is the order the tree will sort - and node 2/b will be the root.
Now add this node:
0/c
New tree ordering:
0/a
1/d
2/b
0/c
3/f
4/g
Either 2/b or 0/c will be the root.
Notice that 1/d is to the left of 0/c. That means that if 1/d ever becomes the root node, because of subsequent additions to its left, we will not be able to look up 0/c, since compareTo would say to go left.
This will not happen any more. The tree will now sort like this:
0/a
0/c
1/d
2/b
3/f
4/g
I could probably further refine it to do this:
if id1 != id2 then sort by id else sort by name
which would work even if ids other than 0 could be duplicated.
TreeMaps are implemented as balanced trees: for any node, the number of children to the left (almost) equals the number to the right. That way, when you want to search the tree for a key, you start at the root and go left or right, making log n comparisons.
As you iteratively add nodes, it rebalances the tree - and the node at the root can change.
Consider adding the following nodes with id/name as given:
0/a
1/d
2/b
3/f
4/g
That is the order the tree will sort - and node 2/b will be the root.
Now add this node:
0/c
New tree ordering:
0/a
1/d
2/b
0/c
3/f
4/g
Either 2/b or 0/c will be the root.
Notice that 1/d is to the left of 0/c. That means that if 1/d ever becomes the root node, because of subsequent additions to its left, we will not be able to look up 0/c, since compareTo would say to go left.
This will not happen any more. The tree will now sort like this:
0/a
0/c
1/d
2/b
3/f
4/g
I could probably further refine it to do this:
if id1 != id2 then sort by id else sort by name
which would work even if ids other than 0 could be duplicated.
So, the bug is fixed, but I'd like to point out the additional issue that this is apparently the first case where KoL has two completely distinct items with the same name. Should mafia have different names for them? For example, I think the Coldfront wiki calls them "rock (crimbo)" and "rock (spelunky)". At the very least, it seems to me that map_to_file and file_to_map ought to store & recognize disambiguated names.
No.
We used to have different names - that did not agree with KoL - for effects that had the same name. A Little Bit Evil, for example. We got rid of that when we went to a lot of trouble to make KoLmafia deal with effects by effect id, always. Ditto for items.
If you want to have map_to_file deal with disambiguated items, use the unique id.
The one data type we have that has an id number that is still problematic is monsters, for whom the unique id is never exposed to us in-game, except while looking at Manuel. All we have to go by for them is the name KoL displays and the image they show you - and even that is not enough to unambiguously disambiguate monsters. Add to that the issue that we don't know the monster ids for all monsters, and handling monsters will need to be a little ad hoc.
We used to have different names - that did not agree with KoL - for effects that had the same name. A Little Bit Evil, for example. We got rid of that when we went to a lot of trouble to make KoLmafia deal with effects by effect id, always. Ditto for items.
If you want to have map_to_file deal with disambiguated items, use the unique id.
The one data type we have that has an id number that is still problematic is monsters, for whom the unique id is never exposed to us in-game, except while looking at Manuel. All we have to go by for them is the name KoL displays and the image they show you - and even that is not enough to unambiguously disambiguate monsters. Add to that the issue that we don't know the monster ids for all monsters, and handling monsters will need to be a little ad hoc.
Last edited: