Russian Qt Forum

Программирование => С/C++ => Тема начата: Igors от Июль 14, 2012, 18:34



Название: Объединить флажки
Отправлено: Igors от Июль 14, 2012, 18:34
Добрый день

Должно быть просто но что-то не выплясывается. Есть такая структура
Код
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.


Название: Re: Объединить флажки
Отправлено: DmitryM от Июль 14, 2012, 20:05
За O(n) при помощи std::for_each устроит?


Название: Re: Объединить флажки
Отправлено: alexis031182 от Июль 15, 2012, 17:54
За O(n) при помощи std::for_each устроит?
А как это будет выглядеть? Я так понял, что в задаче необходимо сравнение каждого флага каждой структуры с соответствующими флагами других структур. Тут по моему без разбиения основного условия на подусловия не обойтись.


Название: Re: Объединить флажки
Отправлено: Igors от Июль 15, 2012, 18:04
Тут по моему без разбиения основного условия на подусловия не обойтись.
Я и разбил, но получается как-то длинно, и совсем не элегантно. Впрочем знатоки std показывают (или не показывают) обычный результат :)


Название: Re: Объединить флажки
Отправлено: alexis031182 от Июль 15, 2012, 19:18
Может быть такое имелось в виду. Псевдокод:
Код
C++ (Qt)
void UnionFlag(Container &c)
{
if(foreach(func_if1, c) && foreach(func_if2, c) && ...) {
...
}
}
То есть по отдельному foreach на каждое подусловие.


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

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


Название: Re: Объединить флажки
Отправлено: Igors от Июль 15, 2012, 19:55
Может быть такое имелось в виду. Псевдокод:
Код
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 (еще один временный контейнер + сортировка). В общем - работает, но длинновато, я недоволен  :'(


Название: Re: Объединить флажки
Отправлено: DmitryM от Июль 15, 2012, 20:09
А как это будет выглядеть? Я так понял, что в задаче необходимо сравнение каждого флага каждой структуры с соответствующими флагами других структур. Тут по моему без разбиения основного условия на подусловия не обойтись.
Когда писал пост, то не было поправки.
Код
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))


Название: Re: Объединить флажки
Отправлено: Igors от Июль 16, 2012, 11:18
Последний вариант не может обсуждаться т.к. не видно кто такой 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))
Если ничего не делилось пополам откуда же логарифм? То наверно "для наукообразности"  :)


Название: Re: Объединить флажки
Отправлено: DmitryM от Июль 19, 2012, 12:50
Но тут уже O(n*log(n))
Если ничего не делилось пополам откуда же логарифм? То наверно "для наукообразности"  :)
std::stable_sort работает за O(n*log(n)).
Во втором случае идея такая: при помощи сортировки группируем элементы так, что бы те которые можно объединить шли друг за другом, а потом идти слева на право, выделяя  интервалы в котором можно вызвать объединение и объединяем.