#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <limits>                           //I used std::numeric_limits<int>::max()
#include "ics46goody.hpp"
#include "stopwatch.hpp"
#include "array_queue.hpp"
#include "heap_priority_queue.hpp"
#include "array_set.hpp"
#include "bst_map.hpp"


typedef ics::ArrayQueue<std::string>         WordQueue;
typedef ics::ArraySet<std::string>           FollowSet;
typedef ics::pair<WordQueue,FollowSet>       CorpusEntry;

bool queue_lt(const WordQueue& a, const WordQueue& b) {
    for (WordQueue::Iterator ac = a.begin(), bc= b.begin(); ac != a.end(); ++ac,++bc)
        if      (*ac < *bc) return true;
        else if (*ac > *bc) return false;
    return false;
}

bool CorpusEntry_gt(const CorpusEntry& a, const CorpusEntry& b) {
    return queue_lt(a.first,b.first); // reverse of lt for queues
}

typedef ics::HeapPriorityQueue<CorpusEntry,CorpusEntry_gt> CorpusPQ;     //Convenient to supply gt at construction
typedef ics::BSTMap<WordQueue,FollowSet,queue_lt>   Corpus;