/*
 * Copyright 1999-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * @author Matthew Hoyt (mhoyt@ca.ibm.com)
 */

#if !defined(XALANDEQUE_HEADER_GUARD_1357924680)
#define XALANDEQUE_HEADER_GUARD_1357924680


// Base include file.  Must be first.
#include <xalanc/Include/PlatformDefinitions.hpp>


#include <xalanc/Include/XalanVector.hpp>
#include <xalanc/Include/XalanMemoryManagement.hpp> 


XALAN_CPP_NAMESPACE_BEGIN


template <class Value>
struct XalanDequeIteratorTraits
{
	typedef Value	        value_type;
	typedef Value&	        reference;
	typedef Value*	        pointer;
    typedef const Value&    const_reference;
};

template <class Value>
struct XalanDequeConstIteratorTraits
{
	typedef Value	        value_type;
	typedef const Value&	reference;
	typedef const Value*	pointer;
    typedef const Value&	const_reference;
};

template <class XalanDequeTraits, class XalanDeque>
struct  XalanDequeIterator
{
    typedef size_t  size_type;
    typedef typename XalanDequeTraits::value_type       value_type;
    typedef typename XalanDequeTraits::reference        reference;
    typedef typename XalanDequeTraits::pointer          pointer;
    typedef typename XalanDequeTraits::const_reference  const_reference;
    typedef ptrdiff_t		                            difference_type;

    typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> Iterator;

	typedef XALAN_STD_QUALIFIER random_access_iterator_tag iterator_category;

    XalanDequeIterator(XalanDeque*  deque,
                       size_type    pos) :
        m_deque(deque),
        m_pos(pos)
    {
    }

    XalanDequeIterator(const Iterator & iterator) :
        m_deque(iterator.m_deque),
        m_pos(iterator.m_pos)
    {
    }

    XalanDequeIterator& operator=(const Iterator & iterator)
    {
        m_deque = iterator.m_deque;
        m_pos = iterator.m_pos;
        return *this;
    }

    XalanDequeIterator& operator++()
    {
        ++m_pos;
        return *this;
    }

    XalanDequeIterator operator++(int)
    {
        XalanDequeIterator temp = *this;
        ++m_pos;
        return temp;
    }

    XalanDequeIterator& operator--()
    {   
        --m_pos;
        return *this;
    }

    pointer operator->()
    {
        return &(*m_deque[m_pos]);
    }

    reference operator*()
    {
        return (*m_deque)[m_pos];
    }

    const_reference operator*() const
    {
        return (*m_deque)[m_pos];
    }

    XalanDequeIterator operator+(difference_type difference) const
    {
        return XalanDequeIterator(m_deque, m_pos + difference);
    }

    XalanDequeIterator operator-(difference_type difference) const
    {
        return XalanDequeIterator(m_deque, m_pos - difference);
    }

    difference_type operator-(const XalanDequeIterator &theRhs) const
    {
        return m_pos - theRhs.m_pos;
    }

    bool operator==(const XalanDequeIterator & theRhs) const
    {
        return (theRhs.m_deque == m_deque)
            &&  theRhs.m_pos == m_pos;
    }

    bool operator!=(const XalanDequeIterator & theRhs) const
    {
        return !(theRhs == *this);
    }

    XalanDeque* m_deque;
    size_type   m_pos;
};

/**
 * Xalan implementation of deque
 */
template <class Type, class ConstructionTraits = MemoryManagedConstructionTraits<Type> >
class XalanDeque
{
public:

    typedef XERCES_CPP_NAMESPACE_QUALIFIER MemoryManager    MemoryManagerType;

    typedef size_t  size_type;

    typedef Type            value_type;
    typedef Type&           reference;
    typedef const Type&     const_reference;

    typedef XalanVector<Type, ConstructionTraits>	    BlockType;

    typedef XalanVector<BlockType*> BlockIndexType;

    typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> iterator;
    typedef XalanDequeIterator<XalanDequeConstIteratorTraits<value_type>, XalanDeque> const_iterator;

#if defined(XALAN_HAS_STD_ITERATORS)
    typedef XALAN_STD_QUALIFIER reverse_iterator<iterator>          reverse_iterator_;
    typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator>    const_reverse_iterator_;
#elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC)
    typedef XALAN_STD_QUALIFIER reverse_iterator<
        iterator,
        XALAN_STD_QUALIFIER random_access_iterator_tag,
        value_type> reverse_iterator_;
    typedef XALAN_STD_QUALIFIER reverse_iterator<
        const_iterator,
        XALAN_STD_QUALIFIER random_access_iterator_tag,
        const value_type> const_reverse_iterator_;
#else
    typedef XALAN_STD_QUALIFIER reverse_iterator<iterator, value_type>                          reverse_iterator_;
    typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator, value_type, const_reference>   const_reverse_iterator_;
#endif

    typedef reverse_iterator_           reverse_iterator;
    typedef const_reverse_iterator_     const_reverse_iterator;

