Преобразование наборов целых чисел в диапазоны - PullRequest
Новая
       49

Преобразование наборов целых чисел в диапазоны

6 голосов
/ 21 февраля 2010

Какой самый идиоматический способ преобразовать набор целых чисел в набор диапазонов?

например. учитывая набор {0, 1, 2, 3, 4, 7, 8, 9, 11}, я хочу получить {{0,4}, {7,9}, {11,11}}.

Допустим, мы конвертируем из std::set<int> в std::vector<std::pair<int, int>>. Я рассматриваю диапазоны как включающие с обеих сторон, так как в моем случае это более удобно, но я могу работать и с открытыми диапазонами, если это необходимо.

Я написал следующую функцию, но мне хочется заново изобрести колесо. Пожалуйста, скажите, может быть, есть что-то в STL или повышение для этого. 

typedef std::pair<int, int> Range;

void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges)
{
    Range r = std::make_pair(-INT_MAX, -INT_MAX);

    BOOST_FOREACH(int i, indices)
    {
           if (i != r.second + 1)
           {
            if (r.second >= 0) ranges.push_back(r);
            r.first = i;                    
           }

           r.second = i;
    }

    ranges.push_back(r);
}

Ответы [ 4 ]

4 голосов
/ 17 мая 2012

Теперь можно использовать interval_set из Boost.ICL (Boost> 1.46) 

#include <set>
#include <iostream>
#include <algorithm>

#include <boost/icl/discrete_interval.hpp>
#include <boost/icl/closed_interval.hpp>
#include <boost/icl/interval_set.hpp>

typedef std::set<int> Set;
typedef boost::icl::interval_set<int> IntervalSet;

void setToInterval(const Set& indices, IntervalSet& intervals)
{
    Set::const_iterator pos;
    for(pos = indices.begin(); pos != indices.end(); ++pos)
    {
        intervals.insert(boost::icl::construct<boost::icl::discrete_interval<int> >(*pos, *pos, boost::icl::interval_bounds::closed()));
    }
}

int main()
{
    std::cout << ">>Interval Container Library Rocks! <<\n";
    std::cout << "----------------------------------------------------\n";

    Set indices = {0, 1, 2, 3, 4, 7, 8, 9, 11};
    IntervalSet intervals;

    setToInterval(indices, intervals);

    std::cout << "  intervals joined:    " << intervals  << "\n";

    return 0;
}

Выход: 

  intervals joined:    {[0,4][7,9][11,11]}
3 голосов
/ 21 февраля 2010

Я не думаю, что в STL или Boost есть что-то, что делает это.

Одна вещь, которую вы можете сделать, это сделать ваш алгоритм немного более общим: 

template<class InputIterator, class OutputIterator>
void setToRanges(InputIterator first, InputIterator last, OutputIterator dest)
{
    typedef std::iterator_traits<InputIterator>::value_type item_type;
    typedef typename std::pair<item_type, item_type> pair_type;
    pair_type r(-std::numeric_limits<item_type>::max(), 
                -std::numeric_limits<item_type>::max());

    for(; first != last; ++first)
    {
        item_type i = *first;
        if (i != r.second + 1)
        {
            if (r.second >= 0) 
                *dest = r;
            r.first = i;                    
        }
        r.second = i;
    }
    *dest = r;
}

Использование: 

std::set<int> set;
// insert items

typedef std::pair<int, int> Range;
std::vector<Range> ranges;

setToRanges(set.begin(), set.end(), std::back_inserter(ranges));

Вам также следует рассмотреть возможность использования термина interval вместо range, поскольку последний на языке STL означает «любая последовательность объектов, к которой можно получить доступ через итераторы или указатели» ( source ).

Наконец, вам, вероятно, стоит взглянуть на Арифметическую библиотеку интервала ускорения , которая в настоящее время находится на рассмотрении для включения ускорения.

1 голос
/ 22 февраля 2010

Я бы использовал adjacent_find с предикатом, который определяет «смежность» как два непоследовательных элемента. Это решение не зависит от INT_MAX. Все еще чувствует себя неуклюже. 

bool notSequential(int a, int b) { return (a + 1) != b; }

void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges)
{
  std::set<int>::iterator iter = indices.begin();
  std::set<int>::iterator end = indices.end();
  int first;
  while (iter != end)
  {
    first = *iter;
    iter = std::adjacent_find(iter, end, notSequential);
    if (iter != end)
    {
      ranges.push_back(std::make_pair(first, *iter));
      ++iter;
    }
  }
  ranges.push_back(std::make_pair(first, *--iter));
}

Это тестирует против end больше, чем необходимо. adjacent_find никогда не сможет вернуть последний элемент списка, поэтому увеличенный итератор никогда не будет равен end и, таким образом, все еще может быть разыменован. Это может быть переписано как: 

void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges)
{
  std::set<int>::iterator iter = indices.begin();
  std::set<int>::iterator end = indices.end();
  if (iter == end) return; // empty set has no ranges
  int first;
  while (true)
  {
    first = *iter;
    iter = std::adjacent_find(iter, end, notSequential);
    if (iter == end) break;
    ranges.push_back(std::make_pair(first, *iter++));
  }
  ranges.push_back(std::make_pair(first, *--iter));
}
1 голос
/ 21 февраля 2010

Боюсь, нет сжатого решения, но альтернативный алгоритм.

Сохраняйте свои элементы в битовом векторе - O (n), если вы знаете максимальный элемент в начале и предварительно выделяете вектор.

Преобразуйте этот вектор в вектор флагов точек перехода - эксклюзивный - или битовый вектор с версией в битовом формате. Слегка неряшливо на границах слова, но все же O (n). По логике вы получаете новый ключ со старым максимумом + 1 (переход к нулям после того, как все ваши ключи исчерпаны), поэтому рекомендуется предусмотреть это в предварительном распределении вектора.

Затем выполните итерацию по битовому вектору, чтобы найти установленные биты. Первый установленный бит указывает начало диапазона, второй конец, третий - начало следующего диапазона и так далее. Следующая функция битового воспроизведения (при условии 32-битного int) может быть полезной ... 

int Low_Bit_No (unsigned int p)
{
  if (p == 0)  return -1;  //  No bits set

  int           l_Result = 31;
  unsigned int  l_Range  = 0xffffffff;
  unsigned int  l_Mask   = 0x0000ffff;

  if (p & l_Mask)  {  l_Result -= 16;  }  else  {  l_Mask ^= l_Range;  }
  l_Range &= l_Mask;
  l_Mask  &= 0x00ff00ff;
  if (p & l_Mask)  {  l_Result -=  8;  }  else  {  l_Mask ^= l_Range;  }
  l_Range &= l_Mask;
  l_Mask  &= 0x0f0f0f0f;
  if (p & l_Mask)  {  l_Result -=  4;  }  else  {  l_Mask ^= l_Range;  }
  l_Range &= l_Mask;
  l_Mask  &= 0x33333333;
  if (p & l_Mask)  {  l_Result -=  2;  }  else  {  l_Mask ^= l_Range;  }
  l_Mask  &= 0x55555555;
  if (p & l_Mask)  {  l_Result -=  1;  }

  return l_Result;
}
...