Code critique please

Discussion in 'C++' started by Adrian, Oct 30, 2004.

  1. Adrian

    Adrian Guest

    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 =====================
    Adrian, Oct 30, 2004
    #1
    1. Advertising

  2. On Sat, 30 Oct 2004 18:00:34 +0000 (UTC), Adrian
    <> wrote:

    (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)


    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)


    Same thing...

    > {
    > return lhs > rhs;
    > };
    >};
    >
    >//********************************************************************************
    >
    >class Mark
    >{
    > public:
    > Mark(const std::string &name="", int mark=0);


    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)

    const

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

    --
    Bob Hairgrove
    Bob Hairgrove, Oct 30, 2004
    #2
    1. Advertising

  3. Adrian

    Adrian Guest

    Bob Hairgrove wrote:
    > On Sat, 30 Oct 2004 18:00:34 +0000 (UTC), Adrian
    > <> wrote:
    >
    > (just a few comments written inline...hopefully you don't expect us to
    > do your homework for you...)

    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."
    Adrian, Oct 31, 2004
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Michael Strorm
    Replies:
    26
    Views:
    752
    J. Campbell
    Nov 10, 2003
  2. Rv5

    Code Critique Please

    Rv5, Nov 16, 2003, in forum: C++
    Replies:
    3
    Views:
    349
    Benny Hill
    Nov 16, 2003
  3. gorda
    Replies:
    16
    Views:
    761
    Karl Heinz Buchegger
    Jul 29, 2004
  4. Rv5

    Code Critique Please

    Rv5, Nov 16, 2003, in forum: C Programming
    Replies:
    2
    Views:
    324
    -berlin.de
    Nov 16, 2003
  5. Brian Blais

    critique my code, please

    Brian Blais, Feb 6, 2006, in forum: Python
    Replies:
    3
    Views:
    324
    Frithiof Andreas Jensen
    Feb 8, 2006
Loading...

Share This Page