source: src/Fragmentation/Summation/SortedVector.hpp

/*
 * SortedVector.hpp
 *
 *  Created on: Jul 3, 2012
 *      Author: heber
 */

#ifndef SORTEDVECTOR_HPP_
#define SORTEDVECTOR_HPP_


// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/bind.hpp>
#include <vector>

/** Functor for transforming instance of type T to copies contained in shared_ptr.
 *
 */
template <typename T>
struct SharedPtrAllocator {
  boost::shared_ptr<T> operator()(const T& a) {
    return boost::shared_ptr<T>( new T(a) );
  }
};


/** This class represents a general sorted container of instances, stored as shared_ptr.
 *
 *  These instances are stored in order not by appearance memory due to shared_ptr but
 *  by the comparison operators of the underlying type.
 *
 *  The sorted vector is truely a sorted vector. Hence, we must access often but change
 *  only seldomly. This is due to item#23 in [Meyers, "Effective STL"].
 *
 */
template <typename T>
struct SortedVector
{
  typedef typename T::ptr T_ptr;
  typedef std::vector<T_ptr> Container_t;
public:
  /** Constructor from an unsorted vector of instances.
   *
   * @param _container unsorted vector of instances
   */
  SortedVector(const Container_t &_container) :
    ContainerSorted(false),
    container(_container)
  {
    sort();
  }

  /** Constructor from an unsorted vector of instances.
   *
   * @param _container unsorted vector of instances
   */
  SortedVector(const std::vector<T> &_container) :
    ContainerSorted(false)
  {
    container.resize(_container.size());
    SharedPtrAllocator<T> allocator;
    std::transform(_container.begin(), _container.end(),
        container.begin(), allocator);
    sort();
  }

  /** Constructor from a single instance.
   *
   * A single instance is automatically sorted.
   *
   * @param _instance single instance
   */
  SortedVector(T_ptr &_instance) :
    ContainerSorted(true)
  {
    container.push_back(_instance);
  }

  /** Default constructor.
   *
   * An empty vector is automatically sorted.
   *
   * @return
   */
  SortedVector() :
    ContainerSorted(true)
  {}

  /** Getter to sorted container.
   *
   * This getter is made const only through the virtue of making the member
   * variables mutable. This is however the only sensible way as to the outside
   * the container must be treatable as const despite "lazy" resorting on this
   * read-only access in the background.
   *
   * @return const ref to internal sorted container
   */
  const Container_t &getContainer() const {
    if (!ContainerSorted)
      sort();
    return container;
  }

  /** Insert a shared_ptr instance
   *
   * We lazily set the container to not sorted, it is sorted on next access.
   *
   * @param a instance to insert
   */
  void insert(T_ptr &a) {
    // check if present via binary_search
    if (!std::binary_search(container.begin(), container.end(), a, Comparator)) {
      // only insert if not present
      container.push_back(a);
      ContainerSorted = false;
    }
  }

  /** Insert an instance not wrapped in shared_ptr.
   *
   * We lazily set the container to not sorted, it is sorted on next access.
   *
   * @param a instance to copy and insert
   */
  void insert(const T &a) {
    T_ptr ptr(new IndexSet(a));
    // check if present via binary_search
    if (!std::binary_search(container.begin(), container.end(), ptr, Comparator)) {
      // only insert if not present
      container.push_back(ptr);
      ContainerSorted = false;
    }
  }

  /** Internal static Comparator function, passing the check on to comparison
   *  operator of underlying type.
   * @param a First instance
   * @param b Second instance
   * @return pointee of a < pointee of b
   */
  struct Comparator_t {
    bool operator()(const T_ptr &a, const T_ptr &b) const {
      return *a < *b;
    }
  } Comparator;

private:
  /** Internal sort function.
   *
   */
  void sort() const {
    std::sort(container.begin(), container.end(), Comparator);
    ContainerSorted = true;
  }

protected:
  //!> internal flag that container is currently sorted, mutable to let getContainer() be const member function
  mutable bool ContainerSorted;

private:
  //!> internal container that is always sorted, mutable to let getContainer() be const member function
  mutable Container_t container;
};



#endif /* SORTEDVECTOR_HPP_ */