module tools.Set;

import std.string;
import std.traits;

/++
 + Template that determines if a function exists with the signature:
 + char[] toString(T);
 + 
 + Params:  T = The type to test.
 + Returns: A bool specifying whether or not the toString(T) function exists.
 +/
private template hasToStringMember(T) {
	const bool hasToStringMember = is(typeof(&T.toString) == char[] function());
}

/++
 + Template that determines if T has a member-function with the signature:
 + char[] toString();
 + 
 + Params:  T = The class or struct to test.
 + Returns: A bool specifying whether or not the T.toString() function exists.
 +/
private template toStringFunctionExists(T) {
	const bool toStringFunctionExists = is(typeof(.toString(cast(T)T.init)));
}

/++
 + Template that checks if a type is a static array type, and if so, returns
 + its dynamic array equivalent.
 + 
 + Params:  T = The type to check.
 + Returns: If the type was not a static array: T itself.
 +          If the type was a static array: the dynamic array equivalent of T.
 +/
private template nonStaticArrayType(T) {
	static if (isStaticArray!(T)) {
		alias typeof(T[0])[] nonStaticArrayType;
	} else {
		alias T nonStaticArrayType;
	}
}

/++
 + Returns the minimum of two values.
 + 
 + Params:  value1 = The first value to compare.
 +          value2 = The second value to compare.
 + Returns: The one with the lowest value, or value1 if both are equal.
 +/
private T min(T)(T value1, T value2) {
	if (value2 < value1) return value2;
	return value1;
}
unittest {
	assert(min(1, 2) == 1);
	assert(min(10, -20) == -20);
	assert(min(42, 42) == 42);
	
	assert(min(1.5, 2.4) == 1.5);
	assert(min(10.3, -20.9) == -20.9);
	assert(min(5.44, 5.44) == 5.44);
}

/++
 + Implementation of a set. The rules:
 + 
 + * Can hold any type that can be used as the key-type of an
 +   associative array.
 + 
 + * Can hold only one of each value.
 + 
 + * Holds no information associated with a value, except the
 +   value itself.
 + 
 + * The elements in a set are not in any order.
 + 
 + * If the type is a static array, the set will actually hold
 +   its dynamic array equivalent.
 + 
 + * Can be used as the key-type of an associative array.
 +   So it is also possible to have a set of sets.
 + 
 + Authors: Michiel Helvensteijn
 + 
 + Bugs: Was not designed for efficiency. If you want to do many set
 +       operations in a loop, this may not be the right class (yet).
 +/
class Set(T)  {
	private:
		
		alias nonStaticArrayType!(T) Type;
		
		static if (isStaticArray!(T)) {
			Type duplicate(Type element) {
				return element.dup;
			}
		} else {
			Type duplicate(T element) {
				return element;
			}
		}
		
	public:
		
		/++
		 + The default constructor that creates an empty set.
		 +/
		this() {
		} // intentionally empty
		
		/++
		 + The copy constructor that creates a copy of 'other'.
		 + 
		 + Params: other = The other set to copy.
		 +/
		this(Set!(T) other) {
			foreach (element ; other) {
				add(element);
			}
		}
		
		/++
		 + Add a new element to the set.
		 + 
		 + Params: element = The new element to add.
		 +/
		void add(Type element) {
			_elements[duplicate(element)] = true;
		}
		unittest {
			auto x = set(1,2,3);
			
			assert(!(4 in x));
			assert(x.size() == 3);
			
			x.add(4);
			
			assert(4 in x);
			assert(x.size() == 4);
			
			x.add(4);
			
			assert(x.size() == 4);
		}
		
		/++
		 + Remove an element from the set.
		 + 
		 + Params: element = The element to remove.
		 +/
		void remove(Type element) {
			_elements.remove(duplicate(element));
		}
		unittest {
			auto x = set(1,2,3,4,5,6,7);
			
			assert(4 in x);
			assert(x.size() == 7);
			
			x.remove(4);
			
			assert(!(4 in x));
			assert(x.size() == 6);
			
			x.remove(4);
			
			assert(x.size() == 6);
		}
		
		/++
		 + Get the number of elements in the set.
		 + 
		 + Returns: The number of elements in the set.
		 +/
		uint size() {
			return _elements.length;
		}
		unittest {
			auto x = set(1,2,3,4,5,6,7);
			
			assert(x.size() == 7);
			
			auto y = new Set!(char[]);
			
			assert(y.size() == 0);
		}
		
		/++
		 + Get an array filled with the elements of the set.
		 + 
		 + Returns: An array filled with the elements of the set in
		 +          undefined order.
		 +/
		Type[] getArray() {
			return _elements.keys;
		}
		unittest {
			auto x = set("one", "two", "three", "fortytwo");
			auto y = x.getArray();
			
			foreach (e ; y) {
				assert(e in x);
			}
		}
		
