总结

把总结放在开头，方便回顾，下面是要点

  • 容量要求：已缓存但未加入流中的字节数+流中的字节数<=capacity
  • 使用1个数据结构保存“已缓存但未加入流中的字节数”，我用的是Map
    • value是一个string，表示一段数据
    • key是一个size_t，表示这段数据的第一个字节在字节流中的序号
    • 这个数据结构实际上处理的是区间合并问题
  • 使用_next_index表示还未加入流中的第一个字节序号，那么总的窗口就是[_next_index, _next_index+capacity)
    • Map的窗口就是[_next_index, _next_index+capacity-ByteStream.size())
    • 或者也可以表示成[_next_index, _next_index+ByteStream.remaining_capacity())
    • Map中保存的是在这个大区间内的不相交的若干个子区间
  • push_string传进来的data，需要和Map的窗口取交集，记为[L, R)，这部分数据是实际上保留下来的，准备加入Map乃至加入流中的数据
  • 找出Map中所有与[L, R)相交的区间
    • 若找到多个这样的区间，则实际起作用的最多是第一个和最后一个区间，中间的区间一定都是[L, R)的子区间
    • 把第一个区间、最后一个区间和[L, R)按照序号合并成1个字符串，其区间记为[union_l, union_r)
    • 若Map中没有区间和[L, R)相交，则[L, R)==[union_l, union_r)
  • 从Map中删除所有与[L, R)相交的区间
  • 将[union_l, union_r)加入Map中
  • 最后按序号从小到大的顺序遍历Map，检查区间的左端点是否与_next_index相等
    • 若相等，则将这个区间加入流中
    • 每次遍历，都要更新_next_index，因为后面的区间虽然不相交，但是可能是连着的，也要处理
  • 当然别忘了处理eof
    • 如果带有eof的字节被加入流中，则调用流的end_input()

  • 代码中使用的序号变量类型是size_t，在64位系统下，这个类型实际上是64位无符号整数

    第一阶段

    思路

  • 保存乱序数据的结构：Map

    • 按照Key的Index从小到大排序，C++的map默认情况下应该就会这样排序

  • 问题：如果当前push了一个string，只能存下这个string的一部分数据怎么办？

    • 方案一：整个数据不要了，等到它下次push再尝试
      • 问题：如果capacity很小，数据很大，那么这个数据永远都放不进来
    • 方案二：存一部分数据进去，那么传进来的string会被拆开

  • Map中缓存的数据应该是有限的

    • next_index+capacity-stream.size()是上界，开区间
    • Map中序号最小和序号最大的这两份数据，都可能只是传进来的string的一部分
      • ①序号最小的数据，如果Map中只保存了一部分，说明它前面的那部分已经被加入到流中了
      • ②序号最大的数据，如果Map中只保存了一部分，说明在它保存进来的那个时刻，达到了capacity指定的上限
      • ②是①的因
  • 设想这样一种情况，capacity的值比较小，只有100，整个字节流只包含1个string，这个string的大小为1000
    • 那么Map中从头到尾放入的数据最多只有1份，且每次只能放入这个string的一部分

