shortest.cpp

ssd5 考试3答案 需要的自己下载

#pragma warning(disable:4786)

#include "Shortest.h"
#include "main.h"

using namespace std;

Shortest::Shortest(const string &start_email) {
	
	vector<Client*>::iterator it_users;
	
	for(it_users = users.begin(); it_users != users.end(); it_users++)
	{
		ShortestEntry entry;
		entry.via = "";
		entry.hop_count = -1;
		entry.relationship = NONE;
		
		Client* pClient = *it_users;
		entry.email = pClient->getEmail();
		
		vector<int>::iterator it_bids = pClient->beginBids();
		
		while(it_bids != pClient->endBids())
		{
			entry.bids.insert(advertisements[*it_bids]->getEmail());
			it_bids++;
		}
		
		it_bids = pClient->beginOfferings();
		
		while(it_bids != pClient->endOfferings()) 
		{
			vector<Bid> highBids = advertisements[*it_bids]->getTopDutchBids();
			vector<Bid>::iterator it_highbids;
			
			for(it_highbids=highBids.begin(); it_highbids!=highBids.end(); it_highbids++) 
			{
				entry.offerings.insert((*it_highbids).getEmail());
			}
			it_bids++;
		}
		
		table.insert( *(new pair<string, ShortestEntry>(pClient->getEmail(), entry)));
	}
	
	ShortestEntry& entry = table[start_email];
	entry.via = start_email;
	entry.hop_count = 0;
	entry.relationship = START;
	recently_known.push(entry);
	
	while(!recently_known.empty()) 
	{
		ShortestEntry& entry = recently_known.front();
		set<string> temp = entry.bids;
		set<string>::iterator it=temp.begin();
		
		for(it=entry.bids.begin(); it!=entry.bids.end(); it++) 
		{
			ShortestEntry& temp = table[*it];
			if(temp.relationship == NONE) 
			{
				temp.relationship = BUYER;
				temp.via = entry.email;
				temp.hop_count = entry.hop_count + 1;
				recently_known.push(temp);
			}
		}
		
		for(it=entry.offerings.begin(); it!=entry.offerings.end(); it++) 
		{
			ShortestEntry& temp = table[*it];
			if(temp.relationship == NONE) 
			{
				temp.relationship = SELLER;
				temp.via = entry.email;
				temp.hop_count = entry.hop_count + 1;
				recently_known.push(temp);
			}
		}
		recently_known.pop();
	}
}


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;
	
}