dense.cpp

/*
 * Copyright (C) 2004 Bryant Lee
 *
 * This file is part of FDense.
 *
 * FDense is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * FDense is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with FDense; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

/* Main function
 * FDense program takes as input N (shift size), k (shift period), the c.a.
 * rule f, and m.  It determines whether f is m-dense where m-dense means
 * that every word of length m appears in a jointly periodic point.  If it
 * is not m-dense, it lists the words that do not appear in jointly periodic
 * points.
 *
 * Written by: Bryant Lee
 * Date: 9/01/05
 */

#define USEARRAY 0
#define DEBUG 0

//Standard C++
#include <string.h>
#include <iostream>
#include <iomanip>
#include <fstream> //for file ops

//C
#include <stdlib.h> //for atoi
#include <math.h> //for pow

//STL
#include <vector>
#include <list>
#include <map>

//local
#include "StringOps.h"
#include "Comp.h"
#include "StorageKey.h"
#include "StorageVal.h"
#include "RecNode.h"

#include "GroupData.h"
#include "MList.h"

/*
 * Function definitions
 */
void convertPeriodList(const string &strInput, vector<int> &periodList);
void exhaustiveExp(unsigned int shiftSize, const vector<int> &periodList,
		   unsigned int density, Comp *comp,
		   list<MList> &recList, MList &unionList, string &prefix,
		   vector<string> &commandbuffer);
void exhaustiveExpTwoShift(unsigned int shiftSize,
			   const vector<int> &periodList, unsigned int density,
			   Comp *comp, list<MList> &recList, MList &unionList,
			   string &prefix, vector<string> &commandbuffer);
void clearStorageNodes(vector<StorageVal*> &table);
void clearRecList(list<RecNode*> &recList);

void output(unsigned int shiftSize, int density, string &prefix,
	    const vector<int> &periodList,
	    Comp * comp, list<MList> &recList, MList &unionList,
	    vector<string> &commandbuffer);
void groupoutput(int density, string &prefix, vector<string> &commandbuffer,
		 vector<GroupData> &groupdata);


void findDivisors(unsigned int x, vector<int> &divisorsList);

bool leastPeriod(byte *word, unsigned int currPeriod,
		 const vector<int> &divisorsList);
bool leastPeriod(unsigned int word, unsigned int currPeriod,
		 const vector<int> &divisorsList);
void makeMPrefixList(vector<bool> &m_table, MList &record, unsigned int shiftSize);

/*
 * GLOBAL variables
 */
int UINTSIZE = 32;

int VERBOSE = 0; //display non-appearing m-words for each individual K

//boolean that determines whether output is given after each completed experiment (after each K)
//or only at end
bool OUTPUT_AFTER_EACH = false;

//determine whether the output is in the "group" format or the normal format
bool GROUP = false;

//main
int main() {
  //book-keeping variables
  unsigned int shiftSize; //# symbols in shift
  string prefix; //prefix for output files
  string strInput, strInput2, strInput3; //temp variables
  string outoption; //output after each or at end

  vector<int> periodList; //list of periods
  unsigned int i = 0, temp; //counter

  //results variables
  list<MList> recList; //list of prefixes not seen, this is per K value
  MList unionList = MList(0); //list of prefixes not seen, over all K values

  //computation variables
  Comp *comp = NULL; //composition to apply
  unsigned int density;

  //hold the command strings
  vector<string> commandbuffer;
  int commandbufferit;

  //storage for the "group" option
  vector<GroupData> groupdata;
  unsigned int groupdatait;

  //grab all input from cin and put in an array of strings
  while(!cin.eof()) {
    std::getline(cin, strInput);
    commandbuffer.push_back(strInput);
  }

  commandbufferit = 0;

  //get "output after each" or "output at end"
  outoption = commandbuffer[commandbufferit++];
  trim(outoption);
  transform(outoption.begin(), outoption.end(), outoption.begin(), tolower);

  if(outoption == "output after each") {
    OUTPUT_AFTER_EACH = true;
  }
  else if(outoption == "output at end") {
    OUTPUT_AFTER_EACH = false;
  }
  else {
    cout << "Error on line 1: invalid value for output mode\n";
    goto cleanup;
  }

  //get "group" or "no group"
  strInput = commandbuffer[commandbufferit++];
  trim(strInput);
  transform(strInput.begin(), strInput.end(), strInput.begin(), tolower);
  
  if(strInput == "group") {
    GROUP = true;
  }
  else if(strInput == "no group") {
    GROUP = false;
  }
  else {
    cout << "Error on line 2: invalid value for group mode\n";
    goto cleanup;
  }

  //get filename prefix
  prefix = commandbuffer[commandbufferit++];
  trim(prefix);

  //get N, the number of symbols in the full shift
  strInput = commandbuffer[commandbufferit++];
  trim(strInput);
  shiftSize = atoi(strInput.c_str());

  //get set of K, the periodicities to be tested
  strInput = commandbuffer[commandbufferit++];
  convertPeriodList(strInput, periodList);

  //get m, to check for m-dense
  strInput = commandbuffer[commandbufferit++];
  trim(strInput);
  density = atoi(strInput.c_str());

  //Allocate composition object
  comp = new Comp(shiftSize);

  //get "Begin Definitions"
  strInput = commandbuffer[commandbufferit++];

  //make it lowercase
  trim(strInput);
  transform(strInput.begin(), strInput.end(), strInput.begin(), tolower);
  
  if(strInput.compare("begin definitions") != 0) {
    cout << "ERROR: Expecting \"BEGIN DEFINITIONS\"\n";
    goto cleanup;
  }

  //read definitions
  while(1) {
    strInput = commandbuffer[commandbufferit++];

    //strInput2 is lowercased and trimmed
    strInput2.resize(strInput.length());
    transform(strInput.begin(), strInput.end(), strInput2.begin(), tolower);
    trim(strInput2);

    //strInput3 is lowercased and NOT TRIMMED
    strInput3.resize(strInput.length());
    transform(strInput.begin(), strInput.end(), strInput3.begin(), tolower);

    if(strInput2 == "" || (strInput2[0] == '/' && strInput2[1] == '/')) {
      //ignore blank lines and allow comment out
    }
    else if(strInput2 == "begin commands") {
      break; //BREAK
    }
    else {
      i = 0;

      while(i < strInput.length()) {
	if(strInput[i] == '=') {
	  break;
	}

	i++;
      }

      if(strInput2[0] == 'o' && strInput2[1] == 'p' && strInput2[2] == 't') {
	temp = strInput3.find("opt");
	temp += 3;

	comp->addFunc(strInput.substr(i+1, strInput.length() - (i+1)),
		      strInput.substr(temp, i-temp), true);
      }
      else {
	comp->addFunc(strInput.substr(i+1, strInput.length() - (i+1)),
		      strInput.substr(0,i), false);
      }
    }
  }

  //read all the valid commands and store in groupdata array
  while(commandbufferit < (int)commandbuffer.size()) {
    strInput = commandbuffer[commandbufferit++];
    trim(strInput);

    //ignore blank lines and allow comment out with "//"
    if(strInput != "" && !(strInput[0] == '/' && strInput[1] == '/')) {
      GroupData gd;
      
      gd.name = strInput;
      groupdata.push_back(gd);
    }
  }

  //iterate and execute commands
  for(groupdatait = 0; groupdatait < groupdata.size(); groupdatait++) {
    strInput = groupdata[groupdatait].name;

    //set composition
    if(!comp->setComposition(strInput)) {
      cout << "ERROR: Command \"" << strInput
	   << "\" references undefined function\n";
      goto cleanup;
    }

    int maxshiftperiod = 0;
    for(i = 0; i < periodList.size(); i++)
      maxshiftperiod = (maxshiftperiod < periodList[i] ?
			periodList[i] : maxshiftperiod);
    
    //do experiment
    if(shiftSize == 2
       && sizeof(unsigned int) == 4
       && !USEARRAY
       && maxshiftperiod <= 32) //if shift period goes > 32 then must use array representation
      exhaustiveExpTwoShift(shiftSize, periodList, density, comp, recList,
			    unionList, prefix, commandbuffer);
    else
      exhaustiveExp(shiftSize, periodList, density, comp, recList, unionList, prefix, commandbuffer);
    
    if(!OUTPUT_AFTER_EACH)
      output(shiftSize, density, prefix, periodList, comp,
	     recList, unionList, commandbuffer);
    
    groupdata[groupdatait].recList = recList;
    groupdata[groupdatait].unionList = unionList;
    groupdata[groupdatait].pending = false;

    //clear list of prefixes
    recList.clear();

    if(OUTPUT_AFTER_EACH) {
      groupoutput(density, prefix, commandbuffer, groupdata);
    }
  }
  
  //Do the group output (assuming output at end)
  if(!OUTPUT_AFTER_EACH) {
    groupoutput(density, prefix, commandbuffer, groupdata);
  }

  //cleanup and exit
  cleanup:
  
  //delete composition (and the functions in the Comp object's storage)
  delete comp;

  return 0;
}