算法步骤

  1. 传入一个string，比较它的区间端点[index, index+string.size())和Map的区间端点[next_index, next_index+capacity-stream.size())的大小关系
    1. 不相交的部分丢弃，相交的部分添加到Map中
    2. 实际上，ByteStream的remaining_capacity返回的就是capacity-stream.size()
    3. [a,b)和[c,d)相交的判断条件是b>c&&d>a；判断相交，则它们相交的区间是[max(a,c), min(b,d)）
  2. 尝试将相交部分放入Map中（实际上是一个区间问题）
    1. 如果序号Key已经存在，则更新Value（有可能保存更多的数据部分进来）
    2. 如果序号Key不存在，则put
  3. 比较next_index和Map中的最小序号
    1. 如果不相等，则没有数据可以提交到流中
    2. 如果相等，则从Map中取出从next_index开始的连续字节，放入流中
  • 问题：第三步中，如果从Map中取出数据，Map有空余容量了，还需要回到第一步吗？
    • 不需要！时刻牢记，Map的容量和Stream的容量是合在一起的，在当前时刻，Stream里的数据肯定不会有人拿走（CS144明确说了不涉及多线程，即使涉及多线程，也是加锁的，别人不可能再同一时刻从Stream里取走数据）
    • Map有空余容量不代表整体有空余容量

如何处理eof？

  • 我设置了一个size_t类型的变量eof_index，初始值为size_t的最大值（字节流会超过size_t的最大值吗）
  • 如果收到了带eof=true的string，则更新eof_index
  • 如果Map已空，且eof_index不是size_t的最大值（已经被设置），且字节序号已经达到了eof_index，则调用ByteStream的end_input

代码

  1. #ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  2. #define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  4. #include "byte_stream.hh"
  6. #include <cstdint>
  7. #include <string>
  8. #include <map>
  10. //! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order,
  11. //! possibly overlapping) into an in-order byte stream.
  12. class StreamReassembler {
  13.   private:
  14.     // Your code here -- add private members as necessary.
  15.     size_t _next_index;
  16.     size_t _eof_index;
  17.     std::map<size_t, std::string> _unassembled_strings;
  18.     size_t _unassembled_bytes;
  20.     ByteStream _output;  //!< The reassembled in-order byte stream
  21.     size_t _capacity;    //!< The maximum number of bytes
  23.   public:
  24.     //! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes.
  25.     //! \note This capacity limits both the bytes that have been reassembled,
  26.     //! and those that have not yet been reassembled.
  27.     StreamReassembler(const size_t capacity);
  29.     //! \brief Receive a substring and write any newly contiguous bytes into the stream.
  30.     //!
  31.     //! The StreamReassembler will stay within the memory limits of the `capacity`.
  32.     //! Bytes that would exceed the capacity are silently discarded.
  33.     //!
  34.     //! \param data the substring
  35.     //! \param index indicates the index (place in sequence) of the first byte in `data`
  36.     //! \param eof the last byte of `data` will be the last byte in the entire stream
  37.     void push_substring(const std::string &data, const uint64_t index, const bool eof);
  39.     //! \name Access the reassembled byte stream
  40.     //!@{
  41.     const ByteStream &stream_out() const { return _output; }
  42.     ByteStream &stream_out() { return _output; }
  43.     //!@}
  45.     //! The number of bytes in the substrings stored but not yet reassembled
  46.     //!
  47.     //! \note If the byte at a particular index has been pushed more than once, it
  48.     //! should only be counted once for the purpose of this function.
  49.     size_t unassembled_bytes() const;
  51.     //! \brief Is the internal state empty (other than the output stream)?
  52.     //! \returns `true` if no substrings are waiting to be assembled
  53.     bool empty() const;
  54. };
  56. #endif  // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  64. #include "stream_reassembler.hh"
  65. #include <cmath>
  67. // Dummy implementation of a stream reassembler.
  69. // For Lab 1, please replace with a real implementation that passes the
  70. // automated checks run by `make check_lab1`.
  72. // You will need to add private members to the class declaration in `stream_reassembler.hh`
  74. template <typename... Targs>
  75. void DUMMY_CODE(Targs &&... /* unused */) {}
  77. using namespace std;
  79. StreamReassembler::StreamReassembler(const size_t capacity) 
  80.     : _next_index(0), _eof_index(unsigned(-1)), _unassembled_strings(), _unassembled_bytes(0),
  81.      _output(capacity), _capacity(capacity) {
  83. }
  85. //! \details This function accepts a substring (aka a segment) of bytes,
  86. //! possibly out-of-order, from the logical stream, and assembles any newly
  87. //! contiguous substrings and writes them into the output stream in order.
  88. void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
  89.     if (eof) {
  90.         _eof_index = index+data.size();
  91.     }
  93.     // [index, index+string.size())
  94.     // [_next_index, _next_index+capacity-stream.size())=[_next_index, _next_index+_output.remaining_capacity())
  95.     if (index+data.size()>_next_index&&_next_index+_output.remaining_capacity()>index) {  // 有相交的部分，或者说有可以缓存的数据
  96.         size_t L = std::max(index, _next_index);
  97.         size_t R = std::min(index+data.size(), _next_index+_output.remaining_capacity());
  99.         auto iter = _unassembled_strings.begin();
  100.         while (iter!=_unassembled_strings.end()) {
  101.             if (iter->first==L) {
  102.                 break;
  103.             }
  104.             iter++;  // 这句话一开始漏了
  105.         }
  106.         if (iter==_unassembled_strings.end()) {  // 没有找到，则新建
  107.             _unassembled_strings.insert(map<size_t, std::string>::value_type(L, data.substr(L-index, R-L)));
  108.         } else {  // 找到了，则更新
  109.             iter->second=data.substr(L-index, R-L);
  110.         }
  111.     }
  113.     // 接下来比较_next_index和Map中的最小序号
  114.     int toDeleteCount=0;
  115.     auto iter = _unassembled_strings.begin();
  116.     while (iter!=_unassembled_strings.end()) {
  117.         if (iter->first!=_next_index) {
  118.             break;
  119.         }
  120.         toDeleteCount++;
  121.         // 一定可以全部写入吧？？？因为前面计算过了
  122.         _output.write(iter->second);
  124.         // string toAddStr = iter->second;
  125.         // size_t added = 0;
  126.         // while (added<iter->second.size()) {
  127.         //     added+=_output.write(iter->second.substr(added, iter->second.size()-added));
  128.         // }
  130.         _next_index+=iter->second.size();
  131.     }
  133.     iter = _unassembled_strings.begin();
  134.     for (int i=0; i<toDeleteCount; i++) {
  135.         _unassembled_strings.erase(iter++);
  136.     }
  138.     if (_unassembled_strings.size()==0&&_next_index==_eof_index) {
  139.         _output.end_input();
  140.     }
  141. }
  143. // 返回已经缓存，但未组装到字节流中的字节个数
  144. size_t StreamReassembler::unassembled_bytes() const { 
  145.     size_t res=0;
  147.     auto iter = _unassembled_strings.begin();
  148.     while (iter!=_unassembled_strings.end()) {
  149.         res+=iter->second.size();
  150.     }
  151.     return res;
  152. }
  154. // unassembled_bytes()==0
  155. bool StreamReassembler::empty() const { 
  156.     return unassembled_bytes()==0; 
  157. }

测试结果

  • 过了一半的样例

image.png
后来发现遍历Map忘记iter++，但是加上去之后测试结果没变

第二阶段

思路

  • 保存乱序数据的结构：Map

    • 按照Key的Index从小到大排序，C++的map默认情况下应该就会这样排序

  • 问题：如果当前push了一个string，只能存下这个string的一部分数据怎么办？

    • 存一部分数据进去，那么传进来的string会被拆开
  • Map中缓存的数据应该是有限的
    • next_index+capacity-stream.size()是上界，开区间
    • Map中序号最小和序号最大的这两份数据，都可能只是传进来的string的一部分
      • ①序号最小的数据，如果Map中只保存了一部分，说明它前面的那部分已经被加入到流中了
      • ②序号最大的数据，如果Map中只保存了一部分，说明在它保存进来的那个时刻，达到了capacity指定的上限
      • ②是①的因
  • 设想这样一种情况，capacity的值比较小，只有100，整个字节流只包含1个string，这个string的大小为1000
    • 那么Map中从头到尾放入的数据最多只有1份，且每次只能放入这个string的一部分

