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     6607357 : static int find_first_set64(uint64_t value) {
      23             :     int bit;
      24             : 
      25     6607357 :     int lower = static_cast<int>(value);
      26     6607357 :     if ((bit = ffs(lower)) > 0)
      27     4493168 :         return bit;
      28             : 
      29     2114189 :     int upper = value >> 32;
      30     2114189 :     if ((bit = ffs(upper)) > 0)
      31       41145 :         return 32 + bit;
      32             : 
      33     2073044 :     return 0;
      34             : }
      35             : 
      36      645633 : static int find_first_clear64(uint64_t value) {
      37      645633 :     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        4496 : static int find_last_set32(uint32_t value) {
      46        4496 :     if (value == 0)
      47        2060 :         return 0;
      48             : 
      49        2436 :     int bit = 32;
      50        2436 :     if ((value & 0xFFFF0000U) == 0) {
      51        2073 :         value <<= 16;
      52        2073 :         bit -= 16;
      53             :     }
      54        2436 :     if ((value & 0xFF000000U) == 0) {
      55        2070 :         value <<= 8;
      56        2070 :         bit -= 8;
      57             :     }
      58        2436 :     if ((value & 0xF0000000U) == 0) {
      59        2086 :         value <<= 4;
      60        2086 :         bit -= 4;
      61             :     }
      62        2436 :     if ((value & 0xC0000000U) == 0) {
      63        1657 :         value <<= 2;
      64        1657 :         bit -= 2;
      65             :     }
      66        2436 :     if ((value & 0x80000000U) == 0) {
      67        1475 :         value <<= 1;
      68        1475 :         bit -= 1;
      69             :     }
      70             : 
      71        2436 :     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        2436 : static int find_last_set64(uint64_t value) {
      80             :     int bit;
      81             : 
      82        2436 :     int upper = value >> 32;
      83        2436 :     if ((bit = find_last_set32(upper)) > 0)
      84         376 :         return 32 + bit;
      85             : 
      86        2060 :     int lower = static_cast<int>(value);
      87        2060 :     if ((bit = find_last_set32(lower)) > 0)
      88        2060 :         return bit;
      89             : 
      90           0 :     return 0;
      91             : }
      92             : 
      93             : //
      94             : // Return the number of set bits. K&R method.
      95             : //
      96       19657 : static int num_bits_set(uint64_t value) {
      97       19657 :     int count = 0;
      98     1070631 :     while (value != 0) {
      99     1050974 :         value &= value - 1;
     100     1050974 :         count++;
     101             :     }
     102       19657 :     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    12816102 : static inline size_t block_index(size_t pos) {
     109    12816102 :     return pos / 64;
     110             : }
     111             : 
     112    16959205 : static inline size_t block_offset(size_t pos) {
     113    16959205 :     return pos % 64;
     114             : }
     115             : 
     116     4536212 : static inline size_t bit_position(size_t idx, size_t offset) {
     117     4536212 :     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     6029945 : BitSet &BitSet::set(size_t pos) {
     126     6029945 :     size_t idx = block_index(pos);
     127     6029931 :     if (idx >= blocks_.size())
     128     1443662 :         blocks_.resize(idx + 1);
     129     6029933 :     blocks_[idx] |= 1LL << block_offset(pos);
     130     6030218 :     return *this;
     131             : }
     132             : 
     133             : //
     134             : // Reset bit at given position, shrinking the vector if possible.
     135             : //
     136     1980445 : BitSet &BitSet::reset(size_t pos) {
     137     1980445 :     size_t idx = block_index(pos);
     138     1980434 :     if (idx < blocks_.size()) {
     139     1980349 :         blocks_[idx] &= ~(1LL << block_offset(pos));
     140     1980330 :         compact();
     141             :     }
     142     1980300 :     return *this;
     143             : }
     144             : 
     145             : // Test bit at given position.
     146      554702 : bool BitSet::test(size_t pos) const {
     147      554702 :     size_t idx = block_index(pos);
     148      554694 :     if (idx < blocks_.size()) {
     149      458320 :         return ((blocks_[idx] & (1LL << block_offset(pos))) != 0);
     150             :     } else {
     151       96375 :         return false;
     152             :     }
     153             : }
     154             : 
     155             : //
     156             : // Shortcut to reset all bits in the bitset.
     157             : //
     158       20597 : void BitSet::clear() {
     159       20597 :     blocks_.resize(0);
     160       20597 : }
     161             : 
     162             : //
     163             : // Return true if there are no bits in the bitset.
     164             : //
     165     6260048 : bool BitSet::empty() const {
     166     6260048 :     return (blocks_.size() == 0);
     167             : }
     168             : 
     169             : //
     170             : // Return true if no bits are set.
     171             : //
     172      367597 : bool BitSet::none() const {
     173      367597 :     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       70818 : size_t BitSet::size() const {
     188       70818 :     return blocks_.size() * 64;
     189             : }
     190             : 
     191             : //
     192             : // Return total number of set bits.
     193             : //
     194        4330 : size_t BitSet::count() const {
     195        4330 :     size_t count = 0;
     196       23987 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     197       19657 :         count += num_bits_set(blocks_[idx]);
     198             :     }
     199        4330 :     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     5251093 : void BitSet::compact() {
     210     5251093 :     if (blocks_.size() == 0)
     211      611097 :         return;
     212             : 
     213     4654869 :     for (size_t idx = blocks_.size() - 1; idx > 0; idx--) {
     214      108246 :         if (blocks_[idx] != 0) {
     215       93137 :             blocks_.resize(idx + 1);
     216       93137 :             return;
     217             :         }
     218             :     }
     219             : 
     220     4546911 :     if (blocks_[0] != 0) {
     221     1672932 :         blocks_.resize(1);
     222     1672925 :         return;
     223             :     }
     224             : 
     225     2873909 :     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    12128023 : void BitSet::check_invariants() {
     233    12128023 :     size_t mysize = blocks_.size();
     234    12127032 :     if (mysize != 0)
     235     8111429 :         assert(blocks_[mysize -1] != 0);
     236    12126820 : }
     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     2933355 : size_t BitSet::find_first() const {
     243     2933547 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     244     1711852 :         int bit = find_first_set64(blocks_[idx]);
     245     1713358 :         if (bit > 0)
     246     1713166 :             return bit_position(idx, bit - 1);
     247             :     }
     248     1221767 :     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     4241314 : size_t BitSet::find_next(size_t pos) const {
     256     4241314 :     size_t idx = block_index(pos);
     257             : 
     258             :     // If the block index is beyond the vector, we're done.
     259     4241111 :     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     4239817 :     if (block_offset(pos) < 63) {
     265     4239266 :         uint64_t temp = blocks_[idx] & ~((1LL << (block_offset(pos) + 1)) - 1);
     266     4238937 :         int bit = find_first_set64(temp);
     267     4240420 :         if (bit > 0)
     268     2523608 :             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     1723912 :     for (idx++; idx < blocks_.size(); idx++) {
     274       10449 :         int bit = find_first_set64(blocks_[idx]);
     275       10456 :         if (bit > 0)
     276        3736 :             return bit_position(idx, bit - 1);
     277             :     }
     278     1713439 :     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        3730 : size_t BitSet::find_last() const {
     289        3730 :     if (blocks_.size() == 0)
     290        1294 :         return BitSet::npos;
     291             : 
     292        2436 :     size_t idx = blocks_.size() - 1;
     293        2436 :     int bit = find_last_set64(blocks_[idx]);
     294        2436 :     if (bit > 0)
     295        2436 :         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      357838 : size_t BitSet::find_first_clear() const {
     308      699350 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     309      628764 :         int bit = find_first_clear64(blocks_[idx]);
     310      628764 :         if (bit > 0) {
     311      287252 :             return bit_position(idx, bit - 1);
     312             :         }
     313             :     }
     314       70586 :     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       10690 : size_t BitSet::find_next_clear(size_t pos) const {
     325       10690 :     size_t idx = block_index(pos);
     326             : 
     327             :     // If the block index is beyond the vector, we're done.
     328       10690 :     if (idx >= blocks_.size())
     329        3486 :         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        7204 :     if (block_offset(pos) < 63) {
     334        7107 :         uint64_t temp = blocks_[idx] | ((1LL << (block_offset(pos) + 1)) - 1);
     335        7107 :         int bit = find_first_clear64(temp);
     336        7107 :         if (bit > 0)
     337        4020 :             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     1359015 : bool BitSet::operator==(const BitSet &rhs) const {
     370     1359015 :     if (blocks_.size() != rhs.blocks_.size())
     371     1214104 :         return false;
     372      303469 :     for (size_t idx = 0; idx < blocks_.size(); idx++) {
     373      162871 :         if (blocks_[idx] != rhs.blocks_[idx])
     374        4311 :             return false;
     375             :     }
     376      140581 :     return true;
     377             : }
     378             : 
     379             : //
     380             : // Return (*this != rhs).
     381             : //
     382      725915 : bool BitSet::operator!=(const BitSet &rhs) const {
     383      725915 :     return !operator==(rhs);
     384             : }
     385             : 
     386             : //
     387             : // Return (*this & rhs).
     388             : //
     389        4727 : BitSet BitSet::operator&(const BitSet &rhs) const {
     390        4727 :     BitSet temp;
     391        4727 :     temp.BuildIntersection(*this, rhs);
     392        4727 :     temp.check_invariants();
     393        4727 :     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     5719989 : BitSet &BitSet::operator|=(const BitSet &rhs) {
     450     5719989 :     if (blocks_.size() < rhs.blocks_.size())
     451     2397268 :         blocks_.resize(rhs.blocks_.size());
     452     9276159 :     for (size_t idx = 0; idx < rhs.blocks_.size(); idx++) {
     453     3556825 :         blocks_[idx] |= rhs.blocks_[idx];
     454             :     }
     455     5717272 :     check_invariants();
     456     5718302 :     return *this;
     457             : }
     458             : 
     459             : //
     460             : // Identical to operator|=.
     461             : //
     462     2248438 : void BitSet::Set(const BitSet &rhs) {
     463     2248438 :     this->operator|=(rhs);
     464     2247936 :     check_invariants();
     465     2247730 : }
     466             : 
     467             : //
     468             : // Implement (*this &= ~rhs).
     469             : //
     470     2634288 : void BitSet::Reset(const BitSet &rhs) {
     471     2634288 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     472     4525059 :     for (size_t idx = 0; idx < minsize; idx++) {
     473     1891067 :         blocks_[idx] &= ~rhs.blocks_[idx];
     474             :     }
     475     2633992 :     compact();
     476     2633547 :     check_invariants();
     477     2633373 : }
     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      636568 : void BitSet::BuildComplement(const BitSet &lhs, const BitSet &rhs) {
     487      636568 :     blocks_.clear();
     488      636577 :     blocks_.resize(lhs.blocks_.size());
     489      636564 :     size_t minsize = std::min(blocks_.size(), rhs.blocks_.size());
     490     1249125 :     for (size_t idx = 0; idx < minsize; idx++) {
     491      612566 :         blocks_[idx] = lhs.blocks_[idx] & ~rhs.blocks_[idx];
     492             :     }
     493      645343 :     for (size_t idx = minsize; idx < lhs.blocks_.size(); idx++) {
     494        8784 :         blocks_[idx] = lhs.blocks_[idx];
     495             :     }
     496      636554 :     compact();
     497      636535 :     check_invariants();
     498      636530 : }
     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     1085601 : void BitSet::BuildIntersection(const BitSet &lhs, const BitSet &rhs) {
     510     1085601 :     blocks_.clear();
     511     1085573 :     size_t minsize = std::min(lhs.blocks_.size(), rhs.blocks_.size());
     512             : 
     513     1085553 :     if (minsize == 0)
     514      191724 :         return;
     515             : 
     516      896189 :     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      893829 :     if (lhs.blocks_[0] & rhs.blocks_[0]) {
     525      877083 :         if (blocks_.size() == 0)
     526      876655 :             blocks_.resize(1);
     527      877186 :         blocks_[0] = lhs.blocks_[0] & rhs.blocks_[0];
     528             :     }
     529             : 
     530      893880 :     check_invariants();
     531             : }
     532             : 
     533             : //
     534             : // Return true if *this contains rhs.  Implemented as (rhs & ~*this != 0).
     535             : //
     536      930118 : bool BitSet::Contains(const BitSet &rhs) const {
     537      930118 :     if (blocks_.size() < rhs.blocks_.size())
     538        1759 :         return false;
     539     1239422 :     for (size_t idx = 0; idx < rhs.blocks_.size(); idx++) {
     540      315178 :         if (rhs.blocks_[idx] & ~blocks_[idx])
     541        4168 :             return false;
     542             :     }
     543      924166 :     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        3217 : string BitSet::ToString() const {
     552        3217 :     size_t last_pos = find_last();
     553        3217 :     if (last_pos == BitSet::npos)
     554        1293 :         return string();
     555             : 
     556        1924 :     string str(last_pos + 1, '0');
     557        6529 :     for (size_t pos = find_first(); pos != BitSet::npos; pos = find_next(pos)) {
     558        4605 :         str[pos] = '1';
     559             :     }
     560        1924 :     return str;
     561        1924 : }
     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          64 : string BitSet::ToNumberedString() const {
     594          64 :     if (empty())
     595           1 :         return "-";
     596             : 
     597          63 :     ostringstream oss;
     598          63 :     bool range = false;
     599          63 :     size_t last_pos = BitSet::npos;
     600         199 :     for (size_t pos = find_first(); pos != BitSet::npos;
     601         136 :          last_pos = pos, pos = find_next(pos)) {
     602         136 :         if (last_pos == BitSet::npos) {
     603          63 :             oss << integerToString(pos);
     604          73 :         } else if (pos == last_pos + 1) {
     605          42 :             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          63 :     if (range)
     616          17 :        oss << "-" << integerToString(last_pos);
     617             : 
     618          63 :     return oss.str();
     619          63 : }