Sets

Jimbo

(Posted 2012) [#1]

I was quite excited to find the Monkey had a Set type, then very disappointed to find that it doesn't. The Set type in Monkey is really a Map variant.

It appears (but I may well be wrong) NOT to have union, exclusion, difference, and equality operators. These make sets very powerful.

I've used proper sets frequently over the last 30+ years. They save huge amounts of iteration. I see complex loops for card games in the forums that could be solved with a couple of proper set statements.

Has anybody produce a sensible Set module?

zoqfotpik

(Posted 2012) [#2]

How long would it really take to do this? Seems like it would be fairly trivial to write such a thing.

Goodlookinguy

(Posted 2012) [#3]

I've never personally used a set data structure, but I looked it up and it took me all of 20-minutes to hack monkey.set and add these. So I might as well share it.

monkey.set (EDIT: I optimized it a bit)

' Module monkey.set
'
' Placed into the public domain 24/02/2011.
' No warranty implied; use at your own risk.

Private

Import map

Public

Class Set<T>

	Method New( map:Map<T,Object> )
		Self.map=map
	End
	
	Method Clear()
		map.Clear
	End
	
	Method Count()
		Return map.Count()
	End
	
	Method IsEmpty?()
		Return map.IsEmpty()
	End

	Method Contains?( value:T )
		Return map.Contains( value )
	End
	
	Method Insert( value:T )
		map.Set value,Null
	End
	
	Method Remove( value:T )
		map.Remove value
	End
	
	Method ObjectEnumerator:KeyEnumerator<T,Object>()
		Return map.Keys().ObjectEnumerator()
	End
	
	Method Union:Void( set:Set<T> )
		For Local key:T = EachIn set
			If ( Not map.Contains(key) )
				Insert(key)
			End
		Next
	End
	
	Method Intersect:Void( set:Set<T> )
		For Local key:T = EachIn Self
			If ( Not set.Contains(key) )
				map.Remove(key)
			End
		Next
	End
	
	Method Difference:Void( set:Set<T> )
		For Local key:T = EachIn Self
			If ( set.Contains(key) )
				map.Remove(key)
			End
		Next
	End
	
	Method Complement:Void( set:Set<T> )
		Intersect(set)
		For Local key:T = EachIn set
			If ( map.Contains(key) )
				map.Remove(key)
			Else
				Insert(key)
			End
		Next
	End
	
	Method Subset:Bool( set:Set<T> )
		If ( map.Count() >= set.Count() ) Return False
		For Local key:T = EachIn Self
			If ( Not set.Contains(key) )
				Return False
			End
		Next
		Return True
	End
	
	Method Equals:Bool( set:Set<T> )
		If ( map.Count() <> set.Count() ) Return False
		For Local key:T = EachIn Self
			If ( Not set.Contains(key) )
				Return False
			End
		Next
		Return True
	End
	
	Method Copy:Void( set:Set<T> )
		map.Clear()
		For Local key:T = EachIn set
			Insert(key)
		Next
	End
	
Private

	Field map:Map<T,Object>

End

'Helper versions...

Class IntSet Extends Set<Int>
	Method New()
		Super.New( New IntMap<Object> )
	End
End

Class FloatSet Extends Set<Float>
	Method New()
		Super.New( New FloatMap<Object> )
	End
End

Class StringSet Extends Set<String>
	Method New()
		Super.New( New StringMap<Object> )
	End
End

Test I made

Strict
Import monkey.set


Function Main:Int()
	Local set1:IntSet, set2:IntSet
	
	
	' Union
	set1 = GetSet123()
	set2 = GetSet246()
	
	Print "==============="
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	set1.Union(set2)
	
	PrintIntSet(set1, "Union")
	
	' Intersection
	set1 = GetSet123()
	set2 = GetSet234()
	
	Print "==============="
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	set1.Intersect(set2)
	
	PrintIntSet(set1, "Intersect")
	
	' Difference
	set1 = GetSet123()
	set2 = GetSet246()
	
	Print "==============="
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	set1.Difference(set2)
	
	PrintIntSet(set1, "Difference")
	
	' Complement
	set1 = GetSet123()
	set2 = GetSet246()
	
	Print "==============="
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	set1.Complement(set2)
	
	PrintIntSet(set1, "Complement")
	
	' Subset
	set1 = GetSet123()
	set2 = GetSet123()
	
	Print "==============="
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	If ( set1.Subset(set2) )
		Print "Set 1 is a subset of Set 2"
	Else
		Print "Set 1 is not a subset of set 2"
	End
	
	set1 = GetSet123()
	set2 = GetSet1234()
	
	Print ""
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	If ( set1.Subset(set2) )
		Print "Set 1 is a subset of Set 2"
	Else
		Print "Set 1 is not a subset of set 2"
	End
	
	set1 = GetSet123()
	set2 = GetSet246()
	
	Print ""
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	If ( set1.Subset(set2) )
		Print "Set 1 is a subset of Set 2"
	Else
		Print "Set 1 is not a subset of set 2"
	End
	
	' Equals
	set1 = GetSet123()
	set2 = GetSet123()
	
	Print "==============="
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	If ( set1.Equals(set2) )
		Print "Set 1 is equal to Set 2"
	Else
		Print "Set 1 is not equal to set 2"
	End
	
	set1 = GetSet123()
	set2 = GetSet1234()
	
	Print ""
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	If ( set1.Equals(set2) )
		Print "Set 1 is equal to Set 2"
	Else
		Print "Set 1 is not equal to set 2"
	End
	
	set1 = GetSet123()
	set2 = GetSet246()
	
	Print ""
	PrintIntSet(set1, "Set 1")
	PrintIntSet(set2, "Set 2")
	
	If ( set1.Equals(set2) )
		Print "Set 1 is equal to Set 2"
	Else
		Print "Set 1 is not equal to set 2"
	End
	
	Return 0
End

Function PrintIntSet:Void( set:IntSet, msg:String = "Set" )
	Local toPrint:String = msg + ": {"
	For Local key := EachIn set
		toPrint += String(key) + ", "
	Next
	Print toPrint[.. toPrint.Length - 2] + "}"
End

Function GetSet123:IntSet()
	Local set:IntSet = New IntSet()
	
	set.Insert(1)
	set.Insert(2)
	set.Insert(3)
	
	Return set
End

Function GetSet246:IntSet()
	Local set:IntSet = New IntSet()
	
	set.Insert(2)
	set.Insert(4)
	set.Insert(6)
	
	Return set
End

Function GetSet234:IntSet()
	Local set:IntSet = New IntSet()
	
	set.Insert(2)
	set.Insert(3)
	set.Insert(4)
	
	Return set
End

Function GetSet1234:IntSet()
	Local set:IntSet = GetSet123()
	set.Insert(4)
	
	Return set
End

Jimbo

(Posted 2012) [#4]

That's very neat!

Normally, however, this will be done highly effectively at processor level by using the logical operators on a small array of bit-fields and involves no iteration. Set elements are enumerated types or sub-ranges.

Simple (very) example in Pascal:

Type TPersonType = (male,female,blonde,brunette,redhead,grey,bald,bearded,minor,senior);

TPerson = set of TPersonType;

var Fred,Mary,IllegalKisser: TPerson;

...
Fred := [male,bald,bearded,senior];
Mary := [female,blonde,minor];
IllegalKisser := [minor,senior];

If (Fred * Mary * IllegalKisser_) = IllegalKisser then // arrest Fred

In game terms the blistering speed of this is very useful for deep alpha-beta pruning, since for any position we can declare which moves are legal and which are not, include legal moves in a set, yielding a very fast evaluation. It's also valuable for token parsing in compilers, since after reading a token there will be a set of expected successors, and if the next token is not in the "expected" set we can throw an error.

I think this needs to be implemented as a core language element to be properly effective!

Goodlookinguy

(Posted 2012) [#5]

I'm gonna be honest, I'm 20-years-old now and was born into an age of electronics getting faster and faster. From my experience, the amount of time it'd take to re-program this to run at these optimal speeds does not outweigh the actual benefits you'll receive in modern electronics. This becomes more true every day and follows a pattern much like that of diminishing returns. So I wouldn't put too much focus on this. That's my two cents anyway.

muddy_shoes

(Posted 2012) [#6]

I think this needs to be implemented as a core language element to be properly effective!

It can't be implemented as a core language element of Monkey in the performant way that you imply it is for Pascal. Monkey is a language that is translated to other languages that aren't Pascal and don't have sets as first-class citizens of the language. There's nothing stopping you writing a bit-field based set class if you want, although it implies limitations on usage that implementations based on maps don't have.

From my experience, the amount of time it'd take to re-program this to run at these optimal speeds does not outweigh the actual benefits you'll receive in modern electronics.

Eh? Are you seriously implying that someone who wants a fast set implementation in Monkey would be better off waiting for all their customers to get faster computers?

Goodlookinguy

(Posted 2012) [#7]

Eh? Are you seriously implying that someone who wants a fast set implementation in Monkey would be better off waiting for all their customers to get faster computers?

No, I'm not. I didn't imply anything like that. My statement simply means that you could waste time programming an optimal set or just use this one and it's unlikely that it'll be that much more of a burden on the machines that run it. Scripting languages were being used back in the 90's and those games ran fine. That's why I don't see any particular reason to put so much focus on something so minute.

Edit: Just to clarify, I referred to scripting languages because they are typically very heavy. Code like this is probably lighter than any average scripting language type code.

Jimbo

(Posted 2012) [#8]

If bit-fields don't work there isn't much point in having the bit-manipulation operators in Monkey, is there? I think that Monkey is an elegant language, but I worry when I find statements such as the range of Int being platform-specific (in the Language docs). It would be nice to have explicit range-types: Int32, Int64, and unsigned equivalent types.

I can see why it would be problematic as a low-level implementation, obviously. Cross-platform code is inevitably lowest common denominator. I was merely disappointed to find that Monkey sets aren't really sets!

Thanks for the comments.

muddy_shoes

(Posted 2012) [#9]

Whether it's minute or not would depend entirely on whether your algorithm makes heavy use of set operations or not. There's no possible way to make a general statement about the benefit of spending time optimising this for whatever purpose Jimbo has in mind from some broad observation that some games in the 90s used scripting languages and ran okay.

muddy_shoes

(Posted 2012) [#10]

If bit-fields don't work there isn't much point in having the bit-manipulation operators in Monkey, is there?

I didn't say that bit-fields don't work. I said that the target languages "...don't have sets as first-class citizens of the language. There's nothing stopping you writing a bit-field based set class if you want...". In other words, you've got the tools to do something similar, but you can't expect Monkey to generate something as fast as a Pascal compiler could.

Goodlookinguy

(Posted 2012) [#11]

You missed the key point of my statements and are being a bit too serious for my taste. So I'm gonna back off before this thread goes in some wayward direction downhill.

Edit: In case the point of my statements is still unclear. It's, finish a game first, if you want to go back and optimize, do it later.

Jimbo

(Posted 2012) [#12]

I didn't mean to spark a controversy!

As Monkey claims to be a "brand new language" I think it's valid to discuss potential extensions. To implement sets properly would require operator overloading, which I don't think Monkey has.

zoqfotpik

(Posted 2012) [#13]

Let's not let this sort of argument culture take root here.

I'll be implementing this just because it's interesting.