Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  * Copyright Contributors to the OpenSDN project
       4             :  */
       5             : 
       6             : #include "base/bitset.h"
       7             : 
       8             : #include <cassert>
       9             : #include <sstream>
      10             : #include <string>
      11             : #include <string.h>
      12             : 
      13             : #include "base/util.h"
      14             : #include "base/string_util.h"
      15             : 
      16             : using namespace std;
      17             : 
      18             : //
      19             : // Provides the same functionality as ffsl.  Needed as ffsl is not supported
      20             : // on all platforms. Note that the positions are numbered 1 through 64, with
      21             : // a return value of 0 indicating that there are no set bits.
      22             : //
      23     6555043 : static int find_first_set64(uint64_t value) {
      24             :     int bit;
      25             : 
      26     6555043 :     int lower = static_cast<int>(value);
      27     6555043 :     if ((bit = ffs(lower)) > 0)
      28     4447205 :         return bit;
      29             : 
      30     2107838 :     int upper = value >> 32;
      31     2107838 :     if ((bit = ffs(upper)) > 0)
      32       41145 :         return 32 + bit;
      33             : 
      34     2066693 :     return 0;
      35             : }
      36             : 
      37      645734 : static int find_first_clear64(uint64_t value) {
      38      645734 :     return find_first_set64(~value);
      39             : }
      40             : 
      41             : //
      42             : // Provides the same functionality as fls.  Needed as fls is not supported
      43             : // on all platforms. Note that the positions are numbered 1 through 32, with
      44             : // a return value of 0 indicating that there are no set bits.
      45             : //
      46        4016 : static int find_last_set32(uint32_t value) {
      47        4016 :     if (value == 0)
      48        1820 :         return 0;
      49             : 
      50        2196 :     int bit = 32;
      51        2196 :     if ((value & 0xFFFF0000U) == 0) {
      52        1833 :         value <<= 16;
      53        1833 :         bit -= 16;
      54             :     }
      55        2196 :     if ((value & 0xFF000000U) == 0) {
      56        1830 :         value <<= 8;
      57        1830 :         bit -= 8;
      58             :     }
      59        2196 :     if ((value & 0xF0000000U) == 0) {
      60        1846 :         value <<= 4;
      61        1846 :         bit -= 4;
      62             :     }
      63        2196 :     if ((value & 0xC0000000U) == 0) {
      64        1535 :         value <<= 2;
      65        1535 :         bit -= 2;
      66             :     }
      67        2196 :     if ((value & 0x80000000U) == 0) {
      68        1365 :         value <<= 1;
      69        1365 :         bit -= 1;
      70             :     }
      71             : 
      72        2196 :     return bit;
      73             : }
      74             : 
      75             : //
      76             : // Provides the same functionality as flsl.  Needed as flsl is not supported
      77             : // on all platforms. Note that the positions are numbered 1 through 64, with
      78             : // a return value of 0 indicating that there are no set bits.
      79             : //
      80        2196 : static int find_last_set64(uint64_t value) {
      81             :     int bit;
      82             : 
      83        2196 :     int upper = value >> 32;
      84        2196 :     if ((bit = find_last_set32(upper)) > 0)
      85         376 :         return 32 + bit;
      86             : 
      87        1820 :     int lower = static_cast<int>(value);
      88        1820 :     if ((bit = find_last_set32(lower)) > 0)
      89        1820 :         return bit;
      90             : 
      91           0 :     return 0;
      92             : }
      93             : 
      94             : //
      95             : // Return the number of set bits. K&R method.
      96             : //
      97       19647 : static int num_bits_set(uint64_t value) {
      98       19647 :     int count = 0;
      99     1070611 :     while (value != 0) {
     100     1050964 :         value &= value - 1;
     101     1050964 :         count++;
     102             :     }
     103       19647 :     return count;
     104             : }
     105             : 
     106             : // Position pos is w.r.t the entire bitset, starts at 0.
     107             : // Index    idx is the block number i.e. the index in the vector, starts at 0.
     108             : // Offset   offset is w.r.t a given 64 bit block, starts at 0.
     109    12749283 : static inline size_t block_index(size_t pos) {
     110    12749283 :     return pos / 64;
     111             : }
     112             : 
     113    16845989 : static inline size_t block_offset(size_t pos) {
     114    16845989 :     return pos % 64;
     115             : }
     116             : 
     117     4490403 : static inline size_t bit_position(size_t idx, size_t offset) {
     118     4490403 :     return (idx * 64 + offset);
     119             : }
     120             : 
     121             : const size_t BitSet::npos;
     122             : 
     123             : //
     124             : // Set bit at given position, growing the vector if needed.
     125             : //
     126     6009251 : BitSet &BitSet::set(size_t pos) {
     127     6009251 :     size_t idx = block_index(pos);
     128     6009234 :     if (idx >= blocks_.size())
     129     1441733 :         blocks_.resize(idx + 1);
     130     6009255 :     blocks_[idx] |= 1LL << block_offset(pos);
     131     6009683 :     return *this;
     132             : }
     133             : 
     134             : //
     135             : // Reset bit at given position, shrinking the vector if possible.
     136             : //
     137     1982503 : BitSet &BitSet::reset(size_t pos) {
     138     1982503 :     size_t idx = block_index(pos);
     139     1982497 :     if (idx < blocks_.size()) {
     140     1982414 :         blocks_[idx] &= ~(1LL << block_offset(pos));
     141     1982400 :         compact();
     142             :     }
     143     1982375 :     return *this;
     144             : }
     145             : 
     146             : // Test bit at given position.
     147      553505 : bool BitSet::test(size_t pos) const {
     148      553505 :     size_t idx = block_index(pos);
     149      553502 :     if (idx < blocks_.size()) {
     150      457548 :         return ((blocks_[idx] & (1LL << block_offset(pos))) != 0);
     151             :     } else {
     152       95954 :         return false;
     153             :     }
     154             : }
     155             : 
     156             : //
     157             : // Shortcut to reset all bits in the bitset.
     158             : //
     159       20580 : void BitSet::clear() {
     160       20580 :     blocks_.resize(0);
     161       20580 : }
     162             : 
     163             : //
     164             : // Return true if there are no bits in the bitset.
     165             : //
     166     6278481 : bool BitSet::empty() const {
     167     6278481 :     return (blocks_.size() == 0);
     168             : }
     169             : 
     170             : //
     171             : // Return true if no bits are set.
     172             : //
     173      367821 : bool BitSet::none() const {
     174      367821 :     return (blocks_.size() == 0);
     175             : }
     176             : 
     177             : //
     178             : // Return true at least one bit is set.
     179             : //
     180         642 : bool BitSet::any() const {
     181         642 :     return (blocks_.size() != 0);
     182             : }
     183             : 
     184             : //
     185             : // Return the raw number of bits in the bitset. Simply depends on the number
     186             : // of blocks in the vector.
     187             : //
     188       71033 : size_t BitSet::size() const {
     189       71033 :     return blocks_.size() * 64;
     190             : }
     191             : 
     192             : //
     193             : // Return total number of set bits.
     194             : //
     195        4320 : size_t BitSet::count() const {
     196        4320 :     size_t count = 0;
     197       23967 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     198       19647 :         count += num_bits_set(blocks_[idx]);
     199             :     }
     200        4320 :     return count;
     201             : }
     202             : 
     203             : //
     204             : // Shrink the underlying vector as much as possible.  All trailing blocks
     205             : // that are 0 can be removed.
     206             : //
     207             : // Note that the for loop does not handle idx 0 since the loop  variable
     208             : // is unsigned.
     209             : //
     210     5273106 : void BitSet::compact() {
     211     5273106 :     if (blocks_.size() == 0)
     212      628861 :         return;
     213             : 
     214     4659118 :     for (size_t idx = blocks_.size() - 1; idx > 0; idx--) {
     215      109990 :         if (blocks_[idx] != 0) {
     216       94881 :             blocks_.resize(idx + 1);
     217       94881 :             return;
     218             :         }
     219             :     }
     220             : 
     221     4549416 :     if (blocks_[0] != 0) {
     222     1677509 :         blocks_.resize(1);
     223     1677513 :         return;
     224             :     }
     225             : 
     226     2871806 :     blocks_.clear();
     227             : }
     228             : 
     229             : //
     230             : // Sanity check a bitset.  The last block must never be 0.  Always called
     231             : // after any compaction is done or in cases where no compaction is needed.
     232             : //
     233    12165800 : void BitSet::check_invariants() {
     234    12165800 :     size_t mysize = blocks_.size();
     235    12164814 :     if (mysize != 0)
     236     8124209 :         assert(blocks_[mysize -1] != 0);
     237    12164524 : }
     238             : 
     239             : //
     240             : // Return the position of the first set bit.  Needs to compensate for the
     241             : // return value convention used by find_first_set64.
     242             : //
     243     2921794 : size_t BitSet::find_first() const {
     244     2921986 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     245     1706342 :         int bit = find_first_set64(blocks_[idx]);
     246     1707208 :         if (bit > 0)
     247     1707016 :             return bit_position(idx, bit - 1);
     248             :     }
     249     1215750 :     return BitSet::npos;
     250             : }
     251             : 
     252             : //
     253             : // Return the position of the next set bit.  Needs to compensate for the
     254             : // return value convention used by find_first_set64.
     255             : //
     256     4194716 : size_t BitSet::find_next(size_t pos) const {
     257     4194716 :     size_t idx = block_index(pos);
     258             : 
     259             :     // If the block index is beyond the vector, we're done.
     260     4194618 :     if (idx >= blocks_.size())
     261        1087 :         return BitSet::npos;
     262             : 
     263             :     // If the offset is not 63, clear out the bits from 0 through offset
     264             :     // and look for the first set bit.
     265     4193371 :     if (block_offset(pos) < 63) {
     266     4192820 :         uint64_t temp = blocks_[idx] & ~((1LL << (block_offset(pos) + 1)) - 1);
     267     4192448 :         int bit = find_first_set64(temp);
     268     4193800 :         if (bit > 0)
     269     2483640 :             return bit_position(idx, bit - 1);
     270             :     }
     271             : 
     272             :     // Go through all blocks after the start block for the pos and see if
     273             :     // there's a set bit.
     274     1717292 :     for (idx++; idx < blocks_.size(); idx++) {
     275       10450 :         int bit = find_first_set64(blocks_[idx]);
     276       10456 :         if (bit > 0)
     277        3736 :             return bit_position(idx, bit - 1);
     278             :     }
     279     1706831 :     return BitSet::npos;
     280             : }
     281             : 
     282             : //
     283             : // Return the position of the last set bit.  Needs to compensate for the
     284             : // return value convention used by find_last_set64.
     285             : //
     286             : // Note that we only need to look at the last block since that must have
     287             : // at least one bit set.
     288             : //
     289        3418 : size_t BitSet::find_last() const {
     290        3418 :     if (blocks_.size() == 0)
     291        1222 :         return BitSet::npos;
     292             : 
     293        2196 :     size_t idx = blocks_.size() - 1;
     294        2196 :     int bit = find_last_set64(blocks_[idx]);
     295        2196 :     if (bit > 0)
     296        2196 :         return bit_position(idx, bit - 1);
     297             : 
     298           0 :     return BitSet::npos;
     299             : }
     300             : 
     301             : //
     302             : // Return the position of the first clear bit.  It could be beyond the last
     303             : // block in the vector. This is fine as we automatically grow the vector if
     304             : // needed from set().
     305             : //
     306             : // Need to compensate for return value convention used by find_first_clear64.
     307             : //
     308      358255 : size_t BitSet::find_first_clear() const {
     309      699767 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     310      628966 :         int bit = find_first_clear64(blocks_[idx]);
     311      628966 :         if (bit > 0) {
     312      287454 :             return bit_position(idx, bit - 1);
     313             :         }
     314             :     }
     315       70801 :     return size();
     316             : }
     317             : 
     318             : //
     319             : // Return the position of the next clear bit.  It could be beyond the last
     320             : // block in the vector. This is fine as we automatically grow the vector if
     321             : // needed from set().
     322             : //
     323             : // Need to compensate for return value convention used by find_first_clear64.
     324             : //
     325       10423 : size_t BitSet::find_next_clear(size_t pos) const {
     326       10423 :     size_t idx = block_index(pos);
     327             : 
     328             :     // If the block index is beyond the vector, we're done.
     329       10423 :     if (idx >= blocks_.size())
     330        3320 :         return pos + 1;
     331             : 
     332             :     // If the offset is not 63, set all the bits from 0 through offset and
     333             :     // look for the first clear bit.
     334        7103 :     if (block_offset(pos) < 63) {
     335        7006 :         uint64_t temp = blocks_[idx] | ((1LL << (block_offset(pos) + 1)) - 1);
     336        7006 :         int bit = find_first_clear64(temp);
     337        7006 :         if (bit > 0)
     338        3919 :             return bit_position(idx, bit - 1);
     339             :     }
     340             : 
     341             :     // Go through all blocks after the start block for the pos and see if
     342             :     // there's a clear bit.
     343        9968 :     for (idx++; idx < blocks_.size(); idx++) {
     344        9762 :         int bit = find_first_clear64(blocks_[idx]);
     345        9762 :         if (bit > 0) {
     346        2978 :             return bit_position(idx, bit - 1);
     347             :         }
     348             :     }
     349         206 :     return size();
     350             : }
     351             : 
     352             : //
     353             : // Return (*this & rhs != 0).
     354             : //
     355         642 : bool BitSet::intersects(const BitSet &rhs) const {
     356         642 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     357        1188 :     for (size_t idx = 0; idx < minsize; idx++) {
     358        1168 :         if (blocks_[idx] & rhs.blocks_[idx])
     359         622 :             return true;
     360             :     }
     361          20 :     return false;
     362             : }
     363             : 
     364             : //
     365             : // Return (*this == rhs).
     366             : //
     367             : // Note that it's fine to first compare the number of blocks in the vectors
     368             : // since we always shrink the vectors whenever possible.
     369             : //
     370     1351578 : bool BitSet::operator==(const BitSet &rhs) const {
     371     1351578 :     if (blocks_.size() != rhs.blocks_.size())
     372     1207968 :         return false;
     373      301068 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     374      161552 :         if (blocks_[idx] != rhs.blocks_[idx])
     375        4121 :             return false;
     376             :     }
     377      139478 :     return true;
     378             : }
     379             : 
     380             : //
     381             : // Return (*this != rhs).
     382             : //
     383      722088 : bool BitSet::operator!=(const BitSet &rhs) const {
     384      722088 :     return !operator==(rhs);
     385             : }
     386             : 
     387             : //
     388             : // Return (*this & rhs).
     389             : //
     390        4571 : BitSet BitSet::operator&(const BitSet &rhs) const {
     391        4571 :     BitSet temp;
     392        4571 :     temp.BuildIntersection(*this, rhs);
     393        4571 :     temp.check_invariants();
     394        4571 :     return temp;
     395           0 : }
     396             : 
     397             : //
     398             : // Return (*this | rhs).
     399             : //
     400         642 : BitSet BitSet::operator|(const BitSet &rhs) const {
     401         642 :     BitSet temp;
     402         642 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     403         642 :     size_t maxsize = std::max(blocks_.size(), rhs.blocks_.size());
     404         642 :     temp.blocks_.resize(maxsize);
     405             : 
     406             :     // Process common blocks.
     407        3578 :     for (size_t idx = 0; idx < minsize; idx++) {
     408        2936 :         temp.blocks_[idx] = blocks_[idx] | rhs.blocks_[idx];
     409             :     }
     410             : 
     411             :     // Process blocks that exist in LHS only. It's a noop if RHS is bigger.
     412        1262 :     for (size_t idx = minsize; idx < blocks_.size(); idx++) {
     413         620 :         temp.blocks_[idx] = blocks_[idx];
     414             :     }
     415             : 
     416             :     // Process blocks that exist in RHS only. It's a noop if LHS is bigger.
     417        1262 :     for (size_t idx = minsize; idx < rhs.blocks_.size(); idx++) {
     418         620 :         temp.blocks_[idx] = rhs.blocks_[idx];
     419             :     }
     420             : 
     421         642 :     temp.check_invariants();
     422         642 :     return temp;
     423           0 : }
     424             : 
     425             : //
     426             : // Implement (*this &= rhs).
     427             : //
     428             : // Note that we can't simply resize the vector to minsize since we may be
     429             : // able to shrink it even more depending on the values in the blocks.
     430             : //
     431         640 : BitSet &BitSet::operator&=(const BitSet &rhs) {
     432         640 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     433        3560 :     for (size_t idx = 0; idx < minsize; idx++) {
     434        2920 :         blocks_[idx] &= rhs.blocks_[idx];
     435             :     }
     436        1252 :     for (size_t idx = minsize; idx < blocks_.size(); idx++) {
     437         612 :         blocks_[idx] = 0;
     438             :     }
     439         640 :     compact();
     440         640 :     check_invariants();
     441         640 :     return *this;
     442             : }
     443             : 
     444             : //
     445             : // Implement (*this |= rhs).
     446             : //
     447             : // Note that we grow the vector only once instead of doing it multiple
     448             : // times.
     449             : //
     450     5727898 : BitSet &BitSet::operator|=(const BitSet &rhs) {
     451     5727898 :     if (blocks_.size() < rhs.blocks_.size())
     452     2400008 :         blocks_.resize(rhs.blocks_.size());
     453     9278314 :     for (size_t idx = 0; idx < rhs.blocks_.size(); idx++) {
     454     3550800 :         blocks_[idx] |= rhs.blocks_[idx];
     455             :     }
     456     5725246 :     check_invariants();
     457     5726417 :     return *this;
     458             : }
     459             : 
     460             : //
     461             : // Identical to operator|=.
     462             : //
     463     2261773 : void BitSet::Set(const BitSet &rhs) {
     464     2261773 :     this->operator|=(rhs);
     465     2261008 :     check_invariants();
     466     2260835 : }
     467             : 
     468             : //
     469             : // Implement (*this &= ~rhs).
     470             : //
     471     2658102 : void BitSet::Reset(const BitSet &rhs) {
     472     2658102 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     473     4551819 :     for (size_t idx = 0; idx < minsize; idx++) {
     474     1894056 :         blocks_[idx] &= ~rhs.blocks_[idx];
     475             :     }
     476     2657763 :     compact();
     477     2657260 :     check_invariants();
     478     2657053 : }
     479             : 
     480             : //
     481             : // Implement (*this = lhs & ~rhs).
     482             : //
     483             : // Note that we won't enter the second for loop at all if lhs is not bigger
     484             : // than rhs.  Need to compact only for this case, but it is cheap enough to
     485             : // try (and do nothing) when lhs is bigger than rhs.
     486             : //
     487      632680 : void BitSet::BuildComplement(const BitSet &lhs, const BitSet &rhs) {
     488      632680 :     blocks_.clear();
     489      632683 :     blocks_.resize(lhs.blocks_.size());
     490      632666 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     491     1241767 :     for (size_t idx = 0; idx < minsize; idx++) {
     492      609116 :         blocks_[idx] = lhs.blocks_[idx] & ~rhs.blocks_[idx];
     493             :     }
     494      640958 :     for (size_t idx = minsize; idx < lhs.blocks_.size(); idx++) {
     495        8307 :         blocks_[idx] = lhs.blocks_[idx];
     496             :     }
     497      632646 :     compact();
     498      632633 :     check_invariants();
     499      632625 : }
     500             : 
     501             : //
     502             : // Implement (*this = lhs & rhs).
     503             : //
     504             : // We avoid the need to compact or to resize multiple times by building
     505             : // the blocks in reverse order.
     506             : //
     507             : // Note that the for loop does not handle idx 0 since the loop  variable
     508             : // is unsigned.
     509             : //
     510     1086999 : void BitSet::BuildIntersection(const BitSet &lhs, const BitSet &rhs) {
     511     1086999 :     blocks_.clear();
     512     1086982 :     size_t minsize = std::min(lhs.blocks_.size(), rhs.blocks_.size());
     513             : 
     514     1086942 :     if (minsize == 0)
     515      195324 :         return;
     516             : 
     517      893978 :     for (size_t idx = minsize - 1; idx > 0; idx--) {
     518        2360 :         if (lhs.blocks_[idx] & rhs.blocks_[idx]) {
     519        1560 :             if (blocks_.size() == 0)
     520         482 :                 blocks_.resize(idx + 1);
     521        1560 :             blocks_[idx] = lhs.blocks_[idx] & rhs.blocks_[idx];
     522             :         }
     523             :     }
     524             : 
     525      891618 :     if (lhs.blocks_[0] & rhs.blocks_[0]) {
     526      876082 :         if (blocks_.size() == 0)
     527      875623 :             blocks_.resize(1);
     528      876087 :         blocks_[0] = lhs.blocks_[0] & rhs.blocks_[0];
     529             :     }
     530             : 
     531      891596 :     check_invariants();
     532             : }
     533             : 
     534             : //
     535             : // Return true if *this contains rhs.  Implemented as (rhs & ~*this != 0).
     536             : //
     537      932465 : bool BitSet::Contains(const BitSet &rhs) const {
     538      932465 :     if (blocks_.size() < rhs.blocks_.size())
     539        1642 :         return false;
     540     1247874 :     for (size_t idx = 0; idx < rhs.blocks_.size(); idx++) {
     541      320985 :         if (rhs.blocks_[idx] & ~blocks_[idx])
     542        4042 :             return false;
     543             :     }
     544      926835 :     return true;
     545             : }
     546             : 
     547             : //
     548             : // Returns string representation of the bitset. A character in the string is
     549             : // '1' if the corresponding bit is set, and '0' if it is not.  The character
     550             : // position i in the string corresponds to bit position i in the bitset.
     551             : //
     552        2905 : string BitSet::ToString() const {
     553        2905 :     size_t last_pos = find_last();
     554        2905 :     if (last_pos == BitSet::npos)
     555        1221 :         return string();
     556             : 
     557        1684 :     string str(last_pos + 1, '0');
     558        5919 :     for (size_t pos = find_first(); pos != BitSet::npos; pos = find_next(pos)) {
     559        4235 :         str[pos] = '1';
     560             :     }
     561        1684 :     return str;
     562        1684 : }
     563             : 
     564             : //
     565             : // Initialize the bitset from the provided string representation. The string
     566             : // must use the same format as described in ToString above. We traverse the
     567             : // string in reverse order to ensure that we do not have to resize multiple
     568             : // times.
     569             : //
     570             : // Note that the for loop does not handle str_idx 0 since the loop variable
     571             : // is unsigned.
     572             : //
     573          65 : void BitSet::FromString(string str) {
     574          65 :     blocks_.clear();
     575             : 
     576          65 :     if (str.length() == 0)
     577           1 :         return;
     578             : 
     579       31773 :     for (size_t str_idx = str.length() - 1; str_idx > 0; str_idx--) {
     580       31709 :         if (str[str_idx] == '1')
     581        2395 :             set(str_idx);
     582             :     }
     583             : 
     584          64 :     if (str[0] == '1')
     585          64 :         set(0);
     586             : }
     587             : 
     588             : //
     589             : // Returns numbered string representation of the bitset. The numbers are the
     590             : // bit positions that are set in the bitset.  Consecutive bit positions are
     591             : // represented as x-y and a comma is used as a separator for non-consecutive
     592             : // positions.
     593             : //
     594          68 : string BitSet::ToNumberedString() const {
     595          68 :     if (empty())
     596           1 :         return "-";
     597             : 
     598          67 :     ostringstream oss;
     599          67 :     bool range = false;
     600          67 :     size_t last_pos = BitSet::npos;
     601         207 :     for (size_t pos = find_first(); pos != BitSet::npos;
     602         140 :          last_pos = pos, pos = find_next(pos)) {
     603         140 :         if (last_pos == BitSet::npos) {
     604          67 :             oss << integerToString(pos);
     605          73 :         } else if (pos == last_pos + 1) {
     606          42 :             range = true;
     607          31 :         } else if (range) {
     608          10 :             oss << "-" << integerToString(last_pos);
     609          10 :             oss << "," << integerToString(pos);
     610          10 :             range = false;
     611             :         } else {
     612          21 :             oss << "," << integerToString(pos);
     613             :         }
     614             :     }
     615             : 
     616          67 :     if (range)
     617          17 :        oss << "-" << integerToString(last_pos);
     618             : 
     619          67 :     return oss.str();
     620          67 : }