bool_array.h

Go to the documentation of this file.

// -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
// vim:tabstop=4:shiftwidth=4:expandtab:

/*
 * Copyright (C) 2004-2013 Wu Yongwei <adah at users dot sourceforge dot net>
 *
 * This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the authors be held liable for any
 * damages arising from the use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute
 * it freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must
 *    not claim that you wrote the original software.  If you use this
 *    software in a product, an acknowledgement in the product
 *    documentation would be appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must
 *    not be misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source
 *    distribution.
 *
 * This file is part of Stones of Nvwa:
 *      http://sourceforge.net/projects/nvwa
 *
 */

#ifndef NVWA_BOOL_ARRAY_H
#define NVWA_BOOL_ARRAY_H

#include <assert.h>             // assert
#include <stdlib.h>             // exit/free/NULL
#include <new>                  // std::bad_alloc
#include <stdexcept>            // std::out_of_range
#include <string>               // for exception constructors
#include "_nvwa.h"              // NVWA_NAMESPACE_*
#include "c++11.h"              // _NOEXCEPT

NVWA_NAMESPACE_BEGIN

class bool_array
{
public:
#if (defined(__x86_64) || defined(__ia64) || defined(__ppc64__) || \
     defined(_WIN64) || defined(_M_IA64)) && \
    !(defined(_LP64) || defined(__lp64))

    typedef unsigned long long  size_type;
#else

    typedef unsigned long       size_type;
#endif

private:
    typedef unsigned char       byte;

    template <typename _Byte_type>
    class _Element
    {
    public:
        _Element(_Byte_type* ptr, size_type pos);
        bool operator=(bool value);
        operator bool() const;
    private:
        _Byte_type* _M_byte_ptr;
        size_t      _M_byte_pos;
        size_t      _M_bit_pos;
    };

public:
    typedef _Element<byte> reference;              
    typedef _Element<const byte> const_reference;  

#if defined(_MSC_VER) && _MSC_VER < 1300
    enum { npos = (size_type)-1   };
#else

    static const size_type npos = (size_type)-1;
#endif

    bool_array() _NOEXCEPT;
    explicit bool_array(size_type size);
    bool_array(const void* ptr, size_type size);
    ~bool_array();

    bool_array(const bool_array& rhs);
    bool_array& operator=(const bool_array& rhs);

    bool create(size_type size) _NOEXCEPT;
    void initialize(bool value) _NOEXCEPT;

    reference operator[](size_type pos);
    const_reference operator[](size_type pos) const;

    bool at(size_type pos) const;
    void reset(size_type pos);
    void set(size_type pos);

    size_type size() const _NOEXCEPT;
    size_type count() const _NOEXCEPT;
    size_type count(size_type begin, size_type end = npos) const;
    size_type find(bool value, size_type offset = 0) const;
    size_type find(bool value, size_type offset, size_type count) const;
    size_type find_until(bool value, size_type begin, size_type end) const;

    void flip() _NOEXCEPT;
    void swap(bool_array& rhs) _NOEXCEPT;
    void merge_and(const bool_array& rhs,
                   size_type begin = 0,
                   size_type end = npos,
                   size_type offset = 0);
    void merge_or (const bool_array& rhs,
                   size_type begin = 0,
                   size_type end = npos,
                   size_type offset = 0);
    void copy_to_bitmap(void* dest, size_type begin = 0, size_type end = npos);

    static size_t get_num_bytes_from_bits(size_type num_bits);

private:
    byte get_8bits(size_type offset, size_type end) const;

    byte*           _M_byte_ptr;
    size_type       _M_length;
    static byte     _S_bit_count[256];
    static byte     _S_bit_ordinal[256];
};


/* Inline functions */

template <typename _Byte_type>
inline bool_array::_Element<_Byte_type>::_Element(
        _Byte_type* ptr,
        size_type pos)
{
    _M_byte_ptr = ptr;
    _M_byte_pos = (size_t)(pos / 8);
    _M_bit_pos  = (size_t)(pos % 8);
}

template <typename _Byte_type>
inline bool bool_array::_Element<_Byte_type>::operator=(bool value)
{
    if (value)
        *(_M_byte_ptr + _M_byte_pos) |= 1 << _M_bit_pos;
    else
        *(_M_byte_ptr + _M_byte_pos) &= ~(1 << _M_bit_pos);
    return value;
}

template <typename _Byte_type>
inline bool_array::_Element<_Byte_type>::operator bool() const
{
    return *(_M_byte_ptr + _M_byte_pos) & (1 << _M_bit_pos) ? true : false;
}

inline bool_array::bool_array() _NOEXCEPT : _M_byte_ptr(NULL), _M_length(0)
{
}

inline bool_array::~bool_array()
{
    if (_M_byte_ptr != NULL)
        free(_M_byte_ptr);
}

inline bool_array::reference bool_array::operator[](size_type pos)
{
    assert(_M_byte_ptr);
    assert(pos < _M_length);
    return reference(_M_byte_ptr, pos);
}

inline bool_array::const_reference bool_array::operator[](size_type pos) const
{
    assert(_M_byte_ptr);
    assert(pos < _M_length);
    return const_reference(_M_byte_ptr, pos);
}

inline bool bool_array::at(size_type pos) const
{
    size_t byte_pos, bit_pos;
    if (pos >= _M_length)
        throw std::out_of_range("invalid bool_array position");
    byte_pos = (size_t)(pos / 8);
    bit_pos  = (size_t)(pos % 8);
    return *(_M_byte_ptr + byte_pos) & (1 << bit_pos) ? true : false;
}

inline void bool_array::reset(size_type pos)
{
    size_t byte_pos, bit_pos;
    if (pos >= _M_length)
        throw std::out_of_range("invalid bool_array position");
    byte_pos = (size_t)(pos / 8);
    bit_pos  = (size_t)(pos % 8);
    *(_M_byte_ptr + byte_pos) &= ~(1 << bit_pos);
}

inline void bool_array::set(size_type pos)
{
    size_t byte_pos, bit_pos;
    if (pos >= _M_length)
        throw std::out_of_range("invalid bool_array position");
    byte_pos = (size_t)(pos / 8);
    bit_pos  = (size_t)(pos % 8);
    *(_M_byte_ptr + byte_pos) |= 1 << bit_pos;
}

inline bool_array::size_type bool_array::size() const _NOEXCEPT
{
    return _M_length;
}

inline bool_array::size_type bool_array::find(
        bool value,
        size_type offset) const
{
    return find_until(value, offset, _M_length);
}

inline bool_array::size_type bool_array::find(
        bool value,
        size_type offset,
        size_type count) const
{
    return find_until(value, offset, offset + count);
}

inline size_t bool_array::get_num_bytes_from_bits(size_type num_bits)
{
    return (size_t)((num_bits + 7) / 8);
}

inline void swap(bool_array& lhs, bool_array& rhs) _NOEXCEPT
{
    lhs.swap(rhs);
}

NVWA_NAMESPACE_END

#endif // NVWA_BOOL_ARRAY_H

---