/**********************************************************************

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2021-2022 Daniel Baston

 *

 * This is free software; you can redistribute and/or modify it under

 * the terms of the GNU Lesser General Public Licence as published

 * by the Free Software Foundation.

 * See the COPYING file for more information.

 *

 **********************************************************************/

#ifndef GEOS_OPERATION_CLUSTER_CLUSTERS

#define GEOS_OPERATION_CLUSTER_CLUSTERS

#include <geos/export.h>

#include <limits>

#include <vector>

namespace geos {

namespace operation {

namespace cluster {

class UnionFind;

class GEOS_DLL Clusters {

private:

    std::vector<std::size_t> m_elemsInCluster; // The IDs of elements that are included in a cluster

    std::vector<std::size_t> m_starts; // Start position of each cluster in m_elemsInCluster

    std::size_t m_numElems; // The number of elements from which clusters were generated

public:

    using const_iterator = decltype(m_elemsInCluster)::const_iterator;

    explicit Clusters(UnionFind & uf, std::vector<std::size_t> elemsInCluster, std::size_t numElems);

    // Get the number of clusters available

    std::size_t getNumClusters() const {

        return m_starts.size();

    }

    // Get the size of a given cluster

    std::size_t getSize(std::size_t cluster) const {

        return static_cast<std::size_t>(std::distance(begin(cluster), end(cluster)));

    }

    // Get a vector containing the cluster ID for each item in `elems`

    std::vector<std::size_t> getClusterIds(std::size_t noClusterValue = std::numeric_limits<std::size_t>::max()) const;

    // Get an iterator to the first element in a given cluster

    const_iterator begin(std::size_t cluster) const {

        return std::next(m_elemsInCluster.begin(), static_cast<std::ptrdiff_t>(m_starts[cluster]));

    }

    // Get an iterator beyond the last element in a given cluster

    const_iterator end(std::size_t cluster) const {

        if (cluster == static_cast<std::size_t>(m_starts.size() - 1)) {

            return m_elemsInCluster.end();

        }

        return begin(cluster + 1);

    }

};

}

}

}

#endif