/*
 * Group output
 */

void groupoutput(int density, string &prefix, vector<string> &commandbuffer,
		 vector<GroupData> &groupdata) {
  int commandbufferit;
  int groupdatait;

  if(GROUP) {
    ofstream fout;
    string fname = prefix + "group.txt";
    fout.open(fname.c_str(), ios::trunc | ios::out);

    if(!fout.is_open()) {
      cout << "ERROR: could not create file " << fname << "\n";
    }

    fout << "FDense 3.67\n\n";
  
    //copy of the input
    fout << "INPUT\n";
    fout << "--------------------\n";
    for(commandbufferit = 0; commandbufferit < (int)commandbuffer.size(); commandbufferit++) {
      string test;
      test = commandbuffer[commandbufferit];
      trim(test);
      if(test != "") {
	fout << commandbuffer[commandbufferit] << "\n";
      }
    }
    fout << "--------------------\n";
    fout << "\n";
  
    fout << "For m = " << density << " the following maps were found to have m-dense jointly periodic points of (not least) shift period k, "
	 << "for the following k:" << "\n";
    fout << "\n";

    for(groupdatait = 0; groupdatait < (int)groupdata.size(); groupdatait++) {
      bool none = true;

      fout << "Map: " << groupdata[groupdatait].name << "\n";
      fout << "----" << "\n";
      
      if(groupdata[groupdatait].pending) {
	fout << "PENDING" << "\n";
      }
      else {
	list<MList>::const_iterator it;
	for(it = groupdata[groupdatait].recList.begin(); it != groupdata[groupdatait].recList.end(); it++) {
	  if((*(it->List.begin())).compare("m-dense") == 0) {
	    fout << it->currPeriod << "\n";
	    none = false;
	  }
	}

	if(none) {
	  fout << "none" << "\n";
	}
      }

      fout << "\n";
    }

    fout.close();
  }
}


/*
 * Full output
 */

