A
Adrian
Hi all,
A while ago while I was doing a part time c++ course at uni and we where
asked to write a code solution to a little problem. The idea being that
you can type in either a name or a mark and return all results that
match what you typed. The code had to include a doubly linked binary
tree. (sorry dont have the original problem description to hand).
My result is below, I know it is way over engineered for the problem at
hand (but I have always wanted to write my own iterators) but I was
testing my limits of c++ and would like to know what you think.
Input file is a the end.
Style comments also appreciated, although I do realise this could be a
controversial subject
Ok, I know all the code is lumped into a single file, but easier for
posting.
Thanks
Adrian
============================ code ======================================
#include <iostream>
#include <ostream>
#include <istream>
#include <string>
#include <functional>
#include <vector>
#include <set>
#include <string>
#include <fstream>
#include <sstream>
//********************************************************************************
template<class A>
struct SortOrder : std::binary_function<const A &, const A &, bool>
{
};
template<class A>
struct SortOrder1 : SortOrder<A>
{
bool operator()(const A &lhs, const A &rhs)
{
return lhs < rhs;
};
};
template<class A>
struct SortOrder2 : SortOrder<A>
{
bool operator()(const A &lhs, const A &rhs)
{
return lhs > rhs;
};
};
//********************************************************************************
class Mark
{
public:
Mark(const std::string &name="", int mark=0);
friend std:stream &operator<<(std:stream &os, const Mark &rhs);
friend std::istream &operator>>(std::istream &is, Mark &rhs);
friend class Sort1;
friend class Sort2;
friend bool operator==(const Mark &lhs, const Mark &rhs);
private:
void read(std::istream &is);
void print(std:stream &os) const;
std::string name_;
int mark_;
};
struct Sort1 : SortOrder<Mark>
{
bool operator()(const Mark &lhs, const Mark &rhs)
{
if(lhs.name_!=rhs.name_)
{
return (lhs.name_ < rhs.name_);
}
else
{
return (lhs.mark_ > rhs.mark_);
}
};
};
struct Sort2 : SortOrder<Mark>
{
bool operator()(const Mark &lhs, const Mark &rhs)
{
if(lhs.mark_!=rhs.mark_)
{
return (lhs.mark_ > rhs.mark_);
}
else
{
return (lhs.name_ < rhs.name_);
}
};
};
Mark::Mark(const std::string &name, int mark)
:name_(name),
mark_(mark)
{
}
void Mark::read(std::istream &is)
{
Mark temp;
is >> temp.name_;
is >> temp.mark_;
if(is)
{
*this=temp;
}
}
void Mark:rint(std:stream &os) const
{
os << name_ << " " << mark_;
}
std:stream &operator<<(std:stream &os, const Mark &rhs)
{
rhs.print(os);
return os;
}
std::istream &operator>>(std::istream &is, Mark &rhs)
{
rhs.read(is);
return is;
}
bool operator==(const Mark &lhs, const Mark &rhs)
{
bool name_match=false;
bool score_match=false;
if(lhs.name_==rhs.name_ || lhs.name_=="*" || rhs.name_=="*")
{
name_match=true;
}
if(lhs.mark_==rhs.mark_ || lhs.mark_==-1 || rhs.mark_==-1)
{
score_match=true;
}
return name_match && score_match;
}
//********************************************************************************
template<class Node>
class TreeIterator;
template<class T, class SO1=SortOrder1<T>, class SO2=SortOrder2<T> >
class Tree
{
private:
struct Node
{
Node() : sort2_left(0), sort2_right(0) {};
typedef std::auto_ptr<Node> Node_ptr_t;
static Node_ptr_t CreateNode() { return Node_ptr_t(new Node); };
const T &operator*() const { return data_; };
const T* operator->() const { return &data_; };
static Node *s1_left(Node *ptr) { return (ptr->sort1_left).get(); };
static Node *s1_right(Node *ptr) { return
(ptr->sort1_right).get(); };
static Node *s2_left(Node *ptr) { return (ptr->sort2_left).get(); };
static Node *s2_right(Node *ptr) { return
(ptr->sort2_right).get(); };
T *data_;
typedef T value_type;
Node_ptr_t sort1_left;
Node_ptr_t sort1_right;
Node_ptr_t sort2_left;
Node_ptr_t sort2_right;
};
typedef std::vector<T *> DataPtrs_t;
public:
typedef TreeIterator<Node> const_iterator;
typedef size_t size_type;
enum SortOrder_t { Order1_e, Order2_e};
Tree() :count_(0) {};
~Tree()
{
for(typename DataPtrs_t::const_iterator i=data_ptrs_.begin();
i!=data_ptrs_.end(); ++i)
{
delete (*i);
}
};
size_type size() const { return count_; };
const_iterator s1_begin() const { return
const_iterator(root_.get(), root_.get()->s1_left, root_.get()->s1_right); }
const_iterator s2_begin() const { return
const_iterator(root_.get(), root_.get()->s2_left, root_.get()->s2_right); }
const_iterator end() const { return const_iterator(); }
const_iterator find(const T &data, const_iterator from, SortOrder_t
so=Order1_e) const
{
while(from!=end())
{
if(*from==data)
{
return from;
}
++from;
}
return const_iterator();
};
void Insert(const T &data);
private:
SO1 Sort1;
SO2 Sort2;
void add_sort1(typename Node::Node_ptr_t new_node, typename
Node::Node_ptr_t &existing_node);
void add_sort2(typename Node::Node_ptr_t new_node, typename
Node::Node_ptr_t &existing_node);
size_type count_;
typename Node::Node_ptr_t root_;
DataPtrs_t data_ptrs_;
};
template<class T, class SO1, class SO2>
void Tree<T, SO1, SO2>::Insert(const T &data)
{
data_ptrs_.push_back(new T(data));
typename Node::Node_ptr_t new_node(Node::CreateNode());
new_node->data_=data_ptrs_.back();
add_sort1(new_node, root_);
if(count_!=1)
{
typename Node::Node_ptr_t new_node_s2(Node::CreateNode());
new_node_s2->data_=data_ptrs_.back();
add_sort2(new_node_s2, root_);
}
}
template<class T, class SO1, class SO2>
void Tree<T, SO1, SO2>::add_sort1(typename Node::Node_ptr_t new_node,
typename Node::Node_ptr_t &existing_node)
{
if(existing_node.get()==0)
{
existing_node=new_node;
++count_;
}
else
{
if(Sort1.operator()(*new_node->data_, *existing_node->data_) )
{
add_sort1(new_node, existing_node->sort1_left);
}
else
{
add_sort1(new_node, existing_node->sort1_right);
}
}
}
template<class T, class SO1, class SO2>
void Tree<T, SO1, SO2>::add_sort2(typename Node::Node_ptr_t new_node,
typename Node::Node_ptr_t &existing_node)
{
if(existing_node.get()==0)
{
existing_node=new_node;
}
else
{
if(Sort2.operator()(*new_node->data_, *existing_node->data_) )
{
add_sort2(new_node, existing_node->sort2_left);
}
else
{
add_sort2(new_node, existing_node->sort2_right);
}
}
}
//********************************************************************************
template<class Node>
class TreeIterator : public std::iterator<std::input_iterator_tag, void,
void, void, void>
{
public:
typedef Node *(* traversal_func)(Node *);
explicit TreeIterator(Node *root=0, traversal_func left=0,
traversal_func right=0)
:node_(root),
left_(left),
right_(right)
{
path_.push_back(0); // save a null as the top of the path
Node *ptr=node_;
while(ptr && left(ptr))
{
path_.push_back(ptr);
ptr=left(ptr);
}
node_=ptr;
};
bool operator!=(const TreeIterator &rhs) const { return
(node_!=rhs.node_); };
void operator++() const
{
processed_.insert(node_);
if(right(node_))
{
node_=right(node_);
while(left(node_))
{
path_.push_back(node_);
node_=left(node_);
}
}
else
{
while(processed_.find(node_)!=processed_.end())
{
node_=path_.back();
path_.pop_back();
}
}
};
const typename Node::value_type &operator*() const { return
*node_->data_; };
private:
Node *left(Node *ptr) const { return left_?left_(ptr):0; };
Node *right(Node *ptr) const { return right_?right_(ptr):0; };
mutable Node *node_;
traversal_func left_;
traversal_func right_;
mutable std::vector<Node *> path_;
mutable std::set<Node *> processed_;
};
//********************************************************************************
int main(int argc, char *argv[])
{
typedef Tree<Mark, Sort1, Sort2> marktree_t;
marktree_t tree;
std::ifstream in("a6p.txt");
Mark mark;
while(in >> mark)
{
tree.Insert(mark);
}
std::cout << "Name order:" << std::endl;
for(marktree_t::const_iterator i=tree.s1_begin(); i!=tree.end(); ++i)
{
std::cout << (*i) << std::endl;
}
std::cout << std::endl << "Mark order:" << std::endl;
for(marktree_t::const_iterator i=tree.s2_begin(); i!=tree.end(); ++i)
{
std::cout << (*i) << std::endl;
}
std::string result;
while(true)
{
std::cout << std::endl << "Type in a name or a mark or ! to quit: "
<< std::flush;
getline(std::cin, result);
if(result=="!")
{
break;
}
std::stringstream strm(result);
int mark=-1;
strm >> mark;
std::string name(result);
if(mark>0)
{
name="*";
}
Mark temp(name, mark);
marktree_t::const_iterator i=tree.find(temp, tree.s1_begin());
if(i!=tree.end())
{
do
{
std::cout << (*i) << " ";
++i;
} while((i=tree.find(temp, i))!=tree.end());
}
else
{
std::cout << result << " not there";
}
std::cout << std::endl;
}
return 0;
}
============================ end of code ===========================
============================ input file ============================
Heald 50
Kitchen 26
Bogie 74
Day 50
Austin 44
Warren 50
Gray 30
Inglethorpe 71
Bart-Williams 76
Zoricich 52
Achampong 75
Whitbread 80
Carter 50
Cockerill 99
Berry 22
West 40
Hackett 50
Howard 40
Jones 55
Stanislaus 9
============================ end of input file =====================
A while ago while I was doing a part time c++ course at uni and we where
asked to write a code solution to a little problem. The idea being that
you can type in either a name or a mark and return all results that
match what you typed. The code had to include a doubly linked binary
tree. (sorry dont have the original problem description to hand).
My result is below, I know it is way over engineered for the problem at
hand (but I have always wanted to write my own iterators) but I was
testing my limits of c++ and would like to know what you think.
Input file is a the end.
Style comments also appreciated, although I do realise this could be a
controversial subject
Ok, I know all the code is lumped into a single file, but easier for
posting.
Thanks
Adrian
============================ code ======================================
#include <iostream>
#include <ostream>
#include <istream>
#include <string>
#include <functional>
#include <vector>
#include <set>
#include <string>
#include <fstream>
#include <sstream>
//********************************************************************************
template<class A>
struct SortOrder : std::binary_function<const A &, const A &, bool>
{
};
template<class A>
struct SortOrder1 : SortOrder<A>
{
bool operator()(const A &lhs, const A &rhs)
{
return lhs < rhs;
};
};
template<class A>
struct SortOrder2 : SortOrder<A>
{
bool operator()(const A &lhs, const A &rhs)
{
return lhs > rhs;
};
};
//********************************************************************************
class Mark
{
public:
Mark(const std::string &name="", int mark=0);
friend std:
stream &operator<<(std:stream &os, const Mark &rhs);friend std::istream &operator>>(std::istream &is, Mark &rhs);
friend class Sort1;
friend class Sort2;
friend bool operator==(const Mark &lhs, const Mark &rhs);
private:
void read(std::istream &is);
void print(std:
stream &os) const;std::string name_;
int mark_;
};
struct Sort1 : SortOrder<Mark>
{
bool operator()(const Mark &lhs, const Mark &rhs)
{
if(lhs.name_!=rhs.name_)
{
return (lhs.name_ < rhs.name_);
}
else
{
return (lhs.mark_ > rhs.mark_);
}
};
};
struct Sort2 : SortOrder<Mark>
{
bool operator()(const Mark &lhs, const Mark &rhs)
{
if(lhs.mark_!=rhs.mark_)
{
return (lhs.mark_ > rhs.mark_);
}
else
{
return (lhs.name_ < rhs.name_);
}
};
};
Mark::Mark(const std::string &name, int mark)
:name_(name),
mark_(mark)
{
}
void Mark::read(std::istream &is)
{
Mark temp;
is >> temp.name_;
is >> temp.mark_;
if(is)
{
*this=temp;
}
}
void Mark:
rint(std:stream &os) const{
os << name_ << " " << mark_;
}
std:
stream &operator<<(std:stream &os, const Mark &rhs){
rhs.print(os);
return os;
}
std::istream &operator>>(std::istream &is, Mark &rhs)
{
rhs.read(is);
return is;
}
bool operator==(const Mark &lhs, const Mark &rhs)
{
bool name_match=false;
bool score_match=false;
if(lhs.name_==rhs.name_ || lhs.name_=="*" || rhs.name_=="*")
{
name_match=true;
}
if(lhs.mark_==rhs.mark_ || lhs.mark_==-1 || rhs.mark_==-1)
{
score_match=true;
}
return name_match && score_match;
}
//********************************************************************************
template<class Node>
class TreeIterator;
template<class T, class SO1=SortOrder1<T>, class SO2=SortOrder2<T> >
class Tree
{
private:
struct Node
{
Node() : sort2_left(0), sort2_right(0) {};
typedef std::auto_ptr<Node> Node_ptr_t;
static Node_ptr_t CreateNode() { return Node_ptr_t(new Node); };
const T &operator*() const { return data_; };
const T* operator->() const { return &data_; };
static Node *s1_left(Node *ptr) { return (ptr->sort1_left).get(); };
static Node *s1_right(Node *ptr) { return
(ptr->sort1_right).get(); };
static Node *s2_left(Node *ptr) { return (ptr->sort2_left).get(); };
static Node *s2_right(Node *ptr) { return
(ptr->sort2_right).get(); };
T *data_;
typedef T value_type;
Node_ptr_t sort1_left;
Node_ptr_t sort1_right;
Node_ptr_t sort2_left;
Node_ptr_t sort2_right;
};
typedef std::vector<T *> DataPtrs_t;
public:
typedef TreeIterator<Node> const_iterator;
typedef size_t size_type;
enum SortOrder_t { Order1_e, Order2_e};
Tree() :count_(0) {};
~Tree()
{
for(typename DataPtrs_t::const_iterator i=data_ptrs_.begin();
i!=data_ptrs_.end(); ++i)
{
delete (*i);
}
};
size_type size() const { return count_; };
const_iterator s1_begin() const { return
const_iterator(root_.get(), root_.get()->s1_left, root_.get()->s1_right); }
const_iterator s2_begin() const { return
const_iterator(root_.get(), root_.get()->s2_left, root_.get()->s2_right); }
const_iterator end() const { return const_iterator(); }
const_iterator find(const T &data, const_iterator from, SortOrder_t
so=Order1_e) const
{
while(from!=end())
{
if(*from==data)
{
return from;
}
++from;
}
return const_iterator();
};
void Insert(const T &data);
private:
SO1 Sort1;
SO2 Sort2;
void add_sort1(typename Node::Node_ptr_t new_node, typename
Node::Node_ptr_t &existing_node);
void add_sort2(typename Node::Node_ptr_t new_node, typename
Node::Node_ptr_t &existing_node);
size_type count_;
typename Node::Node_ptr_t root_;
DataPtrs_t data_ptrs_;
};
template<class T, class SO1, class SO2>
void Tree<T, SO1, SO2>::Insert(const T &data)
{
data_ptrs_.push_back(new T(data));
typename Node::Node_ptr_t new_node(Node::CreateNode());
new_node->data_=data_ptrs_.back();
add_sort1(new_node, root_);
if(count_!=1)
{
typename Node::Node_ptr_t new_node_s2(Node::CreateNode());
new_node_s2->data_=data_ptrs_.back();
add_sort2(new_node_s2, root_);
}
}
template<class T, class SO1, class SO2>
void Tree<T, SO1, SO2>::add_sort1(typename Node::Node_ptr_t new_node,
typename Node::Node_ptr_t &existing_node)
{
if(existing_node.get()==0)
{
existing_node=new_node;
++count_;
}
else
{
if(Sort1.operator()(*new_node->data_, *existing_node->data_) )
{
add_sort1(new_node, existing_node->sort1_left);
}
else
{
add_sort1(new_node, existing_node->sort1_right);
}
}
}
template<class T, class SO1, class SO2>
void Tree<T, SO1, SO2>::add_sort2(typename Node::Node_ptr_t new_node,
typename Node::Node_ptr_t &existing_node)
{
if(existing_node.get()==0)
{
existing_node=new_node;
}
else
{
if(Sort2.operator()(*new_node->data_, *existing_node->data_) )
{
add_sort2(new_node, existing_node->sort2_left);
}
else
{
add_sort2(new_node, existing_node->sort2_right);
}
}
}
//********************************************************************************
template<class Node>
class TreeIterator : public std::iterator<std::input_iterator_tag, void,
void, void, void>
{
public:
typedef Node *(* traversal_func)(Node *);
explicit TreeIterator(Node *root=0, traversal_func left=0,
traversal_func right=0)
:node_(root),
left_(left),
right_(right)
{
path_.push_back(0); // save a null as the top of the path
Node *ptr=node_;
while(ptr && left(ptr))
{
path_.push_back(ptr);
ptr=left(ptr);
}
node_=ptr;
};
bool operator!=(const TreeIterator &rhs) const { return
(node_!=rhs.node_); };
void operator++() const
{
processed_.insert(node_);
if(right(node_))
{
node_=right(node_);
while(left(node_))
{
path_.push_back(node_);
node_=left(node_);
}
}
else
{
while(processed_.find(node_)!=processed_.end())
{
node_=path_.back();
path_.pop_back();
}
}
};
const typename Node::value_type &operator*() const { return
*node_->data_; };
private:
Node *left(Node *ptr) const { return left_?left_(ptr):0; };
Node *right(Node *ptr) const { return right_?right_(ptr):0; };
mutable Node *node_;
traversal_func left_;
traversal_func right_;
mutable std::vector<Node *> path_;
mutable std::set<Node *> processed_;
};
//********************************************************************************
int main(int argc, char *argv[])
{
typedef Tree<Mark, Sort1, Sort2> marktree_t;
marktree_t tree;
std::ifstream in("a6p.txt");
Mark mark;
while(in >> mark)
{
tree.Insert(mark);
}
std::cout << "Name order:" << std::endl;
for(marktree_t::const_iterator i=tree.s1_begin(); i!=tree.end(); ++i)
{
std::cout << (*i) << std::endl;
}
std::cout << std::endl << "Mark order:" << std::endl;
for(marktree_t::const_iterator i=tree.s2_begin(); i!=tree.end(); ++i)
{
std::cout << (*i) << std::endl;
}
std::string result;
while(true)
{
std::cout << std::endl << "Type in a name or a mark or ! to quit: "
<< std::flush;
getline(std::cin, result);
if(result=="!")
{
break;
}
std::stringstream strm(result);
int mark=-1;
strm >> mark;
std::string name(result);
if(mark>0)
{
name="*";
}
Mark temp(name, mark);
marktree_t::const_iterator i=tree.find(temp, tree.s1_begin());
if(i!=tree.end())
{
do
{
std::cout << (*i) << " ";
++i;
} while((i=tree.find(temp, i))!=tree.end());
}
else
{
std::cout << result << " not there";
}
std::cout << std::endl;
}
return 0;
}
============================ end of code ===========================
============================ input file ============================
Heald 50
Kitchen 26
Bogie 74
Day 50
Austin 44
Warren 50
Gray 30
Inglethorpe 71
Bart-Williams 76
Zoricich 52
Achampong 75
Whitbread 80
Carter 50
Cockerill 99
Berry 22
West 40
Hackett 50
Howard 40
Jones 55
Stanislaus 9
============================ end of input file =====================