container.h

Go to the documentation of this file.

/******************************************************************************
 Copyright (c) 2012-2016 Institut für Nachrichtentechnik, Universität Rostock
 Copyright (c) 2006-2012 Quality & Usability Lab
                         Deutsche Telekom Laboratories, TU Berlin
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 THE SOFTWARE.
*******************************************************************************/
 
// https://AudioProcessingFramework.github.io/
 
 
#ifndef APF_CONTAINER_H
#define APF_CONTAINER_H
 
#include <memory>  // for std::allocator
#include <vector>
#include <list>
#include <stdexcept>  // for std::logic_error
#include <algorithm>  // for std::find
 
#include "apf/iterator.h"  // for stride_iterator, ...
 
namespace apf
{
 
// TODO: move metaprogramming stuff into separate file?
namespace internal
{
  template<typename T1, typename...> struct first { using type = T1; };
 
  // This didn't work with GCC 4.8.2 (segmentation fault during compilation)
  //template<typename T1, typename...> using first = T1;
 
  template<typename T1, typename... Ts> struct last : last<Ts...> {};
  template<typename T1> struct last<T1> { using type = T1; };
 
  template<typename... Args> using if_first_not_integral
    = typename std::enable_if<
      !std::is_integral<typename first<Args...>::type>::value>::type;
  template<typename X> using if_integral
    = typename std::enable_if<std::is_integral<X>::value>::type;
 
  template<typename Arg, typename... Args> using if_last_not_convertible
    = typename std::enable_if<
    !std::is_convertible<typename last<Args...>::type, Arg>::value>::type;
}
 
template<typename T, typename Allocator = std::allocator<T>>
class fixed_vector : private std::vector<T, Allocator>
{
  private:
    using _base = typename std::vector<T, Allocator>;
 
  public:
    using typename _base::value_type;
    using typename _base::allocator_type;
    using typename _base::reference;
    using typename _base::const_reference;
    using typename _base::pointer;
    using typename _base::const_pointer;
    using typename _base::iterator;
    using typename _base::const_iterator;
    using typename _base::reverse_iterator;
    using typename _base::const_reverse_iterator;
    using typename _base::difference_type;
    using typename _base::size_type;
 
    fixed_vector() = default;
    fixed_vector(fixed_vector&&) = default;
    fixed_vector(const fixed_vector&) = delete;
    fixed_vector& operator=(const fixed_vector&) = delete;
    fixed_vector& operator=(fixed_vector&&) = delete;
 
    template<typename... Args, typename =
                                       internal::if_first_not_integral<Args...>>
    explicit fixed_vector(Args&&... args)
      : _base(std::forward<Args>(args)...)
    {}
 
// TODO: constructor from size and allocator is missing in C++11 (but not C++14)
#if 0
    // TODO: re-activate with C++14:
    template<typename Size, typename = internal::if_integral<Size>>
    fixed_vector(Size n, const Allocator& a = Allocator())
      : _base(n, a)
    {}
#else
    explicit fixed_vector(size_type n) : _base(n) {}
#endif
 
    template<typename Size, typename Arg
      , typename = internal::if_integral<Size>>
    fixed_vector(Size n, Arg&& arg, const Allocator& a)
      : _base(static_cast<size_type>(n), std::forward<Arg>(arg), a)
    {}
 
    template<typename Size, typename... Args
      , typename = internal::if_integral<Size>
      , typename = internal::if_last_not_convertible<Allocator, Args...>>
    explicit fixed_vector(Size n, Args&&... args)
      : _base()
    {
      _base::reserve(static_cast<size_type>(n));
      for (Size i = 0; i < n; ++i)
      {
        // Note: std::forward is not used here, because it's called repeatedly
        _base::emplace_back(args...);
      }
    }
 
    // Perfect forwarding doesn't cover initializer lists:
    explicit fixed_vector(std::initializer_list<value_type> il
        , const Allocator& a = Allocator())
      : _base(il, a)
    {}
 
    void resize(size_type n)
    {
      if (this->capacity() == 0)
      {
        _base::resize(n);
      }
      else
      {
        throw std::logic_error(
            "Bug: fixed_vector::resize() is only allowed if capacity == 0!");
      }
    }
 
    void reserve(size_type n)
    {
      if (this->capacity() == 0)
      {
        _base::reserve(n);
      }
      else
      {
        throw std::logic_error(
            "Bug: fixed_vector::reserve() is only allowed if capacity == 0!");
      }
    }
 
    template<typename... Args>
    void emplace_back(Args&&... args)
    {
      if (this->size() < this->capacity())
      {
        _base::emplace_back(std::forward<Args>(args)...);
      }
      else
      {
        throw std::logic_error(
            "Bug: fixed_vector::emplace_back() "
            "is only allowed if size < capacity!");
      }
    }
 
