root/ggpa/Sentence.cpp

/*
 * Sentence.cpp
 * Implementation of Sentence class
 */

#include "Sentence.h"
#include "SentenceStructure.h"
#include <vector>
#include <iostream>
#include <string>
using namespace std;


/*
 * Constructor for Sentence
 * Parameters:  theValues - a vector of values for the Sentence
 *              theStructure - a pointer to a SentenceStructure
 * Return type: none
 * Sets the values of the sentence equal to a copy of theValues,
 * checking that the values are all in the SentenceStructure.
 */
Sentence::Sentence(vector<string> theValues, SentenceStructure* theStructure) {
    //cout << "Constructor" << endl;
    if (theStructure == NULL) {
        cerr << "Structure is NULL" << endl;
        exit(1);
    }
    this->structure = theStructure;

    // verify the values
    if (theValues.size() != structure->getNumParameters()) {
        cerr << "Incorrect size for theValues vector: should be "
             << structure->getNumParameters() << endl;
    }
    for (unsigned int i = 0; i < theValues.size(); i++) {
        if (!isVariable(theValues[i]) && 
            structure->getValueIndex(i, theValues[i]) < 0) {
            cerr << "Invalid value \"" << theValues[i] << "\" at index " 
                 << i << endl;
            exit(1);
        }
    }
    this->values = theValues;
}

/*
 * Destructor for Sentence class
 */
Sentence::~Sentence() {
    clearDependencies(true);
}

/*
 * operator[]
 * Parameters: index - an int representing the value that we wish to 
 *                      retrieve
 * Return type: A const reference to a string
 * Returns the value at the index. This should be used to access the 
 * values in a Sentence.
 */
const string& Sentence::operator[](int index) const {
    return values[index];
}

/*
 * getNumValues
 * No parameters
 * Return type: int
 * Returns the number of values for this sentence.
 */
unsigned int Sentence::getNumValues() const {
    return values.size();
}

/*
 * getName
 * No parameters
 * Return type: string
 * Returns the name of this sentence (from its SentenceStructure)
 */
string Sentence::getName() const {
    return structure->getName();
}


/*
 * addAndDependency
 * Parameters:  dependency: a Sentence
 *              negated:  a bool, true if the dependency is negative
 * Return value: none
 * Adds the dependency to the dependency list
 */
void Sentence::addAndDependency(Sentence* dependency, bool negated) {
    vector<Sentence*> temp(1);
    temp[0] = dependency;
    dependencies.push_back(temp);
    dependencyFlags.push_back(negated);
}

/*
 * addOrDependency
 * Parameters: theSentences: a vector of Sentences to be ORed
 *             negated: a bool, true if the dependencyis negative
 * Adds the OR dependency to the dependency list
 */
void Sentence::addOrDependency(const vector<Sentence*>& dependency, 
                               bool negated) {
    dependencies.push_back(dependency);
    dependencyFlags.push_back(negated);

}

/*
 * getDependencies
 * No parameters
 * Return type: a const reference to a vector of vectors of sentences
 * Returns the dependency list for this sentence.
 */
const vector<vector<Sentence*> >& Sentence::getDependencies() const {
    return this->dependencies;
}

/*
 * isDependencyNegated
 * Parameters: index - the index of the dependency in the dependency list
 * Return type: bool
 * Returns true if the dependency is negated, and false otherwise
 */
bool Sentence::isDependencyNegated(int index) const {
    if (index >=0 && (unsigned int)index < dependencyFlags.size()) {
        return dependencyFlags[index];
    } else {
        cerr << "Index out of bounds" << endl;
        exit(1);
    }
}

/*
 * getIndex
 * No parameters
 * Return type: int
 * Returns the index of this Sentence in the State object.  If this sentence
 * has variables, then the function will return -1.  In this case, you 
 * should call getAtomicSentences and then do getIndex on each of those.
 */
int Sentence::getIndex() const {
    //cout << "Get Index" << endl;
    int base = structure->getOffset();

    // calculate the offset using the values vector as a variable length 
    // integer
    int offset = 0;
    int start = values.size()-1, stop = -1, step = -1;
    if (ENDIAN == BIG_ENDIAN) {
        stop = values.size();
        start = 0;
        step = 1;
    }
    for (int i = start; i != stop; i += step) {
        // if it is a variable, return -1
        if (isVariable(values[i])) {
            //cout << "Value is a variable: " << values[i] << endl;
            return -1;
        }
        
        int numValues = structure->getValues(i).size();
        int index = structure->getValueIndex(i, values[i]);

        if (index < 0) {
            cerr << "Value " << i << " = '" << values[i] << "' not found" << endl;
            //int num = 1/0;
            exit(1);
        }
        
        // update the number:
        offset *= numValues;
        offset += index;
    }
    //cout << "End. Base = " << base << ", Offset = " << offset << endl;
    return base + offset;
}

