Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "base/bitset.h"
       6             : 
       7             : #include <cassert>
       8             : #include <sstream>
       9             : #include <string>
      10             : #include <string.h>
      11             : 
      12             : #include "base/util.h"
      13             : #include "base/string_util.h"
      14             : 
      15             : using namespace std;
      16             : 
      17             : //
      18             : // Provides the same functionality as ffsl.  Needed as ffsl is not supported
      19             : // on all platforms. Note that the positions are numbered 1 through 64, with
      20             : // a return value of 0 indicating that there are no set bits.
      21             : //
      22     6634377 : static int find_first_set64(uint64_t value) {
      23             :     int bit;
      24             : 
      25     6634377 :     int lower = static_cast<int>(value);
      26     6634377 :     if ((bit = ffs(lower)) > 0)
      27     4511565 :         return bit;
      28             : 
      29     2122812 :     int upper = value >> 32;
      30     2122812 :     if ((bit = ffs(upper)) > 0)
      31       41145 :         return 32 + bit;
      32             : 
      33     2081667 :     return 0;
      34             : }
      35             : 
      36      646084 : static int find_first_clear64(uint64_t value) {
      37      646084 :     return find_first_set64(~value);
      38             : }
      39             : 
      40             : //
      41             : // Provides the same functionality as fls.  Needed as fls is not supported
      42             : // on all platforms. Note that the positions are numbered 1 through 32, with
      43             : // a return value of 0 indicating that there are no set bits.
      44             : //
      45        4480 : static int find_last_set32(uint32_t value) {
      46        4480 :     if (value == 0)
      47        2052 :         return 0;
      48             : 
      49        2428 :     int bit = 32;
      50        2428 :     if ((value & 0xFFFF0000U) == 0) {
      51        2065 :         value <<= 16;
      52        2065 :         bit -= 16;
      53             :     }
      54        2428 :     if ((value & 0xFF000000U) == 0) {
      55        2062 :         value <<= 8;
      56        2062 :         bit -= 8;
      57             :     }
      58        2428 :     if ((value & 0xF0000000U) == 0) {
      59        2078 :         value <<= 4;
      60        2078 :         bit -= 4;
      61             :     }
      62        2428 :     if ((value & 0xC0000000U) == 0) {
      63        1649 :         value <<= 2;
      64        1649 :         bit -= 2;
      65             :     }
      66        2428 :     if ((value & 0x80000000U) == 0) {
      67        1457 :         value <<= 1;
      68        1457 :         bit -= 1;
      69             :     }
      70             : 
      71        2428 :     return bit;
      72             : }
      73             : 
      74             : //
      75             : // Provides the same functionality as flsl.  Needed as flsl is not supported
      76             : // on all platforms. Note that the positions are numbered 1 through 64, with
      77             : // a return value of 0 indicating that there are no set bits.
      78             : //
      79        2428 : static int find_last_set64(uint64_t value) {
      80             :     int bit;
      81             : 
      82        2428 :     int upper = value >> 32;
      83        2428 :     if ((bit = find_last_set32(upper)) > 0)
      84         376 :         return 32 + bit;
      85             : 
      86        2052 :     int lower = static_cast<int>(value);
      87        2052 :     if ((bit = find_last_set32(lower)) > 0)
      88        2052 :         return bit;
      89             : 
      90           0 :     return 0;
      91             : }
      92             : 
      93             : //
      94             : // Return the number of set bits. K&R method.
      95             : //
      96       19659 : static int num_bits_set(uint64_t value) {
      97       19659 :     int count = 0;
      98     1070635 :     while (value != 0) {
      99     1050976 :         value &= value - 1;
     100     1050976 :         count++;
     101             :     }
     102       19659 :     return count;
     103             : }
     104             : 
     105             : // Position pos is w.r.t the entire bitset, starts at 0.
     106             : // Index    idx is the block number i.e. the index in the vector, starts at 0.
     107             : // Offset   offset is w.r.t a given 64 bit block, starts at 0.
     108    12850138 : static inline size_t block_index(size_t pos) {
     109    12850138 :     return pos / 64;
     110             : }
     111             : 
     112    17010859 : static inline size_t block_offset(size_t pos) {
     113    17010859 :     return pos % 64;
     114             : }
     115             : 
     116     4554771 : static inline size_t bit_position(size_t idx, size_t offset) {
     117     4554771 :     return (idx * 64 + offset);
     118             : }
     119             : 
     120             : const size_t BitSet::npos;
     121             : 
     122             : //
     123             : // Set bit at given position, growing the vector if needed.
     124             : //
     125     6042011 : BitSet &BitSet::set(size_t pos) {
     126     6042011 :     size_t idx = block_index(pos);
     127     6042012 :     if (idx >= blocks_.size())
     128     1449441 :         blocks_.resize(idx + 1);
     129     6041993 :     blocks_[idx] |= 1LL << block_offset(pos);
     130     6042204 :     return *this;
     131             : }
     132             : 
     133             : //
     134             : // Reset bit at given position, shrinking the vector if possible.
     135             : //
     136     1983949 : BitSet &BitSet::reset(size_t pos) {
     137     1983949 :     size_t idx = block_index(pos);
     138     1983940 :     if (idx < blocks_.size()) {
     139     1983852 :         blocks_[idx] &= ~(1LL << block_offset(pos));
     140     1983840 :         compact();
     141             :     }
     142     1983843 :     return *this;
     143             : }
     144             : 
     145             : // Test bit at given position.
     146      555359 : bool BitSet::test(size_t pos) const {
     147      555359 :     size_t idx = block_index(pos);
     148      555356 :     if (idx < blocks_.size()) {
     149      458594 :         return ((blocks_[idx] & (1LL << block_offset(pos))) != 0);
     150             :     } else {
     151       96762 :         return false;
     152             :     }
     153             : }
     154             : 
     155             : //
     156             : // Shortcut to reset all bits in the bitset.
     157             : //
     158       20596 : void BitSet::clear() {
     159       20596 :     blocks_.resize(0);
     160       20596 : }
     161             : 
     162             : //
     163             : // Return true if there are no bits in the bitset.
     164             : //
     165     6256941 : bool BitSet::empty() const {
     166     6256941 :     return (blocks_.size() == 0);
     167             : }
     168             : 
     169             : //
     170             : // Return true if no bits are set.
     171             : //
     172      368109 : bool BitSet::none() const {
     173      368109 :     return (blocks_.size() == 0);
     174             : }
     175             : 
     176             : //
     177             : // Return true at least one bit is set.
     178             : //
     179         642 : bool BitSet::any() const {
     180         642 :     return (blocks_.size() != 0);
     181             : }
     182             : 
     183             : //
     184             : // Return the raw number of bits in the bitset. Simply depends on the number
     185             : // of blocks in the vector.
     186             : //
     187       71365 : size_t BitSet::size() const {
     188       71365 :     return blocks_.size() * 64;
     189             : }
     190             : 
     191             : //
     192             : // Return total number of set bits.
     193             : //
     194        4332 : size_t BitSet::count() const {
     195        4332 :     size_t count = 0;
     196       23991 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     197       19659 :         count += num_bits_set(blocks_[idx]);
     198             :     }
     199        4332 :     return count;
     200             : }
     201             : 
     202             : //
     203             : // Shrink the underlying vector as much as possible.  All trailing blocks
     204             : // that are 0 can be removed.
     205             : //
     206             : // Note that the for loop does not handle idx 0 since the loop  variable
     207             : // is unsigned.
     208             : //
     209     5255383 : void BitSet::compact() {
     210     5255383 :     if (blocks_.size() == 0)
     211      607613 :         return;
     212             : 
     213     4662705 :     for (size_t idx = blocks_.size() - 1; idx > 0; idx--) {
     214      108682 :         if (blocks_[idx] != 0) {
     215       93573 :             blocks_.resize(idx + 1);
     216       93573 :             return;
     217             :         }
     218             :     }
     219             : 
     220     4554272 :     if (blocks_[0] != 0) {
     221     1670671 :         blocks_.resize(1);
     222     1670662 :         return;
     223             :     }
     224             : 
     225     2883536 :     blocks_.clear();
     226             : }
     227             : 
     228             : //
     229             : // Sanity check a bitset.  The last block must never be 0.  Always called
     230             : // after any compaction is done or in cases where no compaction is needed.
     231             : //
     232    12125993 : void BitSet::check_invariants() {
     233    12125993 :     size_t mysize = blocks_.size();
     234    12125527 :     if (mysize != 0)
     235     8100009 :         assert(blocks_[mysize -1] != 0);
     236    12125350 : }
     237             : 
     238             : //
     239             : // Return the position of the first set bit.  Needs to compensate for the
     240             : // return value convention used by find_first_set64.
     241             : //
     242     2948347 : size_t BitSet::find_first() const {
     243     2948539 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     244     1720780 :         int bit = find_first_set64(blocks_[idx]);
     245     1721997 :         if (bit > 0)
     246     1721805 :             return bit_position(idx, bit - 1);
     247             :     }
     248     1227900 :     return BitSet::npos;
     249             : }
     250             : 
     251             : //
     252             : // Return the position of the next set bit.  Needs to compensate for the
     253             : // return value convention used by find_first_set64.
     254             : //
     255     4259144 : size_t BitSet::find_next(size_t pos) const {
     256     4259144 :     size_t idx = block_index(pos);
     257             : 
     258             :     // If the block index is beyond the vector, we're done.
     259     4258816 :     if (idx >= blocks_.size())
     260        1087 :         return BitSet::npos;
     261             : 
     262             :     // If the offset is not 63, clear out the bits from 0 through offset
     263             :     // and look for the first set bit.
     264     4257564 :     if (block_offset(pos) < 63) {
     265     4257033 :         uint64_t temp = blocks_[idx] & ~((1LL << (block_offset(pos) + 1)) - 1);
     266     4256752 :         int bit = find_first_set64(temp);
     267     4257997 :         if (bit > 0)
     268     2532809 :             return bit_position(idx, bit - 1);
     269             :     }
     270             : 
     271             :     // Go through all blocks after the start block for the pos and see if
     272             :     // there's a set bit.
     273     1732317 :     for (idx++; idx < blocks_.size(); idx++) {
     274       10451 :         int bit = find_first_set64(blocks_[idx]);
     275       10456 :         if (bit > 0)
     276        3736 :             return bit_position(idx, bit - 1);
     277             :     }
     278     1721840 :     return BitSet::npos;
     279             : }
     280             : 
     281             : //
     282             : // Return the position of the last set bit.  Needs to compensate for the
     283             : // return value convention used by find_last_set64.
     284             : //
     285             : // Note that we only need to look at the last block since that must have
     286             : // at least one bit set.
     287             : //
     288        3722 : size_t BitSet::find_last() const {
     289        3722 :     if (blocks_.size() == 0)
     290        1294 :         return BitSet::npos;
     291             : 
     292        2428 :     size_t idx = blocks_.size() - 1;
     293        2428 :     int bit = find_last_set64(blocks_[idx]);
     294        2428 :     if (bit > 0)
     295        2428 :         return bit_position(idx, bit - 1);
     296             : 
     297           0 :     return BitSet::npos;
     298             : }
     299             : 
     300             : //
     301             : // Return the position of the first clear bit.  It could be beyond the last
     302             : // block in the vector. This is fine as we automatically grow the vector if
     303             : // needed from set().
     304             : //
     305             : // Need to compensate for return value convention used by find_first_clear64.
     306             : //
     307      358943 : size_t BitSet::find_first_clear() const {
     308      700455 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     309      629322 :         int bit = find_first_clear64(blocks_[idx]);
     310      629322 :         if (bit > 0) {
     311      287810 :             return bit_position(idx, bit - 1);
     312             :         }
     313             :     }
     314       71133 :     return size();
     315             : }
     316             : 
     317             : //
     318             : // Return the position of the next clear bit.  It could be beyond the last
     319             : // block in the vector. This is fine as we automatically grow the vector if
     320             : // needed from set().
     321             : //
     322             : // Need to compensate for return value convention used by find_first_clear64.
     323             : //
     324       10547 : size_t BitSet::find_next_clear(size_t pos) const {
     325       10547 :     size_t idx = block_index(pos);
     326             : 
     327             :     // If the block index is beyond the vector, we're done.
     328       10547 :     if (idx >= blocks_.size())
     329        3450 :         return pos + 1;
     330             : 
     331             :     // If the offset is not 63, set all the bits from 0 through offset and
     332             :     // look for the first clear bit.
     333        7097 :     if (block_offset(pos) < 63) {
     334        7000 :         uint64_t temp = blocks_[idx] | ((1LL << (block_offset(pos) + 1)) - 1);
     335        7000 :         int bit = find_first_clear64(temp);
     336        7000 :         if (bit > 0)
     337        3913 :             return bit_position(idx, bit - 1);
     338             :     }
     339             : 
     340             :     // Go through all blocks after the start block for the pos and see if
     341             :     // there's a clear bit.
     342        9968 :     for (idx++; idx < blocks_.size(); idx++) {
     343        9762 :         int bit = find_first_clear64(blocks_[idx]);
     344        9762 :         if (bit > 0) {
     345        2978 :             return bit_position(idx, bit - 1);
     346             :         }
     347             :     }
     348         206 :     return size();
     349             : }
     350             : 
     351             : //
     352             : // Return (*this & rhs != 0).
     353             : //
     354         642 : bool BitSet::intersects(const BitSet &rhs) const {
     355         642 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     356        1188 :     for (size_t idx = 0; idx < minsize; idx++) {
     357        1168 :         if (blocks_[idx] & rhs.blocks_[idx])
     358         622 :             return true;
     359             :     }
     360          20 :     return false;
     361             : }
     362             : 
     363             : //
     364             : // Return (*this == rhs).
     365             : //
     366             : // Note that it's fine to first compare the number of blocks in the vectors
     367             : // since we always shrink the vectors whenever possible.
     368             : //
     369     1364138 : bool BitSet::operator==(const BitSet &rhs) const {
     370     1364138 :     if (blocks_.size() != rhs.blocks_.size())
     371     1220112 :         return false;
     372      301744 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     373      161972 :         if (blocks_[idx] != rhs.blocks_[idx])
     374        4245 :             return false;
     375             :     }
     376      139752 :     return true;
     377             : }
     378             : 
     379             : //
     380             : // Return (*this != rhs).
     381             : //
     382      728349 : bool BitSet::operator!=(const BitSet &rhs) const {
     383      728349 :     return !operator==(rhs);
     384             : }
     385             : 
     386             : //
     387             : // Return (*this & rhs).
     388             : //
     389        4744 : BitSet BitSet::operator&(const BitSet &rhs) const {
     390        4744 :     BitSet temp;
     391        4744 :     temp.BuildIntersection(*this, rhs);
     392        4744 :     temp.check_invariants();
     393        4744 :     return temp;
     394           0 : }
     395             : 
     396             : //
     397             : // Return (*this | rhs).
     398             : //
     399         642 : BitSet BitSet::operator|(const BitSet &rhs) const {
     400         642 :     BitSet temp;
     401         642 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     402         642 :     size_t maxsize = std::max(blocks_.size(), rhs.blocks_.size());
     403         642 :     temp.blocks_.resize(maxsize);
     404             : 
     405             :     // Process common blocks.
     406        3578 :     for (size_t idx = 0; idx < minsize; idx++) {
     407        2936 :         temp.blocks_[idx] = blocks_[idx] | rhs.blocks_[idx];
     408             :     }
     409             : 
     410             :     // Process blocks that exist in LHS only. It's a noop if RHS is bigger.
     411        1262 :     for (size_t idx = minsize; idx < blocks_.size(); idx++) {
     412         620 :         temp.blocks_[idx] = blocks_[idx];
     413             :     }
     414             : 
     415             :     // Process blocks that exist in RHS only. It's a noop if LHS is bigger.
     416        1262 :     for (size_t idx = minsize; idx < rhs.blocks_.size(); idx++) {
     417         620 :         temp.blocks_[idx] = rhs.blocks_[idx];
     418             :     }
     419             : 
     420         642 :     temp.check_invariants();
     421         642 :     return temp;
     422           0 : }
     423             : 
     424             : //
     425             : // Implement (*this &= rhs).
     426             : //
     427             : // Note that we can't simply resize the vector to minsize since we may be
     428             : // able to shrink it even more depending on the values in the blocks.
     429             : //
     430         640 : BitSet &BitSet::operator&=(const BitSet &rhs) {
     431         640 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     432        3560 :     for (size_t idx = 0; idx < minsize; idx++) {
     433        2920 :         blocks_[idx] &= rhs.blocks_[idx];
     434             :     }
     435        1252 :     for (size_t idx = minsize; idx < blocks_.size(); idx++) {
     436         612 :         blocks_[idx] = 0;
     437             :     }
     438         640 :     compact();
     439         640 :     check_invariants();
     440         640 :     return *this;
     441             : }
     442             : 
     443             : //
     444             : // Implement (*this |= rhs).
     445             : //
     446             : // Note that we grow the vector only once instead of doing it multiple
     447             : // times.
     448             : //
     449     5719348 : BitSet &BitSet::operator|=(const BitSet &rhs) {
     450     5719348 :     if (blocks_.size() < rhs.blocks_.size())
     451     2396524 :         blocks_.resize(rhs.blocks_.size());
     452     9269698 :     for (size_t idx = 0; idx < rhs.blocks_.size(); idx++) {
     453     3550859 :         blocks_[idx] |= rhs.blocks_[idx];
     454             :     }
     455     5717316 :     check_invariants();
     456     5718073 :     return *this;
     457             : }
     458             : 
     459             : //
     460             : // Identical to operator|=.
     461             : //
     462     2242112 : void BitSet::Set(const BitSet &rhs) {
     463     2242112 :     this->operator|=(rhs);
     464     2241663 :     check_invariants();
     465     2241533 : }
     466             : 
     467             : //
     468             : // Implement (*this &= ~rhs).
     469             : //
     470     2632203 : void BitSet::Reset(const BitSet &rhs) {
     471     2632203 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     472     4523130 :     for (size_t idx = 0; idx < minsize; idx++) {
     473     1891230 :         blocks_[idx] &= ~rhs.blocks_[idx];
     474             :     }
     475     2631900 :     compact();
     476     2631595 :     check_invariants();
     477     2631403 : }
     478             : 
     479             : //
     480             : // Implement (*this = lhs & ~rhs).
     481             : //
     482             : // Note that we won't enter the second for loop at all if lhs is not bigger
     483             : // than rhs.  Need to compact only for this case, but it is cheap enough to
     484             : // try (and do nothing) when lhs is bigger than rhs.
     485             : //
     486      639318 : void BitSet::BuildComplement(const BitSet &lhs, const BitSet &rhs) {
     487      639318 :     blocks_.clear();
     488      639312 :     blocks_.resize(lhs.blocks_.size());
     489      639319 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     490     1254821 :     for (size_t idx = 0; idx < minsize; idx++) {
     491      615515 :         blocks_[idx] = lhs.blocks_[idx] & ~rhs.blocks_[idx];
     492             :     }
     493      647833 :     for (size_t idx = minsize; idx < lhs.blocks_.size(); idx++) {
     494        8527 :         blocks_[idx] = lhs.blocks_[idx];
     495             :     }
     496      639303 :     compact();
     497      639308 :     check_invariants();
     498      639295 : }
     499             : 
     500             : //
     501             : // Implement (*this = lhs & rhs).
     502             : //
     503             : // We avoid the need to compact or to resize multiple times by building
     504             : // the blocks in reverse order.
     505             : //
     506             : // Note that the for loop does not handle idx 0 since the loop  variable
     507             : // is unsigned.
     508             : //
     509     1088173 : void BitSet::BuildIntersection(const BitSet &lhs, const BitSet &rhs) {
     510     1088173 :     blocks_.clear();
     511     1088187 :     size_t minsize = std::min(lhs.blocks_.size(), rhs.blocks_.size());
     512             : 
     513     1088153 :     if (minsize == 0)
     514      191923 :         return;
     515             : 
     516      898590 :     for (size_t idx = minsize - 1; idx > 0; idx--) {
     517        2360 :         if (lhs.blocks_[idx] & rhs.blocks_[idx]) {
     518        1560 :             if (blocks_.size() == 0)
     519         482 :                 blocks_.resize(idx + 1);
     520        1560 :             blocks_[idx] = lhs.blocks_[idx] & rhs.blocks_[idx];
     521             :         }
     522             :     }
     523             : 
     524      896230 :     if (lhs.blocks_[0] & rhs.blocks_[0]) {
     525      880942 :         if (blocks_.size() == 0)
     526      880516 :             blocks_.resize(1);
     527      881001 :         blocks_[0] = lhs.blocks_[0] & rhs.blocks_[0];
     528             :     }
     529             : 
     530      896265 :     check_invariants();
     531             : }
     532             : 
     533             : //
     534             : // Return true if *this contains rhs.  Implemented as (rhs & ~*this != 0).
     535             : //
     536      930452 : bool BitSet::Contains(const BitSet &rhs) const {
     537      930452 :     if (blocks_.size() < rhs.blocks_.size())
     538        1683 :         return false;
     539     1237332 :     for (size_t idx = 0; idx < rhs.blocks_.size(); idx++) {
     540      312707 :         if (rhs.blocks_[idx] & ~blocks_[idx])
     541        4185 :             return false;
     542             :     }
     543      924562 :     return true;
     544             : }
     545             : 
     546             : //
     547             : // Returns string representation of the bitset. A character in the string is
     548             : // '1' if the corresponding bit is set, and '0' if it is not.  The character
     549             : // position i in the string corresponds to bit position i in the bitset.
     550             : //
     551        3209 : string BitSet::ToString() const {
     552        3209 :     size_t last_pos = find_last();
     553        3209 :     if (last_pos == BitSet::npos)
     554        1293 :         return string();
     555             : 
     556        1916 :     string str(last_pos + 1, '0');
     557        6505 :     for (size_t pos = find_first(); pos != BitSet::npos; pos = find_next(pos)) {
     558        4589 :         str[pos] = '1';
     559             :     }
     560        1916 :     return str;
     561        1916 : }
     562             : 
     563             : //
     564             : // Initialize the bitset from the provided string representation. The string
     565             : // must use the same format as described in ToString above. We traverse the
     566             : // string in reverse order to ensure that we do not have to resize multiple
     567             : // times.
     568             : //
     569             : // Note that the for loop does not handle str_idx 0 since the loop variable
     570             : // is unsigned.
     571             : //
     572          65 : void BitSet::FromString(string str) {
     573          65 :     blocks_.clear();
     574             : 
     575          65 :     if (str.length() == 0)
     576           1 :         return;
     577             : 
     578       31773 :     for (size_t str_idx = str.length() - 1; str_idx > 0; str_idx--) {
     579       31709 :         if (str[str_idx] == '1')
     580        2395 :             set(str_idx);
     581             :     }
     582             : 
     583          64 :     if (str[0] == '1')
     584          64 :         set(0);
     585             : }
     586             : 
     587             : //
     588             : // Returns numbered string representation of the bitset. The numbers are the
     589             : // bit positions that are set in the bitset.  Consecutive bit positions are
     590             : // represented as x-y and a comma is used as a separator for non-consecutive
     591             : // positions.
     592             : //
     593          66 : string BitSet::ToNumberedString() const {
     594          66 :     if (empty())
     595           1 :         return "-";
     596             : 
     597          65 :     ostringstream oss;
     598          65 :     bool range = false;
     599          65 :     size_t last_pos = BitSet::npos;
     600         205 :     for (size_t pos = find_first(); pos != BitSet::npos;
     601         140 :          last_pos = pos, pos = find_next(pos)) {
     602         140 :         if (last_pos == BitSet::npos) {
     603          65 :             oss << integerToString(pos);
     604          75 :         } else if (pos == last_pos + 1) {
     605          44 :             range = true;
     606          31 :         } else if (range) {
     607          10 :             oss << "-" << integerToString(last_pos);
     608          10 :             oss << "," << integerToString(pos);
     609          10 :             range = false;
     610             :         } else {
     611          21 :             oss << "," << integerToString(pos);
     612             :         }
     613             :     }
     614             : 
     615          65 :     if (range)
     616          19 :        oss << "-" << integerToString(last_pos);
     617             : 
     618          65 :     return oss.str();
     619          65 : }