		/++
		 + Get a textual representation of the content of the set.
		 + For this function to work, the content type (T) of the
		 + set must either be a string or must also have a toString
		 + function, in one of these forms:
		 + * char[] T.toString();
		 + * char[] .toString(T);
		 + 
		 + Returns: A textual representation of the content of the set.
		 +/
		char[] toString() {
			char[] list;
			
			for (uint i = 0; i < _elements.length; ++i) {
			
				static if (is(Type == char[])) {
					list ~= _elements.keys[i];
				} else static if (hasToStringMember!(T)) {
					list ~= _elements.keys[i].toString();
				} else static if(toStringFunctionExists!(T)) {
					list ~= .toString(_elements.keys[i]);
				} else {
					assert(0, "The type " ~ T.stringof ~ " has no toString function defined.");
				}
				
				if (i < _elements.length - 1) {
					list ~= ", ";
				}
			}
			
			return "{" ~ list ~ "}";
		}
		
		/++
		 + Get the hash-value of the set. This function makes it
		 + possible for the set to be the key of an associative array.
		 + 
		 + Returns: The hash-value of the set.
		 +/
		hash_t toHash() {
			hash_t result = 0;
			uint count = 1;
			
			foreach (element ; this) {
				result = (result + typeid(Type).getHash(&element) * count++) % hash_t.max;
			}
			
			return result;
		}
		
		/++
		 + Compare two sets for equality.
		 + 
		 + Params: other = The other set to test against.
		 + Returns: 1 if the two sets are equal. 0 if they are not.
		 +/
		int opEquals(Object other) {
			auto o = cast(Set!(T)) other;
			
			if (!o) return false;
			
			if (_elements.length != o._elements.length) return false;
			
			foreach (element ; o)
				if (!(element in this)) return false;
			
			return true;
		}
		unittest {
			assert(set(1, 2, 3) == set(3, 1, 2));
			assert(set(5, 6, 7) == set(5, 5, 7, 6, 5, 7, 6));
			assert(set(5, 6, 7) != set(5, 6, 8));
		}
		
		/++
		 + Compare two sets for inequality. This function only exists
		 + so that sets can be keys for associative arrays. One set can
		 + not mathematically be less or greater than another set.
		 + 
		 + Params: other = The other set to test against.
		 + Returns:  0 if this = other
		 +          -1 if this < other
		 +           1 if this > other
		 +           The inequality operators return booleans.
		 +/
		int opCmp(Object other) {
			auto o = cast(Set!(T)) other;
			
			if (!o) return -1;
			
			auto thisList = _elements.keys;
			auto otherList = o._elements.keys;
			
			thisList.sort;
			otherList.sort;
			
			for (uint i = 0; i < min(thisList.length, otherList.length); ++i) {
				if (thisList[i] < otherList[i]) return -1;
				if (thisList[i] > otherList[i]) return 1;
			}
			
			if (thisList.length < otherList.length) return -1;
			if (thisList.length > otherList.length) return 1;
			
			return 0;
		}
		
		/++
		 + Check if an element is a member of the set.
		 + 
		 + Params: element = The element to check for.
		 + Returns: true, if the element is in the set
		 +          false, if the element is not in the set
		 +/
		bool opIn_r(Type element) {
			return cast(bool)(duplicate(element) in _elements);
		}
		unittest {
			assert(1 in set(1, 2, 3));
			assert("foo" in set("bleh", "foo", "bar"));
			assert(!(5 in set(1, 2, 3, 4, 6, 7)));
		}
		
		/++
		 + Get the intersection of two sets. An element will be in the
		 + result if and only if it is in both source sets.
		 + 
		 + Params: other = The other set to intersect with this one.
		 + Returns: The intersection of this set with the other.
		 +/
		Set!(T) opAnd(Set!(T) other) {
			auto result = new Set!(T);
			
			foreach (element ; this) {
				if (element in other) {
					result.add(element);
				}
			}
			
			return result;
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert((x & y) == set(3, 4));
			assert((y & x) == set(3, 4));
		}
		
		/++
		 + Intersect this set with another set. This set will become the
		 + intersection result. An element will be in the result if and
		 + only if it is in both source sets.
		 + 
		 + Params: other = The other set to intersect with this one.
		 +/
		void opAndAssign(Set!(T) other) {
			foreach (element ; this) {
				if (!(element in other)) {
					remove(element);
				}
			}
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert(x == set(1, 2, 3, 4));
			
			x &= y;
			
			assert(x == set(3, 4));
		}
		
