////////////////////////////////////////
// movies.cpp
// 
// Jeremy Faller
//
// Copyright (c) 2008, Jeremy Faller
//
// ACO Implementation of Sling Blade Runner
// compile me with:
//  g++ -O3 movies.cpp -o aco
// run me with:
//  ./aco MOVIES.txt

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <map>
#include <list>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <functional>

using namespace std;

#define kALPHA_     static_cast<double>(0.9)
#define kBETA_      static_cast<double>(0.4)
#define kRHO_       static_cast<double>(0.3)
#define kNUMITERS_  (500)


////////////////////////////////////////
// Table to speed up pow calculations
class PowTable
{
    vector<float>   mValues;
    float           mExponent;
public:
    PowTable(float inExponent)
        : mValues(10000)
        , mExponent(inExponent)
    {
        for(unsigned i = 0; i < mValues.size(); ++i)
            mValues[i] = pow(static_cast<float>(i), mExponent);
    }
    
    float operator[](float inIndex) const
    {
        if (inIndex < 0)
            return mValues.front();
        if (inIndex > mValues.size())
            return mValues.back();
        return mValues[static_cast<int>(inIndex)];
    }
} gAlpha(kALPHA_), gBeta(kBETA_);

// Forward Dec'ls
typedef vector<string>  Words_t;


////////////////////////////////////////
// Do some edges match?
bool AreMoviesLinked(const Words_t &inOrigin, const Words_t &inDestination)
{
    // Walk backward
    // We don't check >=0 because if we do, we'd use the complete movie name
    for(int i = inOrigin.size() - 1; i >= 0; --i)
    {
        int numWordsToCheck = (inOrigin.size() - i);
        bool found = true;      
        
        // Check if we have more words we're looking at in origin then destination,
        // we can break, knowing that there's no match
        if (numWordsToCheck > inDestination.size())
            break;

        for(int j = 0; j < numWordsToCheck; ++j)
        {
            if (inDestination[j] != inOrigin[i + j])
            {
                found = false;
                break;
            }
        }
        if (found)
            return true;
    }
    return false;
}



////////////////////////////////////////
struct Movie
{
    typedef pair<Movie*, double>    Edge_t;
    typedef vector<Edge_t>          Edges_t;
protected:
    string      mName;
    Words_t     mWords;
    Edges_t     mEdges;
    unsigned    mIndex;
    bool        mIsLinked;
    bool        mIsVisited;
public:

    // Constructor
    Movie(const char *inName)
        : mName(inName)
        , mIsLinked(false)
        , mIsVisited(false)
    {
        // Get the individual words
        istringstream   stream(inName);
        while(stream)
        {
            string  word;
            stream >> word;
            if(word.length() > 0)
                mWords.push_back(word);
        }
    }
    
    
    // Find all links in the system
    void FindEdges(vector<Movie> &inMovies)
    {
        for(vector<Movie>::iterator i = inMovies.begin(); i != inMovies.end(); ++i)
        {
            // No edges to myself
            if (i->Name() == Name())
                continue;
                
            // Add Edges
            if(AreMoviesLinked(mWords, i->Words()))
                AddEdges(&(*i));
        }
        ResetPheremones();
    }
    

    // Add a link
    void AddEdges(Movie *inVertex)
    {
        mEdges.push_back(Edge_t(inVertex, 1));
        inVertex->IsLinked() = true;
    }
    
    
    
    // Fade the pheremones
    void FadePheromones()
    {
        for(Edges_t::iterator i = mEdges.begin(); i != mEdges.end(); ++i)
            i->second *= kRHO_;
    }
    
    
    // Reset all pheremone levels
    void ResetPheremones()
    {
        for(Edges_t::iterator i = mEdges.begin(); i != mEdges.end(); ++i)
            i->second = 1.0;
    }
    
    
    // Find the open edges on a node
    void FindOpenEdges(Edges_t &ioEdges)
    {
        for(Edges_t::const_iterator i = Edges().begin(); i != Edges().end(); ++i)
            if (i->first->IsVisited() == false)
                ioEdges.push_back(*i);
    }
    

    
    // Calculate the attractiveness of a node
    double CalcAttractiveness() const
    {
        double retVal = 0;
        for(Edges_t::const_iterator i = Edges().begin(); i != Edges().end(); ++i)
            if (i->first->IsVisited() == false)
                retVal += 1.0;
        return retVal;
    }


    
    // Find a probability from a given weight
    static float CalcProb(const Edge_t &inEdge)
    {
        double attractiveness = inEdge.first->CalcAttractiveness();
        return gAlpha[inEdge.second] + gBeta[attractiveness];
    }
    

    // Find the edge the correct edge given a set of edges
    static Edge_t CalcEdge(const Edges_t &inEdges)
    {
        float                   probSum = 0;
        float                   prob = rand() / static_cast<float>(RAND_MAX);
        Edges_t::const_iterator i;
        
        for(i = inEdges.begin(); i != inEdges.end(); ++i)
            probSum += CalcProb(*i);
        for(i = inEdges.begin(); i != inEdges.end(); ++i)
            if ((prob -= CalcProb(*i) / probSum) < 0)
                break;
        if (i == inEdges.end())
            return inEdges.back();
        return *i;
    }
    
    
    // Accessors
    const string&   Name() const        { return mName; }
    const Words_t&  Words() const       { return mWords; }
    unsigned        Index() const       { return mIndex; }
    unsigned&       Index()             { return mIndex; }
    unsigned        Degree() const      { return mEdges.size(); }
    bool            IsLinked() const    { return mIsLinked; }
    bool&           IsLinked()          { return mIsLinked; }
    bool            IsIsolated() const  { return !(mIsLinked || (Degree() != 0)); }
    const Edges_t&  Edges() const       { return mEdges; }
    Edges_t&        Edges()             { return mEdges; }
    bool            IsVisited() const   { return mIsVisited; }
    bool&           IsVisited()         { return mIsVisited; }
};