    using _base::front;
    using _base::back;
    using _base::begin;
    using _base::end;
    using _base::rbegin;
    using _base::rend;
    using _base::cbegin;
    using _base::cend;
    using _base::crbegin;
    using _base::crend;
    using _base::size;
    using _base::max_size;
    using _base::capacity;
    using _base::empty;
    using _base::operator[];
    using _base::at;
    using _base::data;
    using _base::get_allocator;
 
    // using _base::shrink_to_fit;  // This may reallocate!
};
 
template<typename T, typename Allocator = std::allocator<T>>
class fixed_list : private std::list<T, Allocator>
{
  private:
    using _base = typename std::list<T, Allocator>;
 
  public:
    using typename _base::value_type;
    using typename _base::allocator_type;
    using typename _base::reference;
    using typename _base::const_reference;
    using typename _base::pointer;
    using typename _base::const_pointer;
    using typename _base::iterator;
    using typename _base::const_iterator;
    using typename _base::reverse_iterator;
    using typename _base::const_reverse_iterator;
    using typename _base::difference_type;
    using typename _base::size_type;
 
    fixed_list() = default;
    fixed_list(fixed_list&&) = default;
    fixed_list(const fixed_list&) = delete;
    fixed_list& operator=(const fixed_list&) = delete;
    fixed_list& operator=(fixed_list&&) = delete;
 
    template<typename... Args, typename =
                                       internal::if_first_not_integral<Args...>>
    explicit fixed_list(Args&&... args)
      : _base(std::forward<Args>(args)...)
    {}
 
    template<typename Size, typename... Args, typename =
                                                    internal::if_integral<Size>>
    explicit fixed_list(Size n, Args&&... args)
      : _base()
    {
      for (Size i = 0; i < n; ++i)
      {
        // Note: std::forward is not used here, because it's called repeatedly
        _base::emplace_back(args...);
      }
    }
 
    explicit fixed_list(std::initializer_list<value_type> il
        , const Allocator& a = Allocator())
      : _base(il, a)
    {}
 
    void move(iterator from, iterator to)
    {
      _base::splice(to, *this, from);
    }
 
    void move(iterator first, iterator last, iterator target)
    {
      _base::splice(target, *this, first, last);
    }
 
    using _base::begin;
    using _base::end;
    using _base::rbegin;
    using _base::rend;
    using _base::cbegin;
    using _base::cend;
    using _base::crbegin;
    using _base::crend;
    using _base::empty;
    using _base::size;
    using _base::max_size;
    using _base::front;
    using _base::back;
    using _base::get_allocator;
    using _base::reverse;
    using _base::sort;
};
 
template<typename T, typename Allocator = std::allocator<T>>
class fixed_matrix : public fixed_vector<T, Allocator>
{
  private:
    using _base = fixed_vector<T, Allocator>;
 
  public:
    using typename _base::pointer;
    using typename _base::size_type;
 
    using Channel = has_begin_and_end<pointer>;
    using channel_iterator = typename Channel::iterator;
 
    using Slice = has_begin_and_end<stride_iterator<channel_iterator>>;
    using slice_iterator = typename Slice::iterator;
 
    class channels_iterator;
    class slices_iterator;
 
    explicit fixed_matrix(const Allocator& a = Allocator())
      : _base(a)
    {
      this->initialize(0, 0);
    }
 
    fixed_matrix(fixed_matrix&&) = default;
    fixed_matrix(const fixed_matrix&) = delete;
    fixed_matrix& operator=(const fixed_matrix&) = delete;
    fixed_matrix& operator=(fixed_matrix&&) = delete;
 
    fixed_matrix(size_type max_channels, size_type max_slices
        , const Allocator& a = Allocator())
      : fixed_matrix(a)
    {
      this->initialize(max_channels, max_slices);
    }
 
    void initialize(size_type max_channels, size_type max_slices)
    {
      _base::resize(max_channels * max_slices);
 
      this->channels = make_begin_and_end(
          channels_iterator(_base::data(), max_slices), max_channels);
      this->slices = make_begin_and_end(
          slices_iterator(_base::data(), max_channels, max_slices), max_slices);
 
      _channel_ptrs.reserve(max_channels);
      for (const auto channel: this->channels)
      {
        _channel_ptrs.emplace_back(channel.begin());
      }
      assert(_channel_ptrs.size() == max_channels);
    }
 
    template<typename Ch>
    void set_channels(const Ch& ch);
 
    pointer const* get_channel_ptrs() const { return _channel_ptrs.data(); }
 
    has_begin_and_end<channels_iterator> channels;
    has_begin_and_end<slices_iterator> slices;
 
  private:
    // Hide functions from fixed_vector:
    void emplace_back();
    void reserve();
    void resize();
 
    fixed_vector<pointer> _channel_ptrs;
};
 
template<typename T, typename Allocator>
class fixed_matrix<T, Allocator>::channels_iterator
{
  private:
    using self = channels_iterator;
    using _base_type = stride_iterator<channel_iterator>;
 
