sliding_interval_window_iterator.hpp

Go to the documentation of this file.

#ifndef GENESIS_POPULATION_WINDOW_SLIDING_INTERVAL_WINDOW_ITERATOR_H_
#define GENESIS_POPULATION_WINDOW_SLIDING_INTERVAL_WINDOW_ITERATOR_H_
 
/*
    Genesis - A toolkit for working with phylogenetic data.
    Copyright (C) 2014-2022 Lucas Czech
 
    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 <http://www.gnu.org/licenses/>.
 
    Contact:
    Lucas Czech <lczech@carnegiescience.edu>
    Department of Plant Biology, Carnegie Institution For Science
    260 Panama Street, Stanford, CA 94305, USA
*/
 
#include "genesis/population/window/base_window_iterator.hpp"
 
#include <cassert>
#include <functional>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
 
namespace genesis {
namespace population {
 
// =================================================================================================
//     Sliding Interval Window Iterator
// =================================================================================================
 
template<class ForwardIterator, class DataType = typename ForwardIterator::value_type>
class SlidingIntervalWindowIterator final : public BaseWindowIterator<ForwardIterator, DataType>
{
public:
 
    // -------------------------------------------------------------------------
    //     Typedefs and Enums
    // -------------------------------------------------------------------------
 
    using self_type = SlidingIntervalWindowIterator<ForwardIterator, DataType>;
    using base_type = BaseWindowIterator<ForwardIterator, DataType>;
 
    using Window            = ::genesis::population::Window<DataType>;
    using Entry             = typename Window::Entry;
    using InputType         = typename ForwardIterator::value_type;
 
    using iterator_category = std::input_iterator_tag;
    using value_type        = Window;
    using pointer           = value_type*;
    using reference         = value_type&;
    using const_reference   = value_type const&;
 
    // ======================================================================================
    //      Internal Iterator
    // ======================================================================================
 
    class DerivedIterator final : public BaseWindowIterator<ForwardIterator, DataType>::BaseIterator
    {
    public:
 
        // -------------------------------------------------------------------------
        //     Constructors and Rule of Five
        // -------------------------------------------------------------------------
 
        using self_type = typename SlidingIntervalWindowIterator<
            ForwardIterator, DataType
        >::DerivedIterator;
 
        using base_iterator_type = typename BaseWindowIterator<
            ForwardIterator, DataType
        >::BaseIterator;
 
        using Window            = ::genesis::population::Window<DataType>;
        using Entry             = typename Window::Entry;
        using InputType         = typename ForwardIterator::value_type;
 
        using iterator_category = std::input_iterator_tag;
        using value_type        = Window;
        using pointer           = value_type*;
        using reference         = value_type&;
        using const_reference   = value_type const&;
 
    private:
 
        DerivedIterator() = default;
 
        DerivedIterator(
            SlidingIntervalWindowIterator const* parent
        )
            : base_iterator_type( parent )
            , parent_( parent )
        {
            // Edge case check. See Base for details.
            if( ! parent_ ) {
                return;
            }
 
            // Call the base class initializer.
            // base_iterator_type::init_( parent_ );
 
            // Check our own the settings.
            if( parent_->width_ == 0 ) {
                throw std::runtime_error( "Cannot use SlidingIntervalWindowIterator of width 0." );
            }
            if( parent_->stride_ == 0 ) {
                parent_->stride_ = parent_->width_;
            }
            if( parent_->stride_ > parent_->width_ ) {
                throw std::runtime_error(
                    "Cannot use SlidingIntervalWindowIterator with stride > width."
                );
            }
 
            // Let's get going.
            init_chromosome_();
            update_();
        }
 
    public:
 
        ~DerivedIterator() = default;
 
        DerivedIterator( self_type const& ) = default;
        DerivedIterator( self_type&& )      = default;
 
        DerivedIterator& operator= ( self_type const& ) = default;
        DerivedIterator& operator= ( self_type&& )      = default;
 
        friend SlidingIntervalWindowIterator;
 
        // -------------------------------------------------------------------------
        //     Internal and Virtual Members
        // -------------------------------------------------------------------------
 
    private:
 
