Russian Qt Forum

C++ (Qt)
bool Linked( const Point & p0, const Point & p1 );
 

C++ (Qt)
Linked(p0, p1) = true;
Linked(p1, p2) = true;
Linked(p0, p2) = false;
 

Haskell
import Data.List as DL
 
-- cohesion принимает функцию группировки (Linked) и список элементов, возвращает список групп элементов
cohesion :: (a -> a -> Bool) ->[a] -> [[a]]
-- тривиальные случаи
cohesion _ [] = []
cohesion _ [x] = [[x]]
cohesion test [x, y]
  | test x y == True = [[x, y]]
  | otherwise = [[x], [y]]
-- общий алгоритм - выделяем очередную группу по первому элементу и остаток, над остатком проделываем то же самое. 
cohesion test (x:xs) = (x:as_x) : cohesion test not_as_x
  where
    (asx, other) = DL.partition (test x) xs
    (as_x, not_as_x) = collect asx other
    collect [] not_as_x' = ([], not_as_x')
    collect asx' [] = (asx', [])
    collect (y:ys) zs = (y:as_y, not_as_y)
      where
        (asy, ozs) = DL.partition (test y) zs
        (as_y, not_as_y) = collect (ys++asy) ozs
 
-- Ну и протестируем на нескольких списках и функциях
main :: IO ()
main = do
  -- всегда False, групп столько же, сколько элементов
  putStrLn $ show $ cohesion (\_ _ -> False) [1..5]
  -- всегда True одна группа со всеми элементами
  putStrLn $ show $ cohesion (\_ _ -> True) [1..5]
  -- выделяем группу элементов <= 3  и группу > 7
  putStrLn $ show $ cohesion (\a b -> (a <= 3 && b <= 3) || (a > 7 && b > 7)) [1..10]
 

$ ghc Cohesion.hs
[1 of 1] Compiling Main             ( Cohesion.hs, Cohesion.o )
Linking Cohesion ...

$ ./Cohesion
[[1],[2],[3],[4],[5]]
[[1,2,3,4,5]]
[[1,2,3],[4],[5],[6],[7],[8,9,10]]

C++ (Qt)
bool CanAdd( const Point & pt, const vector <CPoint> & c )
{
 for (size_t i = 0; i < c.size(); ++i)
  if (Linked(pt, c[i]) return true;
 return false;
} 
 
...
vector <vector<CPoint> > data; // вектор новых контейнеров
 
for (size_t i = 0; i < src.size(); ++i)  { // scr - исходный контейнер
 size_t index;
 const Point & pt = src[i];
 for (index = 0; i < data.size(); ++i)   // ищем контейнер куда можно добавить
  if (CanAdd(pt, data[i])) break;
 
 if (index >= data.size()) {   // не нашли, создаем новый контейнер
  data.push_back(vector <CPoint> ());
  data.back().push_back(pt);
 } 
 
// нашли подходящий
 else {
   vector <CPoint> & dst = data[index];
   dst.push_back(pt);  // добавили в него
 
// теперь все равно надо проверить оставшиеся
  size_t  index2 = index + 1;  
  while (index2 < data.size()) {
   vector <CPoint> & sec = data[index2];
   if (!CanAdd(pt, sec)) ++index2;
   else {  // сливаем
    dst.insert(dst.end(), src.begin(), sec.end());
    data.erase(data.begin() + index2);
   }
  } 
 }
} 
 

Haskell
-- cohesion принимает функцию группировки принимающую 2 элемента и возвращающую Bool (Linked) и список элементов
-- возвращает список групп элементов
cohesion :: (a -> a -> Bool) ->[a] -> [[a]]
 
-- Запись x:xs обозначает список из головы x и хвоста xs. Хвост может быть пустой 
-- Запись test x обозначает что мы зафиксировали первый параметр функции. Теперь при вызове ей нужен только второй параметр.
-- Запись xs++ys для списков, обозначает конкатенацию списков - список ys добавляется в конец списка xs
 
-- для входного списка с головой x и хвостом xs возвращаем список из 
cohesion test (x:xs) = (x:as_x) : cohesion test not_as_x
  where
    -- делим хвост списка на тех, кто "как x" (asx) и остальных (other), вызывая для каждого test с x-ом в первом параметре
    (asx, other) = DL.partition (test x) xs
    -- из остальных выбираем тех которые походят на какой-нибудь элемент из "как x" и остаток
    (as_x, not_as_x) = collect asx other
    -- тривиальные случаи
    collect [] not_as_x' = ([], not_as_x') -- список "как x" пустой - 
    collect asx' [] = (asx', []) -- список остальных пустой
    collect (y:ys) zs = (y:as_y, not_as_y)
      where
        -- делим остальных на таких как голова тестируемого списка и не таких (ozs)
        (asy, ozs) = DL.partition (test y) zs
        -- для остатка списка и вновь прибывших проводим разделение
        (as_y, not_as_y) = collect (ys++asy) ozs