<commit_before>/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is
 * 'psimpl - generic n-dimensional polyline simplification'.
 *
 * The Initial Developer of the Original Code is
 * <NAME>.
 * Portions created by the Initial Developer are Copyright (C) 2010-2011
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * ***** END LICENSE BLOCK ***** */

/*
    psimpl - generic n-dimensional polyline simplification
    Copyright (C) 2010-2011 <NAME>, <EMAIL>

    This file is part of psimpl, and is hosted at SourceForge:
    http://sourceforge.net/projects/psimpl/
*/

/*!
    \mainpage psimpl - generic n-dimensional polyline simplification

<pre>
    Author  - <NAME>
    Support - <EMAIL>
    Website - http://psimpl.sf.net
    Article - http://www.codeproject.com/KB/recipes/PolylineSimplification.aspx
    License - MPL 1.1
</pre><br>

    \section sec_psimpl psimpl
<pre>
    'psimpl' is a c++ polyline simplification library that is generic, easy to use, and supports
    the following algorithms:

    Simplification
    + Nth point - A naive algorithm that keeps only each nth point
    + Distance between points - Removes successive points that are clustered together
    + Perpendicular distance - Removes points based on their distance to the line segment defined
      by their left and right neighbors
    + Reumann-Witkam - Shifts a strip along the polyline and removes points that fall outside
    + Opheim - A constrained version of Reumann-Witkam
    + Lang - Similar to the Perpendicular distance routine, but instead of looking only at direct
      neighbors, an entire search region is processed
    + Douglas-Peucker - A classic simplification algorithm that provides an excellent approximation
      of the original line
    + A variation on the Douglas-Peucker algorithm - Slower, but yields better results at lower resolutions

    Errors
    + positional error - Distance of each polyline point to its simplification

    All the algorithms have been implemented in a single standalone C++ header using an STL-style
    interface that operates on input and output iterators. Polylines can be of any dimension, and
    defined using floating point or signed integer data types.
</pre><br>
    
    \section sec_changelog changelog
<pre>
    28-09-2010 - Initial version
    23-10-2010 - Changed license from CPOL to MPL
    26-10-2010 - Clarified input (type) requirements, and changed the behavior of the algorithms
                 under invalid input
    01-12-2010 - Added the nth point, perpendicular distance and Reumann-Witkam routines; moved all
                 functions related to distance calculations to the math namespace
    10-12-2010 - Fixed a bug in the perpendicular distance routine
    27-02-2011 - Added Opheim simplification, and functions for computing positional errors due to
                 simplification; renamed simplify_douglas_peucker_alt to simplify_douglas_peucker_n
    18-06-2011 - Added Lang simplification; fixed divide by zero bug when using integers; fixed a
                 bug where incorrect output iterators were returned under invalid input; fixed a bug
                 in douglas_peucker_n where an incorrect number of points could be returned; fixed a
                 bug in compute_positional_errors2 that required the output and input iterator types
                 to be the same; fixed a bug in compute_positional_error_statistics where invalid
                 statistics could be returned under questionable input; documented input iterator
                 requirements for each algorithm; miscellaneous refactoring of most algorithms.
</pre>
*/

#ifndef PSIMPL_GENERIC
#define PSIMPL_GENERIC


#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>


/*!
    \brief Root namespace of the polyline simplification library.
*/
namespace psimpl
{
    /*!
        \brief Contains utility functions and classes.
    */
    namespace util
    {
        /*!
            \brief A smart pointer for holding a dynamically allocated array.

            Similar to boost::scoped_array.
        */
        template <typename T>
        class scoped_array
        {
        public:
            scoped_array (unsigned n) {
                array = new T [n];
            }

            ~scoped_array () {
                delete [] array;
            }

