vector.h

/***************************************************************************
 *  include/stxxl/bits/containers/vector.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2002-2008 Roman Dementiev <[email protected]>
 *  Copyright (C) 2007-2009 Johannes Singler <[email protected]>
 *  Copyright (C) 2008-2010 Andreas Beckmann <[email protected]>
 *
 *  Distributed under the Boost Software License, Version 1.0.
 *  (See accompanying file LICENSE_1_0.txt or copy at
 *  http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_VECTOR_HEADER
#define STXXL_VECTOR_HEADER

#include <vector>
#include <queue>
#include <algorithm>

#include <stxxl/bits/deprecated.h>
#include <stxxl/bits/io/request_operations.h>
#include <stxxl/bits/mng/mng.h>
#include <stxxl/bits/mng/typed_block.h>
#include <stxxl/bits/common/tmeta.h>
#include <stxxl/bits/containers/pager.h>
#include <stxxl/bits/common/is_sorted.h>


__STXXL_BEGIN_NAMESPACE




template <typename size_type, size_type modulo2, size_type modulo1>
class double_blocked_index
{
    static const size_type modulo12 = modulo1 * modulo2;

    size_type pos, block1, block2, offset;


    void set(size_type pos)
    {
        this->pos = pos;
        block2 = pos / modulo12;
        pos -= block2 * modulo12;
        block1 = pos / modulo1;
        offset = (pos - block1 * modulo1);

        assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
        assert(/* 0 <= block1 && */ block1 < modulo2);
        assert(/* 0 <= offset && */ offset < modulo1);
    }

public:
    double_blocked_index()
    {
        set(0);
    }

    double_blocked_index(size_type pos)
    {
        set(pos);
    }

    double_blocked_index(size_type block2, size_type block1, size_type offset)
    {
        assert(/* 0 <= block1 && */ block1 < modulo2);
        assert(/* 0 <= offset && */ offset < modulo1);

        this->block2 = block2;
        this->block1 = block1;
        this->offset = offset;
        pos = block2 * modulo12 + block1 * modulo1 + offset;
    }

    double_blocked_index & operator = (size_type pos)
    {
        set(pos);
        return *this;
    }

    //pre-increment operator
    double_blocked_index & operator ++ ()
    {
        ++pos;
        ++offset;
        if (offset == modulo1)
        {
            offset = 0;
            ++block1;
            if (block1 == modulo2)
            {
                block1 = 0;
                ++block2;
            }
        }

        assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
        assert(/* 0 <= block1 && */ block1 < modulo2);
        assert(/* 0 <= offset && */ offset < modulo1);

        return *this;
    }

    //post-increment operator
    double_blocked_index operator ++ (int)
    {
        double_blocked_index former(*this);
        operator ++ ();
        return former;
    }

    //pre-increment operator
    double_blocked_index & operator -- ()
    {
        --pos;
        if (offset == 0)
        {
            offset = modulo1;
            if (block1 == 0)
            {
                block1 = modulo2;
                --block2;
            }
            --block1;
        }
        --offset;

        assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
        assert(/*0 <= block1 &&*/ block1 < modulo2);
        assert(/*0 <= offset &&*/ offset < modulo1);

        return *this;
    }

    //post-increment operator
    double_blocked_index operator -- (int)
    {
        double_blocked_index former(*this);
        operator -- ();
        return former;
    }

    double_blocked_index operator + (size_type addend) const
    {
        return double_blocked_index(pos + addend);
    }

    double_blocked_index & operator += (size_type addend)
    {
        set(pos + addend);
        return *this;
    }

    double_blocked_index operator - (size_type addend) const
    {
        return double_blocked_index(pos - addend);
    }

    size_type operator - (const double_blocked_index & dbi2) const
    {
        return pos - dbi2.pos;
    }

    double_blocked_index & operator -= (size_type subtrahend)
    {
        set(pos - subtrahend);
        return *this;
    }

    bool operator == (const double_blocked_index & dbi2) const
    {
        return pos == dbi2.pos;
    }

    bool operator != (const double_blocked_index & dbi2) const
    {
        return pos != dbi2.pos;
    }

    bool operator < (const double_blocked_index & dbi2) const
    {
        return pos < dbi2.pos;
    }

    bool operator <= (const double_blocked_index & dbi2) const
    {
        return pos <= dbi2.pos;
    }

    bool operator > (const double_blocked_index & dbi2) const
    {
        return pos > dbi2.pos;
    }

    bool operator >= (const double_blocked_index & dbi2) const
    {
        return pos >= dbi2.pos;
    }

    double_blocked_index & operator >>= (size_type shift)
    {
        set(pos >> shift);
        return *this;
    }

    size_type get_pos() const
    {
        return pos;
    }

    const size_type & get_block2() const
    {
        return block2;
    }

    const size_type & get_block1() const
    {
        return block1;
    }

    const size_type & get_offset() const
    {
        return offset;
    }
};