/*
 * getAtomicSentences
 * Parameters: none
 * Return type: a vector of sentences
 * Returns all possible atomic sentences that can be derived from this 
 * Sentence.  These sentences will be returned in increasing order of 
 * index within State.
 */
vector<Sentence*> Sentence::getAtomicSentences() const {
    vector<Sentence*>* sentences = new vector<Sentence*>();
    int numParameters = structure->getNumParameters();
    vector<vector<string> > possibilities;
    vector<string> start(numParameters, "");
    possibilities.push_back(start);

    int startPos = numParameters - 1, stopPos = 0, step = -1;
    for (int i = startPos; i >= stopPos; i += step) {

        if (isVariable(values[i])) {
            vector<vector<string> > newPossibilities;
            vector<string> posValues = structure->getValues(i);
            
            if (ENDIAN == LITTLE_ENDIAN) {
                for (unsigned int j = 0; j < possibilities.size(); j++) {
                    for (unsigned int k = 0; k < posValues.size(); k++) {
                        vector<string> cur;
                        cur = possibilities[j];
                        cur[i] = posValues[k];
                        newPossibilities.push_back(cur);
                    }
                }
            }
            else {  // BIG_ENDIAN
                for (unsigned int k = 0; k < posValues.size(); k++) {
                    for (unsigned int j = 0; j < possibilities.size(); j++) {
                        vector<string> cur;
                        cur = possibilities[j];
                        cur[i] = posValues[k];
                        newPossibilities.push_back(cur);
                    }
                }
            }
            possibilities = newPossibilities;

        } else {
            for (unsigned int j = 0; j < possibilities.size(); j++) {
                possibilities[j][i] = values[i];
            }
        }
    }

    for (unsigned int i = 0; i < possibilities.size(); i++) {
        //cout << "Creating sentence " << i+1 << " of " << possibilities.size()
        //     << endl;
        sentences->push_back(new Sentence(possibilities[i], structure));
    }
    return *sentences;
}

/*
 * getStructure
 * Parameters: none
 * Return type: a pointer to a SentenceStructure
 * Returns the SentenceStructure for this Sentence
 */
SentenceStructure* Sentence::getStructure() const {
    return this->structure;
}

/*
 * operator==
 * Parameters: s2 - another Sentence for comparison
 * Return type: bool
 * Returns true if the two sentences are equal, and false otherwise
 */
bool Sentence::operator==(const Sentence& s2) const {
    if (!(*(this->structure) == *(s2.structure))) {
        return false;
    }

    if (this->values.size() != s2.values.size()) {
        return false;
    }

    for (unsigned int i = 0; i < this->values.size(); i++) {
        if (this->values[i] != s2.values[i]) {
            return false;
        }
    }
    return true;
}


/**
 * enumerateWithBinding
 * Parameters: none
 * Return type: a vector of sentence*
 * This works similarly to getAtomicSentences, except that it also does
 * binding within the dependencies.
 */
vector<Sentence*> Sentence::enumerateWithBinding() const {
    map<string,string> valueMap;
    return enumerateWithBinding(valueMap);

/*
    vector<Sentence*> sentences = getAtomicSentences();

    for (unsigned int index = 0; index < sentences.size(); index++) {
        Sentence* sentence = sentences[index];
        sentence->dependencies = this->dependencies;

        // get the variable mappings at the base
        map<string, string> valueMap* = new map<string,string>();
        for (unsigned int attribute = 0; attribute < values.size(); 
             attribute++) {
            if (isVariable(values[attribute])) {
                (*valueMap)[values[attribute]] = (*sentence)[attribute];
            } 
        }

        for (unsigned int dependency = 0; dependency <= dependencies; 
             dependency++) {
            for (unsigned int num = 0; num < dependencies[dependency].size();
                 num++) {
                Sentence* component = dependencies[dependency][num];
                for (unsigned int variable = 0; 
                     variable < component->values.size(); variable++) {
                    value = component->values[variable];
                    if (isVariable(value)) {
                        if (valueMap.find(value) != valueMap.end()) {
                            component->values[variable] = valueMap[value];
                        } else {
                            // break apart the variable into multiple sentences
                        }
                    }
                }
            }
        }

        delete valueMap;
    }
*/
}



/*
 * enumerateWithBinding
 * Parameters: valueMap - a map of variables to values
 * Return type: vector of sentence pointers
 * Returns the set of sentences that can be generated from this sentence.
 * The supplied variable values will be used, but if no values exist,
 * we will branch on this value.
 */