		/++
		 + Get the union of two sets. An element will be in the
		 + result if and only if it is in either or both source sets.
		 + 
		 + Params: other = The other set to unite with this one.
		 + Returns: The union of this set with the other.
		 +/
		Set!(T) opOr(Set!(T) other) {
			auto result = new Set!(T)(this);
			
			foreach (element ; other) {
				result.add(element);
			}
			
			return result;
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert((x | y) == set(1, 2, 3, 4, 5, 6));
			assert((y | x) == set(1, 2, 3, 4, 5, 6));
		}
		
		/++
		 + Unite this set with another set. This set will become the union
		 + result. An element will be in the result if and only if it is in
		 + either or both source sets.
		 + 
		 + Params: other = The other set to unite with this one.
		 +/
		void opOrAssign(Set!(T) other) {
			foreach (element ; other) {
				add(element);
			}
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert(x == set(1, 2, 3, 4));
			
			x |= y;
			
			assert(x == set(1, 2, 3, 4, 5, 6));
		}
		
		/++
		 + Get the symmetric difference of two sets. An element will be in the
		 + result if and only if it is in one, but not both, source sets.
		 + 
		 + Params: other = The other set to xor with this one.
		 + Returns: The symmetric difference of this set with the other.
		 +/
		Set!(T) opXor(Set!(T) other) {
			auto result = new Set!(T)(this);
			
			foreach (element ; other) {
				if (element in this) {
					result.remove(element);
				} else {
					result.add(element);
				}
			}
			
			return result;
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert((x ^ y) == set(1, 2, 5, 6));
			assert((y ^ x) == set(1, 2, 5, 6));
		}
		
		/++
		 + Xor this set with another set. This set will become the symmetric
		 + difference result. An element will be in the result if and only if
		 + it is in one, but not both, source sets.
		 + 
		 + Params: other = The other set to unite with this one.
		 +/
		void opXorAssign(Set!(T) other) {
			foreach (element ; other) {
				if (element in this) {
					remove(element);
				} else {
					add(element);
				}
			}
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert(x == set(1, 2, 3, 4));
			
			x ^= y;
			
			assert(x == set(1, 2, 5, 6));
		}
		
		/++
		 + Get the relative complement of another set in this one. An element
		 + will be in the result if and only if it is in this set, but not in
		 + the other.
		 + 
		 + Params: other = The other set to complement in this one.
		 + Returns: The relative complement of the other set in this one.
		 +/
		Set!(T) opSub(Set!(T) other) {
			auto result = new Set!(T)(this);
			
			foreach (element ; other) {
				result.remove(element);
			}
			
			return result;
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert((x - y) == set(1, 2));
			assert((y - x) == set(5, 6));
		}
		
		/++
		 + Complement another set in this one. This set will become the
		 + relative complement result. An element will be in the result if
		 + and only if it is in this set, but not in the other.
		 + 
		 + Params: other = The other set to complement in this one.
		 +/
		void opSubAssign(Set!(T) other) {
			foreach (element ; other) {
				remove(element);
			}
		}
		unittest {
			auto x = set(1, 2, 3, 4);
			auto y = set(3, 4, 5, 6);
			
			assert(x == set(1, 2, 3, 4));
			
			x -= y;
			
			assert(x == set(1, 2));
		}
		
		/++
		 + The foreach loop on this set. It will visit all elements in the
		 + set in an undefined order.
		 + 
		 + Example:
		 + ------------------------------
		 + auto x = new Set!(int);
		 + x.add(5); x.add(6); x.add(7);
		 + 
		 + foreach (e ; x) {
		 +     assert(e in x); 
		 + }
		 + ------------------------------
		 +/
		int opApply(int delegate(inout Type) dg) {
			int result = 0;
			
			foreach (element; _elements.keys) {
				result = dg(element);
				if (result) break;
			}
			
			return result;
		}
		unittest {
			auto x = set(1, 2, 3, 4, 5, 6);
			
			foreach (e ; x) {
				assert(e in x);
			}
		}
		
		int opApplyReverse(int delegate(inout Type) dg) {
			assert(0, "foreach_reverse has no meaning for a set. Use foreach instead.");
		}
		
	private:
		
		bool[Type] _elements;
}

/++
 + A sort of set literal.
 + 
 + Params:  elements = The elements of the set literal. Must all be of the
 +                     same type and must at least include one value.
 + Returns: The set with the elements specified.
 + 
 + Example:
 + ------------------------------
 + auto x = set(1, 2, 3);
 + ------------------------------
 +/
Set!(T[0]) set(T ...)(T elements) {
	auto result = new Set!(T[0]);
	
	foreach (element; elements) {
		result.add(element);
	}
	
	return result;
}
unittest {
	auto x = set(1, 2, 3);
	
	static assert( is(typeof(x) == Set!(int)) );
	assert(x.size() == 3);
	assert(1 in x);
	assert(2 in x);
	assert(3 in x);
}