template <unsigned BlkSize_>
class bid_vector : public std::vector<BID<BlkSize_> >
{
public:
    typedef std::vector<BID<BlkSize_> > _Derived;
    typedef typename _Derived::size_type size_type;
    typedef typename _Derived::value_type bid_type;

    bid_vector(size_type _sz) : _Derived(_sz)
    { }
};


template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
class vector;


template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
          unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
class const_vector_iterator;


template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
          unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
class vector_iterator
{
    typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _Self;
    typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _CIterator;

    friend class const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>;

public:
    typedef _CIterator const_iterator;
    typedef _Self iterator;

    typedef unsigned block_offset_type;
    typedef vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> vector_type;
    friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>;
    typedef typename vector_type::bids_container_type bids_container_type;
    typedef typename bids_container_type::iterator bids_container_iterator;
    typedef typename bids_container_type::bid_type bid_type;
    typedef typename vector_type::block_type block_type;
    typedef typename vector_type::blocked_index_type blocked_index_type;

    typedef std::random_access_iterator_tag iterator_category;
    typedef typename vector_type::size_type size_type;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::value_type value_type;
    typedef typename vector_type::reference reference;
    typedef typename vector_type::const_reference const_reference;
    typedef typename vector_type::pointer pointer;
    typedef typename vector_type::const_pointer const_pointer;

protected:
    blocked_index_type offset;
    vector_type * p_vector;

private:
    vector_iterator(vector_type * v, size_type o) : offset(o),
                                                    p_vector(v)
    { }

public:
    vector_iterator() : offset(0), p_vector(NULL) { }
    vector_iterator(const _Self & a) :
        offset(a.offset),
        p_vector(a.p_vector) { }

    block_offset_type block_offset() const
    {
        return static_cast<block_offset_type>(offset.get_offset());
    }
    bids_container_iterator bid() const
    {
        return p_vector->bid(offset);
    }

    difference_type operator - (const _Self & a) const
    {
        return offset - a.offset;
    }

    difference_type operator - (const const_iterator & a) const
    {
        return offset - a.offset;
    }

    _Self operator - (size_type op) const
    {
        return _Self(p_vector, offset.get_pos() - op);
    }

    _Self operator + (size_type op) const
    {
        return _Self(p_vector, offset.get_pos() + op);
    }

    _Self & operator -= (size_type op)
    {
        offset -= op;
        return *this;
    }

    _Self & operator += (size_type op)
    {
        offset += op;
        return *this;
    }

    reference operator * ()
    {
        return p_vector->element(offset);
    }

    pointer operator -> ()
    {
        return &(p_vector->element(offset));
    }

    const_reference operator * () const
    {
        return p_vector->const_element(offset);
    }

    const_pointer operator -> () const
    {
        return &(p_vector->const_element(offset));
    }

    reference operator [] (size_type op)
    {
        return p_vector->element(offset.get_pos() + op);
    }

    const_reference operator [] (size_type op) const
    {
        return p_vector->const_element(offset.get_pos() + op);
    }

    void block_externally_updated()
    {
        p_vector->block_externally_updated(offset);
    }

    _STXXL_DEPRECATED(void touch())
    {
        block_externally_updated();
    }