        void init_chromosome_()
        {
            // Saveguard. This might be called on an empty range, in which case we just do nothing.
            if( base_iterator_type::current_ == base_iterator_type::end_ ) {
                return;
            }
 
            // Clear the window and prepare for new chromosome.
            window_.clear();
            window_.chromosome( parent_->chromosome_function( *base_iterator_type::current_ ));
            base_iterator_type::is_first_window_ = true;
            base_iterator_type::is_last_window_ = false;
            next_index_ = 0;
 
            if( parent_->emit_leading_empty_windows_ ) {
                current_start_ = 1;
            } else {
                // Set the start to the window position that we would get after going through all
                // the previous windows if they were emitted.
                auto const pos = parent_->position_function( *base_iterator_type::current_ );
                current_start_ = pos - (( pos - 1 ) % parent_->stride_ );
            }
        }
 
        void increment_() override final
        {
            // Special case: If we have no more underlying data, the iterator still needs to stop
            // at the last window(s), so that they can be processed. After that, when this
            // increment_() function is called again by the user, we then set parent_ = nullptr
            // to indicate that now we are done for good.
            if( base_iterator_type::current_ == base_iterator_type::end_ ) {
                // If current_ == end_, we have definitely reached the end of the input, so we need
                // to have set is_last_window_ previously. If not set, that means it was already
                // reset, so that this is an iteration past the end.
                if( ! base_iterator_type::is_last_window_ ) {
                    throw std::runtime_error(
                        "SlidingIntervalWindowIterator: Incrementing past the end"
                    );
                }
 
                // Indicate that we are done now.
                parent_ = nullptr;
                return;
            }
 
            // Check if this call moves to the next chromosome.
            if(
                parent_->chromosome_function( *base_iterator_type::current_ ) != window_.chromosome()
            ) {
                init_chromosome_();
            } else {
                // Update positions.
                current_start_ += parent_->stride_;
                base_iterator_type::is_first_window_ = false;
            }
 
            // Fill window with data.
            update_();
        }
 
        void update_()
        {
            // Dequeue everything that is not part of the current interval any more.
            // We can speed up by clearing the whole window if its last entry is before the current
            // start, as in that case, all its entries are, so we want to pop them all anyway.
            // That is the default case when moving with stride = width, so that's nice.
            if(
                window_.entries().size() > 0 &&
                window_.entries().back().position < current_start_
            ) {
                window_.entries().clear();
            } else {
                while(
                    window_.entries().size() > 0 &&
                    window_.entries().front().position < current_start_
                ) {
                    window_.entries().pop_front();
                }
            }
 
            // Now enqueue new entries.
            while( base_iterator_type::current_ != base_iterator_type::end_ ) {
                auto const cur_pos = parent_->position_function( *base_iterator_type::current_ );
 
                // Get the chromosome and position of the current entry, and see if it belongs
                // into the current window. If not, we are done here with this window.
                if(
                    parent_->chromosome_function(
                        *base_iterator_type::current_
                    ) != window_.chromosome() ||
                    cur_pos >= current_start_ + parent_->width_
                ) {
                    break;
                }
                assert(
                    parent_->chromosome_function( *base_iterator_type::current_ ) ==
                    window_.chromosome()
                );
                assert( cur_pos >= current_start_ );
                assert( cur_pos <  current_start_ + parent_->width_ );
 
                // Check that we are not going backwards in the chromosome,
                // i.e., if we got unsorted data. That would lead to unwanted behaviour.
                if(
                    window_.size() > 0 &&
                    window_.entries().back().position >= cur_pos
                ) {
                    throw std::runtime_error(
                        "Invalid entry in sliding window that not in sequence with other entries. "
                        "Previous entry is " + window_.chromosome() + ":" +
                        std::to_string( window_.entries().back().position ) +
                        ", current (invalid) entry is " + window_.chromosome() + ":" +
                        std::to_string( cur_pos )
                    );
                }
 
                // Now enqueue the entry, and move to the next.
                window_.entries().emplace_back(
                    next_index_,
                    cur_pos,
                    parent_->entry_input_function( *base_iterator_type::current_ )
                );
                ++next_index_;
                ++base_iterator_type::current_;
            }
 
            // Cases in which we are at the last window: Either we reached the end of the input,
            // or the end of the current chromosome.
            if(
                base_iterator_type::current_ == base_iterator_type::end_ ||
                parent_->chromosome_function( *base_iterator_type::current_ ) != window_.chromosome()
            ) {
                base_iterator_type::is_last_window_ = true;
            }
 
            // Update the window positions.
            window_.first_position( current_start_ );
            window_.last_position( current_start_ + parent_->width_ - 1 );
        }
 
        value_type& get_current_window_() const override final
        {
            return const_cast<value_type&>( window_ );
        }
 
        BaseWindowIterator<ForwardIterator, DataType> const* get_parent_() const override final
        {
            return parent_;
        }
 
