/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * 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.
 *
 **********************************************************************
 *
 * Last port: index/chain/MonotoneChainBuilder.java r388 (JTS-1.12)
 *
 **********************************************************************/

#include <geos/index/chain/MonotoneChainBuilder.h>
#include <geos/index/chain/MonotoneChain.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/CoordinateFilter.h>
#include <geos/geom/Quadrant.h>


#include <cassert>
#include <cstdio>
#include <vector>

#ifndef GEOS_DEBUG
#define GEOS_DEBUG 0
#endif

#if GEOS_DEBUG
#include <iostream>
#endif


using namespace geos::geom;

namespace geos {
namespace index { // geos.index
namespace chain { // geos.index.chain

/** \brief
 * Finds the index of the last point in each monotone chain
 * of the provided coordinate sequence.
 */
class ChainBuilder : public CoordinateFilter {
public:
    ChainBuilder(const CoordinateSequence* pts, void* context, std::vector<MonotoneChain> & list) :
     m_prev(nullptr),
     m_i(0),
     m_quadrant(-1),
     m_start(0),
     m_seq(pts),
     m_context(context),
     m_list(list) {}

    void filter_ro(const CoordinateXY* c) override {
        process(c);

        m_prev = c;
        m_i++;
    }

    void finish() {
        finishChain();
    }

private:
    void finishChain() {
        if ( m_i == 0 ) return;
        std::size_t chainEnd = m_i - 1;
        m_list.emplace_back(*m_seq, m_start, chainEnd, m_context);
        m_start = chainEnd;
    }

    void process(const CoordinateXY* curr) {
        if (m_prev == nullptr || curr->equals2D(*m_prev)) {
            return;
        }

        int currQuad = Quadrant::quadrant(*m_prev, *curr);

        if (m_quadrant < 0) {
            m_quadrant = currQuad;
        }

        if (currQuad != m_quadrant) {
            finishChain();
            m_quadrant = currQuad;
        }
    }

    const CoordinateXY* m_prev;
    std::size_t m_i;
    int m_quadrant;
    std::size_t m_start;
    const CoordinateSequence* m_seq;
    void* m_context;
    std::vector<MonotoneChain>& m_list;
};


/* static public */
void
MonotoneChainBuilder::getChains(const CoordinateSequence* pts, void* context,
                                std::vector<MonotoneChain>& mcList) {
    ChainBuilder builder(pts, context, mcList);
    pts->apply_ro(&builder);
    builder.finish();
}

} // namespace geos.index.chain
} // namespace geos.index
} // namespace geos