C++ Guided Design Programming Challenge

This is a discussion on C++ Guided Design Programming Challenge within the C++ Programming forums, part of the General Programming Boards category; I'll start: Code: class CQueue { public: // other methods int GetCount() { return count; } bool IsEmpty(); private: // ...

  1. #31
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    I'll start:
    Code:
    class CQueue
    {
    public:
         // other methods
         int       GetCount()			{ return count; }
         bool	IsEmpty();
    
    private:
         // other vars
         int       count;
    };
    
    bool CQueue::IsEmpty()
    {
    	bool empty;
    
    	if(count)
    		empty = false;
    	else
    		empty = true;
    
    	return empty;
    }
    As you can no doubt tell the count variable will be incremented per push and decremented per pop, for whatever reason the user might want to know how many objects are in the queue, so GetCount simply returns count, and IsEmpty() will return true if queue is empty (i.e. count is 0), count should be set to 0 in CQueue's constructor.

    I took the easy ones, I hope that's what you're looking for.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  2. #32
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    Okay, good start, but an easier way to phrase it would be:

    Code:
    bool CQueue::IsEmpty()
    {
     return count == 0;
    }
    How would you implement IsFull() then?
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  3. #33
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    Well it depends how we're controlling the maximum, if it's just a variable then just return true if count == max, false otherwise.

    Btw I didn't know you could return like that from IsEmpty(), that's cool.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  4. #34
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    Originally posted by HybridM
    Btw I didn't know you could return like that from IsEmpty(), that's cool.
    return (count == 0); would probably be easier to read. Basically (count == 0) can either be true or false which will then be returned by return bool;

    Code:
    class CQueue
    {
      public:
        CQueue()			{ count= 0; count_max= 0; };
    
        // other methods
        int		GetCount()	{ return count; };
        bool	IsEmpty()	{ return (count == 0); };
        bool	IsFull()	{ return (count == count_max); };
    
      private:
        // other vars
        int	count;
        int	count_max; 	
    };
    Maybe add a non default constructor for limited size?
    Last edited by darksaidin; 08-29-2003 at 09:29 AM.
    [code]

    your code here....

    [/code]

  5. #35
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    Okay, so what is the underlying data structure going to be, then?

    How would you implement Pop(), provided it was implemented:

    1) on a list?

    2) on an array?
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  6. #36
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    Actually, I think we have not decided about this yet. Maybe it's Cat's turn to say something

    On a sidenote, my personal opinion is that push and pop are definetly the wrong names. This is not a stack where something can be pushed into and all previous elements will change their "position" in the stack (i.e. one rank up), where stuff get's pushed in and popped out at the same "side", this is a queue where data get's added to the end and taken from the beginning. (At least if I understood the excercise )

    Try to push somebody at the end of a reallife queue. Could be funny. For a second or two...
    Last edited by darksaidin; 08-29-2003 at 12:05 PM.
    [code]

    your code here....

    [/code]

  7. #37
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    OK, feel free to use something else, but this is how I implemented Pop in my queue, I called it "Serve()" as it fits the queue theme better.
    Code:
    int CQueue::Serve(bool Remove)
    {
    	int Value;
    	Node *Temp;
    
    	if(!IsEmpty())
    	{
    		Value = Front->GetData();
    		if(Remove)
    		{
    			--count;
    			Temp = Front;
    			if(count)
    			{
    				Front = Front->Next;
    			}
    			delete Temp;
    		}
    	}
    	else
    		cout << "Unable to serve, queue is empty." << endl;
    
    	return Value;
    }
    This may need some explanation, so here goes...
    The Remove boolean is there so the user can choose whether they wish to peek at the front of the queue (not remove) or remove as well as get value.

    A temporary Node is created so as to allow memory deallocation, value is assigned the data of the front node, so as to be returned, front is assigned to the node behind it, unless it is the last node in the queue. What used to be the front is then deleted through temp, and value is returned.

    I think that's all
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  8. #38
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    It would also be nice to have two (or more) different threads for this project: one for software engineers who just want to post the code and be done with everything, and one for those that want to learn something and maybe go at a slower pace.

    On a sidenote, my personal opinion is that push and pop are definetly the wrong names.

    Agreed.
    Last edited by 7stud; 08-29-2003 at 01:56 PM.

  9. #39
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Originally posted by Cat
    At this point, we're not even thinking about private data members or private methods, just the public and protected interfaces.
    I'm enjoying following this process and seeing people's ideas on how to implement this queue. Just wondering, did everybody agree on an interface? Or maybe the interface cannot be agreed upon without making decisions about implementation.

  10. #40
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    I think a forum is a difficult medium to conduct something like this, someone should do a simple website where people can submit their ideas, perhaps cat (or someone else if cat doesn't have the time) could screen them and launch votes to decide which we go with. On the same page we could also keep an up to date version of the project so far.

    It could be very cool, and could set cprogramming.com apart from the plethora of other boards.
    Last edited by HybridM; 08-31-2003 at 02:27 PM.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  11. #41
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    Originally posted by HybridM
    It could be very cool, and could set cprogramming.com apart from the plethora of other boards.
    You mean like defining new standards, reaching out for new worlds ...errr..?

    The topic was "C++ Guided Design Programming Challenge" and I think we should stick to that. If Cat's project is successful, it can still be extended.
    [code]

    your code here....

    [/code]

  12. #42
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    You mean like defining new standards, reaching out for new worlds ...errr..?
    Hmm..no.

    What I meant was it would make the whole experience easier for everyone and overall more enjoyable. It was a suggestion for if this sort of thing becomes regular.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  13. #43
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    I think this is what we have so far:

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

    Note that in the debate over whether the default size of the queue was intended to be unlimited or not, we overlooked the default constructor description:

    "Creates an empty Queue object that has no capacity specified. "

    I know grib and others argued against this, but the "client" has asked for that. Is this something in the real world where we would go back to the "client" and tell them the requirements they have imposed are not the best way to implement something and suggest they change the requirements, or are we to treat the requirements as set in stone? Since apparently we don't have any way to contact the client, I vote it's set in stone.
    -------------------

    bool append(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 returns false
    //and doesn't add current item to queue

    T& get_first();
    //Gets a reference to the object at the front of the queue, but
    //does nothing to the queue
    //Access: public
    //Parameters: none
    //Returns: A reference to the first object thereby avoiding the object's
    //copy constructor and preventing the operation from failing

    void discard_first()
    // Removes the first item from the queue and discards it
    // Access : public member
    // Parameters: None
    // Returns: void

    OR

    void push(const T &); // throws
    void forced_push(const T &); // best effort

    T & oldest(); // undefined on empty
    T & get_oldest(); // checks and throws
    ---------------------------

    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

    //iterators/pointers to the beginning and end values of the queue
    iterator begin();
    iterator end();

    and maybe:

    //current capacity (potential number of items of type T) of queue
    long capacity();
    -------

    1)We still need to decide if we want to throw exceptions when the queue is full. I don't really understand the argument for throwing exceptions. Is a full queue an exceptional event? If we decide it is, how will the exception be handled--what happens after the exception is thrown?

    3)Do we need a non-default constructor i.e. where a maximum size can be specified?

    2)Do we need a non-default destructor?

    Also, it might be helpful to reread the initial problem statement from time to time. This is some of what Cat had to say:
    ...the problem statement and the first design step are below. Once I think this step has been completed successfully, the next gets posted.

    ...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.
    I think it's safe to assume since Cat hasn't posted anything, we are not done with the first design step, and it's premature to start posting code.

  14. #44
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    Good work, 7Stud. Some additional thoughts, too:

    1) By default, the queue should have no maximum size. Allow this to be reversable, such that a user can set a limit, unset it, set it, ad infinitum.

    2) Exceptions are for more serious errors than full/empty queues.
    For these cases, either let the user crash, as happens with normal user errors (ie: out-of-bounds accesses, etc) OR simply have the ADT exhibit 'no-op' behaviour (ie: nothing happens at all).

    Let's say the user tries to get_front(), but the queue is empty.
    To implement the first sort of behaviour (crash 'n burn), just return a temporary object. Otherwise, the queue has a member of type T called 'dummy' that get's returned when that happens, and no harm is done.


    >> Do we need a non-default destructor?

    Absolutely, how else can we guarantee proper cleanup?
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  15. #45
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    I'm down with the limitable infinite queue now. I was working on a static_queue, where the storage would be a compile-time constant array, but getting it to be faster than deque is going to be more work than I expected, and insuring proper alignment for placement new (without resorting to boost) is more awkward than I want to deal with right now. If you're interested in where I was going with this have a look at boost's optional class, very clever way to get the space for an object and delay constructing it until absolutely necessary.

    As to the general issue of throwing, I look at this as a question of how bad would ignoring the issue be? The standard streams have all sorts of things that they want to tell you, no-one pays any attention to them. How many threads have we seen where the problem is that the file was never opened in the first place(it was in another directory etc..)? You shouldn't rely on exceptions as the normal way of discovering that a queue is full, but it might be a good way to encourage users to check first. It does add a lot of bloat, not just for the throw, but often checking the same thing twice, once before the call and in the method just before you do anything. I can also sympathize with the view that if you wanted this sort of safety you would be using Ada.

    I've confused the matter enough, here's my candidate for a final interface.

    Code:
    template<class T>
    class queue {
    public:
        typedef T value_type;     // comes in handy
        typedef size_t size_type; // future-proofing, clarity
       
        queue();          // infinite
        queue(size_type); // limited
    
        bool limited() const;    // true iff limit exists.
        void unlimit();          // removes any limit.
        void limit(size_type);   // sets new maximum number of elements
        size_type limit() const; // maximum number of elements if limited,
                                 // numeric_limits<size_type>.max() if unlimited
        size_type size() const;  // number of elements in queue
        bool empty() const;      // size() == 0
        bool full() const;       // limited() && size() == limit()
    
        bool append(const T &); // no-ops & returns false if full.
        void discard();         // removes oldest element.
        T & oldest();           // access oldest element, undefined if empty
    };
    I've gone with limit, as opposed to capacity, as capacity already has semantics in the stl, and our behavior is different. front also has semantics in stl, that matches our behavior here, but if we want to use front it should probably be just front (not get_front) to match the stl and discard_front should also probably be pop_front for the same reasons. However, we can't use push_back because we are very different from the stl here, so append is the logical choice. Once append is used it makes sense to define our own words for access and removal.

    There is one more outstanding issue. What should happen if we limit a queue to have fewer elements than it already has? I think that we should probably remove the most recently added elements until we are under the new limit, the users can remove the oldest themselves.

    good summary 7Stud, even if I did pick a lot of nits, I just like arguing these things.
    Last edited by grib; 09-01-2003 at 06:51 PM.

Page 3 of 3 FirstFirst 123
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, 12:34 PM
  4. Cprog tutorial: Design Patterns
    By maes in forum C++ Programming
    Replies: 7
    Last Post: 10-11-2004, 01:41 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21