            T& operator [] (int offset) {
                return array [offset];<commit_msg>Add missing include for std functional<commit_after>/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is
 * 'psimpl - generic n-dimensional polyline simplification'.
 *
 * The Initial Developer of the Original Code is
 * <NAME>.
 * Portions created by the Initial Developer are Copyright (C) 2010-2011
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * ***** END LICENSE BLOCK ***** */

/*
    psimpl - generic n-dimensional polyline simplification
    Copyright (C) 2010-2011 <NAME>, <EMAIL>

    This file is part of psimpl, and is hosted at SourceForge:
    http://sourceforge.net/projects/psimpl/
*/

/*!
    \mainpage psimpl - generic n-dimensional polyline simplification

<pre>
    Author  - <NAME>
    Support - <EMAIL>
    Website - http://psimpl.sf.net
    Article - http://www.codeproject.com/KB/recipes/PolylineSimplification.aspx
    License - MPL 1.1
</pre><br>

    \section sec_psimpl psimpl
<pre>
    'psimpl' is a c++ polyline simplification library that is generic, easy to use, and supports
    the following algorithms:

    Simplification
    + Nth point - A naive algorithm that keeps only each nth point
    + Distance between points - Removes successive points that are clustered together
    + Perpendicular distance - Removes points based on their distance to the line segment defined
      by their left and right neighbors
    + Reumann-Witkam - Shifts a strip along the polyline and removes points that fall outside
    + Opheim - A constrained version of Reumann-Witkam
    + Lang - Similar to the Perpendicular distance routine, but instead of looking only at direct
      neighbors, an entire search region is processed
    + Douglas-Peucker - A classic simplification algorithm that provides an excellent approximation
      of the original line
    + A variation on the Douglas-Peucker algorithm - Slower, but yields better results at lower resolutions

    Errors
    + positional error - Distance of each polyline point to its simplification

    All the algorithms have been implemented in a single standalone C++ header using an STL-style
    interface that operates on input and output iterators. Polylines can be of any dimension, and
    defined using floating point or signed integer data types.
</pre><br>
    
    \section sec_changelog changelog
<pre>
    28-09-2010 - Initial version
    23-10-2010 - Changed license from CPOL to MPL
    26-10-2010 - Clarified input (type) requirements, and changed the behavior of the algorithms
                 under invalid input
    01-12-2010 - Added the nth point, perpendicular distance and Reumann-Witkam routines; moved all
                 functions related to distance calculations to the math namespace
    10-12-2010 - Fixed a bug in the perpendicular distance routine
    27-02-2011 - Added Opheim simplification, and functions for computing positional errors due to
                 simplification; renamed simplify_douglas_peucker_alt to simplify_douglas_peucker_n
    18-06-2011 - Added Lang simplification; fixed divide by zero bug when using integers; fixed a
                 bug where incorrect output iterators were returned under invalid input; fixed a bug
                 in douglas_peucker_n where an incorrect number of points could be returned; fixed a
                 bug in compute_positional_errors2 that required the output and input iterator types
                 to be the same; fixed a bug in compute_positional_error_statistics where invalid
                 statistics could be returned under questionable input; documented input iterator
                 requirements for each algorithm; miscellaneous refactoring of most algorithms.
</pre>
*/

#ifndef PSIMPL_GENERIC
#define PSIMPL_GENERIC


#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <functional> // for ptr_fun, bind2nd


/*!
    \brief Root namespace of the polyline simplification library.
*/
namespace psimpl
{
    /*!
        \brief Contains utility functions and classes.
    */
    namespace util
    {
        /*!
            \brief A smart pointer for holding a dynamically allocated array.

            Similar to boost::scoped_array.
        */
        template <typename T>
        class scoped_array
        {
        public:
            scoped_array (unsigned n) {
                array = new T [n];
            }

            ~scoped_array () {
                delete [] array;
            }

            T& operator [] (int offset) {
                return array [offset];
{'fraction_non_alphanumeric': 0.06251866600298656, 'fraction_numerical': 0.015828770532603287, 'mean_word_length': 2.773854244928625, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6837923', 'n_tokens_mistral': 2704, 'n_tokens_neox': 2476, 'n_words': 1143}