void output(unsigned int shiftSize, int density, string &prefix,
	    const vector<int> &periodList, Comp * comp, list<MList> &recList,
	    MList &unionList, vector<string> &commandbuffer) { 
  list<MList>::const_iterator it;
  //unsigned int i;
  unsigned int commandbufferit;

  if(!GROUP) {

    //output
    ofstream fout;
    string fname = prefix + comp->returnName() + ".txt";
    fout.open(fname.c_str(), ios::trunc | ios::out);

    if(!fout.is_open()) {
      cout << "ERROR: could not create file " << fname << "\n";
      return;
    }

    //HEADER
    fout << "FDense 3.67\n";

    /*
    fout << "N = " << shiftSize << "\n";
    fout << "K = ";
    for(i = 0; i < periodList.size(); i++) {
      fout << periodList[i];
      if(i != periodList.size() - 1)
	fout << ",";
    }
    fout << "\n";
    fout << "m = " << density;
    fout << "\n";
    */

    fout << "\n";

    //copy of the input
    fout << "INPUT\n";
    fout << "--------------------\n";
    for(commandbufferit = 0; commandbufferit < commandbuffer.size(); commandbufferit++) {
      string test;
      test = commandbuffer[commandbufferit];
      trim(test);
      if(test != "") {
	fout << commandbuffer[commandbufferit] << "\n";
      }
    }
    fout << "--------------------\n";
    fout << "\n";

    //fill on right side, show in fixed notation
    fout << setiosflags(ios::left | ios::fixed);

    fout << "COMMAND:\n";
    fout << comp->returnName() << "\n";
    fout << "WITH DEFINITIONS:\n";
    comp->printDefinitions(fout);
    fout << "\n";

    fout << "Outcomes Summary\n";
    for(it = recList.begin(); it != recList.end(); it++) {
      fout << "K=" << it->currPeriod << " ";
      if(it->pending) {
	fout << "PENDING";
      }
      else {
	if((*(it->List.begin())).compare("m-dense") == 0) {
	  fout << "m-dense";
	}
	else { 
	  fout << "not m-dense";
	}
      }
      fout << "\n";
    }
    fout << "\n";

    fout << "List of m-words not appearing in jointly periodic points\n\n";
  
    fout << "For union of all K (excluding those that are PENDING)\n\n";
    list<string>::const_iterator subit;
    for(subit = unionList.List.begin(); subit != unionList.List.end(); subit++) {
      fout << *subit << "\n";
    }
    fout << "\n";

    if(VERBOSE) {
      fout << "For each particular value of K\n\n";

      for(it = recList.begin(); it != recList.end(); it++) {
	fout << "K = " << it->currPeriod << "\n";

	if(it->pending) {
	  fout << "PENDING" << "\n";
	  fout << "\n";
	}
	else {
	  for(subit = it->List.begin(); subit != it->List.end(); subit++) {
	    fout << *subit << "\n";
	  }
	  fout << "\n";
	}
      }
    }
  
    //DONE
    fout.close();
  }
}

