permutation.h

Go to the documentation of this file.

/*
 *  Copyright (c) 2000-2022 Inria
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice,
 *  this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright notice,
 *  this list of conditions and the following disclaimer in the documentation
 *  and/or other materials provided with the distribution.
 *  * Neither the name of the ALICE Project-Team nor the names of its
 *  contributors may be used to endorse or promote products derived from this
 *  software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 *  Contact: Bruno Levy
 *
 *     https://www.inria.fr/fr/bruno-levy
 *
 *     Inria,
 *     Domaine de Voluceau,
 *     78150 Le Chesnay - Rocquencourt
 *     FRANCE
 *
 */
 
#ifndef GEOGRAM_BASIC_PERMUTATION
#define GEOGRAM_BASIC_PERMUTATION
 
#include <geogram/basic/common.h>
#include <geogram/basic/numeric.h>
#include <geogram/basic/memory.h>
 
namespace GEO {
 
    namespace Permutation {
 
        constexpr index_t MARKED_BIT = index_t(1) << (sizeof(index_t)*8 - 1);
 
        constexpr index_t MAX_SIZE = MARKED_BIT;
 
        inline bool is_valid(const vector<index_t>& permutation) {
            std::vector<bool> visited(permutation.size(), false);
            for(index_t i = 0; i < permutation.size(); i++) {
                if(permutation[i] >= permutation.size()) {
                    return false;
                }
                if(visited[permutation[i]]) {
                    return false;
                }
                visited[permutation[i]] = true;
            }
            return true;
        }
 
        inline void mark(vector<index_t>& permutation, index_t i) {
            geo_debug_assert(i < permutation.size());
            permutation[i] |= MARKED_BIT;
        }
 
        inline bool is_marked(const vector<index_t>& permutation, index_t i) {
            geo_debug_assert(i < permutation.size());
            return ((permutation[i] & MARKED_BIT) != 0);
        }
 
        inline void unmark(vector<index_t>& permutation, index_t i) {
            geo_debug_assert(is_marked(permutation, i));
            permutation[i] &= ~MARKED_BIT;
        }
 
        inline void apply(
            void* data, const vector<index_t>& permutation_in,
            size_t elemsize
        ) {
            geo_debug_assert(permutation_in.size() <= MAX_SIZE);
            Memory::pointer pdata = (Memory::pointer) (data);
            vector<index_t>& permutation =
                const_cast<vector<index_t>&>(permutation_in);
            geo_debug_assert(is_valid(permutation));
            Memory::byte* temp = static_cast<Memory::byte*>(alloca(elemsize));
            for(index_t k = 0; k < permutation.size(); k++) {
                if(is_marked(permutation, k)) {
                    continue;
                }
                index_t i = k;
                index_t j = permutation[k];
                Memory::copy(temp, pdata + i * elemsize, elemsize);
                mark(permutation, k);
                while(j != k) {
                    Memory::copy(
                        pdata + i * elemsize, pdata + j * elemsize, elemsize
                    );
                    index_t nj = permutation[j];
                    mark(permutation, j);
                    i = j;
                    j = nj;
                }
                Memory::copy(pdata + i * elemsize, temp, elemsize);
            }
            for(index_t k = 0; k < permutation.size(); k++) {
                unmark(permutation, k);
            }
        }
 
        template <class T>
        inline void apply(
            vector<T>& data, const vector<index_t>& permutation_in
        ) {
            geo_debug_assert(permutation_in.size() <= MAX_SIZE);
            vector<index_t>& permutation =
                const_cast<vector<index_t>&>(permutation_in);
            geo_debug_assert(is_valid(permutation));
            T temp;
            for(index_t k = 0; k < permutation.size(); k++) {
                if(is_marked(permutation, k)) {
                    continue;
                }
                index_t i = k;
                temp = data[i];
                index_t j = permutation[k];
                mark(permutation, k);
                while(j != k) {
                    data[i] = data[j];
                    index_t nj = permutation[j];
                    mark(permutation, j);
                    i = j;
                    j = nj;
                }
                data[i] = temp;
            }
            for(index_t k = 0; k < permutation.size(); k++) {
                unmark(permutation, k);
            }
        }
 
        inline void invert(vector<index_t>& permutation) {
            geo_debug_assert(permutation.size() < MAX_SIZE);
            geo_debug_assert(is_valid(permutation));
            for(index_t k = 0; k < permutation.size(); k++) {
                if(is_marked(permutation, k)) {
                    continue;
                }
                index_t i = k;
                index_t j = permutation[i];
                while(j != k) {
                    index_t temp = permutation[j];
                    permutation[j] = i;
                    mark(permutation, j);
                    i = j;
                    j = temp;
                }
                permutation[j] = i;
                mark(permutation, j);
            }
            for(index_t k = 0; k < permutation.size(); k++) {
                unmark(permutation, k);
            }
        }
 
        inline void invert(
            const vector<index_t>& permutation, vector<index_t>& invert
        ) {
            geo_debug_assert(is_valid(permutation));
            invert.resize(permutation.size());
            for(index_t i=0; i<permutation.size(); ++i) {
                invert[permutation[i]] = i;
            }
        }
 
    }
}
 
#endif