permute.h

/*****************************************************************************
 * VCLib                                                                     *
 * Visual Computing Library                                                  *
 *                                                                           *
 * Copyright(C) 2021-2025                                                    *
 * Visual Computing Lab                                                      *
 * ISTI - Italian National Research Council                                  *
 *                                                                           *
 * All rights reserved.                                                      *
 *                                                                           *
 * This program is free software; you can redistribute it and/or modify      *
 * it under the terms of the Mozilla Public License Version 2.0 as published *
 * by the Mozilla Foundation; either version 2 of the License, or            *
 * (at your option) any later version.                                       *
 *                                                                           *
 * This program is distributed in the hope that it will be useful,           *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the              *
 * Mozilla Public License Version 2.0                                        *
 * (https://www.mozilla.org/en-US/MPL/2.0/) for more details.                *
 ****************************************************************************/
 
#ifndef VCL_BASE_PERMUTE_H
#define VCL_BASE_PERMUTE_H
 
#include <vclib/base/base.h>
 
#include <vector>
 
namespace vcl {
 
template<typename T, typename... Args>
void compactVector(
    std::vector<T, Args...>& vec,
    const std::vector<uint>& newIndices)
{
    assert(vec.size() == newIndices.size());
    uint newSize = 0;
    for (uint i = 0; i < newIndices.size(); ++i) {
        if (newIndices[i] != UINT_NULL) {
            ++newSize;
            if (newIndices[i] != i) {
                // must move the element from position i to position
                // newIndices[i]
                vec[newIndices[i]] = std::move(vec[i]);
            }
        }
    }
    vec.resize(newSize);
}
 
template<typename T, typename... Args>
void permuteInPlace(
    std::vector<T, Args...>& vec,
    const std::vector<uint>& newIndices)
{
    using std::swap;
 
    assert(vec.size() == newIndices.size());
 
    std::vector<bool> visited(vec.size(), false);
 
    for (uint i = 0; i < vec.size(); ++i) {
        if (visited[i] || newIndices[i] == i) {
            continue;
        }
 
        uint current = i;
        T    temp    = std::move(vec[i]);
 
        while (!visited[current]) {
            visited[current] = true;
            int next         = newIndices[current];
            swap(temp, vec[next]);
            current = next;
        }
    }
}
 
} // namespace vcl
 
#endif // VCL_BASE_PERMUTE_H