1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Andreas Gogol-Doering <andreas.doering@mdc-berlin.de>
33 // Author: David Weese <david.weese@fu-berlin.de>
34 // ==========================================================================
35 // Implementation of the StringSet specialization Dependent<Generous>.
36 // ==========================================================================
37
38 #ifndef SEQAN_SEQUENCE_STRING_SET_DEPENDENT_GENEROUS_H_
39 #define SEQAN_SEQUENCE_STRING_SET_DEPENDENT_GENEROUS_H_
40
41 namespace seqan {
42
43 // ============================================================================
44 // Forwards
45 // ============================================================================
46
47 // ============================================================================
48 // Tags, Classes, Enums
49 // ============================================================================
50
51 /*!
52 * @class GenerousDependentStringSet Generous Dependent StringSet
53 * @extends DependentStringSet
54 * @headerfile <seqan/sequence.h>
55 * @brief Dependent StringSet implementation with efficient sequence access by sequence id.
56 *
57 * @signature template <typename TString>
58 * class StringSet<TString, Depedent<Generous> >;
59 *
60 * @tparam TString The type of the string to store in the string set.
61 *
62 * See @link TightDependentStringSet @endlink for a Dependent StringSet implementation with a more memory efficient
63 * representation at higher costs for by-id element access.
64 */
65
66 // The Dddoc documentation of the Dependent specialization is in string_set_tight.h
67 // since Tight is the default specialization of Dependent.
68
69 // StringSet with individual sequences in a string of string pointers
70 template <typename TString>
71 class StringSet<TString, Dependent<Generous> >
72 {
73 public:
74 typedef String<TString *> TStrings;
75 typedef typename Size<StringSet>::Type TSize;
76 typedef typename StringSetLimits<StringSet>::Type TLimits;
77 typedef typename Concatenator<StringSet>::Type TConcatenator;
78
79 TStrings strings;
80 TLimits limits;
81 bool limitsValid; // is true if limits contains the cumulative sum of the sequence lengths
82 TConcatenator concat;
83
StringSet()84 StringSet() :
85 limitsValid(true)
86 {
87 _initStringSetLimits(*this);
88 }
89
90 template <typename TDefault>
StringSet(StringSet<TString,Owner<TDefault>> const & _other)91 StringSet(StringSet<TString, Owner<TDefault> > const& _other) :
92 limitsValid(true)
93 {
94 _initStringSetLimits(*this);
95 for (unsigned int i = 0; i < length(_other); ++i)
96 appendValue(*this, _other[i]);
97 }
98
99 // ----------------------------------------------------------------------
100 // Subscription operators; have to be defined in class def.
101 // ----------------------------------------------------------------------
102
103 template <typename TPos>
104 inline typename Reference<StringSet>::Type
105 operator[] (TPos pos)
106 {
107 return value(*this, pos);
108 }
109
110 template <typename TPos>
111 inline typename Reference<StringSet const>::Type
112 operator[] (TPos pos) const
113 {
114 return value(*this, pos);
115 }
116 };
117
118 // ============================================================================
119 // Metafunctions
120 // ============================================================================
121
122 // ============================================================================
123 // Functions
124 // ============================================================================
125
126 // --------------------------------------------------------------------------
127 // Function appendValue()
128 // --------------------------------------------------------------------------
129
130 template <typename TString, typename TExpand >
appendValue(StringSet<TString,Dependent<Generous>> & me,TString const & obj,Tag<TExpand> tag)131 inline void appendValue(
132 StringSet<TString, Dependent<Generous> > & me,
133 TString const & obj,
134 Tag<TExpand> tag)
135 {
136 SEQAN_CHECKPOINT;
137 appendValue(me.limits, lengthSum(me) + length(obj), tag);
138 appendValue(me.strings, const_cast<TString*>(&obj), tag);
139 }
140
141 // --------------------------------------------------------------------------
142 // Function clear()
143 // --------------------------------------------------------------------------
144
145 template <typename TString >
clear(StringSet<TString,Dependent<Generous>> & me)146 inline void clear(StringSet<TString, Dependent<Generous> > & me)
147 {
148 SEQAN_CHECKPOINT;
149 clear(me.strings);
150 resize(me.limits, 1, Exact());
151 me.limitsValid = true;
152 }
153
154 // --------------------------------------------------------------------------
155 // Function length()
156 // --------------------------------------------------------------------------
157
158 template <typename TString >
159 inline typename Size<StringSet<TString, Dependent<Generous> > >::Type
length(StringSet<TString,Dependent<Generous>> & me)160 length(StringSet<TString, Dependent<Generous> > & me)
161 {
162 return length(me.limits) - 1;
163 }
164
165 // --------------------------------------------------------------------------
166 // Function value()
167 // --------------------------------------------------------------------------
168
169 template <typename TString, typename TPos >
170 inline typename Reference<StringSet<TString, Dependent<Generous> > >::Type
value(StringSet<TString,Dependent<Generous>> & me,TPos pos)171 value(StringSet<TString, Dependent<Generous> >& me, TPos pos)
172 {
173 SEQAN_CHECKPOINT;
174 unsigned i = _findIthNonZeroValue(me.strings, pos);
175 if (i <length(me.strings))
176 return *me.strings[i];
177 static TString tmp = "";
178 return tmp;
179 }
180
181 template <typename TString, typename TPos >
182 inline typename Reference<StringSet<TString, Dependent<Generous> > const >::Type
value(StringSet<TString,Dependent<Generous>> const & me,TPos pos)183 value(StringSet<TString, Dependent<Generous> > const & me, TPos pos)
184 {
185 SEQAN_CHECKPOINT;
186 unsigned i = _findIthNonZeroValue(me.strings, pos);
187 if (i < length(me.strings))
188 return *me.strings[i];
189 static TString tmp = "";
190 return tmp;
191 }
192
193 // --------------------------------------------------------------------------
194 // Function getValueById()
195 // --------------------------------------------------------------------------
196
197 template <typename TString, typename TId>
198 inline typename Reference<StringSet<TString, Dependent<Generous> > >::Type
getValueById(StringSet<TString,Dependent<Generous>> & me,TId const id)199 getValueById(StringSet<TString, Dependent<Generous> >& me,
200 TId const id)
201 {
202 SEQAN_CHECKPOINT;
203 if (me.strings[id])
204 return *me.strings[id];
205 static TString tmp = "";
206 return tmp;
207 }
208
209 // --------------------------------------------------------------------------
210 // Function assignValueById()
211 // --------------------------------------------------------------------------
212
213 template<typename TString, typename TId>
214 inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
assignValueById(StringSet<TString,Dependent<Generous>> & me,TString & obj,TId id)215 assignValueById(StringSet<TString, Dependent<Generous> >& me,
216 TString& obj,
217 TId id)
218 {
219 SEQAN_CHECKPOINT;
220 SEQAN_ASSERT_EQ(length(stringSetLimits(me)), length(me) + 1);
221 if (id >= (TId) length(me.strings)) resize(me.strings, id+1, (TString*) 0);
222 if ((TString*) me.strings[id] == (TString*) 0)
223 resize(me.limits, length(me.limits) + 1, Generous());
224 me.strings[id] = &obj;
225 me.limitsValid = false;
226 SEQAN_ASSERT_EQ(length(stringSetLimits(me)), length(me) + 1);
227 return id;
228 }
229
230 // --------------------------------------------------------------------------
231 // Function removeValueById()
232 // --------------------------------------------------------------------------
233
234 template<typename TString, typename TId>
235 inline void
removeValueById(StringSet<TString,Dependent<Generous>> & me,TId const id)236 removeValueById(StringSet<TString, Dependent<Generous> >& me, TId const id)
237 {
238 SEQAN_CHECKPOINT;
239 if (me.strings[id] != (TString*) 0)
240 {
241 resize(me.limits, length(me.limits) - 1, Generous());
242 me.limitsValid = empty(me);
243 }
244 me.strings[id] = 0;
245 while (!empty(me.strings) && !me.strings[length(me.strings) - 1])
246 resize(me.strings, length(me.strings) - 1, Generous());
247 }
248
249 // --------------------------------------------------------------------------
250 // Function positionToId()
251 // --------------------------------------------------------------------------
252
253 template <typename TString, typename TPos>
254 inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
positionToId(StringSet<TString,Dependent<Generous>> & me,TPos const pos)255 positionToId(StringSet<TString, Dependent<Generous> >& me,
256 TPos const pos)
257 {
258 SEQAN_CHECKPOINT;
259 return _findIthNonZeroValue(me.strings,pos);
260 }
261
262 template <typename TString, typename TPos>
263 inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
positionToId(StringSet<TString,Dependent<Generous>> const & me,TPos const pos)264 positionToId(StringSet<TString, Dependent<Generous> > const& me,
265 TPos const pos)
266 {
267 SEQAN_CHECKPOINT;
268 return _findIthNonZeroValue(me.strings,pos);
269 }
270
271 // --------------------------------------------------------------------------
272 // Function idToPosition()
273 // --------------------------------------------------------------------------
274
275 template <typename TString, typename TId>
276 inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
idToPosition(StringSet<TString,Dependent<Generous>> const & me,TId const id)277 idToPosition(StringSet<TString, Dependent<Generous> > const& me,
278 TId const id)
279 {
280 SEQAN_CHECKPOINT;
281 return _countNonZeroValues(me.strings,id);
282 }
283
284 } // namespace seqan
285
286 #endif // #ifndef SEQAN_SEQUENCE_STRING_SET_DEPENDENT_GENEROUS_H_
287