Code critique please

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::eek:stream &operator<<(std::eek: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::eek: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::print(std::eek:stream &os) const
{
os << name_ << " " << mark_;
}

std::eek:stream &operator<<(std::eek: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 =====================
 
B

Bob Hairgrove

On Sat, 30 Oct 2004 18:00:34 +0000 (UTC), Adrian

(just a few comments written inline...hopefully you don't expect us to
do your homework for you...)
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)
Click to expand...

This should be const, e.g.:
bool operator()(const A &lhs, const A &rhs) const
{
return lhs < rhs;
};
};


template<class A>
struct SortOrder2 : SortOrder<A>
{
bool operator()(const A &lhs, const A &rhs)
Click to expand...

Same thing...
{
return lhs > rhs;
};
};

//********************************************************************************

class Mark
{
public:
Mark(const std::string &name="", int mark=0);
Click to expand...

The default value for the string shouldn't be necessary if you provide
an additional constructor taking only an int.
friend std::eek:stream &operator<<(std::eek: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::eek:stream &os) const;

std::string name_;
int mark_;
};

struct Sort1 : SortOrder<Mark>
{
bool operator()(const Mark &lhs, const Mark &rhs)
Click to expand...
const

[rest of homework snipped, as I don't have time to compile/debug it]
 
A

Adrian

Bob said:
On Sat, 30 Oct 2004 18:00:34 +0000 (UTC), Adrian

(just a few comments written inline...hopefully you don't expect us to
do your homework for you...)
Click to expand...
Thanks for the comments, the homework was handed in over 12 months ago
and got an A+, but as a professional c++ developer I personally think we
should answer everyone's c++ homework questions, this will then increase
the glut of incompetent c++ programmers on the market and thus increase
my (and your) market rate :), just my humble opinion, and I understand
the general feeling of the group on this subject.

I missed the const stuff on the sort functions, thanks for that.


Adrian

"Statistically speaking, remember that half the people you meet are
below average."
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Is there in memory tree structure faster than std::map? 11
Chatbot 0
Extensible 'resource' loading design critique 2
Custom matrix multiplication produces different results to glm 0
Why the destructor executes after its friend operator (in which thereis a copy constructor) runs 5
Is this a good reference-counting smart pointer class? 10
Critique requested..... 5
Operator overloading and inheritence: Code critique please 16

Members online

Total: 57 (members: 1, guests: 56)
Robots: 420

Forum statistics

Threads
473,982
Messages
2,570,190
Members
46,740
Latest member
AdolphBig6

Latest Threads

Top