Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Dec 22nd, 2012  |  syntax: None  |  size: 2.07 KB  |  views: 16  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <vector>
  3. #include <memory>
  4. #include <algorithm>
  5.  
  6. using std::vector;
  7. using std::pair;
  8. using std::make_pair;
  9.  
  10. typedef pair<int, int> interval;    
  11.  
  12. struct interval_container
  13. {
  14.     void add(int start, int len)
  15.     {
  16.         _data.emplace_back( make_pair(start, len) );
  17.     }
  18.  
  19.     void consolidate()
  20.     {
  21.         // sort intervals first by start then by length
  22.         std::sort(_data.begin(), _data.end());
  23.  
  24.         // create temp data
  25.         vector<interval> consolidated;
  26.  
  27.         // iterate over all sorted intervals
  28.         for(const interval& i : _data)
  29.         {
  30.             int start = i.first;
  31.             int len = i.second;
  32.  
  33.             // special case: first interval
  34.             if (consolidated.empty())
  35.             {
  36.                 consolidated.emplace_back(i);
  37.             }
  38.             // all other cases
  39.             else
  40.             {
  41.                 // get last interval in the consolidated array
  42.                 interval& last = consolidated.back();
  43.                 int& last_start = last.first;
  44.                 int& last_len = last.second;
  45.  
  46.  
  47.                 // if the current interval can be merged with the last one
  48.                 if ((start >= last_start) and (start < (last_start + last_len)))
  49.                 {
  50.                     // merge the interval with the last one
  51.                     last_len = std::max(last_len, (start + len - last_start));
  52.                 }
  53.                 // if the current interval can't be merged with the last one
  54.                 else
  55.                 {
  56.                     consolidated.emplace_back(i);
  57.                 }
  58.             }
  59.         }
  60.  
  61.         // copy consolidated data
  62.         _data = consolidated;
  63.     }
  64.  
  65.  
  66.     vector<interval>& data() { return _data; }
  67.  
  68. private:
  69.     vector<interval> _data;
  70. };
  71.  
  72.  
  73. int main()
  74. {
  75.     interval_container intervals;
  76.  
  77.     intervals.add(0, 2);
  78.     intervals.add(1, 3);
  79.     intervals.add(5, 3);
  80.  
  81.     intervals.consolidate();
  82.  
  83.     int c(0);
  84.     for(interval i : intervals.data())
  85.     {
  86.         std::cout << (c++) << ": from " << i.first << " to " << (i.first + i.second) << std::endl;
  87.     }
  88. }
clone this paste RAW Paste Data