generic_RVD_utils.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_VORONOI_GENERIC_RVD_UTILS
#define GEOGRAM_VORONOI_GENERIC_RVD_UTILS
 
#include <geogram/basic/common.h>
#include <geogram/voronoi/generic_RVD_vertex.h>
#include <geogram/voronoi/generic_RVD_polygon.h>
#include <geogram/voronoi/generic_RVD_cell.h>
#include <geogram/basic/memory.h>
#include <stack>
#include <vector>
 
namespace GEOGen {
 
    template <class T>
    class VectorStack {
    public:
        void push(const T& x) {
            rep_.push_back(x);
        }
 
        void pop() {
            rep_.pop_back();
        }
 
        const T& top() const {
            return *rep_.rbegin();
        }
 
        bool empty() const {
            return rep_.size() == 0;
        }
 
    private:
        GEO::vector<T> rep_;
    };
 
    /************************************************************************/
 
    struct FacetSeed {
 
        FacetSeed(index_t f_in, index_t seed_in) :
            f(f_in),
            seed(seed_in) {
        }
 
        FacetSeed() {
        }
 
        bool operator< (const FacetSeed& rhs) const {
            if(f < rhs.f) {
                return true;
            }
            if(f > rhs.f) {
                return false;
            }
            return seed < rhs.seed;
        }
 
        index_t f;
        index_t seed;
    };
 
    typedef FacetSeed TetSeed;
    /************************************************************************/
 
#ifdef GEO_OS_ANDROID
    // VectorStack uses AlignedAllocator, that is protected
    // by a global lock under Android (needed because it
    // seems that malloc() is not SMP-thread-safe under Android).
 
    typedef VectorStack<FacetSeed> FacetSeedStack;
 
    typedef VectorStack<TetSeed> TetSeedStack;
 
    typedef VectorStack<index_t> SeedStack;
#else
 
    typedef std::stack<FacetSeed> FacetSeedStack;
 
    typedef std::stack<TetSeed> TetSeedStack;
 
    typedef std::stack<index_t> SeedStack;
#endif
 
    /************************************************************************/
 
    class FacetSeedMarking {
    public:
        FacetSeedMarking(index_t /* nb_facets*/, index_t nb_seeds) {
            set_size(nb_seeds);
        }
 
        bool is_marked(index_t facet, index_t seed) const {
            return find_index(seed, facet) != -1;
        }
 
        bool is_marked(const FacetSeed& fs) const {
            return is_marked(fs.f, fs.seed);
        }
 
        signed_index_t get_connected_component(const FacetSeed& fs) const {
            return find_value(fs.seed, fs.f);
        }
 
        void mark(const FacetSeed& fs, index_t conn_comp) {
            insert(fs.seed, fs.f, conn_comp);
        }
 
        ~FacetSeedMarking() {
            for(index_t i = 0; i < nb_arrays(); ++i) {
                free(keys_[i]);
            }
            for(index_t i = 0; i < nb_arrays(); ++i) {
                free(values_[i]);
            }
        }
 
    protected:
        index_t nb_arrays() const {
            return index_t(keys_.size());
        }
 
        void set_size(index_t nb_arrays) {
            keys_.assign(nb_arrays, nullptr);
            values_.assign(nb_arrays, nullptr);
            size_.assign(nb_arrays, 0);
        }
 
        index_t array_size(index_t array) const {
            return size_[array];
        }
 
        index_t array_capacity(index_t array) const {
            index_t size = array_size(array);
            if(size == 0) {
                return 0;
            }
            index_t result = 1;
            index_t mask = 1;
            for(index_t i = 0; i < 32; i++) {
                mask = mask << 1;
                if((size & mask) != 0) {
                    result = mask;
                }
            }
            // If size is not already a power of two,
            if(result != size) {
                result = result << 1;
            }
            return result;
        }
 
        signed_index_t find_index(index_t array, index_t key) const {
            index_t* K = keys_[array];
            for(index_t i = 0; i < array_size(array); ++i) {
                if(K[i] == key) {
                    return signed_index_t(i);
                }
            }
            return -1;
        }
 
        signed_index_t find_value(index_t array, index_t key) const {
            signed_index_t i = find_index(array, key);
            if(i == -1) {
                return -1;
            }
            return signed_index_t(values_[array][i]);
        }
 
        void insert(index_t array, index_t key, index_t value) {
            signed_index_t si = find_index(array, key);
            if(si == -1) {
                // If not found, append at the end of array
                index_t i = size_[array];
                if(i == array_capacity(array)) {
                    // If capacity is reached, grow storage
                    index_t new_nb = index_t(2*i);
                    if(new_nb == 0) {
                        new_nb = 1;
                    }
                    keys_[array] = reinterpret_cast<index_t*>(
                        realloc(keys_[array], sizeof(index_t) * new_nb)
                    );
                    values_[array] = reinterpret_cast<index_t*>(
                        realloc(values_[array], sizeof(index_t) * new_nb)
                    );
                }
                size_[array] = i + 1;
                si = signed_index_t(i);
            }
            keys_[array][si] = key;
            values_[array][si] = value;
        }
 
    private:
        std::vector<index_t*> keys_;
        std::vector<index_t*> values_;
        std::vector<index_t> size_;
    };
 
    /************************************************************************/
 
    typedef FacetSeedMarking TetSeedMarking;
 
    /************************************************************************/
}
 
#endif