tpl_random_queue.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/

# ifndef TPL_RANDOM_QUEUE_H
# define TPL_RANDOM_QUEUE_H

# include <gsl/gsl_rng.h>
# include <htlist.H>
# include <ah-dry.H>
# include <tpl_dynArray.H>

namespace Aleph {

    template <class T> 
class Random_Set
      : public LocateFunctions<Random_Set<T>, T>,
        public FunctionalMethods<Random_Set<T>, T>,
        public GenericKeys<Random_Set<T>, T>,
        public EqualToMethod<Random_Set<T>>,
        public StlAlephIterator<Random_Set<T>>
{
private:

  DynArray<T> array;
  gsl_rng * r = nullptr;

public:

  using Set_Type = Random_Set; 

  using Item_Type = T; 

  gsl_rng * get_rng() const { return r; }

  void set_seed(unsigned long seed) noexcept { gsl_rng_set(r, seed); }

  size_t size() const { return array.size(); }
  
  Random_Set() : array(0), r(nullptr)
  {
    r = gsl_rng_alloc (gsl_rng_mt19937);
    if (r == nullptr)
      throw std::bad_alloc();

    gsl_rng_set(r, time(nullptr) % gsl_rng_max(r));
  }

  void swap(Random_Set & s)
  {
    array.swap(s.array);
    std::swap(r, s.r);
  }

  Random_Set(const Random_Set & s) : Random_Set()
  {
    s.for_each([this] (auto item) { this->append(item); });
  }

  Random_Set(Random_Set && s) { swap(s); }

  Random_Set & operator = (const Random_Set & s)
  {
    if (this == &s)
      return *this;

    if (s.size() > size())
      array.reserve(s.size());
    else
      array.cut(s.size);
    s.for_each([this] (auto item) { this->append(item); });

    return *this;
  }

  Random_Set & operator = (Random_Set && s) 
  {
    swap(s);
    return *this;
  }

  Random_Set(const DynList<T> & l) : Random_Set()
  {
    l.for_each([this] (const T & item) { append(item); });
  }

  template <class It> Random_Set(It b, It e) : Random_Set()
  {
    for (It it = b; it != e; ++it)
      append(*it);
  }
  
  Random_Set(std::initializer_list<T> l) : Random_Set()
  {
    for (const auto & item : l)
      append(item);
  }

  ~Random_Set()
  {
    if (r != nullptr)
      gsl_rng_free(r);
  }

  void put(const T & item) { array.append(item); }

  
  void put(T && item) { array.append(std::forward<T>(item)); }

  void append(const T & item)
  {
    put(item);
    auto pos = gsl_rng_uniform_int(r, array.size()); // al azar
    std::swap(array(pos), array(array.size() - 1));
  }

  void append(T && item)
  {
    put(move(item));
    auto pos = gsl_rng_uniform_int(r, array.size()); // al azar
    std::swap(array(pos), array(array.size() - 1));
  }

  T get()
  {
    if (array.size() == 0)
      throw std::underflow_error("Random set is empty");

    const size_t pos = gsl_rng_uniform_int(r, array.size()); // al azar
    T ret_val = array.access(pos);
    array.access(pos) = array.access(array.size() - 1);
    array.cut(array.size() - 1);
    return ret_val;
  }

  bool is_empty() const { return array.size() == 0; }

  struct Iterator : public DynArray<T>
  {
    using Base = DynArray<T>;
    using Base::Base;
  };

  template <class Operation>
    bool traverse(Operation & operation) 
    noexcept(noexcept(array.traverse(operation)))
  {
    return array.traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation & operation) const noexcept(noexcept(operation))
  {
    return const_cast<Random_Set*>(this)->traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation()) const
    noexcept(noexcept(operation))
  {
    return traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation())
    noexcept(noexcept(operation))
  {
    return traverse(operation);
  }
};


  template <typename T, template <typename> class C>
auto shuffle(const C<T> & c)
{
  Random_Set<T*> q;
  c.for_each([&q] (const T & item) { q.put(&const_cast<T&>(item)); });
  
  C<T> ret;
  while (not q.is_empty())
    ret.append(*q.get());

  return ret;
}


  template <typename T, template <typename> class C>
C<T*> shuffle_ptr(const C<T> & c)
{
  Random_Set<T*> q;
  c.for_each([&q] (const T & item) { q.put(&const_cast<T&>(item)); });
  
  C<T*> ret;
  while (not q.is_empty())
    ret.append(q.get());

  return ret;
}

} // end namespace Aleph

# endif // TPL_RANDOM_QUEUE_H