void exhaustiveExp(unsigned int shiftSize, const vector<int> &periodList,
		   unsigned int density, Comp *comp,
		   list<MList> &recList, MList &unionList, string &prefix,
		   vector<string> &commandbuffer) {
  unsigned int i = 0, j = 0; //k = 0; //counters
  unsigned int currPeriod;
  
  list<StorageKey> orbitList;
  list<StorageKey> periodicPoints;

  vector<int> table; //table for storing points, checking for intersections
  vector<bool> global_m_table(pow(shiftSize,density), false); //table for storing m-words not found in union over all K

  list<MList>::iterator recIterator;

  if(DEBUG)
    cout << "Arrays\n";

  //make a list of MList nodes, one per K value
  for(i = 0; i < periodList.size(); i++) {
    recList.push_back(MList(periodList[i]));
  }

  //initialize recIterator
  recIterator = recList.begin();

  for(i = 0; i < periodList.size(); i++) {
    currPeriod = periodList[i];
    byte itWord[currPeriod]; //iterating word

    MList *record = &(*recIterator);

    if(DEBUG)
      cout << "currPeriod = " << currPeriod << "\n";

    //set table size
    table.resize(pow(shiftSize,currPeriod), -2); //initialize to -2

    if(DEBUG)
      cout << "Allocated table\n";

    //zero the itWord
    for(j = 0; j < currPeriod; j++) {
      itWord[j] = 0;
    }
    
    while(true) {
      byte cWord[currPeriod]; //curr word
      byte output[currPeriod]; //helper word
      unsigned int period = 0, preperiod = 0;
      int rt;
      bool halt = false;

      while(halt != true &&
	    table[StorageKey(itWord,currPeriod).hash(shiftSize)] != -2)
	{
	  halt = iterateWord(itWord, currPeriod, shiftSize);
	}

      if(halt == true)
	break; //exit loop

      //Set current word
      copyWord(cWord, itWord, currPeriod);
      
      StorageKey sk1 = StorageKey(cWord, currPeriod);

      table[sk1.hash(shiftSize)] = 0;
     
      orbitList.push_back(sk1);

      //DEBUG
      //cout << "\n-- Start orbit --\n";
      //printArray(cWord, currPeriod);

      //Perform experiment
      j = 1;
      while(true) {
	comp->image(cWord, currPeriod, output);
	copyWord(cWord, output, currPeriod);

	//DEBUG
	//printArray(cWord, currPeriod);
	
	StorageKey sk2 = StorageKey(cWord, currPeriod);

	rt = table[sk2.hash(shiftSize)];
	if(rt != -2) {
	  break;
	}
	else {
	  table[sk2.hash(shiftSize)] = j;
	  orbitList.push_back(sk2);
	}
	
	j++;
      }

      if(rt == -1) {
	//returned to a point we've seen
	//none of these points can be periodic

	list<StorageKey>::iterator it;
	for(it = orbitList.begin(); it != orbitList.end(); it++) {
	  table[it->hash(shiftSize)] = -1;
	}
      }
      else {
	//we circled back to an active point
	period = j - rt;
	preperiod = rt;
	
	list<StorageKey>::iterator it;
	for(it = orbitList.begin(); it != orbitList.end(); it++) {
	  table[it->hash(shiftSize)] = -1; //mark as seen

	  if(preperiod > 0) {
	    preperiod--;
	  }
	  else {
	    periodicPoints.push_back(*it);
	  }
	}
      }

      //cout << "Clearing list\n";
      orbitList.clear();
    }

    //cout << "Clearing table\n";
    table.clear();

    //DEBUG
    /*
    {
      cout << "\n\nPeriodic points\n";
      list<StorageKey>::iterator it;
      for(it = periodicPoints.begin(); it != periodicPoints.end(); it++) {
	printArray(it->word, currPeriod);
      } 
    }
    */
    //DEBUG

    //DEBUG: make a fake point for testing
    /*
    periodicPoints.clear();
    byte t_arr[7];
    t_arr[0] = 1;
    t_arr[1] = 2;
    t_arr[2] = 0;
    t_arr[3] = 1;
    t_arr[4] = 1;
    t_arr[5] = 1;
    t_arr[6] = 1;
    periodicPoints.push_back(StorageKey(t_arr, 7));
    */
    //DEBUG

    //now cross off all m_words that do not exist in periodic point

    vector<bool> m_table(pow(shiftSize,density), false); //table of all m_words (for this particular K)
    byte m_word[density];
    StorageKey hasher(m_word, density);
    unsigned int location;

    list<StorageKey>::iterator it;
    for(it = periodicPoints.begin(); it != periodicPoints.end(); it++) {

      for(location = 0; location < currPeriod; location++) {

	//read the word
	for(j = 0; j < density; j++) {
	  hasher.word[j] = it->word[(j + location) % currPeriod];
	}

	//MAKE SURE TO USE hash_baseB SO THEY HASH TO THE RIGHT PLACE
	m_table[hasher.hash_baseB(shiftSize)] = true; //for this particular K
	global_m_table[hasher.hash_baseB(shiftSize)] = true; //for all K
      }
    }

    makeMPrefixList(m_table, (*record), shiftSize);

    unionList.List.clear(); //clear the list, it will be reset from the complete global table that has all the info
    makeMPrefixList(global_m_table, unionList, shiftSize);

    //clear periodicpoints list
    periodicPoints.clear();

    record->pending = false;
    
    //advance recIterator to next in list
    recIterator++;

    if(OUTPUT_AFTER_EACH) {
      output(shiftSize, density, prefix, periodList, comp, recList, unionList,
	     commandbuffer);
    }
  }
}

