Thread: C++ Guided Design Programming Challenge

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    1,619

    C++ Guided Design Programming Challenge

    Alright, this is not an attempt to compete with the contests that Prelude does a great job running, rather it complements those contests. The point of Prelude's contests is to compete with one another, this is a thread dedicated to cooperation and collaboration. It's on the C++ board as this will be a C++ only challenge.

    Ground rules are simple, anyone can participate, but try not to duplicate effort -- please read other people's replies. As the whole point is to have participation of as many people as are interested, I also ask that people not give too many answers all at once -- give a few, and let others have a chance before you give more. Contributions should be posted to this thread. Feel free to discuss and critique solutions, but as always, keep criticism constructive.

    Dunno how much interest people have in this kind of thing, but I think guided projects are a great learning tool (I did one last semester with a class I taught, and they liked it a lot). Hopefully people will think this is a worthwhile pursuit.

    The focus of this project is to develop and use good programming techniques.

    All that being said, the problem statement and the first design step are below. Once I think this step has been completed successfully, the next gets posted:

    Problem Statement
    -----------------------------------------------------------
    A queue is a data structure which is similar to the line at your local grocery. Data enters the queue at the tail (the "back of the line") and leaves at the head. Once the head leaves the line, the person who was next becomes the new head of the line.

    In this project, we will implement and test a Queue class. The data will be of arbitrary type, T, so we will use templates. This Queue class will also allow us to optionally specify a maximum capacity of the Queue, after which no new data may be queued at the tail until data is removed from the head.

    Step #1 - Interface
    -----------------------------------------------------------
    The interface is the collection of methods exposed as public or protected, as well as friend or other helper functions (which are counted as part of the public interface).

    List methods that we will need or want to include in our Queue class. Don't worry about how we will implement them, just give their signatures and a brief description (one to four lines describing what the function does). Also include relevant information about the method. For example, we will have a default constructor:

    Queue();
    // Creates an empty Queue object that has no capacity specified.
    // Access : public member
    // Parameters: None
    // Returns: N/A

    At this point, we're not even thinking about private data members or private methods, just the public and protected interfaces.

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    T& GetHead()
    // Gets the object at the head of the queue
    // Access : public member
    // Parameters: None
    // Returns: a reference(for efficiency) to the type of object(T) stored in the queue
    Last edited by 7stud; 08-24-2003 at 10:15 PM.

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Code:
    template <class T>
    struct queue {
    ~queue();
    queue();
    queue(const queue & replicate);
    template <class Iter>
    queue(const Iter & _begin, const Iter & _end);
    queue & copy(const queue & replicate);
    // fill with values from another type of container:
    template <class Iter>
    queue & copy(const Iter & _begin, const Iter & _end);
    // returns a dynamically allocated copy:
    queue * clone() const;
    };
    Last edited by Sebastiani; 08-25-2003 at 07:22 AM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    1)...also ask that people not give too many answers all at once

    2) just give their signatures and a brief description (one to four lines describing what the function does). Also include relevant information about the method.

    Sprechen Sie English Sebastiani?
    Last edited by 7stud; 08-25-2003 at 02:25 AM.

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    void push_back(T);
    //adds value T to the end of queue, if queue size not at max size,
    //and increments private variable member itsSize by one;
    //if size is already at max, then sends message to user of error
    //and doesn't add current item to queue
    //or
    //automatically pops first item off queue (decreasing itsSize by 1)
    //and then pushes current item on back of queue with or without
    //notifying user
    //how to handle a "full" queue is a matter of design preference I
    //guess
    //access: public

    int size();
    //returns the number of items in the queue;
    //access: public

    int itsSize;
    //holds the current number of items in the queue
    //access: private
    Last edited by elad; 08-25-2003 at 12:14 PM.

  6. #6
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    push_back() might as well be push() since you can't add values to the head of the queue

    void pop()
    //takes the last value off of the queue
    //decrements itsSize by one
    //access: public
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    true, but putting the _back in there makes it explicit where you are pushing the value. Likewise, I would argue to use pop_front(), for better understanding----we'll be popping the "oldest" value put in the queue, not the "youngest". But it's just a matter of personal taste.

    BTW, I would have pop() (or pop_front()) return type T, not void. That way if I want to ignore the return, I can, but if I want to use it, I can, too.
    Last edited by elad; 08-25-2003 at 12:02 PM.

  8. #8
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    elad,

    I agree with you about the descriptive nature of your function name. I guess the same thing could be said about the GetHead() function I suggested: you can only get objects from the head of the queue, so it could be named just Get().

    Also, why not have push_back() return a reference to T?

  9. #9
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    Also, wouldn't push_back() only return an object if the queue was full? If the queue wasn't full you would have to return some kind of zeroed out object--maybe it's better if it returns void?
    Last edited by 7stud; 08-25-2003 at 12:13 PM.

  10. #10
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    How about using front() or first() instead of GetHead(). That way, irrespective of the private access container the queue is based on (given the defined size the queue class could be based on an array/vector or a list) we would know that we were looking for the item at the front of the queue---head in the case of list, and index 0 in the case of an array/vector.

    I guess we have to decide how to handle a call to push_back() when the queue is full to decide whether to return something other than void or not. I agree there seems to be benefit to returning something other than void in some conditions.

  11. #11
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    get_first(), push_last()?

    I still don't understand how you want to implement push_last() with a return type, since if the queue isn't full there is nothing to return?
    Last edited by 7stud; 08-25-2003 at 02:11 PM.

  12. #12
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    How about Append() for adding something to the stack?

    append implies that the action takes place at the end.
    I can't come up with an english word for doing the oppsite action on the first element, however. It would have to mean something like cut off and return the first element, pull all other elements one down. (Of course we'd just relink the elements and not decrement their position like in an array, but thats what you'd say to describe the process).
    Last edited by darksaidin; 08-25-2003 at 02:19 PM.
    [code]

    your code here....

    [/code]

  13. #13
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Originally posted by elad
    true, but putting the _back in there makes it explicit where you are pushing the value. Likewise, I would argue to use pop_front(), for better understanding----we'll be popping the "oldest" value put in the queue, not the "youngest". But it's just a matter of personal taste.

    BTW, I would have pop() (or pop_front()) return type T, not void. That way if I want to ignore the return, I can, but if I want to use it, I can, too.
    There is one possible pitfall in this approach, you sacrifice exception safety (which is why the STL never allows this). Because you are returning an object that is being removed from the queue, you must return by copy. And if this copy constructor fails, and throws, then the object is no longer retrievable -- it's gone from the queue but never made it back to the caller.

    For this reason, the two effects of the traditional pop (to remove the next item and to return that item) are split into two methods, neither of which can fail. And if the client code uses copy constructor/assignment operator with the return from GetHead(), and this fails, the object was never removed from the queue so they can try again.

    And there is a good point brought up -- how should we handle a full queue? My first thought was to throw an exception derived from std::logic_error, but I'd like to hear other ideas.

  14. #14
    Registered User
    Join Date
    May 2002
    Posts
    66
    Code:
    #include <deque>

  15. #15
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    How about Append() for adding something to the stack?
    Well that might make things confusing, because although you are adding to the "tail" the way things actually are is like this:

    Code:
    push-->tail-------------head-->pop
    "push" makes it clear that you are pushing all the values foward, not just adding one to the end.

    Code:
    #include <deque>
    If you are going to waste our time with a useless post why not just:
    Code:
    #include <queue>
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. which design is better to wrap another class instance
    By George2 in forum C++ Programming
    Replies: 7
    Last Post: 04-13-2008, 12:27 AM
  2. Implementing Inheritence into your design
    By bobthebullet990 in forum C++ Programming
    Replies: 6
    Last Post: 08-05-2006, 04:40 PM
  3. Opinions on new site design
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 23
    Last Post: 01-21-2005, 01:34 PM
  4. Cprog tutorial: Design Patterns
    By maes in forum C++ Programming
    Replies: 7
    Last Post: 10-11-2004, 01:41 AM