extl/container/bit_field.h

   1 /* ///////////////////////////////////////////////////////////////////////
   2  * File:                bit_field.h
   3  *
   4  * Created:             08.10.02
   5  * Updated:             08.10.02
   6  *
   7  * Brief: bit_field class
   8  *
   9  * [<Home>]
  10  * Copyright (c) 2008-2020, Waruqi All rights reserved.
  11  * //////////////////////////////////////////////////////////////////// */
  12
  13 #ifndef EXTL_CONTAINER_BIT_FIELD_H
  14 #define EXTL_CONTAINER_BIT_FIELD_H
  15
  16 /*!\file bit_field.h
  17  * \brief bit_field class
  18  */
  19
  20 /* ///////////////////////////////////////////////////////////////////////
  21  * Includes
  22  */
  23 #include "prefix.h"
  24 #include "detail/bit_field_iterator.h"
  25 #include "../algorithm/algorithm.h"
  26 #include "../string/string.h"
  27
  28 /* ///////////////////////////////////////////////////////////////////////
  29  * ::extl namespace
  30  */
  31 EXTL_BEGIN_NAMESPACE
  32
  33 /*!brief bit_field
  34  *
  35  * \param F The field type
  36  *
  37  * \ingroup extl_group_container
  38  */
  39 template<
  40 #ifdef EXTL_TEMPLATE_CLASS_DEFAULT_ARGUMENT_SUPPORT
  41                         typename_param_k F = e_size_t
  42 #else
  43                         typename_param_k F
  44 #endif
  45                 >
  46 class bit_field
  47 {
  48         /// \name Types
  49         /// @{
  50         public:
  51                 typedef bit_field                                                                                               class_type;
  52                 typedef e_bool_t                                                                                                bool_type;
  53                 typedef e_size_t                                                                                                size_type;
  54                 typedef e_char_t                                                                                                achar_type;
  55                 typedef e_wchar_t                                                                                               wchar_type;
  56                 typedef size_type                                                                                               index_type;
  57                 typedef bool_type                                                                                               value_type;
  58                 typedef value_type*                                                                                             pointer;
  59                 typedef value_type const*                                                                               const_pointer;
  60                 typedef value_type&                                                                                             reference;
  61                 typedef value_type const&                                                                               const_reference;
  62                 typedef F                                                                                                               field_type;
  63                 typedef EXTL_NS_DETAIL(const_bit_field_iterator)<field_type>    const_iterator;
  64         /// @}
  65
  66
  67         /// \name Members
  68         private:
  69                 size_type                                                                                                               m_size;
  70                 field_type                                                                                                              m_field;
  71         /// @}
  72
  73         private:
  74                 enum { en_max_bit_count = 8 * sizeof(field_type) };
  75
  76         /// \name Constructors
  77         /// @{
  78         public:
  79                 /// Default Constructor
  80                 bit_field()
  81                 {
  82                         clear();
  83                 }
  84                 /// Copy Constructor
  85                 bit_field(class_type const& rhs)
  86                 {
  87                         assign(rhs);
  88                 }
  89                 /// Constructs with n-bits values from the given field
  90                 bit_field(class_type const& rhs, size_type n)
  91                 {
  92                         assign(rhs, n);
  93                 }
  94                 /// Constructs with n-bits default values
  95                 explicit_k bit_field(size_type n)
  96                 {
  97                         assign(value_type(), n);
  98                 }
  99                 /// Constructs with n-bits given values
 100                 bit_field(const_reference value, size_type n)
 101                 {
 102                         assign(value, n);
 103                 }
 104                 /// Constructs with n-bits values from bool array
 105                 bit_field(const_pointer p, size_type n)
 106                 {
 107                         assign(p, n);
 108                 }
 109                 /// Constructs from ascii string with null-terminator
 110                 explicit_k bit_field(achar_type const* s)
 111                 {
 112                         assign(s);
 113                 }
 114                 /// Constructs from unicode string with null-terminator
 115                 explicit_k bit_field(wchar_type const* s)
 116                 {
 117                         assign(s);
 118                 }
 119                 /// Constructs with n-bits values from ascii string
 120                 bit_field(achar_type const* s, size_type n)
 121                 {
 122                         assign(s, n);
 123                 }
 124                 /// Constructs with n-bits values from unicode string
 125                 bit_field(wchar_type const* s, size_type n)
 126                 {
 127                         assign(s, n);
 128                 }
 129         /// @}
 130
 131         /// \name Iterators
 132         /// @{
 133         public:
 134                 /// Returns the const begin iterator
 135                 const_iterator          begin() const           { return const_iterator(&m_field, 0);           }
 136                 /// Returns the const end iterator
 137                 const_iterator          end() const                     { return const_iterator(&m_field, size());      }
 138         /// @}
 139
 140         /// \name Accessors
 141         /// @{
 142         public:
 143                 /// Returns const value at the given index
 144                 value_type const        operator[](index_type index) const      { return get(index);    }
 145                 /// Returns const value at the given index and throws index_error() if index >= size()
 146                 value_type const        at(index_type index) const;
 147                 /// Returns const value at the given index
 148                 value_type const        get(index_type index) const;
 149                 /// Returns const value at the front of field
 150                 value_type const        front() const   { return at(0);                         }
 151                 /// Returns const value at the back of field
 152                 value_type const        back()  const   { return at(size() - 1);        }
 153         /// @}
 154
 155         /// \name Attributes
 156         /// @{
 157         public:
 158                 /// Returns the field value
 159                 field_type                      data() const                    { return field();                       }
 160                 /// Returns the field value
 161                 field_type                      field() const                   { return m_field;                       }
 162                 /// Returns the numeric of this field
 163                 field_type                      numeric() const;
 164                 /// Returns the bit count
 165                 size_type                       size() const                    { return m_size;                        }
 166                 /// Returns the reserved bit count in the field
 167                 size_type                       capacity() const                { return max_size();            }
 168                 /// Return \c true if size() == 0
 169                 bool_type                       is_empty() const                { return size() == 0;           }
 170                 /// Return \c true if size() == 0
 171                 bool_type                       empty() const                   { return is_empty();            }
 172                 /// Return the maximum bit count of the field
 173                 static size_type        max_size()                              { return en_max_bit_count;      }
 174         /// @}
 175
 176         /// \name Mutators
 177         /// @{
 178         public:
 179                 /// Clears the field e.g. 001101 => null
 180                 void                            clear()                                 { m_field = e_false_v; m_size = 0;      }
 181                 /// Cleans the field e.g. 001101 => 000000
 182                 void                            clean()                                 { m_field = e_false_v;                          }
 183                 /// Swaps field
 184                 void                            swap(class_type& rhs)   { std_swap(m_field, rhs.m_field); std_swap(m_size, rhs.m_size); }
 185                 /// Sets the value at the given position
 186                 void                            set(index_type index, const_reference value);
 187                 /// Resizes the bit count of the field
 188                 void                            resize(size_type n, const_reference new_value = value_type());
 189                 /// Pushes back the given value
 190                 void                            push_back(const_reference value)        { resize(size() + 1, value);    }
 191                 /// Pops back from this field
 192                 void                            pop_back()                              { --m_size;                                                                     }
 193                 /// Sets the numeric of this field
 194                 void                            numeric(field_type num)                                 { m_field = num;                        }
 195         /// @}
 196
 197         /// \name Assignments
 198         /// @{
 199         public:
 200                 /// Assigns from the given value(fill all)
 201                 class_type&                     assign(const_reference value)                           { return assign(value, 1u);     }
 202                 /// Assigns with n-bits given values
 203                 class_type&                     assign(const_reference value, size_type n);
 204                 /// Assigns with n-bits values from bool array
 205                 class_type&                     assign(const_pointer p, size_type n);
 206                 /// Assigns with n-bits values from ascii string
 207                 class_type&                     assign(achar_type const* s, size_type n);
 208                 /// Assigns with n-bits values from unicode string
 209                 class_type&                     assign(wchar_type const* s, size_type n);
 210                 /// Assigns from ascii string with null-terminator
 211                 class_type&                     assign(achar_type const* s)                                     { return assign(s, (NULL != s)? std_strlen(s) : 0);     }
 212                 /// Assigns from unicode string with null-terminator
 213                 class_type&                     assign(wchar_type const* s)                                     { return assign(s, (NULL != s)? std_strlen(s) : 0);     }
 214                 /// Assigns with n-bits values from the given field
 215                 class_type&                     assign(class_type const& rhs, size_type n);
 216                 /// Assigns from the given field
 217                 class_type&                     assign(class_type const& rhs)                           { return assign(rhs, rhs.size());       }
 218                 /// Assigns from the given field
 219                 class_type&                     operator =(class_type const& rhs)                       { return assign(rhs);                           }
 220                 /// Assigns from the given value(fill all)
 221                 class_type&                     operator =(const_reference value)                       { return assign(value);                         }
 222                 /// Assigns from ascii string with null-terminator
 223                 class_type&                     operator =(achar_type const* s)                         { return assign(s);                                     }
 224                 /// Assigns from unicode string with null-terminator
 225                 class_type&                     operator =(wchar_type const* s)                         { return assign(s);                                     }
 226         /// @}
 227
 228         /// \name Static Methods
 229         /// @{
 230         public:
 231                 /// Makes numeric from bool array
 232                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 233                 static field_type       make_numeric(const_pointer p, size_type n, bool_type is_left_low = e_false_v);
 234                 /// Makes numeric from ascii string with n-characters
 235                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 236                 static field_type       make_numeric(achar_type const* s, size_type n, bool_type is_left_low = e_false_v);
 237                 /// Makes numeric from unicode string with n-characters
 238                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 239                 static field_type       make_numeric(wchar_type const* s, size_type n, bool_type is_left_low = e_false_v);
 240                 /// Makes numeric from ascii string with null-terminator
 241                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 242                 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);  }
 243                 /// Makes numeric from unicode string with null-terminator
 244                 /// \param is_left_low true: low bit=> high bit & false: high bit <= low bit
 245                 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);  }
 246         /// @}
 247
 248         /// \name Reverses
 249         /// @{
 250         public:
 251                 /// Reverses this bit field with the given range [pos, pos + n)
 252                 class_type&                     reverse(size_type pos, size_type n);
 253                 /// Reverses the whole bit field
 254                 class_type&                     reverse()               { return reverse(0, size());    }
 255         /// @}
 256
 257         /// \name Operators
 258         /// @{
 259         public:
 260                 /// Return the copy of ~(*this)
 261                 class_type                      operator ~();
 262                 /// Return \c true if *this == rhs
 263                 bool_type                       operator ==(class_type const& rhs) const;
 264                 /// Return \c true if *this != rhs
 265                 bool_type                       operator !=(class_type const& rhs) const        { return !((*this) == rhs);     }
 266                 /// *this &= rhs
 267                 class_type&                     operator &=(class_type const& rhs);
 268                 /// *this & rhs
 269                 class_type const        operator &(class_type const& rhs) const;
 270                 /// *this |= rhs
 271                 class_type&                     operator |=(class_type const& rhs);
 272                 /// *this | rhs
 273                 class_type const        operator |(class_type const& rhs) const;
 274                 /// *this ^= rhs
 275                 class_type&                     operator ^=(class_type const& rhs);
 276                 /// *this ^ rhs
 277                 class_type const        operator ^(class_type const& rhs) const;
 278         /// @}
 279 };
 280
 281 /* ///////////////////////////////////////////////////////////////////////
 282  * Implementation
 283  */
 284 // at(checked)
 285 template<typename_param_k F>
 286 inline typename_type_ret_k bit_field<F>::
 287 value_type const bit_field<F>::at(index_type index) const
 288 {
 289         EXTL_ASSERT_THROW(index < size(), index_error("out of range"));
 290         return get(index);
 291 }
 292 // get(unchecked)
 293 template<typename_param_k F>
 294 inline typename_type_ret_k bit_field<F>::
 295 value_type const bit_field<F>::get(index_type index) const
 296 {
 297         EXTL_ASSERT(index < size());
 298
 299         // low bit => high bit
 300         return (field_type(0x1) == ((m_field >> index) & field_type(0x1)));
 301 }
 302 // set
 303 template<typename_param_k F>
 304 inline void bit_field<F>::set(index_type index, const_reference value)
 305 {
 306         EXTL_ASSERT(index < size());
 307
 308         // low bit => high bit
 309         m_field &= ~(field_type(0x1) << index);
 310         m_field |= (static_cast<field_type>(value) << index);
 311 }
 312
 313 // assign
 314 template<typename_param_k F>
 315 inline typename_type_ret_k bit_field<F>::
 316 class_type& bit_field<F>::assign(const_reference value, size_type n)
 317 {
 318         EXTL_ASSERT(n <= max_size());
 319
 320         m_size = n;
 321         for (index_type i = 0; i < n; ++i)
 322                 set(i, value);
 323
 324         return *this;
 325 }
 326 template<typename_param_k F>
 327 inline typename_type_ret_k bit_field<F>::
 328 class_type& bit_field<F>::assign(const_pointer p, size_type n)
 329 {
 330         EXTL_ASSERT(n <= max_size());
 331         EXTL_ASSERT(NULL != p);
 332
 333         m_size = n;
 334         for (index_type i = 0; i < n; ++i)
 335                 set(i, p[i]);
 336
 337         return *this;
 338 }
 339 template<typename_param_k F>
 340 inline typename_type_ret_k bit_field<F>::
 341 class_type& bit_field<F>::assign(achar_type const* s, size_type n)
 342 {
 343         EXTL_ASSERT(n <= max_size());
 344         EXTL_ASSERT(NULL != s);
 345
 346         m_size = n;
 347         for (index_type i = 0; i < n; ++i)
 348                 set(i, s[i] != '0');
 349
 350         return *this;
 351 }
 352 template<typename_param_k F>
 353 inline typename_type_ret_k bit_field<F>::
 354 class_type& bit_field<F>::assign(wchar_type const* s, size_type n)
 355 {
 356         EXTL_ASSERT(n <= max_size());
 357         EXTL_ASSERT(NULL != s);
 358
 359         m_size = n;
 360         for (index_type i = 0; i < n; ++i)
 361                 set(i, s[i] != L'0');
 362
 363         return *this;
 364 }
 365 template<typename_param_k F>
 366 inline typename_type_ret_k bit_field<F>::
 367 class_type& bit_field<F>::assign(class_type const& rhs, size_type n)
 368 {
 369         EXTL_ASSERT(n <= max_size());
 370         EXTL_ASSERT(n <= rhs.size());
 371
 372         if (this != &rhs)
 373         {
 374                 m_field = rhs.field();
 375                 m_size = n;
 376         }
 377         return *this;
 378 }
 379 // resize
 380 template<typename_param_k F>
 381 inline void bit_field<F>::resize(size_type n, const_reference new_value)
 382 {
 383         EXTL_ASSERT(n <= max_size());
 384
 385         if (n <= size())
 386         {
 387                 m_size = n;
 388         }
 389         else
 390         {
 391                 index_type i = m_size;
 392                 m_size = n;
 393                 for (; i < n; ++i)
 394                         set(i, new_value);
 395         }
 396 }
 397 // reverse
 398 template<typename_param_k F>
 399 inline typename_type_ret_k bit_field<F>::
 400 class_type& bit_field<F>::reverse(size_type pos, size_type n)
 401 {
 402         EXTL_ASSERT(pos >= 0 && (pos + n) <= size());
 403         EXTL_ASSERT(n > 0);
 404
 405         index_type begin = 0;
 406         index_type end = n - 1;
 407
 408         while (begin < end)
 409         {
 410                 value_type tmp = get(begin);
 411                 set(begin++, get(end));
 412                 set(end--, tmp);
 413         }
 414
 415         return *this;
 416 }
 417
 418 // numeric
 419 template<typename_param_k F>
 420 inline typename_type_ret_k bit_field<F>::
 421 field_type bit_field<F>::numeric() const
 422 {
 423         field_type num = 0;
 424         field_type p2 = 1;
 425
 426         size_type n = size();
 427         for (index_type i = 0; i < n; ++i)
 428         {
 429                 num += get(i) * p2;
 430                 p2 <<= 1;
 431         }
 432
 433         return num;
 434 }
 435 // make_numeric
 436 template<typename_param_k F>
 437 inline typename_type_ret_k bit_field<F>::
 438 field_type bit_field<F>::make_numeric(const_pointer p, size_type n, bool_type is_left_low)
 439 {
 440         EXTL_ASSERT(NULL != p);
 441
 442         field_type num = 0;
 443         field_type p2 = 1;
 444
 445         if (is_left_low)
 446         {
 447                 for (index_type i = 0; i < n; ++i)
 448                 {
 449                         num += p[i] * p2;
 450                         p2 <<= 1;
 451                 }
 452         }
 453         else
 454         {
 455                 for (index_type i = 0; i < n; ++i)
 456                 {
 457                         num += p[n - i - 1] * p2;
 458                         p2 <<= 1;
 459                 }
 460         }
 461         return num;
 462 }
 463
 464 template<typename_param_k F>
 465 inline typename_type_ret_k bit_field<F>::
 466 field_type bit_field<F>::make_numeric(achar_type const* s, size_type n, bool_type is_left_low)
 467 {
 468         EXTL_ASSERT(NULL != s);
 469
 470         field_type num = 0;
 471         field_type p2 = 1;
 472
 473         if (is_left_low)
 474         {
 475                 for (index_type i = 0; i < n; ++i)
 476                 {
 477                         num += (s[i] != '0') * p2;
 478                         p2 <<= 1;
 479                 }
 480         }
 481         else
 482         {
 483                 for (index_type i = 0; i < n; ++i)
 484                 {
 485                         num += (s[n - i - 1] != '0') * p2;
 486                         p2 <<= 1;
 487                 }
 488         }
 489         return num;
 490 }
 491
 492 template<typename_param_k F>
 493 inline typename_type_ret_k bit_field<F>::
 494 field_type bit_field<F>::make_numeric(wchar_type const* s, size_type n, bool_type is_left_low)
 495 {
 496         EXTL_ASSERT(NULL != s);
 497
 498         field_type num = 0;
 499         field_type p2 = 1;
 500
 501         if (is_left_low)
 502         {
 503                 for (index_type i = 0; i < n; ++i)
 504                 {
 505                         num += (s[i] != L'0') * p2;
 506                         p2 <<= 1;
 507                 }
 508         }
 509         else
 510         {
 511                 for (index_type i = 0; i < n; ++i)
 512                 {
 513                         num += (s[n - i - 1] != L'0') * p2;
 514                         p2 <<= 1;
 515                 }
 516         }
 517         return num;
 518 }
 519 // operator ~
 520 template<typename_param_k F>
 521 inline typename_type_ret_k bit_field<F>::
 522 class_type bit_field<F>::operator ~()
 523 {
 524         class_type tmp(*this);
 525         tmp.m_field = ~field();
 526         return tmp;
 527 }
 528 // operator ==
 529 template<typename_param_k F>
 530 inline typename_type_ret_k bit_field<F>::
 531 bool_type bit_field<F>::operator ==(class_type const& rhs) const
 532 {
 533         return (field() == rhs.field());
 534 }
 535 // operator &=
 536 template<typename_param_k F>
 537 inline typename_type_ret_k bit_field<F>::
 538 class_type& bit_field<F>::operator &=(class_type const& rhs)
 539 {
 540         m_field &= rhs.field();
 541         return *this;
 542 }
 543 // operator &
 544 template<typename_param_k F>
 545 inline typename_type_ret_k bit_field<F>::
 546 class_type const bit_field<F>::operator &(class_type const& rhs) const
 547 {
 548         return (class_type(rhs) &= rhs);
 549 }
 550 // operator |=
 551 template<typename_param_k F>
 552 inline typename_type_ret_k bit_field<F>::
 553 class_type& bit_field<F>::operator |=(class_type const& rhs)
 554 {
 555         m_field |= rhs.field();
 556         return *this;
 557 }
 558 // operator |
 559 template<typename_param_k F>
 560 inline typename_type_ret_k bit_field<F>::
 561 class_type const bit_field<F>::operator |(class_type const& rhs) const
 562 {
 563         return (class_type(rhs) |= rhs);
 564 }
 565 // operator ^=
 566 template<typename_param_k F>
 567 inline typename_type_ret_k bit_field<F>::
 568 class_type& bit_field<F>::operator ^=(class_type const& rhs)
 569 {
 570         m_field ^= rhs.field();
 571         return *this;
 572 }
 573 // operator ^
 574 template<typename_param_k F>
 575 inline typename_type_ret_k bit_field<F>::
 576 class_type const bit_field<F>::operator ^(class_type const& rhs) const
 577 {
 578         return (class_type(rhs) ^= rhs);
 579 }
 580 /* /////////////////////////////////////////////////////////////////////////
 581  * swapping
 582  */
 583 template<typename_param_k F>
 584 EXTL_INLINE void swap(bit_field<F>& lhs, bit_field<F>& rhs)
 585 {
 586         lhs.swap(rhs);
 587 }
 588
 589 /* ///////////////////////////////////////////////////////////////////////
 590  * ::extl namespace
 591  */
 592 EXTL_END_NAMESPACE
 593
 594 /* ///////////////////////////////////////////////////////////////////////
 595  * std::swap
 596  */
 597 #if !defined(EXTL_NO_STL) && \
 598                 !defined(EXTL_NO_NAMESPACE)
 599 /* ::std namespace */
 600 EXTL_STD_BEGIN_NAMESPACE
 601
 602 template<typename_param_k F>
 603 EXTL_INLINE void swap(EXTL_NS(bit_field)<F>& lhs, EXTL_NS(bit_field)<F>& rhs)
 604 {
 605     lhs.swap(rhs);
 606 }
 607 /* ::std namespace */
 608 EXTL_STD_END_NAMESPACE
 609 #endif
 610
 611 /* //////////////////////////////////////////////////////////////////// */
 612 #endif  /* EXTL_CONTAINER_BIT_FIELD_H */
 613 /* //////////////////////////////////////////////////////////////////// */