Thread: Queue with a circular array... nitpick !

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Queue with a circular array... nitpick !

    Another one... Works fine(at least on my test cases); but .. for a second opinion.
    Is there a better way to represent the [warping / wrapping (not sure which!)] of the queue ?

    (Press Ctrl+W or Alt+F4 or the Big Red Button if terribly annoyed at these posts :P )

    Code:
    namespace mm
    {
    enum queue_error{overflow, underflow, beheaded};
    
    
    template<typename T, int Size>
    class queue
    {
    private:
        T mem[Size];
        int head_ptr;
        int tail_ptr;
        
        inline int diff(int pt1, int pt2) 
            {return pt1-pt2 >=0 ? pt1-pt2 : pt1+Size-pt2 ;}
        // pt1 - pt2 .. keeping 'circular' logic in mind
        inline void increment(int& ptr) { ptr++; ptr%=Size; };
        // incrementing, and wrapping around when necessary 
    public:
        queue():head_ptr(1),tail_ptr(0){};
        void push(const T& in)
        {
            if(this->full()) throw(overflow);
            increment(tail_ptr);        
            mem[tail_ptr] = in ; 
        };
        
        void pop()
        {
            if(this->empty()) throw(underflow);
            increment(head_ptr);
        };
        
        T& head()
        {
            if(this->empty())throw(beheaded);
            return mem[head_ptr];
        };
        
        int size()
        {
            if(this->empty())return 0;
            else return diff(tail_ptr,head_ptr)+1;
        };
        
        bool empty(){return diff(head_ptr,tail_ptr)==1;};
        bool full(){return diff(head_ptr,tail_ptr) ==2;};
    };
        
    }
    Last edited by manasij7479; 10-02-2011 at 04:47 AM.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It's the same issue with modifying the container before throwing.

    Code:
    void push(const T& in)
        {
            ++tail_ptr;
            tail_ptr%=Size;
            if(diff(head_ptr,tail_ptr) ==2) throw(overflow);
    And empty could be written as

    Code:
    bool empty(){return diff(head_ptr,tail_ptr)==1;}
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Sorry anon, I should have updated the code yesterday.
    I realized that in this case, modifying before throwing also introduced another bug, decrementing the effective size by 1.
    As it is only one reply, I'd update the main post for convenience.

    Thanks for the second point.
    Reflected that.
    Last edited by manasij7479; 10-02-2011 at 04:49 AM.

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    The semicolons after your member functions have no practical purpose, but those should be defined after the declaration anyway.

  5. #5
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by whiteflags View Post
    The semicolons after your member functions have no practical purpose, but those should be defined after the declaration anyway.
    Why "should" ? I knew that there are no technical differences.
    I put them inside because the alternative would look messy in a forum post.

  6. #6
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Well it's the only way to separate the declaration from the implementation. This way you could compile the two separately if you used multiple files.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by whiteflags
    Well it's the only way to separate the declaration from the implementation.
    I am a little confused though: separate the declaration of what from the implementation of what?

    Quote Originally Posted by whiteflags
    This way you could compile the two separately if you used multiple files.
    We are dealing with a class template, so the class template would need to be specialised for this to work, but I do not see any of that here.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Oh.

    I didn't see the template at all.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Incidentally, I notice that a number of member functions do not modify the observable state of the object, yet they are not declared const.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    Incidentally, I notice that a number of member functions do not modify the observable state of the object, yet they are not declared const.
    Thanks..did so.. for empty(), full() and size(). The private ones don't really matter .. right ?

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    The private ones don't really matter .. right ?
    They would, since constness is "viral".

    Also, the empty and full member functions could be implemented as non-member non-friend functions (or rather, function templates) using the Size member function (of course, Size should then not depend on empty).

    In diff, you probably should write pt1 >= pt2 instead of pt1-pt2 >=0. Since diff is already defined in the class definition, there is no need to declare it (and increment) inline with the inline keyword.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    Also, the empty and full member functions could be implemented as non-member non-friend functions (or rather, function templates) using the Size member function (of course, Size should then not depend on empty).
    Er.. couldn't understand this.
    Can you give an example with either of those ?

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    Can you give an example with either of those ?
    They could be something like:
    Code:
    template<typename T, int Size>
    bool empty(const queue<T, Size>& x)
    {
        return x.size() == 0;
    }
    
    template<typename T, int Size>
    bool full(const queue<T, Size>& x)
    {
        return x.size() == Size;
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    They could be something like:...
    Wouldn't that be a substantial deviation from the way the standard containers are designed ?
    Also, what does the design gain by passing the container object to the functions, rather than be a member ?

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    Wouldn't that be a substantial deviation from the way the standard containers are designed ?
    full is not a member function in any standard container; empty is a potential problem since existing code might assume that a container would provide empty as a member function. For new code, you could write this instead:
    Code:
    template<typename Container>
    bool empty(const Container& x)
    {
        return x.size() == 0;
    }
    
    template<typename Container>
    bool full(const Container& x)
    {
        return x.size() == x.max_size();
    }
    in which case code that assumes that a container has empty as a non-member member would also work for standard containers. Note that you would then implement max_size as:
    Code:
    int max_size() const
    {
        return Size;
    }
    Quote Originally Posted by manasij7479
    Also, what does the design gain by passing the container object to the functions, rather than be a member ?
    Read:
    Designing Simple Interfaces by Stroustrup
    How Non-Member Functions Improve Encapsulation by Meyers
    GotW #84: Monoliths "Unstrung" by Sutter
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please ..err..nitpick my code (implementing a stack)
    By manasij7479 in forum C++ Programming
    Replies: 6
    Last Post: 10-04-2011, 05:20 PM
  2. Circular Queue
    By Giridhar Sanjay in forum C++ Programming
    Replies: 6
    Last Post: 07-02-2011, 02:22 PM
  3. Stack and Queue "quack" circular array
    By mrsirpoopsalot in forum C++ Programming
    Replies: 15
    Last Post: 10-20-2009, 03:16 PM
  4. Circular array
    By Opel_Corsa in forum C++ Programming
    Replies: 5
    Last Post: 02-16-2006, 04:15 PM
  5. circular queue
    By strotee76 in forum C++ Programming
    Replies: 2
    Last Post: 05-24-2004, 09:55 AM