// Copyright (c) 2006-2009 Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL: https://github.com/CGAL/cgal/blob/v5.2/Algebraic_kernel_d/include/CGAL/Algebraic_kernel_d/Shear_controller.h $
// $Id: Shear_controller.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
//
// Author(s)     : Michael Kerber <mkerber@mpi-inf.mpg.de>
//
// ============================================================================

#ifndef CGAL_ACK_SHEAR_CONTROLLER
#define CGAL_ACK_SHEAR_CONTROLLER 1

#include <CGAL/disable_warnings.h>

#include <CGAL/basic.h>
#include <CGAL/Random.h>
#include <CGAL/tss.h>

#include<set>

namespace CGAL {

  namespace internal {

    /*!
     * \brief A class that controls the used shear factors
     *
     * The objects returns positive integers that are used as shear factors.
     * It choses integers from the range \c 1..max at random ,
     * where \c c is a positive integer
     * initially set in the constructor (8 by default). No integer is given
     * twice by \c get_shear_factor(), at least if the failed ones are reported
     * with the \c report_failure() method.
     * If more than half of the integers in the range were bad, the range is
     * enlarged to \c 1..2*max.
     */
    template<typename Int,int InitialMax=8>
      class Shear_controller {

    public:

      //! Constructor, getting the maximal absolute value of the shear factor
      Shear_controller()
        :
#if CGAL_ACK_STATIC_SEED
          #warning Warning, uses static seed!
        rng(CGAL_ACK_STATIC_SEED)
#else
        rng()
#endif
        , m_max(InitialMax)
        , pos_next_factor(0)  {
          CGAL_assertion(m_max>=1);
        }

        //! Reports that the shear factor \c factor was bad.
        void report_failure(Int factor) {
          this->bad_shears.insert(factor);
          long failures=static_cast<long>(this->bad_shears.size())+1;
          if(2*failures>this->m_max) {
            this->m_max*=2;
          }

        }

        //! Gets a shear factor
        Int get_shear_factor() {
          if(pos_next_factor==static_cast<int>(value_order().size())) {
            value_order().push_back(get_new_shear_factor());
          }
          return value_order()[pos_next_factor++];
        }

    private:

        //! Gets a new shear factor
        Int get_new_shear_factor() {
          CGAL_assertion(int(this->bad_shears.size())<m_max);
          while(true) {
            Int s = Int((rng.get_int(0,(std::numeric_limits<int>::max)())%m_max )+1);
            if(bad_shears.find(s)==bad_shears.end()) {
              return s;
            }
          }
        }

        Random rng;

        // Maximal absolute value
        Int m_max;

        static std::vector<Int>& value_order() {
          CGAL_STATIC_THREAD_LOCAL_VARIABLE_0(std::vector<Int>, value_order_);
          return value_order_;
        }

        int pos_next_factor;

  // Unsuccessful shear factors
        std::set<Int> bad_shears;

    };

  } // namespace internal
} //namespace CGAL

#include <CGAL/enable_warnings.h>

#endif // CGAL_ACK_SHEAR_CONTROLLER