Homework Assignment #9
bin/Linux/levelPlan
bin/Windows/levelPlan.exe
levelPlan.cpp
#include <algorithm> #include <list> #include <queue> #include <iostream> #include <fstream> #include <string> #include "perk.h" #include "perkCollections.h" #include "skillTree.h" using namespace std; // Look for perks that have no prerequisites. Print and remove them void removeAndListAvailPerks(SkillTree& skilltree) { PerkSet perksWithPrereqs; for (const Perk& perk: skilltree) { PerkSet::iterator start, stop; skilltree.getEnabled(perk, start, stop); for (auto it = start; it != stop; ++it) { Perk c = *it; perksWithPrereqs.insert(c); } } // cerr << "with pre: " << perksWithPrereqs << endl; PerkSet perksWithoutPrereqs; for (Perk p: skilltree) { if (perksWithPrereqs.count(p) == 0) perksWithoutPrereqs.insert(p); } // cerr << "without pre: " << perksWithoutPrereqs << endl; for (const Perk& perk: perksWithoutPrereqs) { cout << perk.name << perk.level << endl; skilltree.removePerk (perk); } } void listPlan(Perk goal, SkillTree& skilltree) { skilltree.restrictTo(goal); while (skilltree.begin() != skilltree.end()) { removeAndListAvailPerks (skilltree); } } int main (int argc, char** argv) { Perk goal; SkillTree skilltree; if (argc > 1) { ifstream in (argv[1]); string word; in >> goal; skilltree.read (in); } else { cin >> goal; skilltree.read (cin); } listPlan (goal, skilltree); return 0; }
makefile
ifeq ($(OS),Windows_NT) # # Flags for Windows compilers CPPFLAGS=-g -std=c++11 -MMD -D_GLIBCXX_DEBUG -Wall LFLAGS= RM=del /q EXE=.exe else # # Flags for Linux & OS/X CPPFLAGS=-g -std=c++11 -MMD -fsanitize=address -D_GLIBCXX_DEBUG -Wall LFLAGS=-pthread RM=/bin/rm -rf EXE= endif # #################################################### # Customization for this project # TARGET=levelPlan$(EXE) CPPS=$(wildcard *.cpp) DEPENDENCIES = $(CPPS:%.cpp=%.d) OBJS=$(CPPS:%.cpp=%.o) #OBJS=corrections.o editdist.o anagrams.o suggestions.o #TESTOBJS=unittest.o testEditDistance.o editdist.o anagrams.o testAnagrams.o # # ######################################################################## # Macro definitions for "standard" C and C++ compilations # # CC=gcc CXX=g++ CFLAGS=-g LINK=g++ $(CPPFLAGS) # # # # In most cases, you should not change anything below this line. # # The following is "boilerplate" to set up the standard compilation # commands: # %.d: %.cpp touch $@ %.o: %.cpp echo $(usingMinGW) $(CXX) $(CPPFLAGS) -o $@ -c $*.cpp # # Targets: # all: $(TARGET) # runtests$(EXE) $(TARGET): $(OBJS) $(LINK) $(FLAGS) -o $@ $^ $(LFLAGS) runtests$(EXE): $(TESTOBJS) $(LINK) $(FLAGS) -o $@ $^ $(LFLAGS) # Convenience target for use with Code::Blocks Debug: all docs: documentation clean: -$(RM) *.o $(TARGET) runtests$(EXE) docs cleanDebug: clean documentation: -mkdir docs doxygen Doxyfile make.dep: $(DEPENDENCIES) -cat $(DEPENDENCIES) > $@ #include make.dep levelPlan.o: levelPlan.cpp perk.h perkCollections.h skillTree.h perkCollections.o: perkCollections.cpp perkCollections.h perk.h perk.o: perk.cpp perk.h skilltree.o: skilltree.cpp skillTree.h perk.h perkCollections.h restrictTree.o: skilltree.cpp skillTree.h perk.h perkCollections.h
perk.cpp
#include "perk.h" #include <iostream> #include <string> #include <sstream> using namespace std; Perk::Perk (string theName, int theLevel) : name(theName), level(theLevel) { } ostream& operator<< (ostream& out, const Perk& p) { out << p.name << p.level; return out; } istream& operator>> (istream& in, Perk& p) { string word; in >> word; p.parsePerkName(word); return in; } void Perk::parsePerkName (string combined) { int i = 0; while (combined[i] >= 'A') ++i; name = combined.substr(0, i); istringstream numIn (combined.substr(i)); numIn >> level; }
perk.h
#ifndef PERK_H #define PERK_H #include <iostream> #include <string> #include <functional> using namespace std; struct Perk { std::string name; int level; Perk (std::string theName = string(), int theLevel=1); private: void parsePerkName (std::string combined); friend std::istream& operator>> (std::istream& in, Perk& c); }; std::ostream& operator<< (std::ostream& out, const Perk& c); std::istream& operator>> (std::istream& in, Perk& c); #endif
perkCollections.cpp
#include <algorithm> #include <iterator> #include "perkCollections.h" using namespace std; ostream& operator<< (ostream& out, const PerkSet& c) { copy (c.begin(), c.end(), ostream_iterator<Perk>(out, " ")); return out; } ostream& operator<< (ostream& out, const PerkMap::value_type& c) { out << c.first << "=>" << c.second; return out; } ostream& operator<< (ostream& out, const PerkMap& c) { copy (c.begin(), c.end(), ostream_iterator<PerkMap::value_type>(out, " ")); return out; } bool operator< (const Perk& c1, const Perk& c2) { if (c1.name < c2.name) return true; else if (c1.name > c2.name) return false; else if (c1.level < c2.level) return true; else return false; }
perkCollections.h
#ifndef PERKCOLLECTIONS_H #define PERKCOLLECTIONS_H #include <unordered_map> #include <unordered_set> #include "perk.h" /** * A collection of perks with no duplicates. */ typedef std::unordered_set<Perk> PerkSet; /** * A map from a course to zero or more other courses. * (This could have been done as a multimap, but the map to a * set speeds up some of the delete operations needed for this * program.) */ typedef std::unordered_map<Perk, PerkSet> PerkMap; bool operator< (const Perk& c1, const Perk& c2); // For debugging purposes ostream& operator<< (ostream& out, const PerkSet& c); ostream& operator<< (ostream& out, const PerkMap& c); #endif
restrictTree.cpp
#include <algorithm> #include <iterator> #include <sstream> #include "skillTree.h" #include <queue> #include <list> #include <algorithm> using namespace std; /** * Remove from the skill tree all perks other than the goal and * perks that are immediate or indirect prereuqisites of the goal. * * @param goal a perk that we want to acquire * */ void SkillTree::restrictTo(Perk goal) { //*** Your code here }
skillTree.h
#ifndef SKILLTREE_H #define SKILLTREE_H #include "perk.h" #include "perkCollections.h" /** * A SkillTree (technically, a skill directed acyclic graph), with information * on perks available and their immediate prerequisites within the game * structure. */ class SkillTree { public: typedef PerkSet::iterator iterator; typedef PerkSet::const_iterator const_iterator; /** * Create a new skill tree. */ SkillTree(); /** * Provide access to the perks in the skill tree. */ iterator begin() {return allPerks.begin();} iterator end() {return allPerks.end();} const_iterator begin() const {return allPerks.begin();} const_iterator end() const {return allPerks.end();} /** * Adds a pair of perks to the skilltree if they have not previously been * encountered, and records that one perk is an immediate prerequisite * of the other. * * @param aPerk a perk, possibly never seen before * @param prereqPerk another perk that is an immediate prerequisite * of aPerk. */ void addPerk ( const Perk& aPerk, const Perk& prereqPerk); /** * Remove a perk from the skilltree, including any * relationships in which it enables other courses. */ void removePerk (const Perk& c); /** * Remove from the skill tree all perks other than the goal and * perks that are immediate or indirect prereuqisites of the goal. * * @param goal a perk that we want to acquire * */ void restrictTo(Perk goal); /** * Gets the positions containing the perks that * are immediate prerequisites ofThisPerk. * * Sets firstPrereq to the position * of the first such perk and sets * afterLastPrereq to the position just after the last * such perk. * * If byThisPerk has no prerequisites, * then sets firstPrereq and afterLastPrereq to any single position. * * Important: This operation must be faster than * O(prereqs.size()). Sequential searches are not * acceptable. */ void getPrereqs (Perk ofThisPerk, iterator& firstPrereq, iterator& afterLastPrereq); /** * Gets the positions containing the perks that * byThisPerk is an immediate prerequsite for. * * Sets first to the position * of the first such perk and sets * afterLast to the position just after the last * perk enabled by byThisCourse. * * If byThisPerk is not a prerequisite to any other perk, * then sets firstPrereq and afterLastPrereq to any single position. * * Important: This operation must be faster than * O(enables.size()). Sequential searches are not * acceptable. */ void getEnabled (Perk byThisPerk, iterator& first, iterator& afterLast); /** * Read a skilltree from an input stream. * * Input is repeated lines of * * perk prereq1OfPerk prereq2OfPerk ... * * @param input the input stream */ void read (istream& input); private: /** * All of the perks in the game. */ PerkSet allPerks; /** * A map from each perk P in allPerks to those perks * that are an immediate prerequisite of P. */ PerkMap prereqs; /** * A map from each perk P in allPerks to those perks * that P is an immediate prerequisite of. */ PerkMap isPrereqFor; Perk parsePerkName (string combined); }; #endif
skilltree.cpp
#include <algorithm> #include <iterator> #include <sstream> #include "skillTree.h" #include <queue> #include <list> #include <algorithm> using namespace std; SkillTree::SkillTree() { } /** * Gets the positions containing the perks that * byThisPerk is an immediate prerequsite for. * * Sets first to the position * of the first such perk and sets * afterLast to the position just after the last * perk enabled by byThisCourse. * * If byThisPerk is not a prerequisite to any other perk, * then sets firstPrereq and afterLastPrereq to any single position. * * Important: This operation must be faster than * O(enables.size()). Sequential searches are not * acceptable. */ void SkillTree::getEnabled (Perk byThisPerk, PerkSet::iterator& first, PerkSet::iterator& afterLast) { PerkSet& prereqSeq = isPrereqFor[byThisPerk]; first = prereqSeq.begin(); afterLast = prereqSeq.end(); } /** * Gets the positions containing the perks that * are immediate prerequisites ofThisPerk. * * Sets firstPrereq to the position * of the first such perk and sets * afterLastPrereq to the position just after the last * such perk. * * If byThisPerk has no prerequisites, * then sets firstPrereq and afterLastPrereq to any single position. * * Important: This operation must be faster than * O(prereqs.size()). Sequential searches are not * acceptable. */ void SkillTree::getPrereqs (Perk ofThisPerk, iterator& firstPrereq, iterator& afterLastPrereq) { PerkSet& prereqSeq = prereqs[ofThisPerk]; firstPrereq = prereqSeq.begin(); afterLastPrereq = prereqSeq.end(); } void SkillTree::read (istream& input) { string line; getline (input, line); while (input) { istringstream in (line); Perk p1; in >> p1; allPerks.insert (p1); Perk p2; while (in >> p2) { addPerk (p1, p2); } getline (input, line); } } /** * Adds a pair of perks to the skilltree if they have not previously been * encountered, and records that one perk is an immediate prerequisite * of the other. * * @param aPerk a perk, possibly never seen before * @param prereqPerk another perk that is an immediate prerequisite * of aPerk. */ void SkillTree::addPerk ( const Perk& aPerk, const Perk& prereqPerk) { allPerks.insert (aPerk); allPerks.insert (prereqPerk); isPrereqFor[prereqPerk].insert(aPerk); prereqs[aPerk].insert(prereqPerk); } /** * Remove a perk from the skilltree, including any * relationships in which it enables other perks. */ void SkillTree::removePerk (const Perk& c) { // First, remove any mentions of c in info about other perks PerkSet& enabled = isPrereqFor[c]; for (Perk p: enabled) { prereqs[p].erase(c); } PerkSet& required = prereqs[c]; for (Perk p: required) { isPrereqFor[p].erase(c); } // Then remove c itself from the skilltree prereqs.erase(c); isPrereqFor.erase(c); allPerks.erase(c); }
test0.in
MasterTrader2 Bargainer1 Charismatic1 Diplomat2 Bargainer1 Diplomat1 MasterTrader1 Bargainer1 Diplomat3 Diplomat2 Leader1 Diplomat2 Bargainer1 Warrior1 Stealth2 Stealth1 MasterTrader2 MasterTrader1