path: root/ml/dlib/dlib/queue/queue_kernel_2.h

// Copyright (C) 2004  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_QUEUE_KERNEl_2_
#define DLIB_QUEUE_KERNEl_2_

#include "queue_kernel_abstract.h"
#include "../algs.h"
#include "../assert.h"
#include "../interfaces/enumerable.h"
#include "../interfaces/remover.h"
#include "../serialize.h"

namespace dlib
{

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager = default_memory_manager
        >
    class queue_kernel_2 : public enumerable<T>,
                           public remover<T>
    {

        /*!
            REQUIREMENTS ON block_size
                0 < block_size < 2000000000

            INITIAL VALUE
                queue_size == 0   
                current_element == 0
                at_start_ == true
            
            CONVENTION
                queue_size == the number of elements in the queue
                at_start() == at_start_
                current_element_valid() == (current_element != 0)
                if (current_element_valid()) then
                    element() == current_element->item[current_element_pos]

                if (queue_size > 0)                
                {                    
                    in->item[in_pos] == the spot where we will put the next item added
                                        into the queue
                    out->item[out_pos] == current()

                    when enqueuing elements inside each node item[0] is filled first, then 
                    item[1], then item[2], etc.
                                                         

                    each node points to the node inserted after it except for the most 
                    recently inserted node.  
                }
                
        !*/


        struct node
        {
            node* next;

            T item[block_size];
        };

        
        public:

            typedef T type;
            typedef mem_manager mem_manager_type;

            queue_kernel_2 (
            ) :
                in(0),
                out(0),
                queue_size(0),
                current_element(0),
                at_start_(true)
            {
            }

            virtual ~queue_kernel_2 (
            ); 

            inline void clear(
            );

            void enqueue (
                T& item
            );

            void dequeue (
                T& item
            );

            void cat (
                queue_kernel_2& item
            );

            T& current (
            );

            const T& current (
            ) const;            

            void swap (
                queue_kernel_2& item
            );

            // functions from the remover interface
            inline void remove_any (
                T& item
            );

            // functions from the enumerable interface
            inline size_t size (
            ) const;

            inline bool at_start (
            ) const;

            inline void reset (
            ) const;

            bool current_element_valid (
            ) const;

            inline const T& element (
            ) const;

            inline T& element (
            );

            bool move_next (
            ) const;

        private:

            void delete_nodes (
                node* start,
                node* end
            );
            /*!
                requires
                    - start points to a node in a singly linked list 
                    - start->next points to the next node in the list 
                    - by following the next pointers you eventually hit the node pointed
                      to by end
                ensures
                    - calls delete on the start node, the end node, and all nodes in between
            !*/

            // data members

            typename mem_manager::template rebind<node>::other pool; 

            node* in;
            node* out;
            size_t queue_size;
            size_t in_pos;
            size_t out_pos;


            mutable node* current_element;
            mutable size_t current_element_pos;
            mutable bool at_start_;

            // restricted functions
            queue_kernel_2(queue_kernel_2&);        // copy constructor
            queue_kernel_2& operator=(queue_kernel_2&);    // assignment operator

    };

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    inline void swap (
        queue_kernel_2<T,block_size,mem_manager>& a, 
        queue_kernel_2<T,block_size,mem_manager>& b 
    ) { a.swap(b); } 

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void deserialize (
        queue_kernel_2<T,block_size,mem_manager>& item, 
        std::istream& in
    )
    {
        try
        {
            item.clear();
            unsigned long size;
            deserialize(size,in);
            T temp;
            for (unsigned long i = 0; i < size; ++i)
            {
                deserialize(temp,in);
                item.enqueue(temp);
            }
        }
        catch (serialization_error e)
        { 
            item.clear();
            throw serialization_error(e.info + "\n   while deserializing object of type queue_kernel_2"); 
        }
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    queue_kernel_2<T,block_size,mem_manager>::
    ~queue_kernel_2 (
    )
    {
        COMPILE_TIME_ASSERT(0 < block_size && block_size < (unsigned long)(2000000000));

        if (queue_size > 0)
            delete_nodes(out,in);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    clear (
    )
    {
        if (queue_size > 0)
        {
            delete_nodes(out,in);
            queue_size = 0;
        }

        // put the enumerator at the start
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    enqueue (
        T& item
    )
    {
        if (queue_size == 0)
        {
            out = in = pool.allocate();
            in_pos = 0;
            out_pos = 0;
        }
        else if (in_pos >= block_size)
        {            
            in->next = pool.allocate();
            in_pos = 0;
            in = in->next;
        }

        exchange(item,in->item[in_pos]);
        ++in_pos;

        ++queue_size;

        // put the enumerator at the start
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    dequeue (
        T& item
    )
    {
        // swap out into item
        exchange(item,out->item[out_pos]);
        
        ++out_pos;
        --queue_size;

        // if this was the last element in this node then remove this node
        if (out_pos == block_size)
        {
            out_pos = 0;
            node* temp = out;
            out = out->next;
            pool.deallocate(temp);
        }
        else if (queue_size == 0)
        {
            pool.deallocate(out);
        }

        // put the enumerator at the start
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    cat (
        queue_kernel_2<T,block_size,mem_manager>& item
    )
    {
        if (queue_size > 0)
        {
            T temp;
            assign_zero_if_built_in_scalar_type(temp);
            while (item.size() > 0)
            {
                item.dequeue(temp);
                enqueue(temp);
            }
        }
        else
        {
            in = item.in;
            out = item.out;
            out_pos = item.out_pos;
            in_pos = item.in_pos;

            queue_size = item.queue_size;
            item.queue_size = 0;

            // put the enumerator at the start
            reset();
        }       
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    T& queue_kernel_2<T,block_size,mem_manager>::
    current (
    )
    {
        return out->item[out_pos];
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    const T& queue_kernel_2<T,block_size,mem_manager>::
    current (
    ) const
    {
        return out->item[out_pos];
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    swap (
        queue_kernel_2<T,block_size,mem_manager>& item
    )
    {
        exchange(in,item.in);
        exchange(out,item.out);
        exchange(queue_size,item.queue_size);
        exchange(in_pos,item.in_pos);
        exchange(out_pos,item.out_pos);
        exchange(current_element,item.current_element);
        exchange(current_element_pos,item.current_element_pos);
        exchange(at_start_,item.at_start_);        
        pool.swap(item.pool);
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // enumerable function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    size_t queue_kernel_2<T,block_size,mem_manager>::
    size (
    ) const
    {
        return queue_size;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    bool queue_kernel_2<T,block_size,mem_manager>::
    at_start (
    ) const
    {
        return at_start_;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    reset (
    ) const
    {
        at_start_ = true;
        current_element = 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    bool queue_kernel_2<T,block_size,mem_manager>::
    current_element_valid (
    ) const
    {
        return (current_element != 0);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    const T& queue_kernel_2<T,block_size,mem_manager>::
    element (
    ) const
    {
        return current_element->item[current_element_pos];
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    T& queue_kernel_2<T,block_size,mem_manager>::
    element (
    )
    {
        return current_element->item[current_element_pos];
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    bool queue_kernel_2<T,block_size,mem_manager>::
    move_next (
    ) const
    {
        if (at_start_)
        {
            at_start_ = false;
            // if the queue is empty then there is nothing to do
            if (queue_size == 0)
            {
                return false;
            }
            else
            {
                current_element = out;
                current_element_pos = out_pos;
                return true;
            }
        }
        else if (current_element == 0)
        {
            return false;
        }
        else
        {
            ++current_element_pos;
            // if we are at the last element then the enumeration has finished
            if (current_element == in && current_element_pos == in_pos )
            {
                current_element = 0;
                return false;
            }
            else if (current_element_pos == block_size)
            {
                current_element_pos = 0;
                current_element = current_element->next;               
            }           

            return true;
        }
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // remover function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    remove_any (
        T& item
    ) 
    {
        dequeue(item);
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // private member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename T,
        unsigned long block_size,
        typename mem_manager
        >
    void queue_kernel_2<T,block_size,mem_manager>::
    delete_nodes (
        node* start,
        node* end
    )
    {
        node* temp;
        while (start != end)
        {
            temp = start;
            start = start->next;
            pool.deallocate(temp);
        }
        pool.deallocate(start);
    }

// ----------------------------------------------------------------------------------------

}

#endif // DLIB_QUEUE_KERNEl_2_