算法步骤

  1. 传入一个string，比较它的区间端点[index, index+string.size())和Map的区间端点[next_index, next_index+capacity-stream.size())的大小关系
    1. 不相交的部分丢弃，相交的部分添加到Map中
    2. 实际上，ByteStream的remaining_capacity返回的就是capacity-stream.size()
    3. [a,b)和[c,d)相交的判断条件是b>c&&d>a；判断相交，则它们相交的区间是[max(a,c), min(b,d)）
    4. 记这里计算得到的待加入Map的字节流区间为[L, R)
  2. 尝试将[x, y)放入Map中（实际上是一个区间问题）
    1. 按顺序遍历Map，从中找出与[x, y)相交的区间，这些区间需要被标记删除
    2. 记这些相交的区间为[a0, b0)，[a2, b2)，……, [an, bn)
    3. 那么最终合并后的结果为[a0, b0)的部分+[L, R)+[an, bn)的部分
      1. 如果没有找到相交的区间，则这里得到的结果就是[L, R)
      2. 如果相交的区间只有一个，则注意它是[a0, b0)还是 [an, bn)，也就是区分在[L, R)的左侧还是右侧
    4. 从Map中删除这些区间
    5. 将合并后的结果加入Map中
  3. 比较next_index和Map中的最小序号
    1. 如果不相等，则没有数据可以提交到流中
    2. 如果相等，则从Map中取出从next_index开始的连续字节，放入流中（就是key最小的那个key-value对）
  • 问题：第三步中，如果从Map中取出数据，Map有空余容量了，还需要回到第一步吗？
    • 不需要！时刻牢记，Map的容量和Stream的容量是合在一起的，在当前时刻，Stream里的数据肯定不会有人拿走（CS144明确说了不涉及多线程，即使涉及多线程，也是加锁的，别人不可能再同一时刻从Stream里取走数据）
    • Map有空余容量不代表整体有空余容量

如何处理eof？

  • 我设置了一个size_t类型的变量eof_index，初始值为size_t的最大值（字节流会超过size_t的最大值吗）
  • 如果收到了带eof=true的string，则更新eof_index
  • 如果Map已空，且eof_index不是size_t的最大值（已经被设置），且字节序号已经达到了eof_index，则调用ByteStream的end_input

代码

发现byte_stream的read的bug

  1. std::string ByteStream::read(const size_t len) {
  2.     string res;
  3.     // 应该用一个变量保存一开始_data_q的大小
  4.     size_t init_sz=_data_q.size();
  5.     // i<_data_q.size()这么写不对！
  6.     for (size_t i=0; i<len&&i<init_sz; i++) {
  7.         res+=_data_q.front();
  8.         _data_q.pop_front();
  9.         _bytes_read++;
  10.     }
  11.     return res;
  12. }
  1. #ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  2. #define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  4. #include "byte_stream.hh"
  6. #include <cstdint>
  7. #include <string>
  8. #include <map>
  9. #include <utility>
  11. //! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order,
  12. //! possibly overlapping) into an in-order byte stream.
  13. class StreamReassembler {
  14.   private:
  15.     // Your code here -- add private members as necessary.
  16.     size_t _next_index;
  17.     size_t _eof_index;
  18.     std::map<size_t, std::string> _unassembled_strings;
  19.     size_t _unassembled_bytes;
  21.     ByteStream _output;  //!< The reassembled in-order byte stream
  22.     size_t _capacity;    //!< The maximum number of bytes
  24.   public:
  25.     //! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes.
  26.     //! \note This capacity limits both the bytes that have been reassembled,
  27.     //! and those that have not yet been reassembled.
  28.     StreamReassembler(const size_t capacity);
  30.     //! \brief Receive a substring and write any newly contiguous bytes into the stream.
  31.     //!
  32.     //! The StreamReassembler will stay within the memory limits of the `capacity`.
  33.     //! Bytes that would exceed the capacity are silently discarded.
  34.     //!
  35.     //! \param data the substring
  36.     //! \param index indicates the index (place in sequence) of the first byte in `data`
  37.     //! \param eof the last byte of `data` will be the last byte in the entire stream
  38.     void push_substring(const std::string &data, const uint64_t index, const bool eof);
  40.     //! \name Access the reassembled byte stream
  41.     //!@{
  42.     const ByteStream &stream_out() const { return _output; }
  43.     ByteStream &stream_out() { return _output; }
  44.     //!@}
  46.     //! The number of bytes in the substrings stored but not yet reassembled
  47.     //!
  48.     //! \note If the byte at a particular index has been pushed more than once, it
  49.     //! should only be counted once for the purpose of this function.
  50.     size_t unassembled_bytes() const;
  52.     //! \brief Is the internal state empty (other than the output stream)?
  53.     //! \returns `true` if no substrings are waiting to be assembled
  54.     bool empty() const;
  55. };
  57. #endif  // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  62. #include "stream_reassembler.hh"
  63. #include <cmath>
  64. #include <vector>
  65. #include <utility>
  66. #include <algorithm>
  67. #include <cstdio>
  68. #include <iostream>
  70. // Dummy implementation of a stream reassembler.
  72. // For Lab 1, please replace with a real implementation that passes the
  73. // automated checks run by `make check_lab1`.
  75. // You will need to add private members to the class declaration in `stream_reassembler.hh`
  77. template <typename... Targs>
  78. void DUMMY_CODE(Targs &&... /* unused */) {}
  80. using namespace std;
  82. StreamReassembler::StreamReassembler(const size_t capacity) 
  83.     : _next_index(0), _eof_index(unsigned(-1)), _unassembled_strings(), _unassembled_bytes(0),
  84.      _output(capacity), _capacity(capacity) {
  86. }
  88. //! \details This function accepts a substring (aka a segment) of bytes,
  89. //! possibly out-of-order, from the logical stream, and assembles any newly
  90. //! contiguous substrings and writes them into the output stream in order.
  91. void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
  92.     if (eof) {
  93.         _eof_index = index+data.size();
  94.     }
  96.     // [index, index+string.size())
  97.     // [_next_index, _next_index+capacity-stream.size())=[_next_index, _next_index+_output.remaining_capacity())
  98.     if (index+data.size()>_next_index&&_next_index+_output.remaining_capacity()>index) {  // 有相交的部分，或者说有可以缓存的数据
  99.         size_t L = std::max(index, _next_index);
  100.         size_t R = std::min(index+data.size(), _next_index+_output.remaining_capacity());
  101.         std::string true_data=data.substr(L-index, R-L);
  103.         size_t x=0,y=0;  // 表示了Map中待删除的区间
  104.         size_t union_l=0, union_r=0;
  105.         bool isOverlap=false;
  106.         auto iter = _unassembled_strings.begin();
  107.         size_t loc=0;
  108.         std::pair<size_t, std::string> first_zone, last_zone;
  109.         // std::vector<std::pair<size_t, std::string>> overlapped_strings;
  110.         while (iter!=_unassembled_strings.end()) {
  111.             // [L, R)和[iter->first, iter->first+iter.second.size())比较
  112.             if (iter->first+iter->second.size()>L&&R>iter->first) {  // 相交
  113.                 if (!isOverlap) {
  114.                     isOverlap = true;
  115.                     x=y=loc;
  116.                     first_zone=make_pair(iter->first, iter->second);
  117.                     union_l=std::min(L, iter->first);
  118.                     union_r=std::max(R, iter->first+iter->second.size());
  119.                 } else {
  120.                     y++;
  121.                     last_zone=make_pair(iter->first, iter->second);
  122.                     union_r=std::max(R, iter->first+iter->second.size());
  123.                 }
  124.             } else {
  125.                 if (isOverlap) {
  126.                     break;
  127.                 }
  128.             }
  129.             loc++;
  130.             iter++;
  131.         }
  133.         std::string union_string;
  134.         if (isOverlap) {
  135.             union_string=std::string(union_r-union_l, 'a');
  136.             union_string.replace(L-union_l, R-L, true_data);
  137.             union_string.replace(first_zone.first-union_l, first_zone.second.size(), first_zone.second);
  138.             if (y>x) {
  139.                 union_string.replace(last_zone.first-union_l, last_zone.second.size(), last_zone.second);
  140.             }
  141.         } else {
  142.             union_l=L;
  143.             union_r=R;
  144.             union_string=true_data;
  145.         }
  147.         if (isOverlap) {
  148.             iter = _unassembled_strings.begin();
  149.             loc=0;
  150.             while (iter!=_unassembled_strings.end()) {
  151.                 if (loc>=x&&loc<=y) {
  152.                     _unassembled_strings.erase(iter++);
  153.                 } else {
  154.                     iter++;
  155.                 }
  156.                 loc++;
  157.             }
  158.         }
  160.         std::cout<<"【"<<union_l<<","<<union_r<<"】"<<"******"<<std::endl;
  162.         _unassembled_strings.insert(map<size_t, std::string>::value_type(union_l, union_string));
  163.     }
  165.     // 接下来比较_next_index和Map中的最小序号
  166.     int toDeleteCount=0;
  167.     auto iter = _unassembled_strings.begin();
  168.     while (iter!=_unassembled_strings.end()) {
  169.         if (iter->first!=_next_index) {
  170.             break;
  171.         }
  172.         toDeleteCount++;
  173.         // 一定可以全部写入吧？？？因为前面计算过了
  174.         _output.write(iter->second);
  176.         // string toAddStr = iter->second;
  177.         // size_t added = 0;
  178.         // while (added<iter->second.size()) {
  179.         //     added+=_output.write(iter->second.substr(added, iter->second.size()-added));
  180.         // }
  182.         _next_index+=iter->second.size();
  184.         // bug1: 这里没有iter++
  185.     }
  187.     iter = _unassembled_strings.begin();
  188.     for (int i=0; i<toDeleteCount; i++) {
  189.         _unassembled_strings.erase(iter++);
  190.     }
  192.     if (_unassembled_strings.size()==0&&_next_index==_eof_index) {
  193.         _output.end_input();
  194.         std::cout<<"****** called _output.end_input(), unassembled_bytes(): "<<unassembled_bytes()<<std::endl;
  195.         // std::cout<<"****** _output.eof(): "<<_output.eof()<<std::endl;
  196.         // std::cout<<"****** empty(): "<<empty()<<std::endl;
  197.         std::cout<<"****** _output.input_ended(): "<<_output.input_ended()<<std::endl;
  198.     }
  200.     std::cout<<"****** new _next_index: "<<_next_index<<std::endl;
  201.     std::cout<<"****** remaining: "<<_output.remaining_capacity()<<std::endl;
  202.     // std::cout<<"****** _output.read(): "<<_output.peek_output(8)<<std::endl;
  203.     // std::cout<<"****** _output"
  204. }
  206. // 返回已经缓存，但未组装到字节流中的字节个数
  207. size_t StreamReassembler::unassembled_bytes() const { 
  208.     size_t res=0;
  209.     // for (size_t i=0; i<_unassembled_strings.size(); i++) {
  210.     //     res+=_unassembled_strings[i].second.size();
  211.     // }
  212.     auto iter = _unassembled_strings.begin();
  213.     while (iter!=_unassembled_strings.end()) {
  214.         res+=iter->second.size();
  215.         // bug2: 这里没有iter++;
  216.     }
  217.     return res;
  218. }
  220. // unassembled_bytes()==0
  221. bool StreamReassembler::empty() const { 
  222.     return unassembled_bytes()==0; 
  223. }

