Summary

This file defines the Set class, instance methods, and static objects/methods. It has no dependencies but is automatically included with Group.js.

/**MathWorx Copyright (c) 2008 Shane Steinert-Threlkeld
Dual-licensed under the MIT and GNU GPL Licenses.
For more information, see LICENSE file */

/** @fileoverview This file defines the Set class, instance methods, and static objects/methods.  It has no dependencies but is automatically included with Group.js. */

/**Constructor function for a new set.
@param {Object} elements Array to become the elements of the set; if a set, will construct a new clone of the set; if not provided, constructs an empty set
@constructor */
function Set(elements) {
	/**the elements of the set 
	@type Array */
	this.elements = new Array();
	/**the cardinality ("dimension") of the set 
	@type Integer */
	this.cardinality = 0;
	if(elements) {
		if(elements instanceof Array) {
			this.elements = elements;
		}
		if(elements instanceof Set) {
			this.elements = elements.elements.slice();
		}
		this.cardinality = this.elements.length;
	} else {
		this.elements = new Array();
		this.cardinality = 0;
	}
}

Set.prototype = {


	/**Determines if a specified element is in the set of this group.
	 * @return {Boolean} true if element is in set, false otherwise**/
	inSet: function(el) {
	       for(i = 0; i < this.cardinality; i++) {
		       if(el == this.elements[i]) {
			       return true;
		       }
	       }
	       return false;
       },

	/**Tests whether or not two sets (including subsets, which must be defined as sets and not simply arrays) are equal.
	@param {Set} set the set to compare to
	@return {Boolean} true if the two sets are equal, false otherwise */
	equalTo: function(set) {
		if(this.cardinality != set.cardinality) {
			return false;
		}
		for(var i = 0; i < this.cardinality; i++) {
			if(this.elements[i] instanceof Set) {
				if(!this.elements[i].equalTo(set.elements[i])) {
					return false;
				} else {
					continue;
				}
			}
			//NOTE: only change to !-- if you are very sure
			if(this.elements[i] != set.elements[i]) {
				return false;
			}
		}
		return true;	
	},

	/**Tests to see if a set is a subset (not necessarily a proper subset; i.e. by this method, a set is a subset of itself) of a given set.
	@param {Set} set the set that may or may not be a superset of the original
	@return {Boolean} true if this is a subset of set, false otherwise */
	subsetOf: function(set) {
		for(i = 0; i < this.cardinality; i++) {
			if(!set.inSet(this.elements[i])) {
				return false;
			}
		}
		return true;
	},

	/**Tests if this set is a proper subset of a given set (i.e. there is at least one element in the superset not in the subset).
	@param {Set} set the set which may or may not be a strict superset
	@return {Boolean} true if this is a proper subset of set, false otherwise */
	properSubsetOf: function(set) {
		if(this.subsetOf(set)) {
			for(i = 0; i < set.cardinality; i++) {
				if(!this.inSet(set.elements[i])) {
					return true;
				}
			}
			return false;
		} else {
			return false;
		}
	},

	/**Tests if the set is a superset of a given set.  Note: not strict definition of superset; any set is also a superset of itself by this definition.
	@param {Set} set the set which may or may not be a subset of the original
	@return {Boolean} true if this is a superset of set, false otherwise */
	supersetOf: function(set) {
		if(set.subsetOf(this)) {
			return true;
		} else {
			return false;
		}
	},

	/**Tests whether or not this set is a proper superset of a given set.
	@param {Set} set the set which may or may not be a proper subset
	@return {Boolean} true if this is proper superset of set, false if not */
	properSupersetOf: function(set) {
		if(set.properSubsetOf(this)) {
			return true;
		} else {
			return false;
		}
	},

	/**Creates a new set that is the union of two sets.
	@param {Set} set the set to join with the current set
	@return {Set} a new set that is the union of the calling and given sets */
	union: function(set) {
		var newSet = new Set(this);
		var testElement;
		for(i = 0; i < set.cardinality; i++) {
			testElement = set.elements[i];
			if(!newSet.inSet(testElement)) {
				newSet.addElement(testElement);
			}
		}
		return newSet;
	},

	/**Creates a new set out of the intersection (shared elements) of two sets.
	@param {Set} set the set with which to find the intersection
	@return {Set} the intersection of the two sets as a new set */
	intersection: function(set) {
		var newSet = new Set();
		var testElement;
		var i = 0;
		while(i < set.cardinality) {		
			testElement = set.elements[i];
			if(this.inSet(testElement)) {
				newSet.addElement(testElement);
			}
			i++;
		}
		return newSet;
	},

	/**Creates a new set that is the relative complement of two sets.  This operation is analogous to subtracting the specified set from the original set.
	@param {Set} set the set to which to find the complement
	@return {Set} a new set that is the specified complement */
	complement: function(set) {
		var newSet = new Set(this);
		var testElement;
		var i = 0;
		while(i < set.cardinality) {
			testElement = set.elements[i];
			if(newSet.inSet(testElement)) {
				newSet.removeElement(testElement);
			}
			i++;
		}
		return newSet;
	},

	/**Calculates the Cartesian product of two sets (the set of all ordered pairs, which are here treated as subsets.
	@param {Set} set the set with which to compute the product
	@return {Set} a new set that is the Cartesian product of the other two */
	cartesianProduct: function(set) {
		var newSet = new Set();
		var el1, el2;
		var i = 0, j= 0;
		while(i < this.cardinality) {
			j = 0;
			el1 = this.elements[i];
			while(j < set.cardinality) {
				el2 = set.elements[j];
				newSet.addElement(new Set([el1,el2]));
				j++;
			}
			i++;
		}
		return newSet;
	},

	/**Adds a new element to the set and updates the cardinality.
	@param {Object} el the element to be added */
	addElement: function(el) {
		this.elements[this.cardinality] = el;
		this.cardinality++;
	},

	/**Removes ALL OCCURENCES of an element from the set and updates the cardinality.
	@param {Object} el the element to be removed */
	removeElement: function(el) {
		while(this.inSet(el)) {
			var index = this.indexOf(el) - 1;
			this.elements.splice(index, 1);
			this.cardinality--;
		}
	},

	/**Finds the index of the first occurence of the specified element.  Should suffice since most sets should be in order and have no recurring elements.
	@param {Object} el the element for which to find the index
	@return {Number} the index of the element in the set (NOT in the array of the set object) */
	indexOf: function(el) {
		var index = null;
		for(i = 0; i < this.cardinality; i++) {
			if(index == null && this.elements[i] == el) {
				index = i + 1;
			}
		}
		return index;
	},

	/**Returns a string representation of the set (and subsets).
	@return {String} the string representatoin of the set.*/
	toString: function() {
		return "{" + this.elements.join(" ") + "}";
	}

} //end Set prototype

/**the empty set {}
@type Set
@final */
Set.empty = new Set();

/**Creates a set with n zero elements
@param {Integer} n the number of elements in the zero set 
@return {Set} a set of n elements all equal to 0 */
Set.zero = function(n) {
	var elements = new Array();
	for(i = 0; i < n; i++) {
		elements[i] = 0;
	}
	return new Set(elements);
}