SeqAn3 Index

index_tree_concepts.hpp

#pragma once

#include "index_tree_iter_concepts.hpp"

namespace seqan3
{

template <typename t>
concept bool index_tree_concept = requires(t tree)
{
    typename t::tree_iter_type; // TODO
    typename t::trie_iter_type;

    typename t::char_type;
    typename t::text_size_type;

    // requires alphabet_concept<typename t::char_type>;
    requires index_tree_iter_concept<typename t::tree_iter_type>;
    requires index_tree_iter_concept<typename t::trie_iter_type>; // TODO

    (uint8_t)t::levels; // TODO
    (bool)t::is_bidirectional;

    // TODO: constructors?

    { tree.tree_root() } -> typename t::tree_iter_type;
    { tree.trie_root() } -> typename t::trie_iter_type;

    // template <typename archive_type>
    // { tree.serialize(archive_type) } -> void;  // throws exception

    // template <typename construction_policy_t>
    // { tree.construct(typename t::text_type const &, construction_policy_t const &) } -> void;  // throws exception
    // TODO
    // requires requires (t tree, typename t::text_type const & text) { { tree.construct(text) } -> void; }; // throws exception
};

} // namespace seqan3

index_tree_iter_concepts.hpp

#pragma once

#include "index_tree_concepts.hpp"

#include <vector>

namespace seqan3
{

template <typename t>
constexpr bool index_tree_concept;

template <typename t>
constexpr bool index_tree_iter_node_concept;

template <typename t>
concept bool index_tree_iter_concept = requires (t it)
{
    typename t::index_type;
    typename t::iter_node_type;

    requires index_tree_concept<typename t::index_type>;
    requires index_tree_iter_node_concept<typename t::iter_node_type>;

    // TODO: constructors
    // requires requires (t it, typename t::index_type const & index) { it(index) };

    { it.go_down()                                                 } -> bool;
    { it.go_down(typename t::index_type::char_type{})              } -> bool;
    { it.go_down(std::vector<typename t::index_type::char_type>{}) } -> bool;
    { it.go_right()                                                } -> bool;
    { it.is_leaf()                                                 } -> bool;
    { *it                                                          } -> typename t::iter_node_type &;
};

template <typename t>
concept bool index_tree_iter_node_concept = requires (t n)
{
    typename t::iter_type;

    typename t::text_pos_type;
    typename t::edge_label_type;
    typename t::search_depth_size_type;
    typename t::path_label_type; // TODO: view of range library

    requires index_tree_iter_concept<typename t::iter_type>;

    { n.edge_label()        } -> typename t::edge_label_type;
    { n.path_label()        } -> typename t::path_label_type;
    { n.path_label_length() } -> typename t::search_depth_size_type;

    // { it.count()  } -> typename t::text_size_type; // TODO: rename. don't use verbs since there is no effect
    // { it.locate() } -> std::vector<typename t::text_pos_type>;
    // ...
};

template <typename t>
concept bool bi_index_tree_iter_concept = requires (t it)
{
    requires index_tree_iter_concept<t>;
    requires t::is_bidirectional;

    { it.go_down_inv()    } -> bool;
    { it.go_right_inv()   } -> bool;

    { it.edge_label_inv() } -> typename t::edge_label_type;
    { it.is_leaf_inv()    } -> bool;
};

} // namespace seqan3

iter.hpp

namespace seqan3
{

template <typename tree_iter_type>
struct tree_iter_node
{
    std::pair<typename tree_iter_type::index_type::text_size_type, typename tree_iter_type::index_type::text_size_type> range;
    typename tree_iter_type::edge_label_type last_char; // TODO: rename
    typename tree_iter_type::search_depth_size_type path_label_length;

    bool operator!=(const tree_iter_node<tree_iter_type> & other)
    {
        return
            this->range == other.range &&
            this->last_char == other.last_char &&
            this->path_label_length == other.path_label_length;
    }
};

template <typename iter_t>
class iter_node
{

};

template <typename index_t>
class index_tree_iter
{
public:
    using index_type = index_t;
    using iter_node_type = iter_node<index_tree_iter<index_type> >;

    index_tree_iter(index_type const & _index) : index(_index) {}

    // rule of six constructors
    index_tree_iter() = delete;
    index_tree_iter(index_tree_iter const &) = default;
    index_tree_iter & operator=(index_tree_iter const &) = default;
    index_tree_iter(index_tree_iter &&) = default;
    index_tree_iter & operator=(index_tree_iter &&) = default;

    // requires requires (t it, typename t::index_type::char_type const & c) { { it.go_down(c) } -> bool; };
    // { it.go_down(std::vector<t::index_type::char_type>{}) } -> bool;
    // { it.go_right() } -> bool;
    // { it.is_leaf()  } -> bool;
    // { *it           } -> typename t::iter_node_type &;

    bool go_down()
    {
        // ...
        return true;
    }

    bool go_down(typename index_type::char_type const & pattern)
    {
        // ...
        return true;
    }

    bool go_down(std::vector<typename index_type::char_type> const & pattern)
    {
        // ...
        return true;
    }

    bool go_right()
    {
        // ...
        return true;
    }

    bool is_leaf()
    {
        // ...
        return true;
    }

    iter_node_type & operator*()
    {
        return node;
    }

protected:
    index_type index;
    std::pair<typename index_type::text_size_type, typename index_type::text_size_type> parent_range;
    iter_node_type node;
};

} // namespace seqan3

tree.hpp

namespace seqan3
{

template <typename char_t, uint8_t LEVELS>
class fm_index
{
public:
    using char_type = char_t;
    using text_size_type = uint32_t;

    using tree_iter_type = index_tree_iter<fm_index<char_type, LEVELS> >;
    using trie_iter_type = index_tree_iter<fm_index<char_type, LEVELS> >; // TODO

    static const bool is_bidirectional = false;
    static const uint8_t levels = LEVELS;

    tree_iter_type tree_root()
    {
        tree_iter_type iter(*this);
        // ...
        return iter;
    }

    trie_iter_type trie_root()
    {
        trie_iter_type iter(*this);
        // ...
        return iter;
    }

    void serialize(int)
    {
        // ...
    }

    // void construct(text_type const & text)
    // {
    //     // ...
    // }
};

} // namespace seqan3