测试结果

image.png
到这里git commit一下

两个bug都是没有写iter++

如果在第一阶段的代码中添加上述两处iter++，测试结果如下
image.png
其中1个样例如下
image.png
很显然是遗漏了1个字节

第三阶段（通过测试）

就是第二阶段的代码，加上两处iter++

  1. #ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  2. #define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  4. #include "byte_stream.hh"
  6. #include <cstdint>
  7. #include <string>
  8. #include <map>
  9. #include <utility>
  11. //! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order,
  12. //! possibly overlapping) into an in-order byte stream.
  13. class StreamReassembler {
  14.   private:
  15.     // Your code here -- add private members as necessary.
  16.     size_t _next_index;
  17.     size_t _eof_index;
  18.     std::map<size_t, std::string> _unassembled_strings;
  19.     size_t _unassembled_bytes;
  21.     ByteStream _output;  //!< The reassembled in-order byte stream
  22.     size_t _capacity;    //!< The maximum number of bytes
  24.   public:
  25.     //! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes.
  26.     //! \note This capacity limits both the bytes that have been reassembled,
  27.     //! and those that have not yet been reassembled.
  28.     StreamReassembler(const size_t capacity);
  30.     //! \brief Receive a substring and write any newly contiguous bytes into the stream.
  31.     //!
  32.     //! The StreamReassembler will stay within the memory limits of the `capacity`.
  33.     //! Bytes that would exceed the capacity are silently discarded.
  34.     //!
  35.     //! \param data the substring
  36.     //! \param index indicates the index (place in sequence) of the first byte in `data`
  37.     //! \param eof the last byte of `data` will be the last byte in the entire stream
  38.     void push_substring(const std::string &data, const uint64_t index, const bool eof);
  40.     //! \name Access the reassembled byte stream
  41.     //!@{
  42.     const ByteStream &stream_out() const { return _output; }
  43.     ByteStream &stream_out() { return _output; }
  44.     //!@}
  46.     //! The number of bytes in the substrings stored but not yet reassembled
  47.     //!
  48.     //! \note If the byte at a particular index has been pushed more than once, it
  49.     //! should only be counted once for the purpose of this function.
  50.     size_t unassembled_bytes() const;
  52.     //! \brief Is the internal state empty (other than the output stream)?
  53.     //! \returns `true` if no substrings are waiting to be assembled
  54.     bool empty() const;
  55. };
  57. #endif  // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  63. #include "stream_reassembler.hh"
  64. #include <cmath>
  65. #include <vector>
  66. #include <utility>
  67. #include <algorithm>
  68. #include <cstdio>
  69. #include <iostream>
  71. // Dummy implementation of a stream reassembler.
  73. // For Lab 1, please replace with a real implementation that passes the
  74. // automated checks run by `make check_lab1`.
  76. // You will need to add private members to the class declaration in `stream_reassembler.hh`
  78. template <typename... Targs>
  79. void DUMMY_CODE(Targs &&... /* unused */) {}
  81. using namespace std;
  83. StreamReassembler::StreamReassembler(const size_t capacity) 
  84.     : _next_index(0), _eof_index(unsigned(-1)), _unassembled_strings(), _unassembled_bytes(0),
  85.      _output(capacity), _capacity(capacity) {
  87. }
  89. //! \details This function accepts a substring (aka a segment) of bytes,
  90. //! possibly out-of-order, from the logical stream, and assembles any newly
  91. //! contiguous substrings and writes them into the output stream in order.
  92. void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
  93.     if (eof) {
  94.         _eof_index = index+data.size();
  95.     }
  97.     // [index, index+string.size())
  98.     // [_next_index, _next_index+capacity-stream.size())=[_next_index, _next_index+_output.remaining_capacity())
  99.     if (index+data.size()>_next_index&&_next_index+_output.remaining_capacity()>index) {  // 有相交的部分，或者说有可以缓存的数据
  100.         size_t L = std::max(index, _next_index);
  101.         size_t R = std::min(index+data.size(), _next_index+_output.remaining_capacity());
  102.         std::string true_data=data.substr(L-index, R-L);
  104.         size_t x=0,y=0;  // 表示了Map中待删除的区间
  105.         size_t union_l=0, union_r=0;
  106.         bool isOverlap=false;
  107.         auto iter = _unassembled_strings.begin();
  108.         size_t loc=0;
  109.         std::pair<size_t, std::string> first_zone, last_zone;
  110.         // std::vector<std::pair<size_t, std::string>> overlapped_strings;
  111.         while (iter!=_unassembled_strings.end()) {
  112.             // [L, R)和[iter->first, iter->first+iter.second.size())比较
  113.             if (iter->first+iter->second.size()>L&&R>iter->first) {  // 相交
  114.                 if (!isOverlap) {
  115.                     isOverlap = true;
  116.                     x=y=loc;
  117.                     first_zone=make_pair(iter->first, iter->second);
  118.                     union_l=std::min(L, iter->first);
  119.                     union_r=std::max(R, iter->first+iter->second.size());
  120.                 } else {
  121.                     y++;
  122.                     last_zone=make_pair(iter->first, iter->second);
  123.                     union_r=std::max(R, iter->first+iter->second.size());
  124.                 }
  125.             } else {
  126.                 if (isOverlap) {
  127.                     break;
  128.                 }
  129.             }
  130.             loc++;
  131.             iter++;
  132.         }
  134.         std::string union_string;
  135.         if (isOverlap) {
  136.             union_string=std::string(union_r-union_l, 'a');
  137.             union_string.replace(L-union_l, R-L, true_data);
  138.             union_string.replace(first_zone.first-union_l, first_zone.second.size(), first_zone.second);
  139.             if (y>x) {
  140.                 union_string.replace(last_zone.first-union_l, last_zone.second.size(), last_zone.second);
  141.             }
  142.         } else {
  143.             union_l=L;
  144.             union_r=R;
  145.             union_string=true_data;
  146.         }
  148.         if (isOverlap) {
  149.             iter = _unassembled_strings.begin();
  150.             loc=0;
  151.             while (iter!=_unassembled_strings.end()) {
  152.                 if (loc>=x&&loc<=y) {
  153.                     _unassembled_strings.erase(iter++);
  154.                 } else {
  155.                     iter++;
  156.                 }
  157.                 loc++;
  158.             }
  159.         }
  161.         std::cout<<"【"<<union_l<<","<<union_r<<"】"<<"******"<<std::endl;
  163.         _unassembled_strings.insert(map<size_t, std::string>::value_type(union_l, union_string));
  164.     }
  166.     // 接下来比较_next_index和Map中的最小序号
  167.     int toDeleteCount=0;
  168.     auto iter = _unassembled_strings.begin();
  169.     while (iter!=_unassembled_strings.end()) {
  170.         if (iter->first!=_next_index) {
  171.             break;
  172.         }
  173.         toDeleteCount++;
  174.         // 一定可以全部写入吧？？？因为前面计算过了
  175.         _output.write(iter->second);
  177.         // string toAddStr = iter->second;
  178.         // size_t added = 0;
  179.         // while (added<iter->second.size()) {
  180.         //     added+=_output.write(iter->second.substr(added, iter->second.size()-added));
  181.         // }
  183.         _next_index+=iter->second.size();
  184.         iter++;
  185.     }
  187.     iter = _unassembled_strings.begin();
  188.     for (int i=0; i<toDeleteCount; i++) {
  189.         _unassembled_strings.erase(iter++);
  190.     }
  192.     if (_unassembled_strings.size()==0&&_next_index==_eof_index) {
  193.         _output.end_input();
  194.         std::cout<<"****** called _output.end_input(), unassembled_bytes(): "<<unassembled_bytes()<<std::endl;
  195.         // std::cout<<"****** _output.eof(): "<<_output.eof()<<std::endl;
  196.         // std::cout<<"****** empty(): "<<empty()<<std::endl;
  197.         std::cout<<"****** _output.input_ended(): "<<_output.input_ended()<<std::endl;
  198.     }
  200.     std::cout<<"****** new _next_index: "<<_next_index<<std::endl;
  201.     std::cout<<"****** remaining: "<<_output.remaining_capacity()<<std::endl;
  202.     // std::cout<<"****** _output.read(): "<<_output.peek_output(8)<<std::endl;
  203.     // std::cout<<"****** _output"
  204. }
  206. // 返回已经缓存，但未组装到字节流中的字节个数
  207. size_t StreamReassembler::unassembled_bytes() const { 
  208.     size_t res=0;
  209.     // for (size_t i=0; i<_unassembled_strings.size(); i++) {
  210.     //     res+=_unassembled_strings[i].second.size();
  211.     // }
  212.     auto iter = _unassembled_strings.begin();
  213.     while (iter!=_unassembled_strings.end()) {
  214.         res+=iter->second.size();
  215.         iter++;
  216.     }
  217.     return res;
  218. }
  220. // unassembled_bytes()==0
  221. bool StreamReassembler::empty() const { 
  222.     return unassembled_bytes()==0; 
  223. }