    XalanDeque(
            size_type initialSize = 0,
            MemoryManagerType* memoryManager = 0, 
            size_type blockSize = 10) :
        m_memoryManager(memoryManager),
        m_blockSize(blockSize),
        m_blockIndex(memoryManager,
                    initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1))                    
    {
        XALAN_STD_QUALIFIER fill_n(XALAN_STD_QUALIFIER back_inserter(*this), initialSize, value_type());
    }

    XalanDeque(const XalanDeque& theRhs) :
        m_memoryManager(theRhs.m_memoryManager),
        m_blockSize(theRhs.m_blockSize),
        m_blockIndex(theRhs.m_memoryManager,
                    theRhs.size() / theRhs.m_blockSize + (theRhs.size() % theRhs.m_blockSize == 0 ? 0 : 1))
    {
        XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this));
    }
    
    ~XalanDeque()
    {
        clear();
        typename BlockIndexType::iterator iter = m_freeBlockVector.begin();

        while (iter != m_freeBlockVector.end())
        {
            (*iter)->~XalanVector<Type>();
            deallocate(*iter);
            ++iter;
        }
    }

    iterator begin()
    {
        return iterator(this, 0);
    }

    const_iterator begin() const
    {
        return const_iterator(const_cast<XalanDeque*>(this), 0);
    }

    iterator end()
    {
        return iterator(this, size());
    }

    const_iterator end() const
    {
         return const_iterator(const_cast<XalanDeque*>(this), size());
    }

    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }

    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

    bool empty() const
    {
        return m_blockIndex.empty();
    }

    size_type size() const
    {
       if (m_blockIndex.empty())
       {
           return 0;
       }
       else
       {
           return (m_blockIndex.size() - 1) * m_blockSize
               +  m_blockIndex.back()->size();
       }
    }

    value_type& back()
    {
        return m_blockIndex.back()->back();
    }

    value_type& operator[](size_type index)
    {
        BlockType & block = *(m_blockIndex[index / m_blockSize]);
        return block[index % m_blockSize];
    }

    const value_type& operator[](size_type index) const
    {
        BlockType & block = *(m_blockIndex[index / m_blockSize]);
        return block[index % m_blockSize];
    }

    void clear()
    {
        typename BlockIndexType::iterator iter = m_blockIndex.begin();

        m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size());

        while (iter != m_blockIndex.end())
        {
            (*iter)->clear();
            m_freeBlockVector.push_back(*iter);
            ++iter;
        }
        
        m_blockIndex.clear();
    }

    void push_back(const value_type & value)
    {
        if (m_blockIndex.empty() ||
            m_blockIndex.back()->size() >= m_blockSize)
        {
            m_blockIndex.push_back(getNewBlock());
        }

        m_blockIndex.back()->push_back(value);
    }

    void pop_back()
    {
        BlockType & lastBlock = *(m_blockIndex.back());
        lastBlock.pop_back();
        if (lastBlock.empty())
        {
            m_freeBlockVector.push_back(&lastBlock);
            m_blockIndex.pop_back();
        }
    }

    void resize(size_type newSize)
    {
        typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager);
        if (newSize > size())
        {
            for (size_type i = 0; i < newSize - size(); ++i)
            {
                push_back(defaultValue.value);
            }
        }
        else
        {
            for (size_type i = 0; i < size() - newSize; ++i)
            {
                pop_back();
            }
        }
    }

    void swap(XalanDeque& theRhs)
    {
        MemoryManagerType* tempMemoryManager = m_memoryManager;
        m_memoryManager = theRhs.m_memoryManager;
        theRhs.m_memoryManager = tempMemoryManager;

        theRhs.m_blockIndex.swap(m_blockIndex);
        theRhs.m_freeBlockVector.swap(m_freeBlockVector);
    }

    const XalanDeque & operator=(const XalanDeque & theRhs) 
    {
        clear();
        XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this));
        return *this;
    }

protected:

    BlockType* getNewBlock()
    {
        BlockType * newBlock;

        if (m_freeBlockVector.empty())
        {
            newBlock = allocate(1);
            new (&*newBlock) BlockType(m_memoryManager, m_blockSize);
        }
        else
        {
            newBlock = m_freeBlockVector.back();
            m_freeBlockVector.pop_back();
        }

        assert (newBlock != 0);

        return newBlock;
    }

    BlockType*
    allocate(size_type  size)
    {
        const size_type     theBytesNeeded = size * sizeof(BlockType);

        void*   pointer = m_memoryManager == 0 ?
                    ::operator new (theBytesNeeded) :
                                    m_memoryManager->allocate(theBytesNeeded);
        assert(pointer != 0);
        return (BlockType*) pointer;
     }

    void
    deallocate(BlockType*  pointer)
    {
        if (m_memoryManager == 0)
        {
            ::operator delete(pointer);
        }
	else
        {
            m_memoryManager->deallocate(pointer);
        }
    }

    BlockIndexType     m_blockIndex; 
    BlockIndexType     m_freeBlockVector;
    
    MemoryManagerType*  m_memoryManager;
    const size_type     m_blockSize;
};

XALAN_CPP_NAMESPACE_END


#endif  // XALANDEQUE_HEADER_GUARD_1357924680