Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <assert.h>
- using namespace std;
- class Date
- {
- public:
- friend istream& operator>>(istream& is, Date& date);
- bool operator< (const Date& rhs) const;
- bool operator>=(const Date& rhs) const;
- #ifndef NDEBUG
- friend ostream& operator<<(ostream& os, const Date& date);
- static void testDateComparisons();
- static void testDateExtractions();
- protected: // protected rather than private to facilitate testing
- #else
- private:
- #endif
- int year;
- int month;
- int day;
- };
- class Story
- {
- public:
- Story(const string& source /*a line from the input file*/);
- typedef string ID_t;
- const ID_t& getID () const;
- const Date& getDate () const;
- const vector<string>& getReferences() const;
- #ifndef NDEBUG
- friend ostream& operator<<(ostream& os, const Story& story);
- #endif
- private:
- string id;
- Date date;
- vector<string> references;
- };
- class ScoredStory : public pair<Story,float>
- {
- public:
- ScoredStory(Story story, float score);
- const Story& story;
- const float& score;
- bool operator<(const ScoredStory& rhs) const;
- };
- class RankedStories : public priority_queue<ScoredStory>
- {
- public:
- RankedStories(const vector<Story>& stories,
- const vector<float>& weights,
- const Date& earliest,
- const Date& latest);
- #ifndef NDEBUG
- friend ostream& operator<<(ostream& os, const RankedStories& stories);
- #endif
- private:
- vector<float> weights;
- Date earliest, latest;
- typedef map<Story::ID_t,ScoredStory> storymap_t;
- storymap_t storymap;
- void rateStory(const Story& story, unsigned int degree, set<string> visited);
- };
- int main()
- {
- #ifndef NDEBUG
- Date::testDateComparisons();
- Date::testDateExtractions();
- #endif
- char lineBuf[1024];
- vector<float> weights;
- cin.getline(lineBuf, sizeof(lineBuf));
- istringstream issWeights(lineBuf);
- while ( !issWeights.eof() )
- {
- float weight;
- issWeights>>weight;
- weights.push_back(weight);
- }
- size_t numStories;
- cin >> numStories >> ws;
- vector<Story> stories;
- while( stories.size() < numStories )
- {
- cin.getline(lineBuf, sizeof(lineBuf));
- stories.push_back(Story(lineBuf));
- }
- size_t top;
- Date startDate, endDate;
- cin >> top >> startDate >> endDate;
- RankedStories rankedStories(stories, weights, startDate, endDate);
- for ( size_t i=1 ; i<=top && !rankedStories.empty() ; ++i )
- {
- ScoredStory topStory = rankedStories.top();
- cout << topStory.first.getID() << " " << topStory.second;
- if (i<top && rankedStories.size()>1) cout<<endl; //provided testcase outputs lack EOL @ EOF
- rankedStories.pop();
- }
- return 0;
- }
- bool Date::operator>=(const Date& rhs) const { return !(*this<rhs); }
- bool Date::operator< (const Date& rhs) const
- {
- return year < rhs.year
- || month < rhs.month
- || day < rhs.day;
- }
- istream& operator>>(istream& is, Date& date)
- {
- is>>ws;
- char strYear [5]; is.get(strYear , 5); istringstream(strYear )>>date.year;
- char strMonth[3]; is.get(strMonth, 3); istringstream(strMonth)>>date.month;
- char strDay [3]; is.get(strDay , 3); istringstream(strDay )>>date.day;
- is>>ws;
- return is;
- }
- Story::Story(const string& source)
- {
- istringstream iss(source);
- iss >> id >> date;
- while ( !iss.eof() )
- {
- string ref;
- iss>>ref;
- references.push_back(ref);
- }
- }
- const Story::ID_t& Story::getID () const { return id; }
- const Date& Story::getDate () const { return date; }
- const vector<string>& Story::getReferences() const { return references; }
- ScoredStory::ScoredStory(Story s, float f) :pair<Story,float>(s, f), story(first), score(second) {}
- bool ScoredStory::operator<(const ScoredStory& rhs) const
- {
- if (this->second != rhs.second)
- return this->second < rhs.second;
- else
- return this->first.getDate() < rhs.first.getDate();
- }
- RankedStories::RankedStories(const vector<Story>& stories,
- const vector<float>& w,
- const Date& e,
- const Date& l )
- :weights(w), earliest(e), latest(l)
- {
- // populate storymap
- for ( size_t i=0 ; i<stories.size() ; ++i )
- {
- storymap.insert(
- storymap_t::value_type(
- stories[i].getID(),
- ScoredStory(stories[i],0)
- )
- );
- }
- // calculate scores for all stories in storymap
- for ( size_t i=0 ; i<stories.size() ; ++i )
- rateStory(stories[i], 0, set<string>());
- // initialize priority queue (self/baseclass)
- for ( storymap_t::const_iterator i = storymap.begin();
- i != storymap.end (); ++i )
- {
- Date date = i->second.first.getDate();
- if ( date >= earliest && date < latest )
- push(ScoredStory(i->second.first,i->second.second));
- }
- }
- void RankedStories::rateStory(const Story& story, unsigned int degree, set<string> visited)
- {
- // A recursive function. 'degree' indicates which weight to use for
- // determining scores. First order references are indicated by
- // degree=0, second order by degree=1, etc. Each nested call
- // increments 'degree' by one.
- if ( degree == weights.size() ) {
- // a base case: Nth order references (where N=degree) don't have associated weights
- return;
- }
- if ( story.getDate()<earliest || story.getDate()>=latest ) {
- // a base case: this story is outside the range of dates of interest
- return;
- }
- if ( visited.find(story.getID()) != visited.end() ) {
- // a base case: disallow cycles of references
- return;
- }
- // for each story referred to by this story, increase its score, and
- // recursively rate it, using the weight of the next highest degree
- for ( vector<string>::const_iterator i = story.getReferences().begin() ;
- i != story.getReferences().end () ; ++i )
- {
- if (*i == story.getID()) continue; // don't evaluate references to self
- storymap_t::iterator iStoryMap = storymap.find(*i);
- Story& refStory = (*iStoryMap).second.first;
- float& refScore = (*iStoryMap).second.second;
- if ( visited.find(*i) == visited.end() )
- refScore += weights[degree];
- visited.insert(story.getID());
- rateStory(refStory, degree+1, visited);
- }
- }
- #ifndef NDEBUG
- void Date::testDateComparisons()
- {
- class TestDate : public Date
- {
- public:
- TestDate(string source)
- {
- istringstream iss(source);
- iss>>*this;
- };
- };
- assert( TestDate("20131123")
- <TestDate("20141123"));
- assert( TestDate("20141123")
- <TestDate("20141223"));
- assert( TestDate("20141223")
- <TestDate("20141224"));
- assert(!(TestDate("20141124")
- <TestDate("20141124")));
- assert( TestDate("20141124")
- >=TestDate("20141124"));
- }
- void Date::testDateExtractions()
- {
- class TestDate : public Date
- {
- public:
- void verifyYear (int expected) { assert(year ==expected); };
- void verifyMonth(int expected) { assert(month==expected); };
- void verifyDay (int expected) { assert(day ==expected); };
- };
- TestDate a, b, c, d;
- istringstream iss(" 20131205 19990815 19830213 20110815");
- iss>>a>>b>>c>>d;
- a.verifyYear(2013); a.verifyMonth(12); a.verifyDay( 5);
- b.verifyYear(1999); b.verifyMonth( 8); b.verifyDay(15);
- c.verifyYear(1983); c.verifyMonth( 2); c.verifyDay(13);
- d.verifyYear(2011); d.verifyMonth( 8); d.verifyDay(15);
- }
- ostream& operator<<(ostream& os, const RankedStories& stories)
- {
- os << "<RankedStories>" << endl;
- os << "weights:";
- for ( size_t i = 0 ; i < stories.weights.size() ; ++i )
- os << " " << stories.weights[i];
- os << endl;
- for ( RankedStories::storymap_t::const_iterator i = stories.storymap.begin() ;
- i != stories.storymap.end () ; ++i )
- {
- const Story& story = i->second.first;
- const float& score = i->second.second;
- os << story << " has score " << score << endl;
- }
- os << "start date: " << stories.earliest << "; end date: " << stories.latest << endl;
- os << "</RankedStories>" << endl;
- return os;
- }
- ostream& operator<<(ostream& os, const Story& story)
- {
- os << "Story(id=" << story.id << ", Date=" << story.date;
- for ( vector<string>::const_iterator i = story.references.begin() ;
- i != story.references.end () ; ++i )
- {
- os << ", ref=" << *i;
- }
- return os<<")";
- }
- ostream& operator<<(ostream& os, const Date& date)
- {
- return os << date.year << "/" << date.month << "/" << date.day;
- }
- #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement