Advertisement
Guest User

Untitled

a guest
Nov 27th, 2014
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. #include <map>
  5. #include <set>
  6. #include <queue>
  7. #include <assert.h>
  8.  
  9. using namespace std;
  10.  
  11.  
  12. class Date
  13. {
  14. public:
  15.     friend istream& operator>>(istream& is, Date& date);
  16.     bool operator< (const Date& rhs) const;
  17.     bool operator>=(const Date& rhs) const;
  18. #ifndef NDEBUG
  19.     friend ostream& operator<<(ostream& os, const Date& date);
  20.     static void testDateComparisons();
  21.     static void testDateExtractions();
  22. protected: // protected rather than private to facilitate testing
  23. #else
  24. private:
  25. #endif
  26.     int year;
  27.     int month;
  28.     int day;
  29. };
  30.  
  31.  
  32. class Story
  33. {
  34. public:
  35.     Story(const string& source /*a line from the input file*/);
  36.     typedef string ID_t;
  37.     const ID_t&           getID        () const;
  38.     const Date&           getDate      () const;
  39.     const vector<string>& getReferences() const;
  40. #ifndef NDEBUG
  41.     friend ostream& operator<<(ostream& os, const Story& story);
  42. #endif
  43. private:
  44.     string id;
  45.     Date date;
  46.     vector<string> references;
  47. };
  48.  
  49.  
  50. class ScoredStory : public pair<Story,float>
  51. {
  52. public:
  53.     ScoredStory(Story story, float score);
  54.     const Story& story;
  55.     const float& score;
  56.     bool operator<(const ScoredStory& rhs) const;
  57. };
  58.  
  59.  
  60. class RankedStories : public priority_queue<ScoredStory>
  61. {
  62. public:
  63.     RankedStories(const vector<Story>& stories,
  64.                   const vector<float>& weights,
  65.                   const Date& earliest,
  66.                   const Date& latest);
  67. #ifndef NDEBUG
  68.     friend ostream& operator<<(ostream& os, const RankedStories& stories);
  69. #endif
  70. private:
  71.     vector<float> weights;
  72.     Date earliest, latest;
  73.  
  74.     typedef map<Story::ID_t,ScoredStory> storymap_t;
  75.     storymap_t storymap;
  76.  
  77.     void rateStory(const Story& story, unsigned int degree, set<string> visited);
  78. };
  79.  
  80.  
  81. int main()
  82. {
  83. #ifndef NDEBUG
  84.     Date::testDateComparisons();
  85.     Date::testDateExtractions();
  86. #endif
  87.  
  88.     char lineBuf[1024];
  89.  
  90.     vector<float> weights;
  91.     cin.getline(lineBuf, sizeof(lineBuf));
  92.     istringstream issWeights(lineBuf);
  93.     while ( !issWeights.eof() )
  94.     {
  95.         float weight;
  96.         issWeights>>weight;
  97.         weights.push_back(weight);
  98.     }
  99.  
  100.     size_t numStories;
  101.     cin >> numStories >> ws;
  102.  
  103.     vector<Story> stories;
  104.     while( stories.size() < numStories )
  105.     {
  106.         cin.getline(lineBuf, sizeof(lineBuf));
  107.         stories.push_back(Story(lineBuf));
  108.     }
  109.  
  110.     size_t top;
  111.     Date startDate, endDate;
  112.     cin >> top >> startDate >> endDate;
  113.  
  114.     RankedStories rankedStories(stories, weights, startDate, endDate);
  115.  
  116.     for ( size_t i=1 ; i<=top && !rankedStories.empty() ; ++i )
  117.     {
  118.         ScoredStory topStory = rankedStories.top();
  119.  
  120.         cout << topStory.first.getID() << " " << topStory.second;
  121.  
  122.         if (i<top && rankedStories.size()>1) cout<<endl; //provided testcase outputs lack EOL @ EOF
  123.  
  124.         rankedStories.pop();
  125.     }
  126.  
  127.     return 0;
  128. }
  129.  
  130. bool Date::operator>=(const Date& rhs) const { return !(*this<rhs); }
  131.  
  132. bool Date::operator< (const Date& rhs) const
  133. {
  134.     return year  < rhs.year
  135.         || month < rhs.month
  136.         || day   < rhs.day;
  137. }
  138.  
  139.  
  140. istream& operator>>(istream& is, Date& date)
  141. {
  142.     is>>ws;
  143.     char strYear [5]; is.get(strYear , 5); istringstream(strYear )>>date.year;
  144.     char strMonth[3]; is.get(strMonth, 3); istringstream(strMonth)>>date.month;
  145.     char strDay  [3]; is.get(strDay  , 3); istringstream(strDay  )>>date.day;
  146.     is>>ws;
  147.     return is;
  148. }
  149.  
  150. Story::Story(const string& source)
  151. {
  152.     istringstream iss(source);
  153.     iss >> id >> date;
  154.  
  155.     while ( !iss.eof() )
  156.     {
  157.         string ref;
  158.         iss>>ref;
  159.         references.push_back(ref);
  160.     }
  161. }
  162.  
  163. const Story::ID_t&    Story::getID        () const { return id; }
  164. const Date&           Story::getDate      () const { return date; }
  165. const vector<string>& Story::getReferences() const { return references; }
  166.  
  167. ScoredStory::ScoredStory(Story s, float f) :pair<Story,float>(s, f), story(first), score(second) {}
  168.  
  169. bool ScoredStory::operator<(const ScoredStory& rhs) const
  170. {
  171.     if (this->second != rhs.second)
  172.         return this->second < rhs.second;
  173.     else
  174.         return this->first.getDate() < rhs.first.getDate();
  175. }
  176.  
  177. RankedStories::RankedStories(const vector<Story>& stories,
  178.                              const vector<float>& w,
  179.                              const Date& e,
  180.                              const Date& l )
  181.     :weights(w), earliest(e), latest(l)
  182. {
  183.     // populate storymap
  184.     for ( size_t i=0 ; i<stories.size() ; ++i )
  185.     {
  186.         storymap.insert(
  187.             storymap_t::value_type(
  188.                 stories[i].getID(),
  189.                 ScoredStory(stories[i],0)
  190.             )
  191.         );
  192.     }
  193.  
  194.     // calculate scores for all stories in storymap
  195.     for ( size_t i=0 ; i<stories.size() ; ++i )
  196.         rateStory(stories[i], 0, set<string>());
  197.  
  198.     // initialize priority queue (self/baseclass)
  199.     for ( storymap_t::const_iterator i  = storymap.begin();
  200.                      i != storymap.end  (); ++i )
  201.     {
  202.         Date date = i->second.first.getDate();
  203.         if ( date >= earliest && date < latest )
  204.             push(ScoredStory(i->second.first,i->second.second));
  205.     }
  206. }
  207.  
  208. void RankedStories::rateStory(const Story& story, unsigned int degree, set<string> visited)
  209. {
  210.     // A recursive function.  'degree' indicates which weight to use for
  211.     // determining scores.  First order references are indicated by
  212.     // degree=0, second order by degree=1, etc.  Each nested call
  213.     // increments 'degree' by one.  
  214.  
  215.     if ( degree == weights.size() ) {
  216.         // a base case: Nth order references (where N=degree) don't have associated weights
  217.         return;
  218.     }
  219.  
  220.     if ( story.getDate()<earliest || story.getDate()>=latest ) {
  221.         // a base case: this story is outside the range of dates of interest
  222.         return;
  223.     }
  224.  
  225.     if ( visited.find(story.getID()) != visited.end() ) {
  226.         // a base case: disallow cycles of references
  227.         return;
  228.     }
  229.  
  230.     // for each story referred to by this story, increase its score, and
  231.     // recursively rate it, using the weight of the next highest degree
  232.     for ( vector<string>::const_iterator i  = story.getReferences().begin() ;
  233.                              i != story.getReferences().end  () ; ++i )
  234.     {
  235.         if (*i == story.getID()) continue; // don't evaluate references to self
  236.  
  237.         storymap_t::iterator iStoryMap = storymap.find(*i);
  238.  
  239.         Story& refStory = (*iStoryMap).second.first;
  240.         float& refScore = (*iStoryMap).second.second;
  241.  
  242.         if ( visited.find(*i) == visited.end() )
  243.             refScore += weights[degree];
  244.  
  245.         visited.insert(story.getID());
  246.  
  247.         rateStory(refStory, degree+1, visited);
  248.     }
  249. }
  250.  
  251. #ifndef NDEBUG
  252.  
  253. void Date::testDateComparisons()
  254. {
  255.     class TestDate : public Date
  256.     {
  257.     public:
  258.         TestDate(string source)
  259.         {
  260.             istringstream iss(source);
  261.             iss>>*this;
  262.         };
  263.     };
  264.  
  265.     assert(  TestDate("20131123")
  266.             <TestDate("20141123"));
  267.  
  268.     assert(  TestDate("20141123")
  269.             <TestDate("20141223"));
  270.  
  271.     assert(  TestDate("20141223")
  272.             <TestDate("20141224"));
  273.  
  274.     assert(!(TestDate("20141124")
  275.             <TestDate("20141124")));
  276.  
  277.     assert(  TestDate("20141124")
  278.            >=TestDate("20141124"));
  279. }
  280.  
  281. void Date::testDateExtractions()
  282. {
  283.     class TestDate : public Date
  284.     {
  285.     public:
  286.         void verifyYear (int expected) { assert(year ==expected); };
  287.         void verifyMonth(int expected) { assert(month==expected); };
  288.         void verifyDay  (int expected) { assert(day  ==expected); };
  289.     };
  290.  
  291.     TestDate a, b, c, d;
  292.     istringstream iss(" 20131205 19990815 19830213 20110815");
  293.     iss>>a>>b>>c>>d;
  294.     a.verifyYear(2013); a.verifyMonth(12); a.verifyDay( 5);
  295.     b.verifyYear(1999); b.verifyMonth( 8); b.verifyDay(15);
  296.     c.verifyYear(1983); c.verifyMonth( 2); c.verifyDay(13);
  297.     d.verifyYear(2011); d.verifyMonth( 8); d.verifyDay(15);
  298. }
  299.  
  300. ostream& operator<<(ostream& os, const RankedStories& stories)
  301. {
  302.     os << "<RankedStories>" << endl;
  303.  
  304.     os << "weights:";
  305.     for ( size_t i = 0 ; i < stories.weights.size() ; ++i )
  306.         os << " " << stories.weights[i];
  307.     os << endl;
  308.  
  309.     for ( RankedStories::storymap_t::const_iterator i  = stories.storymap.begin() ;
  310.                                                     i != stories.storymap.end  () ; ++i )
  311.     {
  312.         const Story& story = i->second.first;
  313.         const float& score = i->second.second;
  314.         os << story << " has score " << score << endl;
  315.     }
  316.  
  317.     os << "start date: " << stories.earliest << "; end date: " << stories.latest << endl;
  318.     os << "</RankedStories>" << endl;
  319.     return os;
  320. }
  321.  
  322. ostream& operator<<(ostream& os, const Story& story)
  323. {
  324.     os << "Story(id=" << story.id << ", Date=" << story.date;
  325.     for ( vector<string>::const_iterator i  = story.references.begin() ;
  326.                                          i != story.references.end  () ; ++i )
  327.     {
  328.         os << ", ref=" << *i;
  329.     }
  330.     return os<<")";
  331. }
  332.  
  333. ostream& operator<<(ostream& os, const Date& date)
  334. {
  335.     return os << date.year << "/" << date.month << "/" << date.day;
  336. }
  337.  
  338. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement