/* isAnagram.cpp
   non-OOP solution for ex. 9.10, p. 310.
   _Intro to Pgmg/C++_
*/


#include <iostream>
#include <string>
using namespace std;

void sort(string& s);
bool isAnagram(string s1, string s2);

int main(){
	cout << boolalpha << isAnagram("silent", "listen") << endl
		<< isAnagram("garden", "ranged") << endl
		<< isAnagram("split", "lisp") << endl;
	return 0;
}

/* isAnagram() --------------------------------
   returns true iff s1 and s2 are anagrams
*/
bool isAnagram(string s1, string s2){
	string new_s1 = s1, new_s2 = s2;

	//diff. lengths? not anagrams
	if (new_s1.length() != new_s2.length()) 
		return false;

	//sort and compare
	sort(new_s1);
	sort(new_s2);

	//anagrams iff equal
	return (new_s1 == new_s2);
}

/* sort() --------------------------------------------
   sorts s into ascending lexicographic order, in situ
   Author: Y. Daniel Liang.
*/
void sort(string& s){
	for (int i = s.length() - 1; i >= 1; i--){
		// Find the maximum in the list[0..i]
		char currentMax = s[0];
		int currentMaxIndex = 0;

		for (int j = 1; j <= i; j++)    {
			if (currentMax < s[j]){
				currentMax = s[j];
				currentMaxIndex = j;
			}
		}

		// Swap list[i] with list[currentMaxIndex] if necessary;
		if (currentMaxIndex != i){
			s[currentMaxIndex] = s[i];
			s[i] = currentMax;
		}
	}

}