// File:            permute.cpp
// ---------------------------------------------------------------------
//          Author: Russell Lowke,  lowke@fas.harvard.edu
//              TF: Francis Crick
//            Date: 7/25/2002
//      Assignment: Unit 6 Main programming exercises
//         Version: 1
//
//     Description: program reads in a string and employs recursive backtracking
//					to print all permutations of the characters in the string.
//
//         Methods:
//
//        int setBit() - bitwise set
//      int clearBit() - bitwise clear
//       bool getBit() - bitwise get
//       int nBitsON() - return the number of bits on
//  void printBitset() - print the bitset
//    void getString() - Get a string [str] of length MAXLEN
//        int getInt() - reads an integer from the keyboard
//      void permute() - print all permutations of the characters in str
//    void printWord() - omits printing words that have already been printed
//
//           Notes: printWord() is limited by   static char * wordLst[1000];
//

#include <iostream>
#include <iomanip>

const int MAXLEN = 31;  // 32 bit int bitset stores values from 0 to 31


//
// bitwise functions
//
int setBit(int bits, int n)
{
	return bits |= (1 << n);
}

int clearBit(int bits, int n)
{
	return bits &= ((1 << n) ^ 255);
}

bool getBit(int bits, int val)
{
	return (bits & (1 << val) );
}

//
// return the number of bits on
//
int nBitsON(int bits, int length)
{
	int n = 0;
	for(int i = 0; i < length; i++) {
		if ( getBit(bits, i) ) {
			n++;
		}
	}
	
	return n;
}

//
// print the bitset
//
void printBitset(int bits, int length)
{
	cout << "{ ";
	for (int i = 0; i < length; i++) {
		cout << getBit(bits, i) << " ";
	}
	cout << "}";
}


//
//  Get a string [str] of length MAXLEN
//
void getString(char * query, char * str, int length)
{
	cout << query;							// ask query
	
	cin >> ws;								// remove all the white spaces
	cin.getline(str, length);				// read characters until \n
}


//
//  reads an integer from the keyboard,
//  uses error checking to ensure value is between minValue and maxValue
//
int getInt(char askStr[], int minValue, int maxValue)
{
	int mVar;
	bool inputOK = false;
	
	while (! inputOK) { 
	
		cout << askStr;						// ask query
		cin >> mVar;						// get input
		
		if ( (mVar >= minValue && mVar <= maxValue) )
			inputOK = true;					// input OK, exit loop
		else {
			cout << "Bad input: please enter a value between "
			     << minValue << " and " << maxValue << endl;
			cin.clear();					// clear error [see  cin.fail();]
			cin.ignore(MAXLEN, '\n');		// empty buffer
		}
	}
	
	return mVar;
}

//
//  makes list of all words
//  omitting printing words that have already been printed
//
void printWord(char * str, int length, bool dump = false)
{
	// find factorial
	int maxWords = length;
	for (int i = 1; i < length; i++) {
		maxWords *= i;
	}
	
	// static char * wordLst = new char*[maxWords]
	static char * wordLst[1000];
	static int nWords;
		
	if (dump) {
		for (int i = 0; i < nWords; i++) {
			delete [] wordLst[i];
		}
	} else {

		bool found = false;
		
		// search list for value
		for(int i = 0; i < nWords; i++) {
			if ( strcmp(str, wordLst[i]) == 0 ) {
				found = true;
			}
		}

		if (! found) {
			wordLst[nWords] = new char[length];
			strcpy(wordLst[nWords], str);
			cout << str << endl;	// print it
			nWords++;
		}
	}
}

//
// print all permutations of the characters in str
//
void permute(char * str, int length, int bitset, char * nStr)
{
	// count 'on' bits to find depth
	int depth = nBitsON(bitset, length);
	
	if ( depth == length ) {	// if reached max depth
		// cout << nStr << endl;	// print it
		printWord(nStr, length);
	} else {
	
		// looking for 'off' bits
		for (int i = 0; i < length; i++) {
		
			if ( ! getBit(bitset, i) ) {
				
				// save char into nStr
				nStr[depth] = str[i];
				
				permute( str, length, setBit(bitset, i), nStr );
			}
		}
	}
}


int main()
{
	
	// intput string length
	int length = getInt("How many characters? ", 1, MAXLEN - 1);
	
	// dynamic memory
	char *str  = new char[length + 1];		
	char *nStr = new char[length + 1];
	
	// input string 
	getString("Enter the string: ", str, length + 1);
	
	// ensure '\0'(null) at end of nStr
	nStr[length] = '\0';
	
	permute(str, length, 0, nStr);
	
	// tell printword to free memory (not used)
	printWord(str, length, true);
	
	// free memory
	delete [] str;					
	delete [] nStr;
	
	exit (0);
}