From aae26492dc1712e3f4783223df158ff5aa65d975 Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Sun, 10 Jul 2005 10:46:58 +0000 Subject: [PATCH] templates --- botsrc/bot.cpp | 123 ++----------------------------------------- botsrc/bot.h | 49 ++++++++++++----- copsrc/cop.cpp | 2 + robbersrc/robber.cpp | 2 + 4 files changed, 43 insertions(+), 133 deletions(-) diff --git a/botsrc/bot.cpp b/botsrc/bot.cpp index 411d933..506330a 100644 --- a/botsrc/bot.cpp +++ b/botsrc/bot.cpp @@ -21,6 +21,8 @@ Bot::Bot(const string& name, PlayerType type){ _playerTypes["robber"] = robber; _playerTypes["cop-foot"] = cop_foot; _playerTypes["cop-car"] = cop_car; + //shortestPath("",robber,SimpleSPGoal("")); + //shortestPath("",robber,FindPlayer(hash_map(),robber)); } @@ -275,125 +277,6 @@ std::string Bot::turn(){ return _location; } -struct SPInfoComp{ - bool operator()(const SPInfo* v1, const SPInfo* v2){ - return v1->cost > v2->cost; - } -}; - -std::list Bot::shortestPath(const std::string& from, PlayerType type, const SPGoal& goal, bool reverse){ - - //cerr << "New shortest path from: " << from << endl; - - priority_queue, SPInfoComp > pq; - hash_map nodes; - - SPInfo* node = &nodes[from]; - node->name = from; - node->settled = false; - node->parent = 0; - node->cost = 0; - pq.push(node); - - int g = 0; - bool hascar = type == cop_car; - ; - SPInfo* n = 0; - while(!pq.empty()){ - node = pq.top(); - pq.pop(); - - g = goal(node); - if (g < 0) - break; - else if (g){ - list l; - front_insert_iterator > ii(l); - do{ - *ii++ = node->name; - node = node->parent; - }while (node != 0); - return l; - } - node->settled = true; - - hash_map::const_iterator intersection = _intersections.find(node->name); - if (intersection == _intersections.end()){ //Sanity check, should never be true.. - cerr << "BUG: Could not find intersection: " << node->name << endl; - continue; - } - for (hash_map::const_iterator street = intersection->second.connections.begin(); - street != intersection->second.connections.end(); ++street){ - hash_map::iterator newNode = nodes.find(street->first); - bool travelStreet = false; - if (hascar){ - if (reverse){ - if (street->second != foot){ - hash_map::const_iterator newInter = _intersections.find(street->first); - if (newInter != _intersections.end()){ - hash_map::const_iterator st = newInter->second.connections.find(node->name); - if (st != newInter->second.connections.end()) - travelStreet = st->second != foot; - } - }else - travelStreet = true; - }else - travelStreet = street->second != foot; - }else{ - travelStreet = street->second != car; - } - if (travelStreet){ - //cerr << "Adding street: " << street->first << endl; - if (newNode == nodes.end()){ - n = &nodes[street->first]; - n->name = street->first; - n->settled = false; - n->parent = 0; - n->cost = 10000; - }else if (newNode->second.settled) - continue; - else - n = &newNode->second; - - if (n->cost > node->cost + 1){ - n->cost = node->cost + 1; - n->parent = node; - pq.push(n); - } - } - - } - - } - - return list(); -} - -SimpleSPGoal::SimpleSPGoal(const std::string& to, int limit):_to(to), _limit(limit){ -} - -int SimpleSPGoal::operator()(const SPInfo* node) const{ - if (_limit > 0 && node->cost >= _limit) - return -1; - if (node->name == _to) - return 1; - return 0; -} - -FindPlayer::FindPlayer(const hash_map& players, PlayerType type, int limit) : _players(players), _type(type), _limit(limit){ -} - -int FindPlayer::operator()(const SPInfo* node) const{ - if (_limit > 0 && node->cost >= _limit) - return -1; - for(hash_map::const_iterator player = _players.begin(); - player != _players.end(); ++player){ - if (player->second.type == _type && player->second.location == node->name){ - return 1; - } - } - return 0; -} void Bot::sendInformation(){ cout << "inf\\" << endl; @@ -446,3 +329,5 @@ void Bot::voteResult(){ ++_winningPlans[winner]; } } + +#include "shortestPath.cpp" diff --git a/botsrc/bot.h b/botsrc/bot.h index aab4e83..aad7473 100644 --- a/botsrc/bot.h +++ b/botsrc/bot.h @@ -64,13 +64,6 @@ struct SPInfo{ int cost; }; - -class SPGoal{ - public: - virtual ~SPGoal(){} - virtual int operator()(const SPInfo* node) const = 0; -}; - class Bot { public: Bot(const std::string& name, PlayerType type); @@ -91,7 +84,8 @@ class Bot { virtual void vote(); virtual void voteResult(); void getPlayers(); - std::list shortestPath(const std::string& from, PlayerType type, const SPGoal& goal, bool reverse = false); + template + std::list shortestPath(const std::string& from, PlayerType type, const Goal& goal, bool reverse = false); __gnu_cxx::hash_map _intersections; __gnu_cxx::hash_map _players; @@ -110,21 +104,48 @@ class Bot { __gnu_cxx::hash_map _winningPlans; }; -class SimpleSPGoal : public SPGoal{ +class SimpleSPGoal{ std::string _to; int _limit; public: - SimpleSPGoal(const std::string& to, int limit = 0); - int operator()(const SPInfo* node) const; + SimpleSPGoal(const std::string& to, int limit = 0):_to(to), _limit(limit){ + } + inline int operator()(const SPInfo* node) const{ + if (_limit > 0 && node->cost >= _limit) + return -1; + if (node->name == _to) + return 1; + return 0; + } + }; -class FindPlayer : public SPGoal{ +class FindPlayer{ int _limit; const __gnu_cxx::hash_map& _players; PlayerType _type; public: - FindPlayer(const __gnu_cxx::hash_map& players, PlayerType type, int limit = 0); - int operator()(const SPInfo* node) const; + FindPlayer(const __gnu_cxx::hash_map& players, PlayerType type, int limit = 0): _players(players), _type(type), _limit(limit){ + } + inline int operator()(const SPInfo* node) const{ + if (_limit > 0 && node->cost >= _limit) + return -1; + for(__gnu_cxx::hash_map::const_iterator player = _players.begin(); + player != _players.end(); ++player){ + if (player->second.type == _type && player->second.location == node->name){ + return 1; + } + } + return 0; + } + }; +struct SPInfoComp{ + inline bool operator()(const SPInfo* v1, const SPInfo* v2){ + return v1->cost > v2->cost; + } +}; + + #endif diff --git a/copsrc/cop.cpp b/copsrc/cop.cpp index 90b5408..411c111 100644 --- a/copsrc/cop.cpp +++ b/copsrc/cop.cpp @@ -297,3 +297,5 @@ int main(){ return 0; } + +#include "../botsrc/shortestPath.cpp" diff --git a/robbersrc/robber.cpp b/robbersrc/robber.cpp index 5f36f47..32124a8 100644 --- a/robbersrc/robber.cpp +++ b/robbersrc/robber.cpp @@ -134,3 +134,5 @@ int main(){ return 0; } + +#include "../botsrc/shortestPath.cpp" -- 2.39.2