package threelbmonkeybrain.collections { import flash.utils.Dictionary; import flash.utils.Proxy; import flash.utils.flash_proxy; import threelbmonkeybrain.relate.Equatable; use namespace flash_proxy; /** * Implementation of a finite set using a hash table (Dictionary object). As an * alternative to using functions, bracket notation can also be used: * 
	 * trace(hashSet[someObject]); // Traces someObject if it is a member, "undefined" otherwise.
	 * delete hashSet[someObject]; // Removes someObject from the set.
	 * hashSet[someObject] = undefined; // Removes someObject from the set.
	 * hashSet[someObject] = someObject; // Adds someObject to the set.
	 * hashSet[someObject] = otherObject; // Throws an error.
	 *
*

* It is also possible to iterate over the set using for..in or * for each..in. Both do the same thing. *

* * @author T. Michael Keesey */ public class HashSet extends Proxy { /** * The hash table that stores data for this set. Keys and values must be the same. * Any key or value is a member of the set; anything else is not. */ protected const hash:Dictionary = new Dictionary(); /** * The number of members in this set. This is maintained separately and must always be * synchronized. * * @private * @see #empty * @see #size */ protected var _size:int = 0; /** * Used to store members during a for..in or for each..in loop. * * @private */ protected var proxyMembers:Array; /** * Creates a new, empty instance. * * @see #empty * @see #clone() * @see #fromArray() */ public function HashSet() { super(); } /** * Tells whether this set is empty. *

* This set is empty if and only if size == 0. *

* * @see #size */ public function get empty():Boolean { return _size == 0; } /** * The number of members in this set. * * @see #empty */ public function get size():int { return _size; } /** * Adds an element as a member of this set. If it is already a member, does nothing. * * @param element * New member to add. * @see #addMembers() * @see #has() * @see #remove() */ public function add(element:Object):void { if (hash[element] != element) { hash[element] = element; ++_size; } } /** * Adds the members of another collection. * * @param value * Another collection. Can be a HashSet, an Array, or any * object that allows for each..in iteration. * @see #add() */ public function addMembers(value:Object):void { for each (var member:Object in value) { add(member); } } /** * Removes all members. * * @see #remove() */ public final function clear():void { for (var member:Object in hash) { delete hash[member]; } _size = 0; } /** * Creates a copy of a set. * * @param value * The set to copy. * @return * A new set with the same membership as value. * @see #fromObject() */ public static function clone(value:HashSet):HashSet { var clone:HashSet = new HashSet(); clone._size = value._size; for (var member:Object in value.hash) { clone.hash[member] = member; } return clone; } /** * Creates a singleton set (a set with one member). * * @param member * The solitary member of the new set. * @return * A new set with a size of 1 and member as the only member. * @see #clone() * @see #fromObject() */ public static function createSingleton(member:Object):HashSet { var singleton:HashSet = new HashSet(); singleton.hash[member] = member; singleton._size = 1; return singleton; } /** * Removes an object from this set. *

* Works much like remove(). The following are equivalent: *

* 
		 * delete hashSet[element];
		 * hashSet.remove(element);
		 *
* * @param name * The member to remove. * @return * A value of true if the object was removed; false otherwise. * @see #remove() */ override flash_proxy function deleteProperty(name:*):Boolean { if (hash[name] == undefined) return false; delete hash[name]; --_size; return true; } /** * Returns the difference between this set and another object. * * @param subtrahend * Set to subtract from this set. This function is optimized for a HashSet * object, but can use any type of object that can be iterated over using * for each..in. * @return * A set that includes all members of this set that are not in subtrahend. * Under some circumstances, may simply return this set. */ public function diff(subtrahend:Object):HashSet { if (subtrahend is HashSet) { if (_size == 0 || subtrahend.empty) return this; var result:HashSet = new HashSet(); for (var member:Object in hash) { if (subtrahend.hash[member] == undefined) { result.hash[member] = member; ++result._size; } } return result; } return diff(fromObject(subtrahend)); } /** * Checks if this set is equivalent to another set. * * @param value * Set to check against. If not a HashSet, returns false * @return * A value of true if value has the same membership as this set; * false otherwise. */ public function equals(value:Object):Boolean { if (this == value) return true; if (value is HashSet) { if (_size != value._size) return false; for (var member:Object in hash) { if (value.hash[member] == undefined) return false; } return true; } return false; } /** * Checks whether all members of the set satisfy a criterion. *

* If this set is empty, this will always return true. *

* * @param test * The criterion to test for. Must take a single argument and return a * Boolean value. * @param thisObject * An object to use as this for the test function. * @return * A value of true is at least one member causes test to return * true; false otherwise. * @see #exists() * @see #empty */ public function every(test:Function, thisObject:* = null):Boolean { for (var member:Object in hash) { if (!test.apply(thisObject, [member])) return false; } return true; } /** * Executes a test function on each member of this set and constructs a new set for all members that return * true for the specified function. If a member returns false, it is not included in * the new set. * * @param test * The criterion to test for. Must take a single argument and return a * Boolean value. * @param thisObject * An object to use as this for the test function. * @return * A new set including only the elements of this set which test returns true for. */ public function filter(test:Function, thisObject:* = null):HashSet { var filtered:HashSet = new HashSet(); for each (var member:Object in hash) { if (test.apply(thisObject, [member])) { filtered.hash[member] = member; ++filtered._size; } } return filtered; } /** * Executes a function on each member of this set. * * @param callback * The function to run on each member. Must take a single argument. * @param thisObject * An object to use as this for the test function. */ public function forEach(test:Function, thisObject:* = null):void { for each (var member:Object in hash) { test.apply(thisObject, [member]) } } /** * Creates a new set and populates with the the elements in another object. *

* If the other object is a HashSet, then using clone() is * recommended. *

* * @param value * An object containing the elements to add as members of the new set. Can be any type * of object, as long as its elements can be iterated over using * for each..in (for example, Array objects). * Duplicated elements will only be added once. * @return * A new HashSet instance with the same membership as members. * @see #clone() * @see #createSingleton * @see Array */ public static function fromObject(value:Object):HashSet { var hashSet:HashSet = new HashSet(); hashSet.addMembers(value); return hashSet; } /** * Allows the use of bracket notation to check membership. If hashSet[x] == x, * then x is a member of the set. If hashSet[x] == undefined, then * x is not a member. * * @param name * Element to look up. * @return * A value of undefined if name is not a member. Returns * name if name is a member. */ override flash_proxy function getProperty(name:*):* { if (hash[name] != undefined) return name; return undefined; } /** * Checks if this set has a certain member. * * @param element * Element to check for. * @return * A value of true if element is a member of this set; * false otherwise. */ public function has(element:Object):Boolean { return hash[element] != undefined; } /** * Checks if this set has a certain member. * * @param name * Element to check for. * @return * A value of true if element is a member of this set; * false otherwise. */ override flash_proxy function hasProperty(name:*):Boolean { return hash[name] != undefined; } /** * Returns the intersection of this set and another object. * * @param value * Object to calculate intersection with. May be a HashSet, an * Array, or any type of object which can be iterated over using * for each..in. (This function is optimized for HashSet * objects.) * @return * A set containing all elements that are members of this set and members of * value. In some circumstances this function may simply return this set or * value. */ public function intersect(value:Object):HashSet { if (value is HashSet) { if (value._size == 0) return value as HashSet; if (_size == 0) return this; var result:HashSet = new HashSet(); for (var member:Object in hash) { if (value.hash[member] != undefined) { result.hash[member] = member; ++result._size; } } return result; } return fromObject(value).intersect(this); } /** * Executes a function on each member of this set, and constructs a new set of elements corresponding to the * results of the function on each member of the original set. * * @param mapper * The function to run on each member of the set. Must take a single argument and return something. * If it returns undefined, that result is not added to the new set. * @param thisObject * An object to use as this for the test function. * @return * New set containing all mapped elements. */ public function map(mapper:Function, thisObject:* = null):HashSet { var mapped:HashSet = new HashSet(); for each (var member:Object in hash) { var mappedMember:* = mapper.apply(thisObject, [member]); if (mappedMember != undefined) mapped.add(mappedMember); } return mapped; } /** * @inheritDoc */ override flash_proxy function nextName(index:int):String { return proxyMembers[index - 1]; } /** * @inheritDoc */ override flash_proxy function nextNameIndex(index:int):int { if (index == 0) proxyMembers = toArray(); if (index < _size) return index + 1; else return 0; } /** * @inheritDoc */ override flash_proxy function nextValue(index:int):* { return proxyMembers[index - 1]; } /** * Tells whether this is a proper subset (that is, a subset that is not identical) * of another object. *

* Empty sets are considered subsets of all nonempty sets. *

* * @param value * Set to check against. Optimized for HashSet objects, but can use any type * of object whose elements can be iterated over using for each..in. * @return * A value of true if this set is a subset of value and not * identical to it; false otherwise. * @see #equals() * @see #subsetOf() */ public function prSubsetOf(value:Object):Boolean { if (value is HashSet) { if (value._size == 0) return false; if (_size == 0) return value._size != 0; if (_size >= value._size) return false; for each (var member:Object in hash) { if (value.hash[member] != member) return false; } return true; } return prSubsetOf(fromObject(value)); } /** * Removes a member of this set. * * @param element * Element to remove. If it is not a member, this function does nothing. */ public function remove(element:Object):void { if (hash[element] != undefined) { delete hash[element]; --_size; } } /** * Removes the members of another collection. * * @param value * Another collection. Can be a HashSet, an Array, or any * object that allows for each..in iteration. * @see #remove() */ public function removeMembers(value:Object):void { for each (var member:Object in value) { remove(member); } } /** * Allows members to be added or removed using bracket notation. *

* This is equivalent to hashSet.add(x): hashSet[x] = x; *

*

* This is equivalent to hashSet.remove(x): hashSet[x] = undefined; *

* * @param name * Member to set the value of. * @param value * A value of undefined to remove the member, or name to * add it. If value is anything else, this function throws an error. * @throws ArgumentError * If value is not undefined or the same as name. */ override flash_proxy function setProperty(name:*, value:*):void { if (name == undefined) return; if (value == undefined) remove(name as Object); if (name != value) throw new ArgumentError("Improper usage of bracket notation to add a set member. Try HashSet.add() instead."); add(name as Object); } /** * Checks whether at least one member of the set satisfies a criterion. *

* If this set is empty, this will always return false. *

* * @param test * The criterion to test for. Must take a single argument and return a * Boolean value. * @param thisObject * An object to use as this for the test function. * @return * A value of true is at least one member causes test to return * true; false otherwise. * @see #forAll() * @see #empty */ public function some(test:Function, thisObject:* = null):Boolean { for (var member:Object in hash) { if (test.apply(thisObject, [member])) return true; } return false; } /** * Tells whether this is a subset of another set. *

* Identical sets are considered subsets of each other. Empty sets are subsets of all other * sets. *

* * @param value * Set to check against. Optimized for HashSet objects, but can use any type * of object whose elements can be iterated over using for each..in. * @return * A value of true if this set is a subset of value; * false otherwise. * @see #equals() * @see #prSubsetOf() */ public function subsetOf(value:Object):Boolean { if (value is HashSet) { if (this == value) return true; if (_size == 0) return true; if (value._size == 0) return false; for (var member:Object in hash) { if (value.hash[member] == undefined) return false; } return true; } return subsetOf(fromObject(value)); } /** * Converts this set into an array with the same membership. * * @return * A new Array instance. */ public final function toArray():Array { var array:Array = new Array(_size); var i:int = 0; for each (var member:Object in hash) { array[i++] = member; } return array; } /** * @inheritDoc */ public final function toString():String { return "{" + toArray().join(", ") + "}"; } /** * Returns the union of this set and another set. * * @param value * Set to calculate union with. Optimized for HashSet objects, but can use any type * of object whose elements can be iterated over using for each..in. * @return * A set containing all elements that are members of this set or members of * value. In some circumstances this function may simply return this set or * value. */ public function union(value:Object):HashSet { if (value is HashSet) { if (value._size == 0 || value == this) return this; if (_size == 0) return value as HashSet; var result:HashSet = clone(this); for each (var member:Object in value) { if (result.hash[member] == undefined) { result.hash[member] = member; ++result._size; } } return result; } return union(fromObject(value)); } } }