image.png

第四阶段

  • 在刚开始写Lab2时，发现TCPReceiver需要用到我在StreamReassembler中设置的私有变量_next_index
  • 但是实验文档强调了不能修改公有接口，所以我开始思考StreamReassembler中是否有必要设置_next_index这个私有成员变量
  • 实际上，ByteStream有一个接口是size_t bytes_written() const;
    • 这个接口返回了流中写入了多少数据，实际上就是流的下一个字节序号
    • 也就是我一开始设置的_next_index

  • 所以我打算去掉_next_index，为了使改动最小化，我将类成员_next_index改为next_index，即去掉了前面的下划线

    • 类的方法中没有一处用到了next_index
    • 在StreamReassembler::push_substring的开头，定义局部变量_next_index，取值为_output.bytes_written()

  • 潜在的问题：在StreamReassembler::push_substring的最后，我假设_output.write一定会成功，且一定能够把所有字节加进去 ```cpp

    ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH

    define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH

include “byte_stream.hh”

include

include

include

include

//! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order, //! possibly overlapping) into an in-order byte stream. class StreamReassembler { private: // Your code here — add private members as necessary. size_t next_index; size_t _eof_index; std::map _unassembled_strings; size_t _unassembled_bytes;

  1. ByteStream _output;  //!< The reassembled in-order byte stream
  2. size_t _capacity;    //!< The maximum number of bytes

public: //! \brief Construct a StreamReassembler that will store up to capacity bytes. //! \note This capacity limits both the bytes that have been reassembled, //! and those that have not yet been reassembled. StreamReassembler(const size_t capacity);

  1. //! \brief Receive a substring and write any newly contiguous bytes into the stream.
  2. //!
  3. //! The StreamReassembler will stay within the memory limits of the `capacity`.
  4. //! Bytes that would exceed the capacity are silently discarded.
  5. //!
  6. //! \param data the substring
  7. //! \param index indicates the index (place in sequence) of the first byte in `data`
  8. //! \param eof the last byte of `data` will be the last byte in the entire stream
  9. void push_substring(const std::string &data, const uint64_t index, const bool eof);
  11. //! \name Access the reassembled byte stream
  12. //!@{
  13. const ByteStream &stream_out() const { return _output; }
  14. ByteStream &stream_out() { return _output; }
  15. //!@}
  17. //! The number of bytes in the substrings stored but not yet reassembled
  18. //!
  19. //! \note If the byte at a particular index has been pushed more than once, it
  20. //! should only be counted once for the purpose of this function.
  21. size_t unassembled_bytes() const;
  23. //! \brief Is the internal state empty (other than the output stream)?
  24. //! \returns `true` if no substrings are waiting to be assembled
  25. bool empty() const;

};

endif // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH

include “stream_reassembler.hh”

include

include

include

include

include

include

// Dummy implementation of a stream reassembler.

// For Lab 1, please replace with a real implementation that passes the // automated checks run by make check_lab1.

// You will need to add private members to the class declaration in stream_reassembler.hh

template void DUMMY_CODE(Targs &&… / unused /) {}

using namespace std;

StreamReassembler::StreamReassembler(const size_t capacity) : next_index(0), _eof_index(unsigned(-1)), _unassembled_strings(), _unassembled_bytes(0), _output(capacity), _capacity(capacity) {

}

//! \details This function accepts a substring (aka a segment) of bytes, //! possibly out-of-order, from the logical stream, and assembles any newly //! contiguous substrings and writes them into the output stream in order. void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) { if (eof) { _eof_index = index+data.size(); }

  1. size_t _next_index=_output.bytes_written();
  2. // [index, index+string.size())
  3. // [_next_index, _next_index+capacity-stream.size())=[_next_index, _next_index+_output.remaining_capacity())
  4. if (index+data.size()>_next_index&&_next_index+_output.remaining_capacity()>index) {  // 有相交的部分，或者说有可以缓存的数据
  5.     size_t L = std::max(index, _next_index);
  6.     size_t R = std::min(index+data.size(), _next_index+_output.remaining_capacity());
  7.     std::string true_data=data.substr(L-index, R-L);
  9.     size_t x=0,y=0;  // 表示了Map中待删除的区间
  10.     size_t union_l=0, union_r=0;
  11.     bool isOverlap=false;
  12.     auto iter = _unassembled_strings.begin();
  13.     size_t loc=0;
  14.     std::pair<size_t, std::string> first_zone, last_zone;
  15.     // std::vector<std::pair<size_t, std::string>> overlapped_strings;
  16.     while (iter!=_unassembled_strings.end()) {
  17.         // [L, R)和[iter->first, iter->first+iter.second.size())比较
  18.         if (iter->first+iter->second.size()>L&&R>iter->first) {  // 相交
  19.             if (!isOverlap) {
  20.                 isOverlap = true;
  21.                 x=y=loc;
  22.                 first_zone=make_pair(iter->first, iter->second);
  23.                 union_l=std::min(L, iter->first);
  24.                 union_r=std::max(R, iter->first+iter->second.size());
  25.             } else {
  26.                 y++;
  27.                 last_zone=make_pair(iter->first, iter->second);
  28.                 union_r=std::max(R, iter->first+iter->second.size());
  29.             }
  30.         } else {
  31.             if (isOverlap) {
  32.                 break;
  33.             }
  34.         }
  35.         loc++;
  36.         iter++;
  37.     }
  39.     std::string union_string;
  40.     if (isOverlap) {
  41.         union_string=std::string(union_r-union_l, 'a');
  42.         union_string.replace(L-union_l, R-L, true_data);
  43.         union_string.replace(first_zone.first-union_l, first_zone.second.size(), first_zone.second);
  44.         if (y>x) {
  45.             union_string.replace(last_zone.first-union_l, last_zone.second.size(), last_zone.second);
  46.         }
  47.     } else {
  48.         union_l=L;
  49.         union_r=R;
  50.         union_string=true_data;
  51.     }
  53.     if (isOverlap) {
  54.         iter = _unassembled_strings.begin();
  55.         loc=0;
  56.         while (iter!=_unassembled_strings.end()) {
  57.             if (loc>=x&&loc<=y) {
  58.                 _unassembled_strings.erase(iter++);
  59.             } else {
  60.                 iter++;
  61.             }
  62.             loc++;
  63.         }
  64.     }
  66.     // std::cout<<"【"<<union_l<<","<<union_r<<"】"<<"******"<<std::endl;
  68.     _unassembled_strings.insert(map<size_t, std::string>::value_type(union_l, union_string));
  69. }
  71. // 接下来比较_next_index和Map中的最小序号
  72. int toDeleteCount=0;
  73. auto iter = _unassembled_strings.begin();
  74. while (iter!=_unassembled_strings.end()) {
  75.     if (iter->first!=_next_index) {
  76.         break;
  77.     }
  78.     toDeleteCount++;
  79.     // 一定可以全部写入吧？？？因为前面计算过了
  80.     _output.write(iter->second);
  82.     // string toAddStr = iter->second;
  83.     // size_t added = 0;
  84.     // while (added<iter->second.size()) {
  85.     //     added+=_output.write(iter->second.substr(added, iter->second.size()-added));
  86.     // }
  88.     _next_index+=iter->second.size();
  89.     iter++;
  90. }
  92. iter = _unassembled_strings.begin();
  93. for (int i=0; i<toDeleteCount; i++) {
  94.     _unassembled_strings.erase(iter++);
  95. }
  97. if (_unassembled_strings.size()==0&&_next_index==_eof_index) {
  98.     _output.end_input();
  99.     // std::cout<<"****** called _output.end_input(), unassembled_bytes(): "<<unassembled_bytes()<<std::endl;
  100.     // std::cout<<"****** _output.eof(): "<<_output.eof()<<std::endl;
  101.     // std::cout<<"****** empty(): "<<empty()<<std::endl;
  102.     // std::cout<<"****** _output.input_ended(): "<<_output.input_ended()<<std::endl;
  103. }
  105. // std::cout<<"****** new _next_index: "<<_next_index<<std::endl;
  106. // std::cout<<"****** remaining: "<<_output.remaining_capacity()<<std::endl;
  107. // std::cout<<"****** _output.read(): "<<_output.peek_output(8)<<std::endl;
  108. // std::cout<<"****** _output"

}

// 返回已经缓存，但未组装到字节流中的字节个数 size_t StreamReassembler::unassembled_bytes() const { size_t res=0; // for (size_t i=0; i<_unassembled_strings.size(); i++) { // res+=_unassembled_strings[i].second.size(); // } auto iter = _unassembled_strings.begin(); while (iter!=_unassembled_strings.end()) { res+=iter->second.size(); iter++; } return res; }

// unassembled_bytes()==0 bool StreamReassembler::empty() const { return unassembled_bytes()==0; }

  1. <a name="ydbF6"></a>
  2. # 第五阶段
  4. - 引入Lab4的代码后，新增了测试，Lab1又有样例没过，经过DEBUG，发现是我对空串的处理没有做好。
  5. - 如果push_strings传入的是一个空串，我可能会把空串放入**_unassembled_strings**这个Map中，然后就一直留在Map中了。
  6. - 需要修改的地方有两处，一个是判断data.size()>0，才进行把它加入**_unassembled_strings**的操作。
  7.    - 由于可能传入一个带着eof标志的空串，所以当前这次操作可能只是更新eof
  8.    - 更新了eof，可能整个流的组装就结束了，所以最后的代码逻辑也需要运行
  10. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/3018011/1614809806850-de75ef8b-5108-4b1f-931d-59f0ba1c274a.png#align=left&display=inline&height=467&margin=%5Bobject%20Object%5D&name=image.png&originHeight=467&originWidth=1196&size=113545&status=done&style=none&width=1196)
  12. - 修改了最后调用_output.end_input()的判断条件
  13.    - 之前是`_unassembled_strings.size()==0`，这个条件不精确
  14.    - 应该改成`unassembled_bytes()==0`
  16. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/3018011/1614809890272-7fd566b1-0a6e-42d5-986b-2a1cde6ba3f9.png#align=left&display=inline&height=311&margin=%5Bobject%20Object%5D&name=image.png&originHeight=311&originWidth=1162&size=77863&status=done&style=none&width=1162)
  18. 下面是修改后的代码
  19. ```cpp
  20. #ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  21. #define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  23. #include "byte_stream.hh"
  25. #include <cstdint>
  26. #include <string>
  27. #include <map>
  28. #include <utility>
  30. //! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order,
  31. //! possibly overlapping) into an in-order byte stream.
  32. class StreamReassembler {
  33.   private:
  34.     // Your code here -- add private members as necessary.
  35.     size_t next_index;
  36.     size_t _eof_index;
  37.     std::map<size_t, std::string> _unassembled_strings;
  38.     size_t _unassembled_bytes;
  40.     ByteStream _output;  //!< The reassembled in-order byte stream
  41.     size_t _capacity;    //!< The maximum number of bytes
  43.   public:
  44.     //! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes.
  45.     //! \note This capacity limits both the bytes that have been reassembled,
  46.     //! and those that have not yet been reassembled.
  47.     StreamReassembler(const size_t capacity);
  49.     //! \brief Receive a substring and write any newly contiguous bytes into the stream.
  50.     //!
  51.     //! The StreamReassembler will stay within the memory limits of the `capacity`.
  52.     //! Bytes that would exceed the capacity are silently discarded.
  53.     //!
  54.     //! \param data the substring
  55.     //! \param index indicates the index (place in sequence) of the first byte in `data`
  56.     //! \param eof the last byte of `data` will be the last byte in the entire stream
  57.     void push_substring(const std::string &data, const uint64_t index, const bool eof);
  59.     //! \name Access the reassembled byte stream
  60.     //!@{
  61.     const ByteStream &stream_out() const { return _output; }
  62.     ByteStream &stream_out() { return _output; }
  63.     //!@}
  65.     //! The number of bytes in the substrings stored but not yet reassembled
  66.     //!
  67.     //! \note If the byte at a particular index has been pushed more than once, it
  68.     //! should only be counted once for the purpose of this function.
  69.     size_t unassembled_bytes() const;
  71.     //! \brief Is the internal state empty (other than the output stream)?
  72.     //! \returns `true` if no substrings are waiting to be assembled
  73.     bool empty() const;
  74. };
  76. #endif  // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
  80. #include "stream_reassembler.hh"
  81. #include <cmath>
  82. #include <vector>
  83. #include <utility>
  84. #include <algorithm>
  85. #include <cstdio>
  86. #include <iostream>
  88. // Dummy implementation of a stream reassembler.
  90. // For Lab 1, please replace with a real implementation that passes the
  91. // automated checks run by `make check_lab1`.
  93. // You will need to add private members to the class declaration in `stream_reassembler.hh`
  95. template <typename... Targs>
  96. void DUMMY_CODE(Targs &&... /* unused */) {}
  98. using namespace std;
  100. StreamReassembler::StreamReassembler(const size_t capacity) 
  101.     : next_index(0), _eof_index(unsigned(-1)), _unassembled_strings(), _unassembled_bytes(0),
  102.      _output(capacity), _capacity(capacity) {
  103.     std::cout<<"****** StreamReassembler created"<<std::endl;
  104. }
  106. //! \details This function accepts a substring (aka a segment) of bytes,
  107. //! possibly out-of-order, from the logical stream, and assembles any newly
  108. //! contiguous substrings and writes them into the output stream in order.
  109. void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
  110.     if (eof) {
  111.         _eof_index = index+data.size();
  112.         std::cout<<"****** get _eof_index: "<<_eof_index<<std::endl;
  113.     }
  114.     std::cout<<"****** try to push string: "<<data;
  116.     size_t _next_index=_output.bytes_written();
  117.     std::cout<<", get _next_index this time: "<<_next_index;
  118.     // [index, index+string.size())
  119.     // [_next_index, _next_index+capacity-stream.size())=[_next_index, _next_index+_output.remaining_capacity())
  120.     // 不能加入空串，加入data.size()>0的判断，因为可能来一个空串，并且更新eof，所以不能直接返回，后面的代码还要运行
  121.     if (data.size()>0&&index+data.size()>_next_index&&_next_index+_output.remaining_capacity()>index) {  // 有相交的部分，或者说有可以缓存的数据
  122.         size_t L = std::max(index, _next_index);
  123.         size_t R = std::min(index+data.size(), _next_index+_output.remaining_capacity());
  124.         std::string true_data=data.substr(L-index, R-L);
  126.         std::cout<<", pushed: "<<true_data;
  128.         size_t x=0,y=0;  // 表示了Map中待删除的区间
  129.         size_t union_l=0, union_r=0;
  130.         bool isOverlap=false;
  131.         auto iter = _unassembled_strings.begin();
  132.         size_t loc=0;
  133.         std::pair<size_t, std::string> first_zone, last_zone;
  134.         // std::vector<std::pair<size_t, std::string>> overlapped_strings;
  135.         while (iter!=_unassembled_strings.end()) {
  136.             // [L, R)和[iter->first, iter->first+iter.second.size())比较
  137.             if (iter->first+iter->second.size()>L&&R>iter->first) {  // 相交
  138.                 if (!isOverlap) {
  139.                     isOverlap = true;
  140.                     x=y=loc;
  141.                     first_zone=make_pair(iter->first, iter->second);
  142.                     union_l=std::min(L, iter->first);
  143.                     union_r=std::max(R, iter->first+iter->second.size());
  144.                 } else {
  145.                     y++;
  146.                     last_zone=make_pair(iter->first, iter->second);
  147.                     union_r=std::max(R, iter->first+iter->second.size());
  148.                 }
  149.             } else {
  150.                 if (isOverlap) {
  151.                     break;
  152.                 }
  153.             }
  154.             loc++;
  155.             iter++;
  156.         }
  158.         std::string union_string;
  159.         if (isOverlap) {
  160.             union_string=std::string(union_r-union_l, 'a');
  161.             union_string.replace(L-union_l, R-L, true_data);
  162.             union_string.replace(first_zone.first-union_l, first_zone.second.size(), first_zone.second);
  163.             if (y>x) {
  164.                 union_string.replace(last_zone.first-union_l, last_zone.second.size(), last_zone.second);
  165.             }
  166.         } else {
  167.             union_l=L;
  168.             union_r=R;
  169.             union_string=true_data;
  170.         }
  172.         if (isOverlap) {
  173.             iter = _unassembled_strings.begin();
  174.             loc=0;
  175.             while (iter!=_unassembled_strings.end()) {
  176.                 if (loc>=x&&loc<=y) {
  177.                     _unassembled_strings.erase(iter++);
  178.                 } else {
  179.                     iter++;
  180.                 }
  181.                 loc++;
  182.             }
  183.         }
  185.         // std::cout<<"【"<<union_l<<","<<union_r<<"】"<<"******"<<std::endl;
  187.         _unassembled_strings.insert(map<size_t, std::string>::value_type(union_l, union_string));
  188.     }
  190.     // 接下来比较_next_index和Map中的最小序号
  191.     int toDeleteCount=0;
  192.     auto iter = _unassembled_strings.begin();
  193.     while (iter!=_unassembled_strings.end()) {
  194.         if (iter->first!=_next_index) {
  195.             break;
  196.         }
  197.         toDeleteCount++;
  198.         // 一定可以全部写入吧？？？因为前面计算过了
  199.         _output.write(iter->second);
  201.         // string toAddStr = iter->second;
  202.         // size_t added = 0;
  203.         // while (added<iter->second.size()) {
  204.         //     added+=_output.write(iter->second.substr(added, iter->second.size()-added));
  205.         // }
  207.         _next_index+=iter->second.size();
  208.         iter++;
  209.     }
  211.     iter = _unassembled_strings.begin();
  212.     for (int i=0; i<toDeleteCount; i++) {
  213.         _unassembled_strings.erase(iter++);
  214.     }
  215.     std::cout<<", buffer size now: "<<_output.buffer_size();
  216.     std::cout<<", _next_index now: "<<_next_index;
  217.     std::cout<<", unassembled_bytes now: "<<unassembled_bytes();
  218.     std::cout<<", _unassembled_strings.size(): "<<_unassembled_strings.size()<<std::endl;
  219.     // if (_unassembled_strings.size()==0&&_next_index==_eof_index) {
  220.     if (unassembled_bytes()==0&&_next_index==_eof_index) {
  221.         _output.end_input();
  222.         std::cout<<"****** called _output.end_input(), unassembled_bytes(): "<<unassembled_bytes();
  223.         std::cout<<" _output.buffer_size(): "<<_output.buffer_size()<<std::endl;
  224.         // std::cout<<"****** _output.eof(): "<<_output.eof()<<std::endl;
  225.         // std::cout<<"****** empty(): "<<empty()<<std::endl;
  226.         // std::cout<<"****** _output.input_ended(): "<<_output.input_ended()<<std::endl;
  227.         // std::cout<<"****** _output.peek_output(8): "<<_output.peek_output(8)<<std::endl;
  228.     }
  230.     // std::cout<<"****** new _next_index: "<<_next_index<<std::endl;
  231.     // std::cout<<"****** remaining: "<<_output.remaining_capacity()<<std::endl;
  232.     // std::cout<<"****** _output.read(): "<<_output.peek_output(8)<<std::endl;
  233.     // std::cout<<"****** _output"
  234. }
  236. // 返回已经缓存，但未组装到字节流中的字节个数
  237. size_t StreamReassembler::unassembled_bytes() const { 
  238.     size_t res=0;
  239.     // for (size_t i=0; i<_unassembled_strings.size(); i++) {
  240.     //     res+=_unassembled_strings[i].second.size();
  241.     // }
  242.     auto iter = _unassembled_strings.begin();
  243.     while (iter!=_unassembled_strings.end()) {
  244.         res+=iter->second.size();
  245.         iter++;
  246.     }
  247.     return res;
  248. }
  250. // unassembled_bytes()==0
  251. bool StreamReassembler::empty() const { 
  252.     return unassembled_bytes()==0; 
  253. }