////////////////////////////////////////
struct Path : public list<Movie*>
{
    // Reset the node
    void Reset()
    {
        for(Path::iterator i = begin(); i != end(); ++i)
            (*i)->IsVisited() = false;
    }
    
    
    // Drop pheremones on the path
    void DropPheromones()
    {
        unsigned    theSize = size();
        iterator    pathIter = begin();
        for(unsigned i = 0; i < theSize - 1; ++i, ++pathIter)
        {
            Movie                       *nextMovie;
            Movie::Edges_t::iterator    j;

            // Get the next movie
            nextMovie = *(++pathIter);
            --pathIter;
            
            // Find the edge in the edge list
            for(j = (*pathIter)->Edges().begin(); j != (*pathIter)->Edges().end(); ++j)
                if (j->first == nextMovie)
                    break;

            // Update the pheremone
            j->second += theSize;
        }
    }
    
    
    // Find a path from a movie
    void FindPath(Movie *inMovie)
    {
        Movie::Edges_t      openEdges;
        
        // Mark the node as visited
        inMovie->IsVisited() = true;
        
        // Find all the open nodes
        inMovie->FindOpenEdges(openEdges);
    
        // If we've found a node, we need to add up the probabilities
        if (openEdges.size())
        {
            Movie::Edge_t   theEdge = Movie::CalcEdge(openEdges);
            this->FindPath(theEdge.first);
        }
    
        this->push_front(inMovie);  
    }
    
    
    // Comparison operator for sorting
    bool operator<(const Path &inPath) { return size() < inPath.size(); }
    bool operator>(const Path &inPath) { return size() > inPath.size(); }
};




////////////////////////////////////////
ostream&
operator<<(ostream &outStream, const Movie &inMovie)
{
    outStream << inMovie.Index() << ")\t" << inMovie.Name();
//  for(Movie::Edges_t::const_iterator i = inMovie.Edges().begin(); i != inMovie.Edges().end(); ++i)
//      outStream << "\n\t" << (*i)->Name() << flush;
    return outStream;
}


////////////////////////////////////////
ostream&
operator<<(ostream &outStream, const Movie *inMovie)
{
    return outStream << (*inMovie);
}


////////////////////////////////////////
ostream&
operator<<(ostream &outStream, const Path &inPath)
{
    outStream << inPath.size() << "\n";
    copy(inPath.begin(), inPath.end(), ostream_iterator<Movie*>(outStream, "\n"));
    return outStream;
}


////////////////////////////////////////
int
main(int argc, char **argv)
{
    vector<Movie>   movies;
    
    srand(time(0));
    
    // Check usage
    if (argc != 2)
    {
        cerr << "Usage: " << argv[0] << " [filename]" << endl;
        return -1;
    }
    
    // Open the input file
    ifstream    inputFile(argv[1]);
    if (!inputFile)
    {
        cerr << "Cannot open \"" << argv[1] << "\" for input" << endl;
        return -1;
    }
    
    // Read the Movies
    while(1)
    {
        char    c[4096];
        inputFile.getline(c, sizeof(c) - 1);
        if (inputFile.gcount() > 0)
            movies.push_back(Movie(c));
        if (!inputFile)
            break;
    }
    cout << "Read (" << movies.size() << ") Movies" << endl;

    // Find the links   
    cout << "Finding Edges" << endl;
    for(vector<Movie>::iterator i = movies.begin(); i != movies.end(); ++i)
        i->FindEdges(movies);
    cout << "Found Edges" << endl;

    // Setup the indices
    for(unsigned i = 0; i < movies.size(); ++i)
        movies[i].Index() = i;

    // Find a node
    Path        longestPath;
    for(unsigned k = 0; k < kNUMITERS_; ++k)
    {
        vector<Path>    antPaths;
        for(unsigned j = 0; j < movies.size(); ++j)
        {
            Path        path;
            unsigned    num;
            
            // Pick a movie that has links
            do { num = rand() % movies.size(); } while(movies[num].Degree() == 0);
            
            // Find the path
            path.FindPath(&movies[num]);
            
            // If we've already found this path, don't save it
            if (find(antPaths.begin(), antPaths.end(), path) != antPaths.end())
                continue;
                
            // Save the path (only save 30 of them).  Probably a better way to do this
            if (antPaths.size() == 0)
                antPaths.push_back(path);
            for(vector<Path>::iterator i = antPaths.begin(); i < antPaths.end(); ++i)
                if (path > *i)
                {
                    antPaths.insert(i, path);
                    if (antPaths.size() > 30)
                        antPaths.resize(30);
                    break;
                }

            // If it's the longest path we've seen, save it, and report it
            if (path.size() > longestPath.size())
            {
            	ostringstream	str;
            	str << path.size() << ".txt";
            	ofstream outFile(str.str().c_str());
                longestPath = path;
            	outFile << longestPath;
                cerr << k << ' ' << longestPath.size() << endl;
            }

            // Reset the path
            path.Reset();
        }
        
        // Fade the Pheremones
        for_each(movies.begin(), movies.end(), mem_fun_ref(&Movie::FadePheromones));

        // Drop Pheremones on the paths
        for_each(antPaths.begin(), antPaths.end(), mem_fun_ref(&Path::DropPheromones));
        longestPath.DropPheromones();
    

        // Forget all the ant paths
        antPaths.clear();
    }
    cout << longestPath;
    return 0;
}