vector<Sentence*> Sentence::enumerateWithBinding(map<string,string>& valueMap) const {
    vector<Sentence*> sentences;
    Sentence* thisSentence = new Sentence(*this);
    // assign all the variables that we can.
    for (unsigned int valueIndex = 0; valueIndex < values.size(); 
         valueIndex++) {
        string value = values[valueIndex];
        if (isVariable(value)) {
            if (valueMap.find(value) != valueMap.end()) {
                // the variable is defined, just assign the value
                (*thisSentence).values[valueIndex] = valueMap[value];
            }
        }
    }

    sentences = thisSentence->getAtomicSentences();
    map<string,string> valueMapCopy(valueMap);
    for (unsigned int sentenceIndex = 0; sentenceIndex < sentences.size();
         sentenceIndex++) {
        Sentence* sentence = sentences[sentenceIndex];
        
        // extend the valueMap
        valueMap = valueMapCopy;
        for (unsigned int valueIndex = 0; valueIndex < values.size();
             valueIndex++) {
            if (isVariable((*thisSentence)[valueIndex])) {
                valueMap[(*thisSentence)[valueIndex]] 
                    = (*sentence)[valueIndex];
            }
        }

        // process each sentence in the dependencies.
        
    }
    return sentences;
    
}


/**
 * getVariables
 * No parameters.
 * Return type: a map from variables to vectors of of their possible values
 * Searches through the sentence and its dependencies, and returns all
 * of the variables, along with their posible values
 */
map<string, vector<string> > Sentence::getVariables() const {
    map<string, vector<string> > variableMap;
    getVariables(variableMap);

    return variableMap;
}


/*
 * getVariables
 * Parameters: variableMap: a map where we should add the new variables
 * Return type: none
 * Adds the variables and their set of possible values to the variableMap
 */
void Sentence::getVariables(map<string, vector<string> >& variableMap) const {
    for (unsigned int valueIndex = 0; valueIndex < values.size(); 
         valueIndex++) {
        string value = values[valueIndex];
        if (isVariable(value)) {
            variableMap[value] = structure->getValues(valueIndex);
        }
    }
    
    for (unsigned int index = 0; index < dependencies.size(); index++) {
        vector<Sentence*> dependency = dependencies[index];
        for (unsigned int subIndex = 0; subIndex < dependency.size(); 
             subIndex++) {
            Sentence* component = dependency[subIndex];
            component->getVariables(variableMap);
        }
    }
    
    return;
}


/**
 * getAtomicSentence
 * Parameters: variableMap - a mapping of the variables
 * Return type: a new Sentence
 * Creates a new sentence with any variables mapped by the parameter map
 */
Sentence* Sentence::getAtomicSentence(map<string, string> variableMap) const {
    Sentence* atomicSentence = new Sentence(*this);

    for (unsigned int valueIndex = 0; 
         valueIndex < atomicSentence->values.size(); 
         valueIndex++) {
        string value = atomicSentence->values[valueIndex];
        if (isVariable(value)) {
            atomicSentence->values[valueIndex] = variableMap[value];
        }
    }

    for (unsigned int dependencyIndex = 0; 
         dependencyIndex < dependencies.size();
         dependencyIndex++) {
        vector<Sentence*> dependency = dependencies[dependencyIndex];
        for (unsigned int sentenceIndex = 0; 
             sentenceIndex < dependency.size();
             sentenceIndex++) {
            Sentence* sentence;
            sentence = dependency[sentenceIndex]->getAtomicSentence(variableMap);
            atomicSentence->dependencies[dependencyIndex][sentenceIndex] = sentence;
            // NOTE:  Do we need to delete the old sentence?
        }
    }

    return atomicSentence;
}


/*
 * clearDependencies
 * No parameters or return type.
 * Removes all of the dependencies
 */
void Sentence::clearDependencies(bool recursiveDelete) {
    if (recursiveDelete) {
        for (unsigned int dependencyIndex = 0; 
             dependencyIndex < dependencies.size();
             dependencyIndex++) {
            vector<Sentence*> dependency = dependencies[dependencyIndex];
            for (unsigned int subIndex = 0; subIndex < dependency.size(); 
                 subIndex++) {
                delete dependency[subIndex];
                dependency[subIndex] = NULL;
            }
        }
    }
    dependencies.clear();
}

/*
 * print
 * Parameters: output: a stream to output to.
 * No return type.
 * Prints the sentence to the given stream
 */