    private:
 
        // Parent. Needs to live here to have the correct derived type.
        SlidingIntervalWindowIterator const* parent_ = nullptr;
 
        // Current window and its position
        Window window_;
        size_t current_start_ = 1;
        size_t next_index_ = 0;
 
    };
 
    // ======================================================================================
    //      Main Class
    // ======================================================================================
 
    // -------------------------------------------------------------------------
    //     Constructors and Rule of Five
    // -------------------------------------------------------------------------
 
    SlidingIntervalWindowIterator(
        ForwardIterator begin, ForwardIterator end
    )
        : base_type( begin, end )
    {}
 
    ~SlidingIntervalWindowIterator() = default;
 
    SlidingIntervalWindowIterator( SlidingIntervalWindowIterator const& ) = default;
    SlidingIntervalWindowIterator( SlidingIntervalWindowIterator&& )      = default;
 
    SlidingIntervalWindowIterator& operator= ( SlidingIntervalWindowIterator const& ) = default;
    SlidingIntervalWindowIterator& operator= ( SlidingIntervalWindowIterator&& )      = default;
 
    friend DerivedIterator;
 
    // -------------------------------------------------------------------------
    //     Settings
    // -------------------------------------------------------------------------
 
    self_type& width( size_t value )
    {
        width_ = value;
        return *this;
    }
 
    size_t width() const
    {
        return width_;
    }
 
    self_type& stride( size_t value )
    {
        stride_ = value;
        return *this;
    }
 
    size_t stride() const
    {
        return stride_;
    }
 
    self_type& emit_leading_empty_windows( bool value )
    {
        emit_leading_empty_windows_ = value;
        return *this;
    }
 
    bool emit_leading_empty_windows() const
    {
        return emit_leading_empty_windows_;
    }
 
    // -------------------------------------------------------------------------
    //     Virtual Members
    // -------------------------------------------------------------------------
 
protected:
 
    std::unique_ptr<typename BaseWindowIterator<ForwardIterator, DataType>::BaseIterator>
    get_begin_iterator_() override final
    {
        // Cannot use make_unique here, as the Iterator constructor is private,
        // and trying to make make_unique a friend does not seem to be working...
        return std::unique_ptr<DerivedIterator>( new DerivedIterator( this ));
        // return utils::make_unique<DerivedIterator>( this );
    }
 
    std::unique_ptr<typename BaseWindowIterator<ForwardIterator, DataType>::BaseIterator>
    get_end_iterator_() override final
    {
        return std::unique_ptr<DerivedIterator>( new DerivedIterator( nullptr ));
        // return utils::make_unique<DerivedIterator>( nullptr );
    }
 
    // -------------------------------------------------------------------------
    //     Data Members
    // -------------------------------------------------------------------------
 
private:
 
    // Settings. We make stride_ mutable so that the iterator can set it to the width.
    size_t width_ = 0;
    mutable size_t stride_ = 0;
 
    bool emit_leading_empty_windows_ = true;
 
    // bool emit empty_windows = true;
    // bool emit_unfinished_trailing_window = false;
 
};
 
// =================================================================================================
//     Make Sliding Window Iterator
// =================================================================================================
 
template<class ForwardIterator, class DataType = typename ForwardIterator::value_type>
SlidingIntervalWindowIterator<ForwardIterator, DataType>
make_sliding_interval_window_iterator(
    ForwardIterator begin, ForwardIterator end, size_t width = 0, size_t stride = 0
) {
    auto it = SlidingIntervalWindowIterator<ForwardIterator, DataType>( begin, end );
    it.width( width );
    it.stride( stride );
    return it;
}
 
template<class ForwardIterator>
SlidingIntervalWindowIterator<ForwardIterator>
make_default_sliding_interval_window_iterator(
    ForwardIterator begin, ForwardIterator end, size_t width = 0, size_t stride = 0
) {
    using DataType = typename ForwardIterator::value_type;
 
    // Set functors.
    auto it = SlidingIntervalWindowIterator<ForwardIterator>( begin, end );
    it.entry_input_function = []( DataType const& variant ) {
        return variant;
    };
    it.chromosome_function = []( DataType const& variant ) {
        return variant.chromosome;
    };
    it.position_function = []( DataType const& variant ) {
        return variant.position;
    };
 
    // Set properties.
    it.width( width );
    it.stride( stride );
    return it;
}
 
} // namespace population
} // namespace genesis
 
#endif // include guard