Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
FullAndLinearIndex.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <alib/string>
27
29
31
33
34namespace indexes {
35
36namespace arbology {
37
38class GeneralAlphabet;
39
48template < class SymbolType = DefaultSymbolType, template < typename > class StringIndex = indexes::stringology::PositionHeap >
49class FullAndLinearIndex final {
53 StringIndex < common::ranked_symbol < SymbolType > > m_StringIndex;
54
58 ext::vector < int > m_JumpTable;
59
60public:
67 explicit FullAndLinearIndex ( StringIndex < common::ranked_symbol < SymbolType > > stringIndex, ext::vector < int > jumpTable );
68
74 const StringIndex < common::ranked_symbol < SymbolType > > & getStringIndex ( ) const &;
75
81 StringIndex < common::ranked_symbol < SymbolType > > && getStringIndex ( ) &&;
82
88 const ext::vector < int > & getJumps ( ) const &;
89
96
103 return m_StringIndex.getAlphabet ( );
104 }
105
112 return std::move ( m_StringIndex ).getAlphabet ( );
113 }
114
120 void setStringIndex ( StringIndex < common::ranked_symbol < SymbolType > > stringIndex );
121
128 return m_StringIndex.removeSymbolFromAlphabet ( symbol );
129 }
130
138 auto operator <=> ( const FullAndLinearIndex & other ) const {
139 return std::tie ( getStringIndex ( ), getJumps ( ) ) <=> std::tie ( other.getStringIndex ( ), other.getJumps ( ) );
140 }
141
149 bool operator == ( const FullAndLinearIndex & other ) const {
150 return std::tie ( getStringIndex ( ), getJumps ( ) ) == std::tie ( other.getStringIndex ( ), other.getJumps ( ) );
151 }
152
161 friend ext::ostream & operator << ( ext::ostream & out, const FullAndLinearIndex & instance ) {
162 return out << "(FullAndLinearIndex " << instance.m_StringIndex << ", " << instance.m_JumpTable << ")";
163 }
164};
165
166} /* namespace arbology */
167
168} /* namespace indexes */
169
170namespace indexes {
171
172namespace arbology {
173
174template < class SymbolType, template < typename > class StringIndex >
175FullAndLinearIndex < SymbolType, StringIndex >::FullAndLinearIndex ( StringIndex < common::ranked_symbol < SymbolType > > stringIndex, ext::vector < int > jumpTable ) : m_StringIndex ( std::move ( stringIndex ) ), m_JumpTable ( std::move ( jumpTable ) ) {
176}
177
178template < class SymbolType, template < typename > class StringIndex >
179const StringIndex < common::ranked_symbol < SymbolType > > & FullAndLinearIndex < SymbolType, StringIndex >::getStringIndex ( ) const & {
180 return m_StringIndex;
181}
182
183template < class SymbolType, template < typename > class StringIndex >
184StringIndex < common::ranked_symbol < SymbolType > > && FullAndLinearIndex < SymbolType, StringIndex >::getStringIndex ( ) && {
185 return std::move ( m_StringIndex );
186}
187
188template < class SymbolType, template < typename > class StringIndex >
190 return m_JumpTable;
191}
192
193template < class SymbolType, template < typename > class StringIndex >
195 return std::move ( m_JumpTable );
196}
197
198template < class SymbolType, template < typename > class StringIndex >
199void FullAndLinearIndex < SymbolType, StringIndex >::setStringIndex ( StringIndex < common::ranked_symbol < SymbolType > > stringIndex ) {
200 this->m_StringIndex = std::move ( stringIndex );
201}
202
203} /* namespace arbology */
204
205} /* namespace indexes */
206
207namespace core {
208
214template < class SymbolType, template < typename > class StringIndex >
215struct normalize < indexes::arbology::FullAndLinearIndex < SymbolType, StringIndex > > {
217 StringIndex < common::ranked_symbol < > > stringIndex = core::normalize < StringIndex < common::ranked_symbol < SymbolType > > >::eval ( std::move ( value ).getStringIndex ( ) );
218
219 return indexes::arbology::FullAndLinearIndex < > ( std::move ( stringIndex ), std::move ( value ).getJumps ( ) );
220 }
221};
222
223} /* namespace core */
224
Definition: ranked_symbol.hpp:20
Definition: ostream.h:14
Definition: set.hpp:44
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
Full and linear tree index. The index serves as a adaptor of string index so that searching for tree ...
Definition: FullAndLinearIndex.h:49
void setStringIndex(StringIndex< common::ranked_symbol< SymbolType > > stringIndex)
Definition: FullAndLinearIndex.h:199
auto operator<=>(const FullAndLinearIndex &other) const
Definition: FullAndLinearIndex.h:138
ext::set< common::ranked_symbol< SymbolType > > && getAlphabet() &&
Definition: FullAndLinearIndex.h:111
friend ext::ostream & operator<<(ext::ostream &out, const FullAndLinearIndex &instance)
Definition: FullAndLinearIndex.h:161
const StringIndex< common::ranked_symbol< SymbolType > > & getStringIndex() const &
Definition: FullAndLinearIndex.h:179
const ext::vector< int > & getJumps() const &
Definition: FullAndLinearIndex.h:189
FullAndLinearIndex(StringIndex< common::ranked_symbol< SymbolType > > stringIndex, ext::vector< int > jumpTable)
Definition: FullAndLinearIndex.h:175
const ext::set< common::ranked_symbol< SymbolType > > & getAlphabet() const &
Definition: FullAndLinearIndex.h:102
bool removeSymbolFromAlphabet(const common::ranked_symbol< SymbolType > &symbol)
Definition: FullAndLinearIndex.h:127
bool operator==(const FullAndLinearIndex &other) const
Definition: FullAndLinearIndex.h:149
Position heap string index. Tree like representation of all suffixes. The suffixes are themselves rep...
Definition: PositionHeap.h:56
Definition: BoyerMooreHorspool.h:22
Definition: normalize.hpp:10
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
Definition: CompressedBitParallelTreeIndex.h:40
static indexes::arbology::FullAndLinearIndex< > eval(indexes::arbology::FullAndLinearIndex< SymbolType, StringIndex > &&value)
Definition: FullAndLinearIndex.h:216
Definition: normalize.hpp:13