void makeMPrefixList(vector<bool> &m_table, MList &record, unsigned int shiftSize) {
  unsigned int j; //counter

  //DEBUG: make a fake table for testing
  /*
    for(j = 0; j < m_table.size(); j++)
    m_table[j] = false;
    
    for(j = 0; j <= 1; j++) {
    m_table[j] = true;
    }
    for(j = 12; j <= 27; j++) {
    m_table[j] = true;
    }
    for(j = 52; j < m_table.size(); j++) {
    m_table[j] = true;
    }
  */
  //DEBUG

  //DEBUG: print the m_table
  /*
    cout <<"\n\nm_table\n";
    for(j = 0; j < m_table.size(); j++) {
    if(m_table[j]) {
    unsigned int t;
    for(t = m_table.size() / shiftSize; t >=  1; t /= shiftSize) {
    cout << (j / t) % shiftSize;
    if(t > 1)
    cout << ",";
    }
    cout << "\n";
    }
    }
  */
  //DEBUG

  //now list the m words lexicographically with truncate
  unsigned int count_true = 0; //count true's, lets us know if table full
  for(j = 0; j < m_table.size(); j++) {
    if(!m_table[j]) {
      string m_prefix = "";

      if(j % shiftSize == 0) { //has a zero at lsb so this might be cut to a prefix
	//t = shiftSize ^ (numzeros on right in j in base shiftsize)
	unsigned int t;
	for(t = shiftSize; (j / t) % shiftSize == 0
	      && t < m_table.size(); t *= shiftSize) {
	}

	//count is how many adjacent elements are false (counting this one)
	unsigned int count;
	for(count = 1; count < t && !m_table[j + count]; count++) {
	}

	//s is the largest power of shiftsize that is <= count
	unsigned int s;
	for(s = shiftSize; s <= count; s *= shiftSize) {
	}
	s /= shiftSize; //adjust since the for loop goes 1 further
	  
	int spacing = 0; //count up to four, then add a space
	  
	//create the correct prefix
	for(t = m_table.size() / shiftSize; t >= 1; t /= shiftSize) {
	  char temp_c[80];
	    
	  if(t >= s) {
	    sprintf(temp_c, "%d", (j / t) % shiftSize);
	    m_prefix += string(temp_c);
	  }
	  else
	    m_prefix += "-";
	    
	  if(spacing % 4 == 3) //on every fourth char, add a space
	    m_prefix += " ";
	    
	  spacing++;
	}
	  
	// j JUMPS s SPACES AHEAD because these s elements constitute
	// one prefix, but at the end of the loop j increments 1 more,
	// so we need to increment by s - 1
	j += (s - 1);
	  
      }
      else { //not a prefix
	unsigned int t;

	int spacing = 0;

	for(t = m_table.size() / shiftSize; t >= 1; t /= shiftSize) {
	  char temp_c[80];

	  sprintf(temp_c, "%d", (j / t) % shiftSize);
	  m_prefix += string(temp_c);
	   
	  if(spacing % 4 == 3)
	    m_prefix += " ";

	  spacing++;
	}
      }
	
      //push back a prefix of non-appearing word
      record.List.push_back(m_prefix);
    }
    else {
      count_true++;

      //push back m-dense
      if(count_true == m_table.size()) {
	record.List.push_back("m-dense");
      }
    }
  }
}

