shortest.cpp

SSD5 Exam3 代码

#pragma warning(disable:4786)

#include "Shortest.h"
#include "main.h"
#include<map>
#include<string>

using namespace std;

Shortest::Shortest(const string &start_email) {

	for(Group::iterator itr=users.begin();itr!=users.end();itr++){
     
		string bid=(*itr)->getEmail();
		ShortestEntry entry;
		  entry.email=bid;
		  entry.hop_count=-1;
		  entry.relationship=NULL;
		  entry.via="";
	
		vector<int>::iterator itr3=(*itr)->beginBids();
		for(;itr3!=(*itr)->endBids();itr3++){

			int k=*itr3;
			string post=advertisements[k]->getEmail();
			entry.bids.insert(post);
		}

		vector<int>::iterator itr4=(*itr)->beginOfferings();
		for(;itr4!=(*itr)->endOfferings();itr4++){

			int p=*itr4;
			vector<Bid> win=advertisements[p]->getTopDutchBids();
			int n=0;
			while(n++ < win.size())
				entry.offerings.insert(win[n].getEmail());
			}

        if(table.find(bid)==table.end())
			table[bid]=entry;
	}


       table[start_email].email=start_email;
	   table[start_email].hop_count=0;
	   table[start_email].relationship=START;

	   recently_known.push(table[start_email]);

	   while(!recently_known.empty()){

		   ShortestEntry& en=recently_known.front();
		   recently_known.pop();

		   set<string>::iterator itr1=en.bids.begin();
		   while(itr1!=en.bids.end()){

			   ShortestEntry& en2=table[*itr1];
			   if(en2.relationship==NONE){
  				    en2.relationship=BUYER;
					en2.hop_count=en2.hop_count+1;
					en2.via=en.email;
					recently_known.push(en2);
			   }
			   itr1++;
		   }

		   set<string>::iterator itr2=en.offerings.begin();
			   while(itr2!=en.offerings.end()){

				   ShortestEntry& en3=table[*itr2];
				    if(en3.relationship==NONE){
  				    en3.relationship=SELLER;
					en3.hop_count=en3.hop_count+1;
					en3.via=en.email;
					recently_known.push(en3);
					}
			   
			      itr2++;
			   }
	   }
	   
}

				   


vector<string> Shortest::get_path(const string &destination_userid) {

  string current_userid = destination_userid;
  vector<string> events;
  bool relationship = true;

  while (true) {

        map<string,ShortestEntry>::iterator posn = 
           table.find(current_userid);

        // Stop if the current user is unknown
        if (posn == table.end()) {
          relationship = false;
          break;
        }

        // Stop if the current user is unreachable
        if (NONE == posn->second.relationship) {
          relationship = false;
          break;
        }

        // We have a valid, reachable user, so save the action
        if (BUYER == posn->second.relationship) {
          string description;

          description = posn->second.via + " bid on an item offered by " 
                  + posn->second.email;
          events.push_back(description);
          cout << description << endl;
        }
        else if (SELLER == posn->second.relationship) {
          string description;

          description = posn->second.via 
                  + " is offering an item with a high bid from " 
                  + posn->second.email;
          events.push_back(description);
          cout << description << endl;
        }


        // Stop if this was the first one -- no more actions
        if (START == posn->second.relationship) {
          break;
        }

        // Set up for the next action
        current_userid = posn->second.via;
      
  }

  if (0 == events.size() || !relationship) {
    events.push_back ("No relationship found between specified users.");
  }

  return events;

}