Skip to content

Instantly share code, notes, and snippets.

@jason790228

jason790228/ Familytree.cpp

Last active July 12, 2017 11:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jason790228/cf419a8bd80522eddad758010c0204c9 to your computer and use it in GitHub Desktop.
Save jason790228/cf419a8bd80522eddad758010c0204c9 to your computer and use it in GitHub Desktop.
Download ZIP
11484
Raw
Familytree.cpp
#include "FamilyTree.h"
using namespace std;
bool Familytree::join_member(People *new_member, People *parent)
{
setup_relationship(new_member, !parent ? m_familytree_root : parent);
return true;
}
void Familytree::setup_relationship(People *new_member, People *parent)
{
if (parent->get_child().size() > 0)
{
parent->get_child().back()->set_younger_brother(new_member);
new_member->set_older_brother(parent->get_child().back());
}
parent->add_child(new_member);
new_member->set_parent(parent);
}
bool Familytree::go_to_first_child(People &familytree_position) const
{
if (familytree_position.get_child().size() <= 0) return false;
familytree_position = *familytree_position.get_child()[0];
return true;
}
bool Familytree::go_to_older_brother(People &familytree_position) const
{
if (familytree_position.get_older_brother() == nullptr) return false;
familytree_position = *familytree_position.get_older_brother();
return true;
}
bool Familytree::go_to_younger_brother(People &familytree_position) const
{
if (familytree_position.get_younger_brother() == nullptr) return false;
familytree_position = *familytree_position.get_younger_brother();
return true;
}
bool Familytree::go_to_parent(People &familytree_position) const
{
if (familytree_position.get_parent() == nullptr || familytree_position.get_parent() == m_familytree_root) return false;
familytree_position = *familytree_position.get_parent();
return true;
}
Raw
11484.cpp
#include "gtest\gtest.h"
#include "FamilyTree.h"
#include <iostream>
#include <vector>
#include "string"
#include <regex>
using namespace std;
void run_instruction(const Familytree& ftree, const vector<string> &instruction)
{
People position = *ftree.get_root();
ftree.go_to_first_child(position);
for (size_t i = 0; i < instruction.size(); i++)
{
if (instruction[i] == "first_child")
{
ftree.go_to_first_child(position);
}
else if (instruction[i] == "next_sibling")
{
ftree.go_to_younger_brother(position);
}
else if (instruction[i] == "previous_sibling")
{
ftree.go_to_older_brother(position);
}
else if (instruction[i] == "parent")
{
ftree.go_to_parent(position);
}
cout << position.get_knowledge() << endl;
}
}
Familytree build_familytree(const vector<string> &member)
{
Familytree ftree;
vector<People *> stack;
regex start_pattern("<(.+) value='(.+)'>");
regex stop_pattern("</(.+)>");
People* m = new People[member.size() / 2];
int member_count(0);
for (size_t i = 0; i < member.size(); i++)
{
smatch sm;
if (regex_match(member[i], sm, start_pattern))
{
m[member_count].set_name(sm[1]);
m[member_count].set_knowledge(sm[2]);
if (stack.size() > 0)
{
ftree.join_member(&m[member_count], stack.back());
}
else
{
ftree.join_member(&m[member_count]);
}
stack.push_back(&m[member_count]);
member_count++;
}
else if (regex_match(member[i], stop_pattern))
{
stack.pop_back();
}
}
return ftree;
}
void run(const vector<string> &member, const vector<string> &instruction)
{
Familytree ftree = build_familytree(member);
run_instruction(ftree, instruction);
}
int main(int argc, char* argv[])
{
int count(1);
while (1)
{
int a, b;
vector<string> member;
vector<string> instruction;
cin >> a;
if (a == 0) break;
cin.ignore(1024, '\n');
for (int i = 0; i < a; i++)
{
string temp;
getline(cin, temp);
member.push_back(temp);
}
cin >> b;
cin.ignore(1024, '\n');
for (int i = 0; i < b; i++)
{
string temp;
getline(cin, temp);
instruction.push_back(temp);
}
cout << "Case " << count++ << ":" << endl;
run(member, instruction);
}
system("pause");
return 0;
}
Raw
Familytree.h
#include "People.h"
class Familytree
{
public:
Familytree()
{
m_familytree_root = new People();
m_familytree_root->set_name("root");
}
~Familytree()
{
/*if (m_familytree_root != nullptr)
{
delete m_familytree_root;
m_familytree_root = nullptr;
}*/
}
public:
bool join_member(People *people, People *parent = nullptr);
People* get_root() const { return m_familytree_root; }
bool go_to_first_child(People &familytree_position) const;
bool go_to_older_brother(People &familytree_position) const;
bool go_to_younger_brother(People &familytree_position) const;
bool go_to_parent(People &familytree_position) const;
private:
void setup_relationship(People *new_member, People *parent);
private:
People *m_familytree_root;
};
Raw
People.cpp
#include "People.h"
People::People() : m_parent(nullptr), m_older_brother(nullptr), m_younger_brother(nullptr), m_children(std::vector<People *>(0, 0)), m_knowledge(std::string()), m_name(std::string())
{}
People::~People()
{
}
bool People::set_parent(People *parent)
{
if (nullptr != m_parent) return false;
if (nullptr == parent) return false;
m_parent = parent;
return true;
}
bool People::set_older_brother(People *older_brother)
{
if (nullptr != m_older_brother) return false;
if (nullptr == older_brother) return false;
m_older_brother = older_brother;
return true;
}
bool People::set_younger_brother(People *younger_brother)
{
if (nullptr != m_younger_brother) return false;
if (nullptr == younger_brother) return false;
m_younger_brother = younger_brother;
return true;
}
bool People::add_child(People *child)
{
if (nullptr == child) return false;
m_children.push_back(child);
return true;
}
Raw
People.h
#include <vector>
#include <iterator>
class People
{
public:
People();
~People();
public:
bool set_parent(People *parent);
bool set_older_brother(People *older_brother);
bool set_younger_brother(People *younger_brother);
bool add_child(People *child);
const People* get_parent() { return m_parent; }
const People* get_older_brother() { return m_older_brother; }
const People* get_younger_brother() { return m_younger_brother; }
std::vector<People *>& get_child() { return m_children; }
void set_knowledge(std::string s) { m_knowledge = s; }
std::string get_knowledge() { return m_knowledge; }
void set_name(std::string s) { m_name = s; }
std::string get_name() { return m_name; }
public:
bool operator == (const People& other) const
{
if (m_parent == other.m_parent
&& m_older_brother == other.m_older_brother
&& m_younger_brother == other.m_younger_brother
&& m_children.size() == other.m_children.size()
&& equal(m_children.begin(), m_children.end(), other.m_children.begin())
)
{
return true;
}
return false;
}
bool operator != (const People& other) const
{
if (m_parent == other.m_parent
&& m_older_brother == other.m_older_brother
&& m_younger_brother == other.m_younger_brother
&& m_children.size() == other.m_children.size()
&& equal(m_children.begin(), m_children.end(), other.m_children.begin())
)
{
return false;
}
return true;
}
private:
std::string m_knowledge;
std::string m_name;
People *m_parent;
People *m_older_brother;
People *m_younger_brother;
std::vector<People *> m_children;
};
Raw
test11484.cpp
#include "gtest\gtest.h"
#include "FamilyTree.h"
TEST(PeopleParentTest, PeopleFamilyShipTest)
{
People test;
People test_parent;
People test_parent2;
EXPECT_EQ(true, test.set_parent(&test_parent));
EXPECT_EQ(false, test.set_parent(&test_parent2));
EXPECT_EQ(&test_parent, test.get_parent());
EXPECT_NE(&test_parent2, test.get_parent());
}
TEST(PeopleOlderBrotherTest, PeopleOlderBrotherTest)
{
People test;
People test_older_brother;
People test_older_brother2;
EXPECT_EQ(true, test.set_older_brother(&test_older_brother));
EXPECT_EQ(false, test.set_older_brother(&test_older_brother2));
EXPECT_EQ(&test_older_brother, test.get_older_brother());
EXPECT_NE(&test_older_brother2, test.get_older_brother());
}
TEST(PeopleYoungerBrotherTest, PeopleYoungerBrotherTest)
{
People test;
People test_younger_brother;
People test_younger_brother2;
EXPECT_EQ(true, test.set_younger_brother(&test_younger_brother));
EXPECT_EQ(false, test.set_younger_brother(&test_younger_brother2));
EXPECT_EQ(&test_younger_brother, test.get_younger_brother());
EXPECT_NE(&test_younger_brother2, test.get_younger_brother());
}
TEST(PeopleChildTest, PeopleChildTest)
{
People test;
People test_child;
People test_child2;
EXPECT_EQ(true, test.add_child(&test_child));
EXPECT_EQ(true, test.add_child(&test_child2));
EXPECT_EQ(2, test.get_child().size());
EXPECT_EQ(test_child, *test.get_child()[0]);
EXPECT_EQ(test_child2, *test.get_child()[1]);
}
TEST(PeopleKnowlegdeTest, PeopleKnowlegdeTest)
{
People test;
test.set_knowledge("123");
EXPECT_EQ("123", test.get_knowledge());
}
TEST(PeopleNameTest, v)
{
People test;
test.set_name("123");
EXPECT_EQ("123", test.get_name());
}
TEST(FamilytreeJoinTest, FamilytreeJoinTest)
{
Familytree test;
People member;
member.set_name("member");
EXPECT_EQ(true, test.join_member(&member));
EXPECT_EQ(test.get_root(), member.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
People member2;
member2.set_name("member2");
EXPECT_EQ(true, test.join_member(&member2));
EXPECT_EQ(test.get_root(), member2.get_parent());
EXPECT_EQ(member, *member2.get_older_brother());
EXPECT_EQ(member2, *member.get_younger_brother());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
People member3;
member3.set_name("member3");
EXPECT_EQ(true, test.join_member(&member3, &member));
EXPECT_EQ(member, *member3.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
People member4;
member4.set_name("member4");
EXPECT_EQ(true, test.join_member(&member4, &member));
EXPECT_EQ(member, *member4.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
EXPECT_EQ(member4, *member.get_child()[1]);
EXPECT_EQ(member3, *member4.get_older_brother());
EXPECT_EQ(member4, *member3.get_younger_brother());
People member5;
member5.set_name("member5");
EXPECT_EQ(true, test.join_member(&member5));
EXPECT_EQ(test.get_root(), member5.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
EXPECT_EQ(member5, *test.get_root()->get_child()[2]);
EXPECT_EQ(member2, *member5.get_older_brother());
EXPECT_EQ(member5, *member2.get_younger_brother());
}
TEST(FamilytreeFirstChildTest, FamilytreeFirstChildTest)
{
Familytree test;
People member;
member.set_name("member");
EXPECT_EQ(true, test.join_member(&member));
EXPECT_EQ(test.get_root(), member.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
People member2;
member2.set_name("member2");
EXPECT_EQ(true, test.join_member(&member2));
EXPECT_EQ(test.get_root(), member2.get_parent());
EXPECT_EQ(member, *member2.get_older_brother());
EXPECT_EQ(member2, *member.get_younger_brother());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
People member3;
member3.set_name("member3");
EXPECT_EQ(true, test.join_member(&member3, &member));
EXPECT_EQ(member, *member3.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
People member4;
member4.set_name("member4");
EXPECT_EQ(true, test.join_member(&member4, &member));
EXPECT_EQ(member, *member4.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
EXPECT_EQ(member4, *member.get_child()[1]);
EXPECT_EQ(member3, *member4.get_older_brother());
EXPECT_EQ(member4, *member3.get_younger_brother());
People member5;
member5.set_name("member5");
EXPECT_EQ(true, test.join_member(&member5));
EXPECT_EQ(test.get_root(), member5.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
EXPECT_EQ(member5, *test.get_root()->get_child()[2]);
EXPECT_EQ(member2, *member5.get_older_brother());
EXPECT_EQ(member5, *member2.get_younger_brother());
People position = *test.get_root();
EXPECT_EQ(true, test.go_to_first_child(position));
EXPECT_EQ(member, position);
EXPECT_EQ(true, test.go_to_first_child(position));
EXPECT_EQ(member3, position);
EXPECT_EQ(false, test.go_to_first_child(position));
position = member4;
EXPECT_EQ(false, test.go_to_first_child(position));
}
TEST(FamilytreeOlderBrotherTest, FamilytreeOlderBrotherTest)
{
Familytree test;
People member;
member.set_name("member");
EXPECT_EQ(true, test.join_member(&member));
EXPECT_EQ(test.get_root(), member.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
People member2;
member2.set_name("member2");
EXPECT_EQ(true, test.join_member(&member2));
EXPECT_EQ(test.get_root(), member2.get_parent());
EXPECT_EQ(member, *member2.get_older_brother());
EXPECT_EQ(member2, *member.get_younger_brother());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
People member3;
member3.set_name("member3");
EXPECT_EQ(true, test.join_member(&member3, &member));
EXPECT_EQ(member, *member3.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
People member4;
member4.set_name("member4");
EXPECT_EQ(true, test.join_member(&member4, &member));
EXPECT_EQ(member, *member4.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
EXPECT_EQ(member4, *member.get_child()[1]);
EXPECT_EQ(member3, *member4.get_older_brother());
EXPECT_EQ(member4, *member3.get_younger_brother());
People member5;
member5.set_name("member5");
EXPECT_EQ(true, test.join_member(&member5));
EXPECT_EQ(test.get_root(), member5.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
EXPECT_EQ(member5, *test.get_root()->get_child()[2]);
EXPECT_EQ(member2, *member5.get_older_brother());
EXPECT_EQ(member5, *member2.get_younger_brother());
People position = *test.get_root();
EXPECT_EQ(false, test.go_to_older_brother(position));
position = member;
EXPECT_EQ(false, test.go_to_older_brother(position));
position = member2;
EXPECT_EQ(true, test.go_to_older_brother(position));
EXPECT_EQ(member, position);
position = member3;
EXPECT_EQ(false, test.go_to_older_brother(position));
position = member4;
EXPECT_EQ(true, test.go_to_older_brother(position));
EXPECT_EQ(member3, position);
position = member5;
EXPECT_EQ(true, test.go_to_older_brother(position));
EXPECT_EQ(member2, position);
EXPECT_EQ(true, test.go_to_older_brother(position));
EXPECT_EQ(member, position);
}
TEST(FamilytreeYoungerBrotherTest, FamilytreeYoungerBrotherTest)
{
Familytree test;
People member;
member.set_name("member");
EXPECT_EQ(true, test.join_member(&member));
EXPECT_EQ(test.get_root(), member.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
People member2;
member2.set_name("member2");
EXPECT_EQ(true, test.join_member(&member2));
EXPECT_EQ(test.get_root(), member2.get_parent());
EXPECT_EQ(member, *member2.get_older_brother());
EXPECT_EQ(member2, *member.get_younger_brother());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
People member3;
member3.set_name("member3");
EXPECT_EQ(true, test.join_member(&member3, &member));
EXPECT_EQ(member, *member3.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
People member4;
member4.set_name("member4");
EXPECT_EQ(true, test.join_member(&member4, &member));
EXPECT_EQ(member, *member4.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
EXPECT_EQ(member4, *member.get_child()[1]);
EXPECT_EQ(member3, *member4.get_older_brother());
EXPECT_EQ(member4, *member3.get_younger_brother());
People member5;
member5.set_name("member5");
EXPECT_EQ(true, test.join_member(&member5));
EXPECT_EQ(test.get_root(), member5.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
EXPECT_EQ(member5, *test.get_root()->get_child()[2]);
EXPECT_EQ(member2, *member5.get_older_brother());
EXPECT_EQ(member5, *member2.get_younger_brother());
People position = *test.get_root();
EXPECT_EQ(false, test.go_to_younger_brother(position));
position = member;
EXPECT_EQ(true, test.go_to_younger_brother(position));
EXPECT_EQ(member2, position);
EXPECT_EQ(true, test.go_to_younger_brother(position));
EXPECT_EQ(member5, position);
EXPECT_EQ(false, test.go_to_younger_brother(position));
position = member3;
EXPECT_EQ(true, test.go_to_younger_brother(position));
EXPECT_EQ(member4, position);
EXPECT_EQ(false, test.go_to_younger_brother(position));
}
TEST(FamilytreeParentTest, FamilytreeParentTest)
{
Familytree test;
People member;
member.set_name("member");
EXPECT_EQ(true, test.join_member(&member));
EXPECT_EQ(test.get_root(), member.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
People member2;
member2.set_name("member2");
EXPECT_EQ(true, test.join_member(&member2));
EXPECT_EQ(test.get_root(), member2.get_parent());
EXPECT_EQ(member, *member2.get_older_brother());
EXPECT_EQ(member2, *member.get_younger_brother());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
People member3;
member3.set_name("member3");
EXPECT_EQ(true, test.join_member(&member3, &member));
EXPECT_EQ(member, *member3.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
People member4;
member4.set_name("member4");
EXPECT_EQ(true, test.join_member(&member4, &member));
EXPECT_EQ(member, *member4.get_parent());
EXPECT_EQ(member3, *member.get_child()[0]);
EXPECT_EQ(member4, *member.get_child()[1]);
EXPECT_EQ(member3, *member4.get_older_brother());
EXPECT_EQ(member4, *member3.get_younger_brother());
People member5;
member5.set_name("member5");
EXPECT_EQ(true, test.join_member(&member5));
EXPECT_EQ(test.get_root(), member5.get_parent());
EXPECT_EQ(member, *test.get_root()->get_child()[0]);
EXPECT_EQ(member2, *test.get_root()->get_child()[1]);
EXPECT_EQ(member5, *test.get_root()->get_child()[2]);
EXPECT_EQ(member2, *member5.get_older_brother());
EXPECT_EQ(member5, *member2.get_younger_brother());
People position = *test.get_root();
EXPECT_EQ(false, test.go_to_parent(position));
position = member;
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(*test.get_root(), position);
EXPECT_EQ(false, test.go_to_parent(position));
position = member2;
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(*test.get_root(), position);
EXPECT_EQ(false, test.go_to_parent(position));
position = member3;
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(member, position);
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(*test.get_root(), position);
EXPECT_EQ(false, test.go_to_parent(position));
position = member4;
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(member, position);
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(*test.get_root(), position);
EXPECT_EQ(false, test.go_to_parent(position));
position = member5;
EXPECT_EQ(true, test.go_to_parent(position));
EXPECT_EQ(*test.get_root(), position);
EXPECT_EQ(false, test.go_to_parent(position));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment