#include <zip_code_tree.hpp>

Public Types
enum	State { S_START, S_SCAN_CHAIN, S_SCAN_DAG_SNARL, S_SCAN_CYCLIC_SNARL }

Public Member Functions
	distance_iterator (size_t start_index, const vector< tree_item_t > &zip_code_tree, std::stack< size_t > chain_numbers=std::stack< size_t >(), bool right_to_left=true, size_t distance_limit=std::numeric_limits< size_t >::max())

distance_iterator &	operator++ ()
	Move in right_to_left direction until we hit another seed or the end. More...

void	move_index ()
	Move index in right_to_left direction. More...

bool	operator== (const distance_iterator &other) const

bool	operator!= (const distance_iterator &other) const
	Compare for inequality. More...

bool	done () const
	Is the iteration done? More...

seed_result_t	operator* () const

Private Member Functions
void	push (size_t value)
	Push a value to the stack. More...

size_t	pop ()
	Pop a value from the stack and return it. More...

size_t &	top ()
	Get a mutable reference to the value on top of the stack. More...

void	dup ()
	Duplicate the top item on the stack. More...

size_t	depth () const
	Check stack depth. More...

void	swap ()
	Reverse the top two elements of the stack. More...

void	stack_snarl_distances (size_t snarl_start_i, size_t chain_num, bool right_side)

void	stack_matrix_value (size_t matrix_start_i, bool has_main_diagonal, size_t row, size_t col)

void	stack_below_top (size_t value)

void	state (State new_state)
	Adopt a new state. More...

void	halt ()

void	unimplemented_error ()
	Throw a domain_error that the current state/symbol combo is unimplemented. More...

tree_item_t	current_item () const
	What item does index point to? More...

bool	entered_snarl () const

bool	exited_snarl () const

bool	entered_chain () const

bool	exited_chain () const

void	skip_chain ()

void	initialize_chain ()

bool	initialize_snarl (size_t chain_num)

void	continue_snarl ()

bool	tick ()

Private Attributes
size_t	index
	Where we are in the stored tree. More...

const size_t	end_index
	Where we have to stop. More...

const size_t	original_index
	Where we started from. More...

std::stack< size_t >	chain_numbers
	Within each parent snarl, which chain are we in? More...

size_t	distance_limit
	Distance limit we will go up to. More...

bool	right_to_left
	Whether we are looking right to left (true) or left to right (false) More...

const bool	original_right_to_left
	Original direction. More...

const vector< tree_item_t > &	zip_code_tree
	References to the zip code tree to let us look up distance matrices. More...

std::stack< size_t >	stack_data
	Stack for computing distances. More...

State	current_state
	Current state of the automaton. More...

Detailed Description

Iterator that looks sideways in the tree from a seed, possibly up to a maximum base distance.

Iteration flow:

Original Python implementation: https://github.com/benedictpaten/long_read_giraffe_chainer_prototype/blob/b590c34055474b0c901a681a1aa99f1651abb6a4/zip_tree_iterator.py.

New cyclic snarl handling flowchart: https://docs.google.com/drawings/d/1diKMXCuMteR06fF64BhSttsD5RHh3eTnd8FtyYqs17Y/edit?usp=sharing

In order to de-duplicate work, this iterator will not actually look at everything before it. If it knows that seeds from a given chain would have already output transitions to its own position, then it won't even look at anything in that chain. This occurs in cyclic snarls.

For example, since previous chains in a cyclic snarl will have already visited all other chains, later chains do not have to visit previous ones. Similarly, when the traversal enters a cyclic snarl, it only has to handle the chains going in the opposite orientation, since the ones in the same orientation will have already seen the traversal's starting position by exiting the snarl.

Member Enumeration Documentation

◆ State

enum vg::ZipCodeTree::distance_iterator::State

Type for the state of the I-can't-believe-it's-not-a-pushdown-automaton

Enumerator
S_START
S_SCAN_CHAIN
S_SCAN_DAG_SNARL
S_SCAN_CYCLIC_SNARL

Constructor & Destructor Documentation

◆ distance_iterator()

vg::ZipCodeTree::distance_iterator::distance_iterator	(	size_t	start_index,
		const vector< tree_item_t > &	zip_code_tree,
		std::stack< size_t >	chain_numbers = `std::stack<size_t>()`,
		bool	right_to_left = `true`,
		size_t	distance_limit = `std::numeric_limits<size_t>::max()`
	)

Make a reverse iterator starting from start_index, until the given rend, with the given distance limit.

Member Function Documentation

◆ continue_snarl()

void vg::ZipCodeTree::distance_iterator::continue_snarl ( )

private

Decide what to do when re-entering a snarl, having already stacked up distances

◆ current_item()

tree_item_t vg::ZipCodeTree::distance_iterator::current_item ( ) const

inlineprivate

What item does index point to?

◆ depth()

auto vg::ZipCodeTree::distance_iterator::depth ( ) const

private

Check stack depth.

◆ done()

bool vg::ZipCodeTree::distance_iterator::done ( ) const

inline

Is the iteration done?

◆ dup()

auto vg::ZipCodeTree::distance_iterator::dup ( )

private

Duplicate the top item on the stack.

◆ entered_chain()

bool vg::ZipCodeTree::distance_iterator::entered_chain ( ) const

inlineprivate

◆ entered_snarl()

bool vg::ZipCodeTree::distance_iterator::entered_snarl ( ) const

inlineprivate

Check if the current symbol is an entrance/exit, based on the direction the iterator is going (right_to_left)

◆ exited_chain()

bool vg::ZipCodeTree::distance_iterator::exited_chain ( ) const

inlineprivate

◆ exited_snarl()

bool vg::ZipCodeTree::distance_iterator::exited_snarl ( ) const

inlineprivate

◆ halt()

auto vg::ZipCodeTree::distance_iterator::halt ( )

private

Stop parsing because nothing else can be below the distance limit. This moves the current iterator it.

◆ initialize_chain()

void vg::ZipCodeTree::distance_iterator::initialize_chain ( )

private

Decide what to do right after entering a new chain. This chain's distance should be on top of the stack.

◆ initialize_snarl()

bool vg::ZipCodeTree::distance_iterator::initialize_snarl ( size_t chain_num )

private

Decide what to do right after entering a new snarl. Return whether the initialization was successful, i.e. whether the snarl was a non-root snarl.

◆ move_index()

void vg::ZipCodeTree::distance_iterator::move_index ( )

inline

Move index in right_to_left direction.

◆ operator!=()

bool vg::ZipCodeTree::distance_iterator::operator!= ( const distance_iterator & other ) const

inline

Compare for inequality.

◆ operator*()

auto vg::ZipCodeTree::distance_iterator::operator* ( ) const

Get the index and orientation of the seed we are currently at, and the distance to it. Automatically handles orientation depending on right_to_left

◆ operator++()

auto vg::ZipCodeTree::distance_iterator::operator++ ( )

Move in right_to_left direction until we hit another seed or the end.

◆ operator==()

bool vg::ZipCodeTree::distance_iterator::operator== ( const distance_iterator & other ) const

inline

Compare for equality to see if we hit end This just trusts that the two iterators are for the same tree

◆ pop()

auto vg::ZipCodeTree::distance_iterator::pop ( )

private

Pop a value from the stack and return it.

◆ push()

auto vg::ZipCodeTree::distance_iterator::push ( size_t value )

private

Push a value to the stack.

◆ skip_chain()

void vg::ZipCodeTree::distance_iterator::skip_chain ( )

private

Skip the current chain, jumping to the matching end and then one past it to continue the snarl Bound pair index should be right below current distance

◆ stack_below_top()

void vg::ZipCodeTree::distance_iterator::stack_below_top ( size_t value )

private

Helper for stack_snarl_distances() Stack a single value below the running distance

◆ stack_matrix_value()

void vg::ZipCodeTree::distance_iterator::stack_matrix_value	(	size_t	matrix_start_i,
		bool	has_main_diagonal,
		size_t	row,
		size_t	col
	)

private

Helper for stack_snarl_distances() Stack a single value from a triangular distance matrix

◆ stack_snarl_distances()

void vg::ZipCodeTree::distance_iterator::stack_snarl_distances	(	size_t	snarl_start_i,
		size_t	chain_num,
		bool	right_side
	)

private

Push distances relevant to a given chain onto the stack chain_num is one-indexed, so the first chain is 1, and the last is N right_side indicates if distances exit from the right or left side

◆ state()

void vg::ZipCodeTree::distance_iterator::state ( State new_state )

inlineprivate

Adopt a new state.

◆ swap()

auto vg::ZipCodeTree::distance_iterator::swap ( )

private

Reverse the top two elements of the stack.

◆ tick()

auto vg::ZipCodeTree::distance_iterator::tick ( )

private

Tick the automaton, looking at the symbol at *it and updating the stack and current_state. Returns true to yield a value at the current symbol, or to halt, and false otherwise.

◆ top()

auto vg::ZipCodeTree::distance_iterator::top ( )

private

Get a mutable reference to the value on top of the stack.

◆ unimplemented_error()

void vg::ZipCodeTree::distance_iterator::unimplemented_error ( )

private

Throw a domain_error that the current state/symbol combo is unimplemented.

Member Data Documentation

◆ chain_numbers

std::stack<size_t> vg::ZipCodeTree::distance_iterator::chain_numbers

private

Within each parent snarl, which chain are we in?

◆ current_state

State vg::ZipCodeTree::distance_iterator::current_state

private

Current state of the automaton.

◆ distance_limit

size_t vg::ZipCodeTree::distance_iterator::distance_limit

private

Distance limit we will go up to.

◆ end_index

const size_t vg::ZipCodeTree::distance_iterator::end_index

private

Where we have to stop.

◆ index

size_t vg::ZipCodeTree::distance_iterator::index

private

Where we are in the stored tree.

◆ original_index

const size_t vg::ZipCodeTree::distance_iterator::original_index

private

Where we started from.

◆ original_right_to_left

const bool vg::ZipCodeTree::distance_iterator::original_right_to_left

private

Original direction.

◆ right_to_left

bool vg::ZipCodeTree::distance_iterator::right_to_left

private

Whether we are looking right to left (true) or left to right (false)

◆ stack_data

std::stack<size_t> vg::ZipCodeTree::distance_iterator::stack_data

private

Stack for computing distances.

◆ zip_code_tree

const vector<tree_item_t>& vg::ZipCodeTree::distance_iterator::zip_code_tree

private

References to the zip code tree to let us look up distance matrices.

The documentation for this class was generated from the following files:

src/zip_code_tree.hpp
src/zip_code_tree.cpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ State

Constructor & Destructor Documentation

◆ distance_iterator()

Member Function Documentation

◆ continue_snarl()

◆ current_item()

◆ depth()

◆ done()

◆ dup()

◆ entered_chain()

◆ entered_snarl()

◆ exited_chain()

◆ exited_snarl()

◆ halt()

◆ initialize_chain()

◆ initialize_snarl()

◆ move_index()

◆ operator!=()

◆ operator*()

◆ operator++()

◆ operator==()

◆ pop()

◆ push()

◆ skip_chain()

◆ stack_below_top()

◆ stack_matrix_value()

◆ stack_snarl_distances()

◆ state()

◆ swap()

◆ tick()

◆ top()

◆ unimplemented_error()

Member Data Documentation

◆ chain_numbers

◆ current_state

◆ distance_limit

◆ end_index

◆ index

◆ original_index

◆ original_right_to_left

◆ right_to_left

◆ stack_data

◆ zip_code_tree