Объединить флажки

[Igors]

Добрый день

Должно быть просто но что-то не выплясывается. Есть такая структура

Код

C++ (Qt)
struct CData {
 int mFace;
 int * mFlag;
 ...
};
 

Если бы было всего 2 экземпляра CData, то нужное объединение достигается так

Код

C++ (Qt)
void UnionFlag( CData & d0, CData & d1 )
{
 if (d0.mFace == d1.mFace && d0.mFlag && d1.mFlag && (*d0.mFlag & *d1.mFlag) == 0) {
  *d0.mFlag |= *d1.mFlag;
   d1.mFlag = d0.mFlag;
 }
}
 

А как сделать для контейнера содержащего N элементов CData? (N может быть приличным)

Спасибо

Edit: виноват, забыл упомянуть важную деталь. Если один указатель mFlag присваивается другому, то это должно выполняться для всех элементов с таким mFlag. Другими словами - элементы контейнера с одинаковым mFlag  принадлежат одной группе/множеству. Множества могут быть объединены если позволяет маска mFlag. Нужно выполнить объединение всех множеств которые имеют хотя бы 1 общий mFace.

[DmitryM]

За O(n) при помощи std::for_each устроит?

[alexis031182]

За O(n) при помощи std::for_each устроит?

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

[Igors]

Тут по моему без разбиения основного условия на подусловия не обойтись.

Я и разбил, но получается как-то длинно, и совсем не элегантно. Впрочем знатоки std показывают (или не показывают) обычный результат

[alexis031182]

Может быть такое имелось в виду. Псевдокод:

Код

C++ (Qt)
void UnionFlag(Container &c)
{
if(foreach(func_if1, c) && foreach(func_if2, c) && ...) {
 ...
}
}

То есть по отдельному foreach на каждое подусловие.

[trot]

Может быть я ошибаюсь, но я предлагаю следующее
1) с начало объединить абсолютно одинаковые структуры;
2) создать в каждой структуре одного множества вместо указателя mFlag, какую-то переменную, которая была одна для всех элементов этого множества;
3) выполнить объединение по условию (d0.mFace == d1.mFace && d0.mFlag && d1.mFlag && (*d0.mFlag & *d1.mFlag) == 0), при этом новое множество должно иметь одну разделяемую переменную вместо предыдущих двух для каждого множества.

Может в этом направлении подумать.

[Igors]

Может быть такое имелось в виду. Псевдокод:

Код

C++ (Qt)
void UnionFlag(Container &c)
{
if(foreach(func_if1, c) && foreach(func_if2, c) && ...) {
 ...
}
}

То есть по отдельному foreach на каждое подусловие.

Мудрено и непонятно  

Может быть я ошибаюсь, но я предлагаю следующее
1) с начало объединить абсолютно одинаковые структуры;
2) создать в каждой структуре одного множества вместо указателя mFlag, какую-то переменную, которая была одна для всех элементов этого множества;
3) выполнить объединение по условию (d0.mFace == d1.mFace && d0.mFlag && d1.mFlag && (*d0.mFlag & *d1.mFlag) == 0), при этом новое множество должно иметь одну разделяемую переменную вместо предыдущих двух для каждого множества.

Может в этом направлении подумать.

Ну "объединить абсолютно одинаковые" наверное имеется ввиду "создать новую структуру которая будет представлять все одинаковые элементы исходного массива". Я так и сделал

Код

C++ (Qt)
struct CJoinFrag {
 int mBeg, mEnd;  // индексы диапазона элементов в сортированном массиве
 bool mDone;        // флаг "объединено"
 CJoinFrag * mHead, * mNext; // см ниже
}; 
 

Сортирую массив - первый ключ mFace, второй ключ mFlag. Создаю контейнер CJoinFrag, в каждом диапазоне элементы исходного массива с обоими равными mFace и mFlag. Однако на этом дело не кончается - элементы с одним mFlag могут иметь разный mFace. Приходится связать в списки CJoinFrag с одинаковыми mFlag (еще один временный контейнер + сортировка). В общем - работает, но длинновато, я недоволен  

[DmitryM]

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

Когда писал пост, то не было поправки.

Код

C++ (Qt)
#include <algorithm>
 
struct CData
{
 int mFace;
 int * mFlag;
};
 
 
void UnionFlag( CData & d0, CData & d1 )
{
 if (d0.mFace == d1.mFace && d0.mFlag && d1.mFlag && (*d0.mFlag & *d1.mFlag) == 0) {
  *d0.mFlag |= *d1.mFlag;
   d1.mFlag = d0.mFlag;
 }
}
 
using namespace 
{
   class MyFunctor
   {
   public:
   MyFunctor(const CData& bar):m_foo(bar)
   {
   }
 
   void operator() (CData& foo)
   {
        UnionFlag(m_foo, foo);
   }
 
   private:
 
   CData m_foo;
   }
}
    //
    Container c;
    //...
    MyFunctor un = std::for_each(c.begin(), c.end(), MyFunctor(*c.begin()));
    std::for_each(c.begin(), c.end(), un);
 

Если правильно понял поправки, то

Код

C++ (Qt)
    std::stable_sort(c.begin(), c.end(), [](const CData& a, const CData& b){return a.mFlag<b.mFlag;});
    typedef Container::iterator iterator;
 
    iterator cur = c.begin();
    for(iterator a = c.begin(), a!=c.end(), a++)
    {
        if(cur->mFlag != a->mFlag)
        {
            MyFunctor un = std::for_each(first, a, MyFunctor(*first)));
            std::for_each(first, a, un);
            cur = a;
        }
    }
 

Но тут уже O(n*log(n))

[Igors]

Последний вариант не может обсуждаться т.к. не видно кто такой first.

Код

C++ (Qt)
    MyFunctor un = std::for_each(c.begin(), c.end(), MyFunctor(*c.begin()));
    std::for_each(c.begin(), c.end(), un);
 

Не понял самой задумки. Ну пробегаем по всем и объединяем с первым (если можно). А если напр первый ни с кем не может быть объединен, зато могут быть напр 3-й и 5-й? Не вижу как они сольются.  std::for_each вернет тот же функтор, зачем пробегать еще раз? Но и слияние с первым сработает лишь один раз, ведь дальше флаг будет изменен.

Но тут уже O(n*log(n))

Если ничего не делилось пополам откуда же логарифм? То наверно "для наукообразности" 

[DmitryM]

Но тут уже O(n*log(n))

Если ничего не делилось пополам откуда же логарифм? То наверно "для наукообразности" 

std::stable_sort работает за O(n*log(n)).
Во втором случае идея такая: при помощи сортировки группируем элементы так, что бы те которые можно объединить шли друг за другом, а потом идти слева на право, выделяя  интервалы в котором можно вызвать объединение и объединяем.