trees_cousins1.zip

bin/Linux/cousins

cousins.cpp
#include #include
#include
#include
#include

#include “familyTree.h”

using namespace std;

FamilyTree* readNode (istream& in, FamilyTree* parent)
{
char c;
in >> c;
if (c == ‘(‘)
{
int id;
in >> id;
FamilyTree* newNode = new FamilyTree(id, parent);
while (c != ‘)’)
{
in >> c;
if (c != ‘)’)
{
in.unget();
readNode(in, newNode);
}
}
return newNode;
}
else // should be a numeric digit
{
in.unget();
int id;
in >> id;
return new FamilyTree(id, parent);
}
}

void readTree (istream& in, FamilyTree*& root, FamilyTree*& interest)
{
int idOfInterest;
in >> idOfInterest;

root = readNode(in, nullptr);

interest = root->find(idOfInterest);
}

void solve (istream& in)
{
FamilyTree* root;
FamilyTree* nodeOfInterest;
readTree (in, root, nodeOfInterest);
cout << nodeOfInterest->numberOfCousins() << endl; } int main (int argc, char** argv) { if (argc > 1)
{
ifstream in (argv[1]);
solve(in);
in.close();
}
else
solve(cin);
return 0;
}

familyTree.cpp
#include #include
#include
#include

#include “familyTree.h”

using namespace std;

FamilyTree::FamilyTree (int id, FamilyTree* theParent)
: identifier(id), parent(theParent)
{
if (parent != nullptr)
parent->children.push_back(this);
}

FamilyTree::~FamilyTree()
{
for (FamilyTree* child: children)
delete child;
}

familyTree.h
#ifndef FAMILYTREE_H
#define FAMILYTREE_H

#include

class FamilyTree
{
int identifier;
FamilyTree *parent;
std::vector children;

public:
typedef std::vector::iterator iterator;
typedef std::vector::const_iterator const_iterator;

/**
* @brief Construct a new Family Tree object
*
* @param id identifier of this node
* @param theParent pointer to the parent of this node, null if this will be the root.
*/
FamilyTree(int id, FamilyTree *theParent = nullptr);
~FamilyTree();

/**
* @brief Get the identifier for this node
*
* @return int
*/
int getIdentifier() const {return identifier;}

/**
* @brief Get the parent of this node
*
* @return the parent, or null if this is the root
*/
FamilyTree *getParent() {return parent;}
const FamilyTree *getParent() const {return parent;}

/**
* @brief the number of cousins of this node
*
* @return the number of cousins
*/
int numberOfCousins() const;

/**
* @brief Find a node
*
* @param identifier the identifier to search for
* @return the descendent of this node (or this node itself) matching the identifier, or
* null if no such matching node exists
*/
const FamilyTree *find(int identifier) const;
FamilyTree *find(int identifier);

/**
* @brief Iterator access (to children of this node)
*
* @return iterator
*/
iterator begin() {return children.begin();}
const_iterator begin() const {return children.begin();}
iterator end() {return children.end();}
const_iterator end() const {return children.end();}

private:

// Because these are private, they cannot be called
FamilyTree(const FamilyTree &) {}
void operator=(const FamilyTree &) {}
};

#endif

make.dep
unittest.o: unittest.cpp unittest.h
testFamilyTree.o: testFamilyTree.cpp unittest.h familyTree.h
familyTree.o: familyTree.cpp familyTree.h
cousins.o: cousins.cpp familyTree.h
convert.o: convert.cpp familyTree.h

makefile
MAINPROG=cousins
DIR=${PWD}
ASST=$(notdir ${DIR})
CC=gcc
CXX=g++
##
# Adjust settings for different compilers
#
ifeq ($(OS),Windows_NT)
#
# Flags for Windows compilers
CPPFLAGS=-g -std=c++17 -MMD -pthread -D_GLIBCXX_DEBUG -Wall
LFLAGS=
RM=del /q
EXE=.exe
else
#
# Flags for Linux & MacOS
CPPFLAGS=-g -std=c++17 -MMD -pthread -D_GLIBCXX_DEBUG -Wall
LFLAGSx=-fuse-ld=gold -pthread
RM=/bin/rm -rf
EXE=
endif
#
########################################################################
# Macro definitions for “standard” C and C++ compilations
#
CFLAGS=-g
TARGET=$(MAINPROG)$(EXE)
CPPS=$(wildcard *.cpp)
MAINCPPS=$(filter-out convert.cpp unittest.cpp test%.cpp, $(CPPS))
TESTCPPS=$(filter-out convert.cpp $(MAINPROG).cpp, $(CPPS))

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:
#

MAINOBJS=$(MAINCPPS:%.cpp=%.o)
TESTOBJS=$(TESTCPPS:%.cpp=%.o)
DEPENDENCIES = $(CPPS:%.cpp=%.d)

%.d: %.cpp
touch $@

%.o: %.cpp
$(CXX) $(CPPFLAGS) -o $@ -c $*.cpp

#
# Targets:
#

all: $(TARGET) unittest$(EXE)

$(TARGET): $(MAINOBJS)
$(LINK) $(FLAGS) -o $(TARGET) $^ $(LFLAGS)

clean:
-/bin/rm -rf *.d *.o $(TARGET) unittest$(EXE) docs

documentation:
-mkdir docs
doxygen Doxyfile

unittest$(EXE): $(TESTOBJS)
$(LINK) $(FLAGS) -o $@ $^ $(LFLAGS)

convert$(EXE): convert.o familyTree.o
$(LINK) $(FLAGS) -o $@ convert.o familyTree.o $(LFLAGS)

make.dep: $(DEPENDENCIES)
-cat $(DEPENDENCIES) > $@

include make.dep

testFamilyTree.cpp
#include “unittest.h”
#include “familyTree.h”
#include

using namespace std;

struct Setup
{
/**
* Build a tree in the form
*
* 1-
* |-2-
* | |-3
* | |-4
* |
* |-5-
* | |-6-
* | | |-7
* | |-8
* | |-9
*/

FamilyTree *root;

Setup()
{
root = new FamilyTree(1, nullptr);
FamilyTree *node2 = new FamilyTree(2, root);
FamilyTree *node5 = new FamilyTree(5, root);

/*FamilyTree *node3 =*/ new FamilyTree(3, node2);
/*FamilyTree *node4 =*/ new FamilyTree(4, node2);

FamilyTree *node6 = new FamilyTree(6, node5);
/*FamilyTree *node8 =*/ new FamilyTree(8, node5);
/*FamilyTree *node9 =*/ new FamilyTree(9, node5);
/*FamilyTree *node7 =*/ new FamilyTree(7, node6);
}

~Setup()
{
delete root;
}
};

UnitTest(testSetup)
{
Setup s;
assertThat(s.root->getIdentifier(), isEqualTo(1));
assertThat(s.root->getParent(), isNull());
int expected[] = {2, 5};
int ctr = 0;
for (FamilyTree *child : *(s.root))
{
assertThat(child->getIdentifier(), isEqualTo(expected[ctr]));
++ctr;
assertThat(child->getParent(), isEqualTo(s.root));
}
}

UnitTest(testFind)
{
Setup s;

for (int i = 1; i < 10; ++i) { FamilyTree *node = s.root->find(i);
assertThat(node, isNotNull());
assertThat(node->getIdentifier(), isEqualTo(i));
if (i > 1)
{
assertThat(node->getIdentifier(), isGreaterThan(node->getParent()->getIdentifier()));
}
}
FamilyTree *n2 = s.root->find(2);
const FamilyTree *node2 = n2;
for (int i = 3; i < 5; ++i) { const FamilyTree *node = node2->find(i);
assertThat(node, isNotNull());
assertThat(node->getIdentifier(), isEqualTo(i));
assertThat(node->getParent(), isEqualTo(node2));
}
assertThat(n2->find(1), isNull());
assertThat(node2->find(7), isNull());
}

UnitTest(testCousins)
{
Setup s;

FamilyTree *n1 = s.root->find(1);
assertThat(n1->numberOfCousins(), isEqualTo(0));
assertThat(((const FamilyTree *)n1)->numberOfCousins(), isEqualTo(0));

FamilyTree *n2 = s.root->find(2);
assertThat(n2->numberOfCousins(), isEqualTo(0));

FamilyTree *n3 = s.root->find(3);
assertThat(n3->numberOfCousins(), isEqualTo(3));

const FamilyTree *n6 = s.root->find(6);
assertThat(n6->numberOfCousins(), isEqualTo(2));

const FamilyTree *n7 = s.root->find(7);
assertThat(n7->numberOfCousins(), isEqualTo(0));
}

unittest.cpp
#include
#include
#include
#include
#include
#include

#include
#include #include

#include
#include

#include
#include
#include

#include

#include “unittest.h”

#ifdef __MINGW32__
#ifdef __MINGW64__
#include
#else
#include
#endif
#elif __CYGWIN__
#include
#endif

using namespace CppUnitLite;

std::map *UnitTest::tests = nullptr;

long UnitTest::numSuccesses = 0L;
long UnitTest::numFailures = 0L;
long UnitTest::numErrors = 0L;
std::string UnitTest::currentTest;
bool UnitTest::expectToFail = false;
bool UnitTest::diagnosticMessagesBeforeResults = true;
std::vector UnitTest::callLog;
std::vector UnitTest::failedTests;

#ifdef __amd64__
#define breakDebugger { asm volatile (“int $3”); }
#elif __i386__
#define breakDebugger { asm volatile (“int $3”); }
#else
#define breakDebugger { }
#endif

template <>
std::string CppUnitLite::getStringRepr(std::string t)
{
return std::string(“””) + t + ‘””‘;