    struct ChannelArrowProxy : Channel
    {
      ChannelArrowProxy(const Channel& ch) : Channel(ch) {}
      Channel* operator->() { return this; }
    };
 
  public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = Channel;
    using reference = Channel;
    using difference_type = typename _base_type::difference_type;
    using pointer = ChannelArrowProxy;
 
    channels_iterator()
      : _size(0)
    {}
 
    channels_iterator(channel_iterator base_iterator, size_type step)
      : _base_iterator(base_iterator, static_cast<difference_type>(step))
      , _size(step)
    {}
 
    reference operator*() const
    {
      auto temp = _base_iterator.base();
      assert(apf::no_nullptr(temp));
      return Channel(temp, temp + _size);
    }
 
    pointer operator->() const
    {
      return this->operator*();
    }
 
    APF_ITERATOR_RANDOMACCESS_EQUAL(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREINCREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREDECREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_ADDITION_ASSIGNMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_DIFFERENCE(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_SUBSCRIPT
    APF_ITERATOR_RANDOMACCESS_LESS(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_OTHER_COMPARISONS
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
    APF_ITERATOR_BASE(_base_type, _base_iterator)
 
  private:
    _base_type _base_iterator;
    size_type _size;
};
 
template<typename T, typename Allocator>
class fixed_matrix<T, Allocator>::slices_iterator
{
  private:
    using self = slices_iterator;
 
    struct SliceArrowProxy : Slice
    {
      SliceArrowProxy(const Slice& sl) : Slice(sl) {}
      Slice* operator->() { return this; }
    };
 
  public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = Slice;
    using reference = Slice;
    using pointer = SliceArrowProxy;
    using difference_type
      = typename std::iterator_traits<channel_iterator>::difference_type;
 
    slices_iterator()
      : _max_channels(0)
      , _max_slices(0)
    {}
 
    slices_iterator(channel_iterator base_iterator
        , size_type max_channels, size_type max_slices)
      : _base_iterator(base_iterator)
      , _max_channels(max_channels)
      , _max_slices(max_slices)
    {}
 
    reference operator*() const
    {
      assert(apf::no_nullptr(_base_iterator));
      slice_iterator temp{_base_iterator
        , static_cast<difference_type>(_max_slices)};
      return Slice(temp, temp + static_cast<difference_type>(_max_channels));
    }
 
    pointer operator->() const
    {
      return this->operator*();
    }
 
    APF_ITERATOR_RANDOMACCESS_EQUAL(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREINCREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREDECREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_ADDITION_ASSIGNMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_DIFFERENCE(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_SUBSCRIPT
    APF_ITERATOR_RANDOMACCESS_LESS(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_OTHER_COMPARISONS
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
    APF_ITERATOR_BASE(channel_iterator, _base_iterator)
 
  private:
    channel_iterator _base_iterator;
    size_type _max_channels;
    size_type _max_slices;
};
 
template<typename T, typename Allocator>
template<typename Ch>
void
fixed_matrix<T, Allocator>::set_channels(const Ch& ch)
{
  assert(std::distance(ch.begin(), ch.end())
      == std::distance(this->channels.begin(), this->channels.end()));
  assert((ch.begin() == ch.end()) ? true :
      std::distance(ch.begin()->begin(), ch.begin()->end()) ==
      std::distance(this->channels.begin()->begin()
                  , this->channels.begin()->end()));
 
  auto target = this->channels.begin();
 
  for (const auto i: ch)
  {
    std::copy(i.begin(), i.end(), target->begin());
    ++target;
  }
}
 
template<typename L1, typename L2>
void append_pointers(L1& source, L2& target)
{
  for (auto& i: source)
  {
    target.push_back(&i);
  }
}
 
template<typename L1, typename L2>
void append_pointers(const L1& source, L2& target)
{
  for (const auto& i: source)
  {
    target.push_back(&i);
  }
}
 
template<typename L1, typename L2, typename DataMember>
void distribute_list(L1& source, L2& target, DataMember member)
{
  if (source.size() != target.size())
  {
    throw std::logic_error("distribute_list: Different sizes!");
  }
 
  auto in = source.begin();
 
  for (auto& out: target)
  {
    (out.*member).splice((out.*member).end(), source, in++);
  }
}
 
// TODO: better name?
template<typename L1, typename L2, typename DataMember, typename L3>
void
undistribute_list(const L1& source, L2& target, DataMember member, L3& garbage)
{
  if (source.size() != target.size())
  {
    throw std::logic_error("undistribute_list(): Different sizes!");
  }
 
  auto in = source.begin();
 
  for (auto& out: target)
  {
    auto delinquent
      = std::find((out.*member).begin(), (out.*member).end(), *in++);
    if (delinquent == (out.*member).end())
    {
      throw std::logic_error("undistribute_list(): Element not found!");
    }
    garbage.splice(garbage.end(), out.*member, delinquent);
  }
}
 
}  // namespace apf
 
#endif