void Sentence::print(ostream& output, string indent) const {
    if (dependencies.size() == 0) {
        output << indent << "(" << structure->getName();
        for (unsigned int index = 0; index < values.size(); index++) {
            output << " " << values[index];
        }
        output << ")" << endl;
    } else {
        output << "(<= ";
        output << "(" << structure->getName();
        for (unsigned int index = 0; index < values.size(); index++) {
            output << " " << values[index];
        }
        output << endl;
        
        for (unsigned int index = 0; index < dependencies.size(); index++) {
            string curIndent = indent+"\t";
            vector<Sentence*> dependency = dependencies[index];
            if (isDependencyNegated(index)) {
                output << curIndent << "(not" << endl;
                curIndent = curIndent + "\t";
            }
            if (dependency.size() == 1) {
                dependency[0]->print(output, curIndent);
            } else {
                output << curIndent << "(or ";
                for (unsigned int subIndex = 0; subIndex < dependency.size();
                     subIndex++) {
                    output << endl;
                    dependency[subIndex]->print(output, curIndent +"\t");
                }
                output << ")" << endl;
            }
            if (isDependencyNegated(index)) {
                output << indent << "\t)" << endl;
            }
        }
        output << indent << "))";

    }
}


/*
 * mergeValues
 * No parameters or return type.
 * Merges possible values for variables in this sentence.
 */
void Sentence::mergeValues() {
    multimap<string, PossibleValues*> variableMap;
    mergeValues(variableMap);
    
}


/*
 * mergeValues
 * Parameters: variableMap:  a multimap from variables to their set of
 *                           possible values
 * Return type: none
 * Merges the sets of values for the variables
 */
void Sentence::mergeValues(multimap<string, PossibleValues*>& variableMap) {
    // first merge the current variables and add them to the map
    for (unsigned int index = 0; index < values.size(); index++) {
        string value = values[index];
        vector<string>* valueSet = structure->getValuesPointer(index);
        mergeValue(value, valueSet, variableMap);
    }

    // then perform the merge for all of the dependencies
    for (unsigned int index = 0; index < dependencies.size(); index++) {
        vector<Sentence*> dependency = dependencies[index];
        for (unsigned int subIndex = 0; subIndex < dependency.size();
             subIndex++) {
            dependency[subIndex]->mergeValues(variableMap);
        }
    }
        
}

/*
 * mergeValue
 * Parameters: value - the value to merge in
 *             valueSet - the set of values for that variable
 *             variableMap - the mapping from variable name to value set
 * Return type: none
 * Merges the value with the valueMap.
 */
void Sentence::mergeValue(string value, vector<string>* valueSet, 
                          multimap<string, PossibleValues*>& variableMap) {
    pair<multimap<string, PossibleValues*>::iterator, multimap<string, PossibleValues*>::iterator> range;
    multimap<string, PossibleValues*>::iterator equalItr;
    PossibleValues* possibleValues;
    if (isVariable(value)) {
        if (structure->getName() == DISTINCT_NAME) {
            possibleValues = new DistinctPossibleValues(valueSet);
        } else {
            possibleValues = new PossibleValues(valueSet);
            
        }
        range = variableMap.equal_range(value);
        for (equalItr = range.first; equalItr != range.second; 
             equalItr++) {
            possibleValues->merge(equalItr->second);
            equalItr->second->merge(possibleValues);
        }
        variableMap.insert(pair<string, PossibleValues*>(value, possibleValues));
    }
}


// functions for PossibleValues subclasses

Sentence::PossibleValues::PossibleValues(vector<string>* possibleValues) {
    values = possibleValues;
}

        
/*
 * merge
 * Parameters: otherValues: the values to add to the current
 * No return type
 * Adds the otherValues to these values, avoiding duplication.
 */
void Sentence::PossibleValues::merge(PossibleValues* otherValues) {
    vector<string>* addValues = otherValues->getValues();
    if (addValues == NULL) {
        return;
    }
    
    unsigned int thisSize = values->size();
    for (unsigned int index = 0; index < addValues->size(); index++) {
        string value = (*addValues)[index];
        bool found = false;
        for (unsigned int thisIndex = 0; thisIndex < thisSize;
             thisIndex++) {
            if ((*values)[thisIndex] == value) {
                found = true;
                break;
            }
        }
        if (!found) {
            values->push_back(value);
        }
    }
}

/*
 * getValues
 * no parameters
 * return type: vector<string>*
 * gets the values for this object.
 */
vector<string>* Sentence::PossibleValues::getValues() {
    return values;
}


Sentence::DistinctPossibleValues::DistinctPossibleValues(vector<string>* possibleValues) {
    values = possibleValues;
}

/*
 * getValues
 * no parameters
 * return type: vector<string>*
 * gets the values for this object.
 */
vector<string>* Sentence::DistinctPossibleValues::getValues() {
    return NULL;
}