Code critique please

From: Adrian (nntp_at_bluedreamer.com)
Date: 10/30/04 

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

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

std::ostream &operator<<(std::ostream &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 =====================