#include <iostream>
#include <iterator>
#include <fstream>
#include <string>
#include <boost/date_time/gregorian/gregorian.hpp>

struct Log
{
    typedef boost::gregorian::date Date;
    Date date;
    int info;
};

std::ostream& operator <<(std::ostream& os, const Log& l)
{
    return os << l.date << " " << l.info;
}

std::istream& operator >>(std::istream& is, Log& l)
{
    return is >> l.date >> l.info;
}

Log LowerBound(std::istream& os, Log::Date d)
{
    using namespace std;
    os.seekg(0, std::ios::end);
    streamoff length = os.tellg();
    streampos current = 0;
    Log l;
    for(; length > 0;)
    {
        streamoff half = length / 2;
        streampos mid = current + half;
        os.seekg(mid);

        string line;
        getline(os, line);
        
        if (!(os >> l.date >> l.info))
            throw std::runtime_error("bad log format");
        if (l.date < d)
        {
            mid += 1;
            current = mid;
            length = length - half + 1;
        }
        else
            length = half;
    }
    return l;
}

template<typename OutIter>
void ReadLogsInRange(
    std::istream& logStream, Log::Date from, Log::Date to, OutIter out)
{
    using namespace std;

    Log l = LowerBound(logStream, from);
    *out++ = l;
    // Upper Bound
    while(logStream >> l && l.date < to)
        *out++ = l;
}


int main()
{
    using namespace boost::gregorian;
    
    // Create log
    Log l;
    l.date = Log::Date(2011, Sep, 1);
    l.info = 1;

    std::stringstream log;
    for(int i = 0; i < 1000; ++i)
    {
        log << l << std::endl;
        l.date += days(1);
        ++l.info;
    }

    // Read the log
    std::vector<Log> range;
    ReadLogsInRange(log, 
        date(2011, Sep, 9), date(2011, Sep, 12), 
        std::back_inserter(range));

    std::copy(range.begin(), range.end(), 
        std::ostream_iterator<Log>(std::cout, "\n"));
}