void exhaustiveExpTwoShift(unsigned int shiftSize,
			   const vector<int> &periodList,
			   unsigned int density,
			   Comp *comp, list<MList> &recList, MList &unionList,
			   string &prefix, vector<string> &commandbuffer) {
  unsigned int i = 0, j = 0; //k = 0; //counters
  unsigned int currPeriod, numTrials;
  
  list<unsigned int> orbitList;
  list<unsigned int> periodicPoints;

  vector<int> table; //table for storing points, checking for intersections
  vector<bool> global_m_table(pow(shiftSize,density), false); //table for storing m-words not found in union over all K

  list<MList>::iterator recIterator;

  if(DEBUG)
    cout << "Special case 2-shift\n";

  //make a list of MList nodes, one per K value
  for(i = 0; i < periodList.size(); i++) {
    recList.push_back(MList(periodList[i]));
  }

  //initialize recIterator
  recIterator = recList.begin();

  for(i = 0; i < periodList.size(); i++) {
    currPeriod = periodList[i];
    unsigned int itWord = 0; //iterating word

    MList *record = &(*recIterator);
    
    numTrials = (int) pow(2, currPeriod);
    
    table.resize(numTrials, -2);

    while(true) {
      unsigned int cWord = 0; //curr word
      unsigned int output = 0; //helper word
      unsigned int period = 0, preperiod = 0;
      int rt;

      while(itWord != numTrials &&
	    table[itWord] != -2) {
	itWord++;
      }

      if(itWord == numTrials)
	break; //exit loop

      //Set current word
      cWord = itWord;

      table[cWord] = 0;
      orbitList.push_back(cWord);

      //DEBUG
      //cout << "-- start orbit --\n";
      //printUInt(cWord, currPeriod);

      //Perform experiment
      j = 1;
      while(true) {
	comp->image(&cWord, currPeriod, &output, 1);

	cWord = output;

	//DEBUG
	//printUInt(cWord, currPeriod);
	
	rt = table[cWord];
	if(rt != -2) {
	  break;
	}
	else {
	  table[cWord] = j;
	  orbitList.push_back(cWord);
	}
	
	j++;
      }

      //DEBUG
      //cout << "-- end orbit --\n";

      if(rt == -1) {
	//returned to a point we've seen
	//none of these points can be periodic

	list<unsigned int>::iterator it;
	for(it = orbitList.begin(); it != orbitList.end(); it++) {
	  table[*it] = -1;
	}
      }
      else {
	//we circled back to an active point
	period = j - rt;
	preperiod = rt;
	
	list<unsigned int>::iterator it;
	for(it = orbitList.begin(); it != orbitList.end(); it++) {
	  table[*it] = -1;

	  if(preperiod > 0) {
	    preperiod--;
	  }
	  else {
	    periodicPoints.push_back(*it);
	  }
	}
      }

      //cout << "Clearing list\n";
      orbitList.clear();
    }

    //cout << "Clearing table\n";
    table.clear();

    //DEBUG
    /*
    {
      cout << "\n\nPeriodic points\n";
      list<unsigned int>::iterator it;
      for(it = periodicPoints.begin(); it != periodicPoints.end(); it++) {
	printUInt(*it, currPeriod);
      } 
    }
    */
    //DEBUG

    //DEBUG: make up the periodicpoint
    /*
    periodicPoints.clear();
    periodicPoints.push_back(23);
    */
    //DEBUG

    //now cross off all m_words that exist in periodic point

    vector<bool> m_table(pow(2,density), false); //table of all m_words
    byte m_word[density];
    StorageKey hasher(m_word, density);
    unsigned int location;

    list<unsigned int>::iterator it;
    for(it = periodicPoints.begin(); it != periodicPoints.end(); it++) {

      for(location = 0; location < currPeriod; location++) {

	//read the word
	for(j = 0; j < density; j++) {
	  int index = (j + location) % currPeriod;

	  hasher.word[j] = (*it & (1 << index)) >> index;
	}

	//MAKE SURE TO USE hash_baseB SO THEY HASH TO THE RIGHT PLACE
	m_table[hasher.hash_baseB(2)] = true; //for this K
	global_m_table[hasher.hash_baseB(2)] = true; //for union of K
      }
    }

    makeMPrefixList(m_table, (*record), shiftSize);
    
    unionList.List.clear(); //clear the list, it will be reset from the complete global table that has all the info
    makeMPrefixList(global_m_table, unionList, shiftSize);

    //clear periodicPoints
    periodicPoints.clear();

    record->pending = false;
    //advance recIterator to next in list
    recIterator++;

    if(OUTPUT_AFTER_EACH) {
      output(shiftSize, density, prefix, periodList, comp, recList, unionList,
	     commandbuffer);
    }
  }
}

