- メインページ
- モジュール
- ネームスペース
- データ構造
- ファイル

- ファイル一覧
- グローバル

interval_tree.h
説明を見る。
1 //
2 // Copyright (c) 2003-2011, MIST Project, Nagoya University
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without modification,
6 // are permitted provided that the following conditions are met:
7 //
8 // 1. Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 //
11 // 2. Redistributions in binary form must reproduce the above copyright notice,
12 // this list of conditions and the following disclaimer in the documentation
13 // and/or other materials provided with the distribution.
14 //
15 // 3. Neither the name of the Nagoya University nor the names of its contributors
16 // may be used to endorse or promote products derived from this software
17 // without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
26 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 //
28
33
34 #ifndef __INCLUDE_INTERVAL_TREE_H__
35 #define __INCLUDE_INTERVAL_TREE_H__
36
37 #include <iostream>
38 #include <vector>
39 #include <algorithm>
40
41 // mist名前空間の始まり
42 _MIST_BEGIN
43
51
52 template< typename M, typename T > class tagged_section;
53 template< typename M, typename T > class tagged_section_min_less;
54 template< typename M, typename T > class tagged_section_max_greater;
55
91 template< typename S, typename V >
92 class interval_tree
93 {
94 public:
95 typedef S section_type;
96 typedef typename S::min_max_type min_max_type;
97 typedef typename S::tag_type tag_type;
98 typedef V value_type;
99
100 class node;
101
107 void find( const value_type &val, std::vector< tag_type > &tags )
108 {
109 tags.resize( 0 );
110 _find( val, tags, root_ );
111 }
112
118 bool construct( const std::vector< section_type > &secs )
119 {
120 if( root_ != NULL )
121 {
122 destruct( );
123 }
124 if( secs.size( ) > 0 )
125 {
126 size_t tree_size = 0;
127 root_= new node( secs, tree_size );
128 return ( tree_size == secs.size( ) );
129 }
130 destruct( );
131 return false;
132 }
133
135 void destruct( )
136 {
137 if( root_ != NULL )
138 {
139 delete root_;
140 root_ = NULL;
141 }
142 }
143
145 interval_tree( ) : root_( NULL )
146 {
147 }
148
153 interval_tree( const std::vector< section_type > &secs ) : root_( NULL )
154 {
155 construct( secs );
156 }
157
162 interval_tree( const interval_tree< section_type, value_type > &it ) : root_( NULL )
163 {
164 *this = it;
165 }
166
168 ~interval_tree( )
169 {
170 destruct( );
171 }
172
177 interval_tree &operator =( const interval_tree< section_type, value_type > &it )
178 {
179 if( &it == this )
180 {
181 return *this;
182 }
183 else
184 {
185 destruct( );
186 if( it.root_ != NULL )
187 {
188 root_ = new node( *it.root_ );
189 }
190 return *this;
191 }
192 }
193
194 private:
195 void _find( const value_type &val, std::vector< tag_type > &tags, node *p )
196 {
197 if( p != NULL )
198 {
199 if( val < p->val( ) )
200 {
201 for( size_t i = 0 ; i < p->min_inc_secs_size( ) ; i ++ )
202 {
203 if( static_cast< value_type >( p->min_inc_secs( i ).minimum( ) ) > val )
204 {
205 break;
206 }
207 tags.push_back( p->min_inc_secs( i ).tag( ) );
208 }
209 _find( val, tags, p->left( ) );
210 }
211 else if( val > p->val( ) )
212 {
213 for( size_t i = 0 ; i < p->max_dec_secs_size( ) ; i ++ )
214 {
215 if( static_cast< value_type >( p->max_dec_secs( i ).maximum( ) ) <= val )
216 {
217 break;
218 }
219 tags.push_back( p->max_dec_secs( i ).tag( ) );
220 }
221 _find( val, tags, p->right( ) );
222 }
223 else
224 {
225 for( size_t i = 0 ; i < p->min_inc_secs_size( ) ; i ++ )
226 {
227 tags.push_back( p->min_inc_secs( i ).tag( ) );
228 }
229 }
230 }
231 }
232
233 node *root_;
234 };
235
236
246 template< typename M, typename T >
247 class tagged_section
248 {
249 public:
250 typedef M min_max_type;
251 typedef T tag_type;
252
257 const min_max_type &minimum( ) const { return min_; }
258
263 const min_max_type &maximum( ) const { return max_; }
264
269 const tag_type &tag( ) const { return tag_; }
270
275 min_max_type &minimum( ) { return min_; }
276
281 min_max_type &maximum( ) { return max_; }
282
287 tag_type &tag( ) { return tag_; }
288
290 tagged_section( ) : min_( min_max_type( ) ), max_( min_max_type( ) ), tag_( tag_type( ) ) { }
291
298 tagged_section( const min_max_type &min, const min_max_type &max, const tag_type &tag ) : min_( min ), max_( max ), tag_( tag ) { }
299
300 private:
301 min_max_type min_;
302 min_max_type max_;
303 tag_type tag_;
304 };
305
312 template< typename M, typename T >
313 inline std::ostream &operator <<( std::ostream &out, const tagged_section< M, T > &in )
314 {
315 return out << in.tag( ) << " [" << in.minimum( ) << ", " << in.maximum( ) << ")";
316 }
317
319 template< typename M, typename T >
320 class tagged_section_min_less
321 {
322 public:
323 bool operator ( )( const tagged_section< M, T > &s0, const tagged_section< M, T > &s1 ) const { return s0.minimum( ) < s1.minimum( ); }
324 };
325
327 template< typename M, typename T >
328 class tagged_section_max_greater
329 {
330 public:
331 bool operator ( )( const tagged_section< M, T > &s0, const tagged_section< M, T > &s1 ) const { return s0.maximum( ) > s1.maximum( ); }
332 };
333
334
340 template< typename S, typename V >
341 class interval_tree< S, V >::node
342 {
343 friend class interval_tree< S, V >;
344
345 private:
346 const value_type &val( ) const { return val_; }
347 const section_type &min_inc_secs( const size_t i ) const { return min_inc_secs_[ i ]; }
348 const section_type &max_dec_secs( const size_t i ) const { return max_dec_secs_[ i ]; }
349 size_t min_inc_secs_size( ) const { return min_inc_secs_.size( ); }
350 size_t max_dec_secs_size( ) const { return max_dec_secs_.size( ); }
351
352 node *left( ) { return left_; }
353 node *right( ) { return right_; }
354
355 node( const std::vector< section_type > &secs, size_t &tree_size ) : left_( NULL ), right_( NULL )
356 {
357 val_ = middle( secs );
358 std::vector< section_type > l_secs, r_secs;
359 for( size_t i = 0 ; i < secs.size( ) ; i ++ )
360 {
361 if( static_cast< value_type >( secs[ i ].maximum( ) ) <= val_ )
362 {
363 l_secs.push_back( secs[ i ] );
364 continue;
365 }
366 if( static_cast< value_type >( secs[ i ] .minimum( ) ) > val_ )
367 {
368 r_secs.push_back( secs[ i ] );
369 continue;
370 }
371 min_inc_secs_.push_back( secs[ i ] );
372 }
373 tree_size += min_inc_secs_.size( );
374 std::sort( min_inc_secs_.begin( ), min_inc_secs_.end( ), tagged_section_min_less< min_max_type, tag_type >( ) );
375 max_dec_secs_ = min_inc_secs_;
376 std::sort( max_dec_secs_.begin( ), max_dec_secs_.end( ), tagged_section_max_greater< min_max_type, tag_type >( ) );
377 if( l_secs.size( ) > 0 )
378 {
379 left_ = new node( l_secs, tree_size );
380 }
381 if( r_secs.size( ) > 0 )
382 {
383 right_ = new node( r_secs, tree_size );
384 }
385 }
386
387 node( const node &nd ) : left_( NULL ), right_( NULL )
388 {
389 *this = nd;
390 }
391
392 ~node( )
393 {
394 if( left_ != NULL )
395 {
396 delete left_;
397 left_ = NULL;
398 }
399 if( right_ != NULL )
400 {
401 delete right_;
402 right_ = NULL;
403 }
404 }
405
406 node &operator =( const node &nd )
407 {
408 if( &nd == this )
409 {
410 return *this;
411 }
412 else
413 {
414 delete left_;
415 delete right_;
416 val_ = nd.val_;
417 min_inc_secs_ = nd.min_inc_secs_;
418 max_dec_secs_ = nd.max_dec_secs_;
419 if( nd.left_ != NULL )
420 {
421 left_ = new node( *nd.left_ );
422 }
423 if( nd.right_ != NULL )
424 {
425 right_ = new node( *nd.right_ );
426 }
427 return *this;
428 }
429 }
430
431 value_type middle( const std::vector< section_type > &secs ) const
432 {
433 typename section_type::min_max_type minimum = secs[ 0 ].minimum( );
434 typename section_type::min_max_type maximum = secs[ 0 ].maximum( );
435 for( size_t i = 1 ; i < secs.size( ) ; i ++ )
436 {
437 minimum = ( secs[ i ].minimum( ) < minimum ) ? secs[ i ].minimum( ) : minimum;
438 maximum = ( secs[ i ].maximum( ) > maximum ) ? secs[ i ].maximum( ) : maximum;
439 }
440
441 return( static_cast< value_type >( ( minimum + maximum ) / 2.0 ) );
442 }
443
444 value_type val_;
445 std::vector< section_type > min_inc_secs_;
446 std::vector< section_type > max_dec_secs_;
447 node *left_;
448 node *right_;
449 };
450
451
453 // Interval-tree グループの終わり
454
455 // mist名前空間の終わり
456 _MIST_END
457
458 #endif // #ifndef __INCLUDE_INTERVAL_TREE_H__
459