extl/container/bit_array.h

   1 /* ///////////////////////////////////////////////////////////////////////
   2  * File:                bit_array.h
   3  *
   4  * Created:             08.10.02
   5  * Updated:             08.10.02
   6  *
   7  * Brief:               The bit_array class
   8  *
   9  * [<Home>]
  10  * Copyright (c) 2008-2020, Waruqi All rights reserved.
  11  * //////////////////////////////////////////////////////////////////// */
  12
  13 #ifndef EXTL_CONTAINER_BIT_ARRAY_H
  14 #define EXTL_CONTAINER_BIT_ARRAY_H
  15
  16 /*!\file bit_array.h
  17  *
  18  * \brief bit_array class
  19  */
  20
  21 /* ///////////////////////////////////////////////////////////////////////
  22  * Includes
  23  */
  24 #include "prefix.h"
  25 #include "../algorithm/algorithm.h"
  26 #include "detail/bit_array_iterator.h"
  27 #include "../memory/buffer.h"
  28 #include "../string/string.h"
  29
  30 /* ///////////////////////////////////////////////////////////////////////
  31  * ::extl namespace
  32  */
  33 EXTL_BEGIN_NAMESPACE
  34
  35 /*!brief bit_array
  36  *
  37  * \param Fld The field type
  38  * \param Buf The buffer type
  39  *
  40  * \ingroup extl_group_container
  41  */
  42 #ifdef EXTL_TEMPLATE_CLASS_DEFAULT_ARGUMENT_SUPPORT
  43 template<       typename_param_k Fld = e_size_t
  44                 ,       typename_param_k Buf = typename_type_def_k buffer_selector<Fld>::buffer_type
  45                 >
  46 #else
  47 template<       typename_param_k Fld
  48                 ,       typename_param_k Buf
  49                 >
  50 #endif
  51 class bit_array
  52 {
  53         /// \name Types
  54         /// @{
  55         public:
  56                 typedef bit_array                                                                                                                       class_type;
  57                 typedef e_bool_t                                                                                                                        bool_type;
  58                 typedef e_size_t                                                                                                                        size_type;
  59                 typedef e_char_t                                                                                                                        achar_type;
  60                 typedef e_wchar_t                                                                                                                       wchar_type;
  61                 typedef size_type                                                                                                                       index_type;
  62                 typedef bool_type                                                                                                                       value_type;
  63                 typedef value_type*                                                                                                                     pointer;
  64                 typedef value_type const*                                                                                                       const_pointer;
  65                 typedef value_type&                                                                                                                     reference;
  66                 typedef value_type const&                                                                                                       const_reference;
  67                 typedef Fld                                                                                                                                     field_type;
  68                 typedef Buf                                                                                                                                     buffer_type;
  69                 typedef typename_type_k buffer_type::allocator_type                                                     allocator_type;
  70                 typedef EXTL_NS_DETAIL(const_bit_array_iterator)<field_type, buffer_type>       const_iterator;
  71         /// @}
  72
  73         /// \name Members
  74         private:
  75                 buffer_type                                                                                                                                     m_buffer;
  76                 size_type                                                                                                                                       m_size;
  77         /// @}
  78
  79         private:
  80                 enum { en_field_bit_count = 8 * sizeof(field_type) };
  81
  82         /// \name Constructors
  83         /// @{
  84         public:
  85                 /// Default Constructor
  86                 bit_array()
  87                 {
  88                         clear();
  89                 }
  90                 /// Copy Constructor
  91                 bit_array(class_type const& rhs)
  92                 {
  93                         assign(rhs);
  94                 }
  95                 /// Constructs with n-bits values from the given array
  96                 bit_array(class_type const& rhs, size_type n)
  97                 {
  98                         assign(rhs, n);
  99                 }
 100                 /// Constructs with n-bits default values
 101                 explicit_k bit_array(size_type n)
 102                 {
 103                         assign(value_type(), n);
 104                 }
 105                 /// Constructs with n-bits given values
 106                 bit_array(const_reference value, size_type n)
 107                 {
 108                         assign(value, n);
 109                 }
 110                 /// Constructs with n-bits values from bool array
 111                 bit_array(const_pointer p, size_type n)
 112                 {
 113                         assign(p, n);
 114                 }
 115                 /// Constructs from ascii string with null-terminator
 116                 explicit_k bit_array(achar_type const* s)
 117                 {
 118                         assign(s);
 119                 }
 120                 /// Constructs from unicode string with null-terminator
 121                 explicit_k bit_array(wchar_type const* s)
 122                 {
 123                         assign(s);
 124                 }
 125                 /// Constructs with n-bits values from ascii string
 126                 bit_array(achar_type const* s, size_type n)
 127                 {
 128                         assign(s, n);
 129                 }
 130                 /// Constructs with n-bits values from unicode string
 131                 bit_array(wchar_type const* s, size_type n)
 132                 {
 133                         assign(s, n);
 134                 }
 135         /// @}
 136
 137         /// \name Attributes
 138         /// @{
 139         public:
 140                 /// Returns the allocator of the array
 141                 allocator_type          allocator() const               { return buffer().allocator();                                                          }
 142                 /// Returns the bit count
 143                 size_type                       size() const                    { return m_size;                                                                                        }
 144                 /// Returns the reserved bit count in the array
 145                 size_type                       capacity() const                { return (buffer().capacity() * en_field_bit_count);            }
 146                 /// Return \c true if size() == 0
 147                 bool_type                       is_empty() const                { return 0 == m_size;                                                                           }
 148                 /// Return \c true if size() == 0
 149                 bool_type                       empty() const                   { return is_empty();                                                                            }
 150                 /// Return the maximum bit count of the array
 151                 size_type                       max_size()                              { return (buffer().max_size() * en_field_bit_count);            }
 152         /// @}
 153
 154         /// \name Iterators
 155         /// @{
 156         public:
 157                 /// Returns the const begin iterator
 158                 const_iterator          begin() const                   { return const_iterator(&buffer(), 0);          }
 159                 /// Returns the const end iterator
 160                 const_iterator          end() const                             { return const_iterator(&buffer(), size());     }
 161         /// @}
 162
 163         /// \name Accessors
 164         /// @{
 165         public:
 166                 /// Returns the field value
 167                 field_type const*       data() const                    { return buffer().data();       }
 168                 /// Returns the field value
 169                 field_type const*       fields() const                  { return buffer().data();       }
 170                 /// Returns the numeric of this field
 171                 field_type                      numeric() const;
 172                 /// Returns const value at the given index
 173                 value_type const        operator[](index_type index) const      { return get(index);    }
 174                 /// Returns const value at the given index and throws index_error() if index >= size()
 175                 value_type const        at(index_type index) const;
 176                 /// Returns const value at the given index
 177                 value_type const        get(index_type index) const;
 178                 /// Returns const value at the front of field
 179                 value_type const        front() const   { return at(0);                         }
 180                 /// Returns const value at the back of field
 181                 value_type const        back()  const   { return at(size() - 1);        }
 182         /// @}
 183
 184         /// \name Mutators
 185         /// @{
 186         public:
 187                 /// Clears the field e.g. 001101 => null
 188                 void                            clear()                                 { buffer().clear(); m_size = 0; }
 189                 /// Cleans the field e.g. 001101 => 000000
 190                 void                            clean()                                 { buffer().clean();                             }
 191                 /// Swaps the content of array
 192                 void                            swap(class_type& rhs)   { buffer().swap(rhs.buffer()); std_swap(m_size, rhs.m_size);    }
 193                 /// Sets the value at the given position
 194                 void                            set(index_type index, const_reference value);
 195                 /// Resizes the bit count of the array
 196                 void                            resize(size_type n, const_reference new_value = value_type());
 197                 /// Pushes back the given value
 198                 void                            push_back(const_reference value)        { resize(size() + 1, value);    }
 199                 /// Pops back from this array
 200                 void                            pop_back()                                                      { resize(size() - 1);                   }
 201                 /// Sets the numeric
 202                 void                            numeric(field_type num)                         { buffer().assign(num, 1u); xtl_min(size_type(en_field_bit_count), size());             }
 203         /// @}
 204
 205         /// \name Assignments
 206         /// @{
 207         public:
 208                 /// Assigns from the given value
 209                 class_type&                     assign(const_reference value)                           { return assign(value, 1u);     }
 210                 /// Assigns with n-bits given values
 211                 class_type&                     assign(const_reference value, size_type n);
 212                 /// Assigns with n-bits values from bool array
 213                 class_type&                     assign(const_pointer p, size_type n);
 214                 /// Assigns with n-bits values from ascii string
 215                 class_type&                     assign(achar_type const* s, size_type n);
 216                 /// Assigns with n-bits values from unicode string
 217                 class_type&                     assign(wchar_type const* s, size_type n);
 218                 /// Assigns from ascii string with null-terminator
 219                 class_type&                     assign(achar_type const* s)                                     { return assign(s, (NULL != s)? std_strlen(s) : 0);     }
 220                 /// Assigns from unicode string with null-terminator
 221                 class_type&                     assign(wchar_type const* s)                                     { return assign(s, (NULL != s)? std_strlen(s) : 0);     }
 222                 /// Assigns from the given field
 223                 class_type&                     assign(class_type const& rhs, size_type n);
 224                 /// Assigns from the given field
 225                 class_type&                     assign(class_type const& rhs)                           { return assign(rhs, rhs.size());       }
 226                 /// Assigns from the given field
 227                 class_type&                     operator =(class_type const& rhs)                       { return assign(rhs);                           }
 228                 /// Assigns from the given value(fill all)
 229                 class_type&                     operator =(const_reference value)                       { return assign(value);                         }
 230                 /// Assigns from ascii string with null-terminator
 231                 class_type&                     operator =(achar_type const* s)                         { return assign(s);                                     }
 232                 /// Assigns from unicode string with null-terminator
 233                 class_type&                     operator =(wchar_type const* s)                         { return assign(s);                                     }
 234         /// @}
 235
 236         /// \name Appends
 237         /// @{
 238         public:
 239                 /// Appends from the given value
 240                 class_type&                     append(const_reference value)                           { return append(value, 1);      }
 241                 /// Appends with n-bits given values
 242                 class_type&                     append(const_reference value, size_type n);
 243                 /// Appends with n-bits values from bool array
 244                 class_type&                     append(const_pointer p, size_type n);
 245                 /// Appends with n-bits values from ascii string
 246                 class_type&                     append(achar_type const* s, size_type n);
 247                 /// Appends with n-bits values from unicode string
 248                 class_type&                     append(wchar_type const* s, size_type n);
 249                 /// Appends from ascii string with null-terminator
 250                 class_type&                     append(achar_type const* s)                                     { return append(s, (NULL != s)? std_strlen(s) : 0);     }
 251                 /// Appends from unicode string with null-terminator
 252                 class_type&                     append(wchar_type const* s)                                     { return append(s, (NULL != s)? std_strlen(s) : 0);     }
 253                 /// Appends from the given field
 254                 class_type&                     append(class_type const& rhs, size_type n);
 255                 /// Appends from the given field
 256                 class_type&                     append(class_type const& rhs)                           { return append(rhs, rhs.size());       }
 257                 /// Appends from the given field
 258                 class_type&                     operator +=(class_type const& rhs)                      { return append(rhs);                           }
 259                 /// Appends from the given value
 260                 class_type&                     operator +=(const_reference value)                      { return append(value);                         }
 261                 /// Appends from ascii string with null-terminator
 262                 class_type&                     operator +=(achar_type const* s)                        { return append(s);                                     }
 263                 /// Appends from unicode string with null-terminator
 264                 class_type&                     operator +=(wchar_type const* s)                        { return append(s);                                     }
 265         /// @}
 266
 267         /// \name Replacements
 268         /// @{
 269         public:
 270                 /// Replaces the given range [pos, pos + old_n) with the given bool array with n characters
 271                 class_type&                     replace(size_type pos, size_type old_n, const_pointer p, size_type n);
 272                 /// Replaces the given range [pos, pos + old_n) with the given n values
 273                 class_type&                     replace(size_type pos, size_type old_n, const_reference value, size_type n);
 274                 /// Replaces the given range [pos, pos + old_n) with the given ascii string with n characters
 275                 class_type&                     replace(size_type pos, size_type old_n, achar_type const* s, size_type n);
 276                 /// Replaces the given range [pos, pos + old_n) with the given unicode string with n characters
 277                 class_type&                     replace(size_type pos, size_type old_n, wchar_type const* s, size_type n);
 278                 /// Replaces the given range [pos, pos + old_n) with the given value
 279                 class_type&                     replace(size_type pos, size_type old_n, const_reference value)                          { return replace(pos, old_n, value, 1u);        }
 280                 /// Replaces the given range [pos, pos + old_n) with the given ascii string
 281                 class_type&                     replace(size_type pos, size_type old_n, achar_type const* s)                            { return replace(pos, old_n, s, (NULL != s)? std_strlen(s) : 0);        }
 282                 /// Replaces the given range [pos, pos + old_n) with the given unicode string
 283                 class_type&                     replace(size_type pos, size_type old_n, wchar_type const* s)                            { return replace(pos, old_n, s, (NULL != s)? std_strlen(s) : 0);        }
 284         /// @}
 285
 286         /// \name Inserts
 287         /// @{
 288         public:
 289                 /// Inserts the given bool array with n characters into the given position *this[pos]
 290                 class_type&                     insert(size_type pos, const_pointer p, size_type n)                     { return replace(pos, 0, p, n);         }
 291                 /// Inserts the given n values into the given position *this[pos]
 292                 class_type&                     insert(size_type pos, const_reference value, size_type n)       { return replace(pos, 0, value, n);     }
 293                 /// Inserts the given ascii string with n characters into the given position *this[pos]
 294                 class_type&                     insert(size_type pos, achar_type const* s, size_type n)         { return replace(pos, 0, s, n);         }
 295                 /// Inserts the given unicode string with n characters into the given position *this[pos]
 296                 class_type&                     insert(size_type pos, wchar_type const* s, size_type n)         { return replace(pos, 0, s, n);         }
 297                 /// Inserts the given value into the given position *this[pos]
 298                 class_type&                     insert(size_type pos, const_reference value)                            { return replace(pos, 0, value);        }
 299                 /// Inserts the given ascii string  into the given position *this[pos]
 300                 class_type&                     insert(size_type pos, achar_type const* s)                                      { return replace(pos, 0, s);            }
 301                 /// Inserts the given unicode string  into the given position *this[pos]
 302                 class_type&                     insert(size_type pos, wchar_type const* s)                                      { return replace(pos, 0, s);            }
 303         /// @}
 304
 305         /// \name Erases
 306         /// @{
 307         public:
 308                 /// Erases the given range [pos, pos + n)
 309                 class_type&                     erase(size_type pos, size_type n = 1u);
 310         /// @}
 311
 312         /// \name Reverses
 313         /// @{
 314         public:
 315                 /// Reverses this bit array with the given range [pos, pos + n)
 316                 class_type&                     reverse(size_type pos, size_type n);
 317                 /// Reverses the whole bit array
 318                 class_type&                     reverse()               { return reverse(0, size());    }
 319         /// @}
 320
 321         /// \name Static Methods
 322         /// @{
 323         public:
 324                 /// Makes numeric from bool array
 325                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 326                 static field_type       make_numeric(const_pointer p, size_type n, bool_type is_left_low = e_false_v);
 327                 /// Makes numeric from ascii string with n-characters
 328                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 329                 static field_type       make_numeric(achar_type const* s, size_type n, bool_type is_left_low = e_false_v);
 330                 /// Makes numeric from unicode string with n-characters
 331                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 332                 static field_type       make_numeric(wchar_type const* s, size_type n, bool_type is_left_low = e_false_v);
 333                 /// Makes numeric from ascii string with null-terminator
 334                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 335                 static field_type       make_numeric(achar_type const* s, bool_type is_left_low = e_false_v)            { return make_numeric(s, (NULL != s)? std_strlen(s) : 0, is_left_low);  }
 336                 /// Makes numeric from unicode string with null-terminator
 337                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 338                 static field_type       make_numeric(wchar_type const* s, bool_type is_left_low = e_false_v)            { return make_numeric(s, (NULL != s)? std_strlen(s) : 0, is_left_low);  }
 339         /// @}
 340
 341         /// \name Operators
 342         /// @{
 343         public:
 344                 /// Return the copy of ~(*this)
 345                 class_type                      operator ~();
 346                 /// Return \c true if *this == rhs
 347                 bool_type                       operator ==(class_type const& rhs) const;
 348                 /// Return \c true if *this != rhs
 349                 bool_type                       operator !=(class_type const& rhs) const        { return !((*this) == rhs);     }
 350                 /// *this &= rhs
 351                 class_type&                     operator &=(class_type const& rhs);
 352                 /// *this & rhs
 353                 class_type const        operator &(class_type const& rhs) const;
 354                 /// *this |= rhs
 355                 class_type&                     operator |=(class_type const& rhs);
 356                 /// *this | rhs
 357                 class_type const        operator |(class_type const& rhs) const;
 358                 /// *this ^= rhs
 359                 class_type&                     operator ^=(class_type const& rhs);
 360                 /// *this ^ rhs
 361                 class_type const        operator ^(class_type const& rhs) const;
 362         /// @}
 363
 364         /// \name Helper
 365         /// @{
 366         private:
 367                 buffer_type const&      buffer() const          { return m_buffer;      }
 368                 buffer_type&            buffer()                        { return m_buffer;      }
 369         /// @}
 370
 371 };
 372 /* ///////////////////////////////////////////////////////////////////////
 373  * Implementation
 374  */
 375
 376 // at(checked)
 377 template<       typename_param_k Fld
 378                 ,       typename_param_k Buf
 379                 >
 380 inline typename_type_ret_k bit_array<Fld, Buf>::
 381 value_type const bit_array<Fld, Buf>::at(index_type index) const
 382 {
 383         EXTL_ASSERT_THROW((index / en_field_bit_count) < size(), index_error("out of range"));
 384         return get(index);
 385 }
 386 // get(unchecked)
 387 template<       typename_param_k Fld
 388                 ,       typename_param_k Buf
 389                 >inline typename_type_ret_k bit_array<Fld, Buf>::
 390 value_type const bit_array<Fld, Buf>::get(index_type index) const
 391 {
 392         // low bit => high bit
 393         EXTL_ASSERT((index / en_field_bit_count) < buffer().size());
 394         return (field_type(0x1) == ((buffer()[index / en_field_bit_count] >> (index % en_field_bit_count)) & field_type(0x1)));
 395 }
 396 // set
 397 template<       typename_param_k Fld
 398                 ,       typename_param_k Buf
 399                 >
 400 inline void bit_array<Fld, Buf>::set(index_type index, const_reference value)
 401 {
 402         index_type i = index / en_field_bit_count;
 403         index_type n = index % en_field_bit_count;
 404
 405         EXTL_ASSERT(i < size());
 406
 407         // low bit => high bit
 408         buffer()[i] &= ~(field_type(0x1) << n);
 409         buffer()[i] |= (static_cast<field_type>(value) << n);
 410 }
 411
 412 // replace
 413 template<       typename_param_k Fld
 414                 ,       typename_param_k Buf
 415                 >
 416 inline typename_type_ret_k bit_array<Fld, Buf>::
 417 class_type& bit_array<Fld, Buf>::replace(size_type pos, size_type old_n, const_pointer p, size_type n)
 418 {
 419         EXTL_ASSERT(NULL != p);
 420         EXTL_ASSERT(pos >= 0 && pos < size());
 421
 422         if (old_n == n)
 423         {
 424                 EXTL_ASSERT((pos + n) <= size());
 425                 for (index_type i = 0; i < n; ++i)
 426                         set(pos + i, p[i]);
 427         }
 428         else
 429         {
 430                 class_type tmp(*this);
 431
 432                 if (pos + old_n > size()) old_n = size() - pos;
 433
 434                 size_type new_n = size() - (old_n - n);
 435                 EXTL_ASSERT(new_n <= max_size());
 436
 437                 resize(new_n);
 438                 for (index_type i = 0; i < n; ++i)
 439                         set(pos + i, p[i]);
 440
 441                 size_type left_n = tmp.size() - pos - old_n;
 442                 for (index_type j = 0; j < left_n; ++j)
 443                         set(pos + n + j, tmp[pos + old_n + j]);
 444         }
 445
 446         return *this;
 447 }
 448
 449 template<       typename_param_k Fld
 450                 ,       typename_param_k Buf
 451                 >
 452 inline typename_type_ret_k bit_array<Fld, Buf>::
 453 class_type& bit_array<Fld, Buf>::replace(size_type pos, size_type old_n, const_reference value, size_type n)
 454 {
 455         EXTL_ASSERT(pos >= 0 && pos < size());
 456         if (old_n == n)
 457         {
 458                 EXTL_ASSERT((pos + n) <= size());
 459                 for (index_type i = 0; i < n; ++i)
 460                         set(pos + i, value);
 461         }
 462         else
 463         {
 464                 class_type tmp(*this);
 465
 466                 if (pos + old_n > size()) old_n = size() - pos;
 467
 468                 size_type new_n = size() - (old_n - n);
 469                 EXTL_ASSERT(new_n <= max_size());
 470
 471                 resize(new_n);
 472                 for (index_type i = 0; i < n; ++i)
 473                         set(pos + i, value);
 474
 475                 size_type left_n = tmp.size() - pos - old_n;
 476                 for (index_type j = 0; j < left_n; ++j)
 477                         set(pos + n + j, tmp[pos + old_n + j]);
 478         }
 479
 480         return *this;
 481 }
 482
 483 template<       typename_param_k Fld
 484                 ,       typename_param_k Buf
 485                 >inline typename_type_ret_k bit_array<Fld, Buf>::
 486 class_type& bit_array<Fld, Buf>::replace(size_type pos, size_type old_n, achar_type const* s, size_type n)
 487 {
 488         EXTL_ASSERT(NULL != s);
 489         EXTL_ASSERT(pos >= 0 && pos < size());
 490
 491         if (old_n == n)
 492         {
 493                 EXTL_ASSERT((pos + n) <= size());
 494                 for (index_type i = 0; i < n; ++i)
 495                         set(pos + i, s[i] != '0');
 496         }
 497         else
 498         {
 499                 class_type tmp(*this);
 500
 501                 if (pos + old_n > size()) old_n = size() - pos;
 502
 503                 size_type new_n = size() - (old_n - n);
 504                 EXTL_ASSERT(new_n <= max_size());
 505
 506                 resize(new_n);
 507                 for (index_type i = 0; i < n; ++i)
 508                         set(pos + i, s[i] != '0');
 509
 510                 size_type left_n = tmp.size() - pos - old_n;
 511                 for (index_type j = 0; j < left_n; ++j)
 512                         set(pos + n + j, tmp[pos + old_n + j]);
 513         }
 514
 515         return *this;
 516 }
 517
 518 template<       typename_param_k Fld
 519                 ,       typename_param_k Buf
 520                 >
 521 inline typename_type_ret_k bit_array<Fld, Buf>::
 522 class_type& bit_array<Fld, Buf>::replace(size_type pos, size_type old_n, wchar_type const* s, size_type n)
 523 {
 524         EXTL_ASSERT(NULL != s);
 525         EXTL_ASSERT(pos >= 0 && pos < size());
 526
 527         if (old_n == n)
 528         {
 529                 EXTL_ASSERT((pos + n) <= size());
 530                 for (index_type i = 0; i < n; ++i)
 531                         set(pos + i, s[i] != L'0');
 532         }
 533         else
 534         {
 535                 class_type tmp(*this);
 536
 537                 if (pos + old_n > size()) old_n = size() - pos;
 538
 539                 size_type new_n = size() - (old_n - old_n);
 540                 EXTL_ASSERT(new_n <= max_size());
 541
 542                 resize(new_n);
 543                 for (index_type i = 0; i < n; ++i)
 544                         set(pos + i, s[i] != L'0');
 545
 546                 size_type left_n = tmp.size() - pos - old_n;
 547                 for (index_type j = 0; j < left_n; ++j)
 548                         set(pos + n + j, tmp[pos + old_n + j]);
 549         }
 550
 551         return *this;
 552 }
 553
 554 // assign
 555 template<       typename_param_k Fld
 556                 ,       typename_param_k Buf
 557                 >
 558 inline typename_type_ret_k bit_array<Fld, Buf>::
 559 class_type& bit_array<Fld, Buf>::assign(const_reference value, size_type n)
 560 {
 561         EXTL_ASSERT(n <= max_size());
 562
 563         resize(n);
 564         for (index_type i = 0; i < n; ++i)
 565                 set(i, value);
 566
 567         return *this;
 568 }
 569
 570 template<       typename_param_k Fld
 571                 ,       typename_param_k Buf
 572                 >
 573 inline typename_type_ret_k bit_array<Fld, Buf>::
 574 class_type& bit_array<Fld, Buf>::assign(const_pointer p, size_type n)
 575 {
 576         EXTL_ASSERT(n <= max_size());
 577         EXTL_ASSERT(NULL != p);
 578
 579         resize(n);
 580         for (index_type i = 0; i < n; ++i)
 581                 set(i, p[i]);
 582
 583         return *this;
 584 }
 585
 586 template<       typename_param_k Fld
 587                 ,       typename_param_k Buf
 588                 >
 589 inline typename_type_ret_k bit_array<Fld, Buf>::
 590 class_type& bit_array<Fld, Buf>::assign(achar_type const* s, size_type n)
 591 {
 592         EXTL_ASSERT(n <= max_size());
 593         EXTL_ASSERT(NULL != s);
 594
 595         resize(n);
 596         for (index_type i = 0; i < n; ++i)
 597                 set(i, s[i] != '0');
 598
 599         return *this;
 600 }
 601
 602 template<       typename_param_k Fld
 603                 ,       typename_param_k Buf
 604                 >
 605 inline typename_type_ret_k bit_array<Fld, Buf>::
 606 class_type& bit_array<Fld, Buf>::assign(wchar_type const* s, size_type n)
 607 {
 608         EXTL_ASSERT(n <= max_size());
 609         EXTL_ASSERT(NULL != s);
 610
 611         resize(n);
 612         for (index_type i = 0; i < n; ++i)
 613                 set(i, s[i] != L'0');
 614
 615         return *this;
 616 }
 617 template<       typename_param_k Fld
 618                 ,       typename_param_k Buf
 619                 >
 620 inline typename_type_ret_k bit_array<Fld, Buf>::
 621 class_type& bit_array<Fld, Buf>::assign(class_type const& rhs, size_type n)
 622 {
 623         EXTL_ASSERT(n <= max_size());
 624         EXTL_ASSERT(n <= rhs.size());
 625
 626         if (this != &rhs)
 627         {
 628                 buffer().assign(rhs.buffer(), EXTL_ALIGN(n, en_field_bit_count) / en_field_bit_count);
 629                 m_size = n;
 630         }
 631         return *this;
 632 }
 633 // append
 634 template<       typename_param_k Fld
 635                 ,       typename_param_k Buf
 636                 >
 637 inline typename_type_ret_k bit_array<Fld, Buf>::
 638 class_type& bit_array<Fld, Buf>::append(const_reference value, size_type n)
 639 {
 640         size_type bit_n = size() + n;
 641         EXTL_ASSERT(bit_n <= max_size());
 642
 643         resize(bit_n, value);
 644         return *this;
 645 }
 646
 647 template<       typename_param_k Fld
 648                 ,       typename_param_k Buf
 649                 >
 650 inline typename_type_ret_k bit_array<Fld, Buf>::
 651 class_type& bit_array<Fld, Buf>::append(const_pointer p, size_type n)
 652 {
 653         size_type bit_n = size();
 654         EXTL_ASSERT((bit_n + n) <= max_size());
 655         EXTL_ASSERT(NULL != p);
 656
 657         resize(bit_n + n);
 658         for (index_type i = 0; i < n; ++i)
 659                 set(bit_n + i, p[i]);
 660
 661         return *this;
 662 }
 663
 664 template<       typename_param_k Fld
 665                 ,       typename_param_k Buf
 666                 >
 667 inline typename_type_ret_k bit_array<Fld, Buf>::
 668 class_type& bit_array<Fld, Buf>::append(achar_type const* s, size_type n)
 669 {
 670         size_type bit_n = size();
 671         EXTL_ASSERT((bit_n + n) <= max_size());
 672         EXTL_ASSERT(NULL != s);
 673
 674         resize(bit_n + n);
 675         for (index_type i = 0; i < n; ++i)
 676                 set(bit_n + i, s[i] != '0');
 677
 678         return *this;
 679 }
 680
 681 template<       typename_param_k Fld
 682                 ,       typename_param_k Buf
 683                 >
 684 inline typename_type_ret_k bit_array<Fld, Buf>::
 685 class_type& bit_array<Fld, Buf>::append(wchar_type const* s, size_type n)
 686 {
 687         size_type bit_n = size();
 688         EXTL_ASSERT((bit_n + n) <= max_size());
 689         EXTL_ASSERT(NULL != s);
 690
 691         resize(bit_n + n);
 692         for (index_type i = 0; i < n; ++i)
 693                 set(bit_n + i, s[i] != L'0');
 694
 695         return *this;
 696 }
 697
 698 template<       typename_param_k Fld
 699                 ,       typename_param_k Buf
 700                 >
 701 inline typename_type_ret_k bit_array<Fld, Buf>::
 702 class_type& bit_array<Fld, Buf>::append(class_type const& rhs, size_type n)
 703 {
 704         size_type bit_n = size();
 705         EXTL_ASSERT((bit_n + n) <= max_size());
 706         EXTL_ASSERT(n <= rhs.size());
 707
 708         resize(bit_n + n);
 709         for (index_type i = 0; i < n; ++i)
 710                 set(bit_n + i, rhs[i]);
 711
 712         return *this;
 713 }
 714
 715 template<       typename_param_k Fld
 716                 ,       typename_param_k Buf
 717                 >
 718 inline typename_type_ret_k bit_array<Fld, Buf>::
 719 class_type& bit_array<Fld, Buf>::erase(size_type pos, size_type n)
 720 {
 721         EXTL_ASSERT(n > 0);
 722         EXTL_ASSERT(pos >= 0 && pos < size());
 723
 724         if (pos + n > size()) n = size() - pos;
 725
 726         if ((0 == pos) && (n == size()))
 727         {
 728                 clear();
 729         }
 730         else if (!(pos % en_field_bit_count) && !(n % en_field_bit_count))
 731         {
 732                 buffer().erase(pos / en_field_bit_count, n / en_field_bit_count);
 733                 m_size -= n;
 734         }
 735         else
 736         {
 737                 class_type tmp(*this);
 738                 resize(size() - n);
 739                 size_type left_n = tmp.size() - pos - n;
 740                 for (index_type i = 0; i < left_n; ++i)
 741                         set(pos + i, tmp[pos + n + i]);
 742         }
 743         return *this;
 744 }
 745 // resize
 746 template<       typename_param_k Fld
 747                 ,       typename_param_k Buf
 748                 >
 749 inline void bit_array<Fld, Buf>::resize(size_type n, const_reference new_value)
 750 {
 751         EXTL_ASSERT(n <= max_size());
 752
 753         if (n <= size())
 754         {
 755                 m_size = n;
 756                 buffer().resize((n / en_field_bit_count) + 1);
 757         }
 758         else
 759         {
 760                 index_type i = m_size;
 761                 m_size = n;
 762                 buffer().resize((n / en_field_bit_count) + 1);
 763                 for (; i < n; ++i)
 764                         set(i, new_value);
 765         }
 766 }
 767 // reverse
 768 template<       typename_param_k Fld
 769                 ,       typename_param_k Buf
 770                 >
 771 inline typename_type_ret_k bit_array<Fld, Buf>::
 772 class_type& bit_array<Fld, Buf>::reverse(size_type pos, size_type n)
 773 {
 774         EXTL_ASSERT(pos >= 0 && (pos + n) <= size());
 775         EXTL_ASSERT(n > 0);
 776
 777         index_type begin = 0;
 778         index_type end = n - 1;
 779
 780         while (begin < end)
 781         {
 782                 value_type tmp = get(begin);
 783                 set(begin++, get(end));
 784                 set(end--, tmp);
 785         }
 786
 787         return *this;
 788 }
 789 // numeric
 790 template<       typename_param_k Fld
 791                 ,       typename_param_k Buf
 792                 >
 793 inline typename_type_ret_k bit_array<Fld, Buf>::
 794 field_type bit_array<Fld, Buf>::numeric() const
 795 {
 796         field_type num = 0;
 797         field_type p2 = 1;
 798
 799         size_type n = xtl_min(size_type(en_field_bit_count), size());
 800         for (index_type i = 0; i < n; ++i)
 801         {
 802                 num += get(i) * p2;
 803                 p2 <<= 1;
 804         }
 805
 806         return num;
 807 }
 808 // make_numeric
 809 template<       typename_param_k Fld
 810                 ,       typename_param_k Buf
 811                 >
 812 inline typename_type_ret_k bit_array<Fld, Buf>::
 813 field_type bit_array<Fld, Buf>::make_numeric(const_pointer p, size_type n, bool_type is_left_low)
 814 {
 815         EXTL_ASSERT(NULL != p);
 816
 817         field_type num = 0;
 818         field_type p2 = 1;
 819
 820         if (is_left_low)
 821         {
 822                 for (index_type i = 0; i < n; ++i)
 823                 {
 824                         num += p[i] * p2;
 825                         p2 <<= 1;
 826                 }
 827         }
 828         else
 829         {
 830                 for (index_type i = 0; i < n; ++i)
 831                 {
 832                         num += p[n - i - 1] * p2;
 833                         p2 <<= 1;
 834                 }
 835         }
 836         return num;
 837 }
 838
 839 template<       typename_param_k Fld
 840                 ,       typename_param_k Buf
 841                 >
 842 inline typename_type_ret_k bit_array<Fld, Buf>::
 843 field_type bit_array<Fld, Buf>::make_numeric(achar_type const* s, size_type n, bool_type is_left_low)
 844 {
 845         EXTL_ASSERT(NULL != s);
 846
 847         field_type num = 0;
 848         field_type p2 = 1;
 849
 850         if (is_left_low)
 851         {
 852                 for (index_type i = 0; i < n; ++i)
 853                 {
 854                         num += (s[i] != '0') * p2;
 855                         p2 <<= 1;
 856                 }
 857         }
 858         else
 859         {
 860                 for (index_type i = 0; i < n; ++i)
 861                 {
 862                         num += (s[n - i - 1] != '0') * p2;
 863                         p2 <<= 1;
 864                 }
 865         }
 866         return num;
 867 }
 868
 869 template<       typename_param_k Fld
 870                 ,       typename_param_k Buf
 871                 >
 872 inline typename_type_ret_k bit_array<Fld, Buf>::
 873 field_type bit_array<Fld, Buf>::make_numeric(wchar_type const* s, size_type n, bool_type is_left_low)
 874 {
 875         EXTL_ASSERT(NULL != s);
 876
 877         field_type num = 0;
 878         field_type p2 = 1;
 879
 880         if (is_left_low)
 881         {
 882                 for (index_type i = 0; i < n; ++i)
 883                 {
 884                         num += (s[i] != L'0') * p2;
 885                         p2 <<= 1;
 886                 }
 887         }
 888         else
 889         {
 890                 for (index_type i = 0; i < n; ++i)
 891                 {
 892                         num += (s[n - i - 1] != L'0') * p2;
 893                         p2 <<= 1;
 894                 }
 895         }
 896         return num;
 897 }
 898 // operator ~
 899 template<       typename_param_k Fld
 900                 ,       typename_param_k Buf
 901                 >
 902 inline typename_type_ret_k bit_array<Fld, Buf>::
 903 class_type bit_array<Fld, Buf>::operator ~()
 904 {
 905         class_type tmp(*this);
 906         size_type n = tmp.buffer().size();
 907         for (index_type i = 0; i < n; ++i)
 908         {
 909                 tmp.buffer()[i] = ~tmp.buffer()[i];
 910         }
 911         return tmp;
 912 }
 913 // operator ==
 914 template<       typename_param_k Fld
 915                 ,       typename_param_k Buf
 916                 >
 917 inline typename_type_ret_k bit_array<Fld, Buf>::
 918 bool_type bit_array<Fld, Buf>::operator ==(class_type const& rhs) const
 919 {
 920         size_type bit_n = size();
 921         if (bit_n != rhs.size()) return e_false_v;
 922
 923         size_type n = buffer().size();
 924         for (index_type i = 0; i < (n - 1); ++i)
 925         {
 926                 if (buffer()[i] != rhs.buffer()[i])
 927                         return e_false_v;
 928         }
 929
 930         for (index_type j = (n - 1) * en_field_bit_count; j < bit_n; ++j)
 931         {
 932                 if (get(j) != rhs.get(j))
 933                         return e_false_v;
 934         }
 935
 936         return e_true_v;
 937 }
 938 // operator &=
 939 template<       typename_param_k Fld
 940                 ,       typename_param_k Buf
 941                 >
 942 inline typename_type_ret_k bit_array<Fld, Buf>::
 943 class_type& bit_array<Fld, Buf>::operator &=(class_type const& rhs)
 944 {
 945         EXTL_ASSERT(size() == rhs.size());
 946
 947         size_type n = buffer().size();
 948         for (index_type i = 0; i < n; ++i)
 949         {
 950                 buffer()[i] &= rhs.buffer()[i];
 951         }
 952
 953         return *this;
 954 }
 955 // operator &
 956 template<       typename_param_k Fld
 957                 ,       typename_param_k Buf
 958                 >
 959 inline typename_type_ret_k bit_array<Fld, Buf>::
 960 class_type const bit_array<Fld, Buf>::operator &(class_type const& rhs) const
 961 {
 962         return (class_type(rhs) &= rhs);
 963 }
 964 // operator |=
 965 template<       typename_param_k Fld
 966                 ,       typename_param_k Buf
 967                 >
 968 inline typename_type_ret_k bit_array<Fld, Buf>::
 969 class_type& bit_array<Fld, Buf>::operator |=(class_type const& rhs)
 970 {
 971         EXTL_ASSERT(size() == rhs.size());
 972
 973         size_type n = buffer().size();
 974         for (index_type i = 0; i < n; ++i)
 975         {
 976                 buffer()[i] |= rhs.buffer()[i];
 977         }
 978
 979         return *this;
 980 }
 981 // operator |
 982 template<       typename_param_k Fld
 983                 ,       typename_param_k Buf
 984                 >
 985 inline typename_type_ret_k bit_array<Fld, Buf>::
 986 class_type const bit_array<Fld, Buf>::operator |(class_type const& rhs) const
 987 {
 988         return (class_type(rhs) |= rhs);
 989 }
 990 // operator ^=
 991 template<       typename_param_k Fld
 992                 ,       typename_param_k Buf
 993                 >
 994 inline typename_type_ret_k bit_array<Fld, Buf>::
 995 class_type& bit_array<Fld, Buf>::operator ^=(class_type const& rhs)
 996 {
 997         EXTL_ASSERT(size() == rhs.size());
 998
 999         size_type n = buffer().size();
1000         for (index_type i = 0; i < n; ++i)
1001         {
1002                 buffer()[i] ^= rhs.buffer()[i];
1003         }
1004
1005         return *this;
1006 }
1007 // operator ^
1008 template<       typename_param_k Fld
1009                 ,       typename_param_k Buf
1010                 >
1011 inline typename_type_ret_k bit_array<Fld, Buf>::
1012 class_type const bit_array<Fld, Buf>::operator ^(class_type const& rhs) const
1013 {
1014         return (class_type(rhs) ^= rhs);
1015 }
1016
1017 /* /////////////////////////////////////////////////////////////////////////
1018  * swapping
1019  */
1020 template<       typename_param_k Fld
1021                 ,       typename_param_k Buf
1022                 >
1023 EXTL_INLINE void swap(bit_array<Fld, Buf>& lhs, bit_array<Fld, Buf>& rhs)
1024 {
1025         lhs.swap(rhs);
1026 }
1027
1028 /* ///////////////////////////////////////////////////////////////////////
1029  * ::extl namespace
1030  */
1031 EXTL_END_NAMESPACE
1032
1033 /* ///////////////////////////////////////////////////////////////////////
1034  * std::swap
1035  */
1036 #if !defined(EXTL_NO_STL) && \
1037                 !defined(EXTL_NO_NAMESPACE)
1038 /* ::std namespace */
1039 EXTL_STD_BEGIN_NAMESPACE
1040
1041 template<       typename_param_k Fld
1042                 ,       typename_param_k Buf
1043                 >
1044 EXTL_INLINE void swap(EXTL_NS(bit_array)<Fld, Buf>& lhs, EXTL_NS(bit_array)<Fld, Buf>& rhs)
1045 {
1046     lhs.swap(rhs);
1047 }
1048 /* ::std namespace */
1049 EXTL_STD_END_NAMESPACE
1050 #endif
1051
1052 /* //////////////////////////////////////////////////////////////////// */
1053 #endif  /* EXTL_CONTAINER_BIT_ARRAY_H */
1054 /* //////////////////////////////////////////////////////////////////// */