void convertPeriodList(const string &strInput,
		       vector<int> &periodList) {
  vector<string> strList; //all terms
  vector<string> subList; //vector representation of an "[a,b]" term
  unsigned int strListLength = 0, i = 0;

  split(strInput,';', strList);
  strListLength = strList.size();

  for(i = 0; i < strListLength; i++) {
    string *temp = &(strList[i]);

    trim(*temp);

    if((*temp)[0] == '[') {
      int j, low, high;

      temp->erase(0,1); //remove '['
      temp->erase(temp->length() - 1, 1); //remove ']'
      
      split(*temp, ',', subList);
      
      trim(subList[0]);
      trim(subList[1]);
      
      low = atoi(subList[0].c_str());
      high = atoi(subList[1].c_str());
      
      for(j = low; j <= high; j++) {
	periodList.push_back(j);
      }

      subList.clear();
    }
    else {
      periodList.push_back(atoi(temp->c_str()));
    }
  }
}

/*
 * Delete the nodes pointed to by ptrs in recList
 */
void clearRecList(list<RecNode*> &recList) {
  list<RecNode*>::iterator it;
  
  for(it = recList.begin(); it != recList.end(); it++) {
    delete (*it);
  }
}

/*
 * Delete the nodes pointed to by the values in the table
 */
void clearStorageNodes(vector<StorageVal*> &table) {
  vector<StorageVal*>::iterator it;

  for(it = table.begin(); it != table.end(); it++) {
    delete (*it);
  }
}

/*
 * Find divisors of X, excluding X itself
 */
void findDivisors(unsigned int x, vector<int> &divisorsList) {
  unsigned int i = 2;
  unsigned int halfX = x/2;

  divisorsList.clear();

  if(x > 1) {
    divisorsList.push_back(1);
  }

  for(i = 2; i <= halfX; i++) {
    if(x % i == 0) {
      divisorsList.push_back(i);
    }
  }
}

/*
 * returns true if this word has least period p
 */
bool leastPeriod(byte *word, unsigned int currPeriod,
		 const vector<int> &divisorsList) {
  bool result = false;
  unsigned int i, j, k;

  if(currPeriod == 1)
    return true;
  
  //for every divisor d
  for(i = 0; i < divisorsList.size(); i++) {
    unsigned int d = divisorsList[i];

    result = false;

    //check in chunks of length d
    for(j = 0; j < currPeriod; j+= d) {
      //check that this chunk is same as other chunks
      for(k = 0; k < d; k++) {
	if(word[k + j] != word[k]) {
	  result = true;
	  break;
	}
      }

      if(result == true)
	break;
    }

    if(result == false)
      break;
  }
  
  return result;
}

/*
 * returns true if this word has least period p
 */
bool leastPeriod(unsigned int word, unsigned int currPeriod,
		 const vector<int> &divisorsList) {
  bool result = false;
  unsigned int i, j, k;
  
  if(currPeriod == 1)
    return true;

  //for every divisor d
  for(i = 0; i < divisorsList.size(); i++) {
    unsigned int d = divisorsList[i];

    result = false;

    //check in chunks of length d
    for(j = 0; j < currPeriod; j+= d) {
      //check that this chunk is same as other chunks
      for(k = 0; k < d; k++) {
	if(((word >> (k + j)) & 1) != ((word >> k) & 1)) {
	  result = true;
	  break;
	}
      }

      if(result == true)
	break;
    }

    if(result == false)
      break;
  }
  
  return result;
}