Like Tree1Likes

Queue with a circular array... nitpick !

This is a discussion on Queue with a circular array... nitpick ! within the C++ Programming forums, part of the General Programming Boards category; Another one... Works fine(at least on my test cases); but .. for a second opinion. Is there a better way ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  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
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



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

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    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
    21,457
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    Oh.

    I didn't see the template at all.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,457
    Incidentally, I notice that a number of member functions do not modify the observable state of the object, yet they are not declared const.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,457
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,457
    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;
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,457
    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
    manasij7479 likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
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, 03:15 PM
  5. circular queue
    By strotee76 in forum C++ Programming
    Replies: 2
    Last Post: 05-24-2004, 09:55 AM

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