    _Self & operator ++ ()
    {
        offset++;
        return *this;
    }
    _Self operator ++ (int)
    {
        _Self __tmp = *this;
        offset++;
        return __tmp;
    }
    _Self & operator -- ()
    {
        offset--;
        return *this;
    }
    _Self operator -- (int)
    {
        _Self __tmp = *this;
        offset--;
        return __tmp;
    }
    bool operator == (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;
    }
    bool operator != (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    bool operator == (const const_iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;
    }
    bool operator != (const const_iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const const_iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const const_iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const const_iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const const_iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    void flush()
    {
        p_vector->flush();
    }
#if 0
    std::ostream & operator << (std::ostream & o) const
    {
        o << "vectorpointer: " << ((void *)p_vector) << " offset: " << offset;
        return o;
    }
#endif
};

template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
          unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
class const_vector_iterator
{
    typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _Self;
    typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _NonConstIterator;

    friend class vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>;

public:
    typedef _Self const_iterator;
    typedef _NonConstIterator iterator;

    typedef unsigned block_offset_type;
    typedef vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> vector_type;
    friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>;
    typedef typename vector_type::bids_container_type bids_container_type;
    typedef typename bids_container_type::iterator bids_container_iterator;
    typedef typename bids_container_type::bid_type bid_type;
    typedef typename vector_type::block_type block_type;
    typedef typename vector_type::blocked_index_type blocked_index_type;

    typedef std::random_access_iterator_tag iterator_category;
    typedef typename vector_type::size_type size_type;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::value_type value_type;
    typedef typename vector_type::const_reference reference;
    typedef typename vector_type::const_reference const_reference;
    typedef typename vector_type::const_pointer pointer;
    typedef typename vector_type::const_pointer const_pointer;

protected:
    blocked_index_type offset;
    const vector_type * p_vector;

private:
    const_vector_iterator(const vector_type * v, size_type o) : offset(o),
                                                                p_vector(v)
    { }

public:
    const_vector_iterator() : offset(0), p_vector(NULL)
    { }
    const_vector_iterator(const _Self & a) :
        offset(a.offset),
        p_vector(a.p_vector)
    { }

    const_vector_iterator(const iterator & a) :
        offset(a.offset),
        p_vector(a.p_vector)
    { }

    block_offset_type block_offset() const
    {
        return static_cast<block_offset_type>(offset.get_offset());
    }
    bids_container_iterator bid() const
    {
        return ((vector_type *)p_vector)->bid(offset);
    }

    difference_type operator - (const _Self & a) const
    {
        return offset - a.offset;
    }

    difference_type operator - (const iterator & a) const
    {
        return offset - a.offset;
    }

    _Self operator - (size_type op) const
    {
        return _Self(p_vector, offset.get_pos() - op);
    }

    _Self operator + (size_type op) const
    {
        return _Self(p_vector, offset.get_pos() + op);
    }

    _Self & operator -= (size_type op)
    {
        offset -= op;
        return *this;
    }

    _Self & operator += (size_type op)
    {
        offset += op;
        return *this;
    }

    const_reference operator * () const
    {
        return p_vector->const_element(offset);
    }

    const_pointer operator -> () const
    {
        return &(p_vector->const_element(offset));
    }

    const_reference operator [] (size_type op) const
    {
        return p_vector->const_element(offset.get_pos() + op);
    }

    void block_externally_updated()
    {
        p_vector->block_externally_updated(offset);
    }

    _STXXL_DEPRECATED(void touch())
    {
        block_externally_updated();
    }

    _Self & operator ++ ()
    {
        offset++;
        return *this;
    }
    _Self operator ++ (int)
    {
        _Self tmp_ = *this;
        offset++;
        return tmp_;
    }
    _Self & operator -- ()
    {
        offset--;
        return *this;
    }
    _Self operator -- (int)
    {
        _Self __tmp = *this;
        offset--;
        return __tmp;
    }
    bool operator == (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;                 // or (offset + stxxl::int64(p_vector))
    }
    bool operator != (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const _Self & a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    bool operator == (const iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset; // or (offset + stxxl::int64(p_vector))
    }
    bool operator != (const iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const iterator & a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    void flush()
    {
        p_vector->flush();
    }

#if 0
    std::ostream & operator << (std::ostream & o) const
    {
        o << "vector pointer: " << ((void *)p_vector) << " offset: " << offset;
        return o;
    }
#endif
};



template <
    typename Tp_,
    unsigned PgSz_ = 4,
    typename PgTp_ = lru_pager<8>,
    unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_),
    typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY,
    typename SzTp_ = stxxl::uint64       // will be deprecated soon
    >
class vector
{
public:
    typedef Tp_ value_type;
    typedef value_type & reference;
    typedef const value_type & const_reference;
    typedef value_type * pointer;
    typedef SzTp_ size_type;
    typedef stxxl::int64 difference_type;
    typedef const value_type * const_pointer;

    typedef PgTp_ pager_type;
    typedef AllocStr_ alloc_strategy_type;

    enum constants {
        block_size = BlkSize_,
        page_size = PgSz_,
        n_pages = pager_type::n_pages,
        on_disk = -1
    };

    typedef vector_iterator<value_type, alloc_strategy_type, size_type,
                            difference_type, block_size, pager_type, page_size> iterator;
    friend class vector_iterator<value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size>;
    typedef const_vector_iterator<value_type, alloc_strategy_type,
                                  size_type, difference_type, block_size, pager_type, page_size> const_iterator;
    friend class const_vector_iterator<value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size>;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    typedef bid_vector<block_size> bids_container_type;
    typedef typename bids_container_type::iterator bids_container_iterator;
    typedef typename bids_container_type::const_iterator const_bids_container_iterator;

    typedef typed_block<BlkSize_, Tp_> block_type;
    typedef double_blocked_index<SzTp_, PgSz_, block_type::size> blocked_index_type;

private:
    alloc_strategy_type alloc_strategy;
    size_type _size;
    bids_container_type _bids;
    mutable pager_type pager;

    enum { valid_on_disk = 0, uninitialized = 1, dirty = 2 };
    mutable std::vector<unsigned char> _page_status;
    mutable std::vector<int_type> _page_to_slot;
    mutable simple_vector<int_type> _slot_to_page;
    mutable std::queue<int_type> _free_slots;
    mutable simple_vector<block_type> * _cache;
    file * _from;
    block_manager * bm;
    config * cfg;
    bool exported;

    size_type size_from_file_length(stxxl::uint64 file_length) const
    {
        stxxl::uint64 blocks_fit = file_length / stxxl::uint64(block_type::raw_size);
        size_type cur_size = blocks_fit * stxxl::uint64(block_type::size);
        stxxl::uint64 rest = file_length - blocks_fit * stxxl::uint64(block_type::raw_size);
        return (cur_size + rest / stxxl::uint64(sizeof(value_type)));
    }

    stxxl::uint64 file_length() const
    {
        typedef stxxl::uint64 file_size_type;
        size_type cur_size = size();
        size_type num_full_blocks = cur_size / block_type::size;
        if (cur_size % block_type::size != 0)
        {
            size_type rest = cur_size - num_full_blocks * block_type::size;
            return file_size_type(num_full_blocks) * block_type::raw_size + rest * sizeof(value_type);
        }
        return file_size_type(num_full_blocks) * block_type::raw_size;
    }

public:
    vector(size_type n = 0) :
        _size(n),
        _bids(div_ceil(n, block_type::size)),
        _page_status(div_ceil(_bids.size(), page_size)),
        _page_to_slot(div_ceil(_bids.size(), page_size)),
        _slot_to_page(n_pages),
        _cache(NULL),
        _from(NULL),
        exported(false)
    {
        bm = block_manager::get_instance();
        cfg = config::get_instance();

        allocate_page_cache();
        int_type all_pages = div_ceil(_bids.size(), page_size);
        int_type i = 0;
        for ( ; i < all_pages; ++i)
        {
            _page_status[i] = uninitialized;
            _page_to_slot[i] = on_disk;
        }

        for (i = 0; i < n_pages; ++i)
            _free_slots.push(i);

        bm->new_blocks(alloc_strategy, _bids.begin(), _bids.end(), 0);
    }

    void swap(vector & obj)
    {
        std::swap(alloc_strategy, obj.alloc_strategy);
        std::swap(_size, obj._size);
        std::swap(_bids, obj._bids);
        std::swap(pager, obj.pager);
        std::swap(_page_status, obj._page_status);
        std::swap(_page_to_slot, obj._page_to_slot);
        std::swap(_slot_to_page, obj._slot_to_page);
        std::swap(_free_slots, obj._free_slots);
        std::swap(_cache, obj._cache);
        std::swap(_from, obj._from);
        std::swap(exported, obj.exported);
    }

    void allocate_page_cache() const
    {
        if (!_cache)
            _cache = new simple_vector<block_type>(n_pages * page_size);
    }

    // allows to free the cache, but you may not access any element until call allocate_pacge_cache() again
    void deallocate_page_cache() const
    {
        flush();
        delete _cache;
        _cache = NULL;
    }

    size_type capacity() const
    {
        return size_type(_bids.size()) * block_type::size;
    }
    size_type raw_capacity() const
    {
        return size_type(_bids.size()) * block_type::raw_size;
    }

    void reserve(size_type n)
    {
        if (n <= capacity())
            return;

        unsigned_type old_bids_size = _bids.size();
        unsigned_type new_bids_size = div_ceil(n, block_type::size);
        unsigned_type new_pages = div_ceil(new_bids_size, page_size);
        _page_status.resize(new_pages, uninitialized);
        _page_to_slot.resize(new_pages, on_disk);

        _bids.resize(new_bids_size);
        if (_from == NULL)
        {
            bm->new_blocks(alloc_strategy, _bids.begin() + old_bids_size, _bids.end(), old_bids_size);
        }
        else
        {
            size_type offset = size_type(old_bids_size) * size_type(block_type::raw_size);
            bids_container_iterator it = _bids.begin() + old_bids_size;
            for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size))
            {
                (*it).storage = _from;
                (*it).offset = offset;
            }
            STXXL_VERBOSE1("vector::reserve(): Changing size of file " << ((void *)_from) << " to "
                                                                       << offset);
            _from->set_size(offset);
        }
    }

    void resize(size_type n)
    {
        _resize(n);
    }

    void resize(size_type n, bool shrink_capacity)
    {
        if (shrink_capacity)
            _resize_shrink_capacity(n);
        else
            _resize(n);
    }

private:
    void _resize(size_type n)
    {
        reserve(n);
        if (n < _size) {
            // mark excess pages as uninitialized and evict them from cache
            unsigned_type first_page_to_evict = div_ceil(n, block_type::size * page_size);
            for (unsigned_type i = first_page_to_evict; i < _page_status.size(); ++i) {
                if (_page_to_slot[i] != on_disk) {
                    _free_slots.push(_page_to_slot[i]);
                    _page_to_slot[i] = on_disk;
                }
                _page_status[i] = uninitialized;
            }
        }
        _size = n;
    }

    void _resize_shrink_capacity(size_type n)
    {
        unsigned_type old_bids_size = _bids.size();
        unsigned_type new_bids_size = div_ceil(n, block_type::size);

        if (new_bids_size > old_bids_size)
        {
            reserve(n);
        }
        else if (new_bids_size < old_bids_size)
        {
            if (_from != NULL)
                _from->set_size(new_bids_size * block_type::raw_size);
            else
                bm->delete_blocks(_bids.begin() + old_bids_size, _bids.end());

            _bids.resize(new_bids_size);
            unsigned_type new_pages = div_ceil(new_bids_size, page_size);
            _page_status.resize(new_pages);

            unsigned_type first_page_to_evict = div_ceil(new_bids_size, page_size);
            // clear dirty flag, so these pages will be never written
            std::fill(_page_status.begin() + first_page_to_evict,
                      _page_status.end(), (unsigned char)valid_on_disk);
        }

        _size = n;
    }

public:
    void clear()
    {
        _size = 0;
        if (_from == NULL)
            bm->delete_blocks(_bids.begin(), _bids.end());

        _bids.clear();
        _page_status.clear();
        _page_to_slot.clear();
        while (!_free_slots.empty())
            _free_slots.pop();


        for (int_type i = 0; i < n_pages; ++i)
            _free_slots.push(i);
    }

    void push_back(const_reference obj)
    {
        size_type old_size = _size;
        resize(old_size + 1);
        element(old_size) = obj;
    }
    void pop_back()
    {
        resize(_size - 1);
    }

    reference back()
    {
        return element(_size - 1);
    }
    reference front()
    {
        return element(0);
    }
    const_reference back() const
    {
        return const_element(_size - 1);
    }
    const_reference front() const
    {
        return const_element(0);
    }

    vector(file * from, size_type size = size_type(-1)) :
        _size((size == size_type(-1)) ? size_from_file_length(from->size()) : size),
        _bids(div_ceil(_size, size_type(block_type::size))),
        _page_status(div_ceil(_bids.size(), page_size)),
        _page_to_slot(div_ceil(_bids.size(), page_size)),
        _slot_to_page(n_pages),
        _cache(NULL),
        _from(from),
        exported(false)
    {
        // initialize from file
        if (!block_type::has_only_data)
        {
            std::ostringstream str_;
            str_ << "The block size for a vector that is mapped to a file must be a multiple of the element size (" <<
            sizeof(value_type) << ") and the page size (4096).";
            throw std::runtime_error(str_.str());
        }

        bm = block_manager::get_instance();
        cfg = config::get_instance();

        allocate_page_cache();
        int_type all_pages = div_ceil(_bids.size(), page_size);
        int_type i = 0;
        for ( ; i < all_pages; ++i)
        {
            _page_status[i] = valid_on_disk;
            _page_to_slot[i] = on_disk;
        }

        for (i = 0; i < n_pages; ++i)
            _free_slots.push(i);


        //allocate blocks equidistantly and in-order
        size_type offset = 0;
        bids_container_iterator it = _bids.begin();
        for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size))
        {
            (*it).storage = from;
            (*it).offset = offset;
        }
        from->set_size(offset);
    }

    vector(const vector & obj) :
        _size(obj.size()),
        _bids(div_ceil(obj.size(), block_type::size)),
        _page_status(div_ceil(_bids.size(), page_size)),
        _page_to_slot(div_ceil(_bids.size(), page_size)),
        _slot_to_page(n_pages),
        _cache(NULL),
        _from(NULL),
        exported(false)
    {
        assert(!obj.exported);
        bm = block_manager::get_instance();
        cfg = config::get_instance();

        allocate_page_cache();
        int_type all_pages = div_ceil(_bids.size(), page_size);
        int_type i = 0;
        for ( ; i < all_pages; ++i)
        {
            _page_status[i] = uninitialized;
            _page_to_slot[i] = on_disk;
        }

        for (i = 0; i < n_pages; ++i)
            _free_slots.push(i);

        bm->new_blocks(alloc_strategy, _bids.begin(), _bids.end(), 0);

        const_iterator inbegin = obj.begin();
        const_iterator inend = obj.end();
        std::copy(inbegin, inend, begin());
    }

    vector & operator = (const vector & obj)
    {
        if (&obj != this)
        {
            vector tmp(obj);
            this->swap(tmp);
        }
        return *this;
    }

    size_type size() const
    {
        return _size;
    }
    bool empty() const
    {
        return (!_size);
    }
    iterator begin()
    {
        return iterator(this, 0);
    }
    const_iterator begin() const
    {
        return const_iterator(this, 0);
    }
    const_iterator cbegin() const
    {
        return begin();
    }
    iterator end()
    {
        return iterator(this, _size);
    }
    const_iterator end() const
    {
        return const_iterator(this, _size);
    }
    const_iterator cend() const
    {
        return end();
    }

    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator crbegin() const
    {
        return const_reverse_iterator(end());
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }
    const_reverse_iterator crend() const
    {
        return const_reverse_iterator(begin());
    }

    reference operator [] (size_type offset)
    {
        return element(offset);
    }
    const_reference operator [] (size_type offset) const
    {
        return const_element(offset);
    }

    bool is_element_cached(size_type offset) const
    {
        return is_page_cached(blocked_index_type(offset));
    }

    void flush() const
    {
        simple_vector<bool> non_free_slots(n_pages);
        int_type i = 0;
        for ( ; i < n_pages; i++)
            non_free_slots[i] = true;

        while (!_free_slots.empty())
        {
            non_free_slots[_free_slots.front()] = false;
            _free_slots.pop();
        }

        for (i = 0; i < n_pages; i++)
        {
            _free_slots.push(i);
            int_type page_no = _slot_to_page[i];
            if (non_free_slots[i])
            {
                STXXL_VERBOSE1("vector: flushing page " << i << " at address "
                                                        << (int64(page_no) * int64(block_type::size) * int64(page_size)));
                write_page(page_no, i);

                _page_to_slot[page_no] = on_disk;
            }
        }
    }

    ~vector()
    {
        STXXL_VERBOSE("~vector()");
        try
        {
            flush();
        }
        catch (io_error e)
        {
            STXXL_ERRMSG("io_error thrown in ~vector(): " << e.what());
        }
        catch (...)
        {
            STXXL_ERRMSG("Exception thrown in ~vector()");
        }

        if (!exported)
        {
            if (_from == NULL)
                bm->delete_blocks(_bids.begin(), _bids.end());
            else        // file must be truncated
            {
                STXXL_VERBOSE1("~vector(): Changing size of file " << ((void *)_from) << " to "
                                                                   << file_length());
                STXXL_VERBOSE1("~vector(): size of the vector is " << size());
                try
                {
                    _from->set_size(file_length());
                }
                catch (...)
                {
                    STXXL_ERRMSG("Exception thrown in ~vector()...set_size()");
                }
            }
        }
        delete _cache;
    }

    void export_files(std::string filename_prefix)
    {
        int64 no = 0;
        for (bids_container_iterator i = _bids.begin(); i != _bids.end(); ++i) {
            std::ostringstream number;
            number << std::setw(9) << std::setfill('0') << no;
            size_type current_block_size =
                ((i + 1) == _bids.end() && _size % block_type::size > 0) ?
                (_size % block_type::size) * sizeof(value_type) :
                block_type::size * sizeof(value_type);
            (*i).storage->export_files((*i).offset, current_block_size, filename_prefix + number.str());
            ++no;
        }
        exported = true;
    }

    file * get_file() const
    {
        return _from;
    }

    template <typename ForwardIterator>
    void set_content(const ForwardIterator & bid_begin, const ForwardIterator & bid_end, size_type n)
    {
        unsigned_type new_bids_size = div_ceil(n, block_type::size);
        _bids.resize(new_bids_size);
        std::copy(bid_begin, bid_end, _bids.begin());
        unsigned_type new_pages = div_ceil(new_bids_size, page_size);
        _page_status.resize(new_pages, valid_on_disk);
        _page_to_slot.resize(new_pages, on_disk);
        _size = n;
    }

