Conversión de conjuntos de enteros en rangos

Question

¿Cuál es la forma más idiomática de convertir un conjunto de enteros en un conjunto de rangos?

E.g. dado el conjunto {0, 1, 2, 3, 4, 7, 8, 9, 11}, quiero obtener {{0,4}, {7,9}, {11,11}}.

Digamos que estamos convirtiendo de std::set<int> en std::vector<std::pair<int, int>>. Trato los rangos como inclusivos en ambos lados, ya que es más conveniente en mi caso, pero también puedo trabajar con rangos abiertos si es necesario.

He escrito la siguiente función, pero tengo ganas de reinventar la rueda. Por favor, díganos que hay algo en STL o impulso para esto.

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); 
} 

Answer 1

No creo que haya nada en el STL o Boost que lo haga.

Una cosa que puede hacer es hacer que su algoritmo de un poco más general:

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; 
} 

Uso:

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)); 

También debe considerar el uso del término interval en lugar de range, debido a que la el último en el lenguaje STL significa "cualquier secuencia de objetos a los que se puede acceder a través de iteradores o punteros" (source).

Finalmente, probablemente debería echarle un vistazo al Boost Interval Arithmetic Library, que se encuentra actualmente en revisión para la inclusión de Boost.

Answer 2

No hay solución retráctil, me temo, pero un algoritmo alternativo.

Almacene sus artículos en un bitvector - O (n) si conoce el artículo máximo al inicio y preasigne el vector.

Traducir ese vector en un vector de indicadores de punto de transición - exclusivo - o el bitvector con una versión de desplazamiento de bits de sí mismo. Ligeramente complicado en los límites de las palabras, pero aún así O (n). Lógicamente, obtienes una nueva clave en el antiguo máximo + 1 (la transición vuelve a ceros después de que todas tus claves se hayan agotado), así que es una buena idea permitir eso en la asignación previa del vector.

Luego, itere a través del bitvector encontrando los bits establecidos. El primer bit configurado indica el inicio de un rango, el segundo el final, el tercero el inicio del siguiente rango y así sucesivamente. La siguiente función de bit-tocar el violín (suponiendo 32 int bit) puede ser útil ...

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; 
} 

Answer 3

que haría uso de adjacent_find con un predicado que define la "adyacencia" como dos elementos que no son secuenciales. Esta solución no depende de INT_MAX. Todavía se siente un poco torpe.

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)); 
} 

Eso prueba contra end más de lo necesario. adjacent_find nunca puede devolver el último elemento de una lista, por lo que el iterador incrementado nunca será end y, por lo tanto, todavía se puede desreferenciar. Podría ser reescrita como:

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)); 
} 

Answer 4

Ahora uno puede usar interval_set de 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; 
} 

de salida:

intervals joined: {[0,4][7,9][11,11]}