private:
    bids_container_iterator bid(const size_type & offset)
    {
        return (_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset / block_type::size));
    }
    bids_container_iterator bid(const blocked_index_type & offset)
    {
        return (_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset.get_block2() * PgSz_ + offset.get_block1()));
    }
    const_bids_container_iterator bid(const size_type & offset) const
    {
        return (_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset / block_type::size));
    }
    const_bids_container_iterator bid(const blocked_index_type & offset) const
    {
        return (_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset.get_block2() * PgSz_ + offset.get_block1()));
    }

    void read_page(int_type page_no, int_type cache_slot) const
    {
        if (_page_status[page_no] == uninitialized)
            return;
        STXXL_VERBOSE1("vector " << this << ": reading page_no=" << page_no << " cache_slot=" << cache_slot);
        request_ptr * reqs = new request_ptr[page_size];
        int_type block_no = page_no * page_size;
        int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size()));
        int_type i = cache_slot * page_size, j = 0;
        for ( ; block_no < last_block; ++block_no, ++i, ++j)
        {
            reqs[j] = (*_cache)[i].read(_bids[block_no]);
        }
        assert(last_block - page_no * page_size > 0);
        wait_all(reqs, last_block - page_no * page_size);
        delete[] reqs;
    }
    void write_page(int_type page_no, int_type cache_slot) const
    {
        if (!(_page_status[page_no] & dirty))
            return;
        STXXL_VERBOSE1("vector " << this << ": writing page_no=" << page_no << " cache_slot=" << cache_slot);
        request_ptr * reqs = new request_ptr[page_size];
        int_type block_no = page_no * page_size;
        int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size()));
        int_type i = cache_slot * page_size, j = 0;
        for ( ; block_no < last_block; ++block_no, ++i, ++j)
        {
            reqs[j] = (*_cache)[i].write(_bids[block_no]);
        }
        _page_status[page_no] = valid_on_disk;
        assert(last_block - page_no * page_size > 0);
        wait_all(reqs, last_block - page_no * page_size);
        delete[] reqs;
    }

    reference element(size_type offset)
    {
        #ifdef STXXL_RANGE_CHECK
        assert(offset < size());
        #endif
        return element(blocked_index_type(offset));
    }

    reference element(const blocked_index_type & offset)
    {
        #ifdef STXXL_RANGE_CHECK
        assert(offset.get_pos() < size());
        #endif
        int_type page_no = offset.get_block2();
        assert(page_no < int_type(_page_to_slot.size()));   // fails if offset is too large, out of bound access
        int_type cache_slot = _page_to_slot[page_no];
        if (cache_slot < 0)                                 // == on_disk
        {
            if (_free_slots.empty())                        // has to kick
            {
                int_type kicked_slot = pager.kick();
                pager.hit(kicked_slot);
                int_type old_page_no = _slot_to_page[kicked_slot];
                _page_to_slot[page_no] = kicked_slot;
                _page_to_slot[old_page_no] = on_disk;
                _slot_to_page[kicked_slot] = page_no;

                write_page(old_page_no, kicked_slot);
                read_page(page_no, kicked_slot);

                _page_status[page_no] = dirty;

                return (*_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
            else
            {
                int_type free_slot = _free_slots.front();
                _free_slots.pop();
                pager.hit(free_slot);
                _page_to_slot[page_no] = free_slot;
                _slot_to_page[free_slot] = page_no;

                read_page(page_no, free_slot);

                _page_status[page_no] = dirty;

                return (*_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
        }
        else
        {
            _page_status[page_no] = dirty;
            pager.hit(cache_slot);
            return (*_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()];
        }
    }

    // don't forget to first flush() the vector's cache before updating pages externally
    void page_externally_updated(unsigned_type page_no) const
    {
        // fails if offset is too large, out of bound access
        assert(page_no < _page_status.size());
        // "A dirty page has been marked as newly initialized. The page content will be lost."
        assert(!(_page_status[page_no] & dirty));
        if (_page_to_slot[page_no] != on_disk) {
            // remove page from cache
            _free_slots.push(_page_to_slot[page_no]);
            _page_to_slot[page_no] = on_disk;
        }
        _page_status[page_no] = valid_on_disk;
    }

    void block_externally_updated(size_type offset) const
    {
        page_externally_updated(offset / (block_type::size * page_size));
    }

    void block_externally_updated(const blocked_index_type & offset) const
    {
        page_externally_updated(offset.get_block2());
    }

    _STXXL_DEPRECATED(void touch(size_type offset) const)
    {
        page_externally_updated(offset / (block_type::size * page_size));
    }

    _STXXL_DEPRECATED(void touch(const blocked_index_type & offset) const)
    {
        page_externally_updated(offset.get_block2());
    }

    const_reference const_element(size_type offset) const
    {
        return const_element(blocked_index_type(offset));
    }

    const_reference const_element(const blocked_index_type & offset) const
    {
        int_type page_no = offset.get_block2();
        assert(page_no < int_type(_page_to_slot.size()));   // fails if offset is too large, out of bound access
        int_type cache_slot = _page_to_slot[page_no];
        if (cache_slot < 0)                                 // == on_disk
        {
            if (_free_slots.empty())                        // has to kick
            {
                int_type kicked_slot = pager.kick();
                pager.hit(kicked_slot);
                int_type old_page_no = _slot_to_page[kicked_slot];
                _page_to_slot[page_no] = kicked_slot;
                _page_to_slot[old_page_no] = on_disk;
                _slot_to_page[kicked_slot] = page_no;

                write_page(old_page_no, kicked_slot);
                read_page(page_no, kicked_slot);

                return (*_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
            else
            {
                int_type free_slot = _free_slots.front();
                _free_slots.pop();
                pager.hit(free_slot);
                _page_to_slot[page_no] = free_slot;
                _slot_to_page[free_slot] = page_no;

                read_page(page_no, free_slot);

                return (*_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
        }
        else
        {
            pager.hit(cache_slot);
            return (*_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()];
        }
    }

    bool is_page_cached(const blocked_index_type & offset) const
    {
        int_type page_no = offset.get_block2();
        assert(page_no < int_type(_page_to_slot.size()));   // fails if offset is too large, out of bound access
        int_type cache_slot = _page_to_slot[page_no];
        return (cache_slot >= 0);                           // on_disk == -1
    }
};

template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
inline bool operator == (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & a,
                         stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & b)
{
    return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
}

template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
inline bool operator != (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & a,
                         stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & b)
{
    return !(a == b);
}

template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
inline bool operator < (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                      AllocStr_, SzTp_> & a,
                        stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                      AllocStr_, SzTp_> & b)
{
    return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
inline bool operator > (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                      AllocStr_, SzTp_> & a,
                        stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                      AllocStr_, SzTp_> & b)
{
    return b < a;
}

template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
inline bool operator <= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & a,
                         stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & b)
{
    return !(b < a);
}

template <
    typename Tp_,
    unsigned PgSz_,
    typename PgTp_,
    unsigned BlkSize_,
    typename AllocStr_,
    typename SzTp_>
inline bool operator >= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & a,
                         stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
                                       AllocStr_, SzTp_> & b)
{
    return !(a < b);
}



// specialization for stxxl::vector, to use only const_iterators
template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
          unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
bool is_sorted(
    stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first,
    stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last)
{
    return is_sorted_helper(
               stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first),
               stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last));
}

template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
          unsigned BlkSize_, typename PgTp_, unsigned PgSz_, typename _StrictWeakOrdering>
bool is_sorted(
    stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first,
    stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last,
    _StrictWeakOrdering __comp)
{
    return is_sorted_helper(
               stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first),
               stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last),
               __comp);
}




template <
    typename Tp_,
    unsigned PgSz_ = 4,
    unsigned Pages_ = 8,
    unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_),
    typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY,
    pager_type Pager_ = lru
    >
struct VECTOR_GENERATOR
{
    typedef typename IF<Pager_ == lru,
                        lru_pager<Pages_>, random_pager<Pages_> >::result PagerType;

    typedef vector<Tp_, PgSz_, PagerType, BlkSize_, AllocStr_> result;
};



__STXXL_END_NAMESPACE


namespace std
{
    template <
        typename Tp_,
        unsigned PgSz_,
        typename PgTp_,
        unsigned BlkSize_,
        typename AllocStr_,
        typename SzTp_>
    void swap(stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & a,
              stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & b)
    {
        a.swap(b);
    }
}

#endif // !STXXL_VECTOR_HEADER
// vim: et:ts=4:sw=4