sequence_map.h
Go to the documentation of this file.00001 #ifndef Sequence_Map_h_included
00002 #define Sequence_Map_h_included
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00039
00040 #include <cxxtls/hash_list.h>
00041 #include <iostream>
00042 #include <stdlib.h>
00043
00044 namespace cxxtls
00045 {
00046
00047 template<class T, class ID, class H = Hasher<T> >
00048 class Sequence_Map
00165 {
00166 public:
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183 typedef Sequence_Map<T,ID,H> self;
00184
00185 struct node;
00186
00187
00188
00189 typedef hash_list<T,node*,H> rest_type;
00190
00191
00192
00193 struct node
00194 : public rest_type
00195 {
00196
00197 };
00198
00199 struct H1
00200 {
00201 int operator() (node* n)
00202 {
00203 union
00204 {
00205 node *n1;
00206 int i1;
00207 } junk;
00208
00209 junk.n1 = n;
00210
00211 return junk.i1;
00212 }
00213 };
00214
00215
00216 typedef hash_list<node*,ID,H1> id_map_type;
00217
00218 Sequence_Map() {}
00219
00221
00222 ~Sequence_Map() { destroy_tree(); }
00223
00225
00226 bool find(T const *first, size_t count, ID *id)
00227
00228
00229
00230
00231 {
00232 if(count == 0)
00233 return false;
00234
00235 search c(*this);
00236
00237 while(count && c(*first))
00238 {
00239 ++first;
00240 --count;
00241 ++c;
00242 }
00243
00244 if(count != 0)
00245 return false;
00246
00247 if(c.finished(id))
00248 return true;
00249
00250 return false;
00251
00252 }
00253
00254 template<class Iterator>
00255 bool find(Iterator first, Iterator last, ID *id)
00256
00257
00258
00259
00260
00261 {
00262 search c(*this);
00263
00264 while(first != last && c(*first))
00265 {
00266 ++first;
00267 ++c;
00268 }
00269
00270 if(first != last)
00271 return false;
00272
00273 if(c.finished(id))
00274 return true;
00275
00276 return false;
00277 }
00278
00279 class search
00280
00292 {
00293 self* tree_;
00294 node* scan_;
00295 node* next_;
00296
00297 public:
00298
00299 search(self &tree)
00300 : tree_(&tree),
00301 scan_((node*)(&tree.root_)),
00302 next_(0)
00303 {
00306 }
00307
00308 bool operator() (T const & value)
00309 {
00312
00313
00314
00315
00316
00317
00318 next_ = 0;
00319
00320 if(scan_->size() == 0)
00321 return false;
00322
00323 typename rest_type::iterator where = scan_->find(value);
00324
00325 if(where == scan_->end())
00326 return false;
00327
00328 next_ = where->data_.second;
00329
00330 return true;
00331
00332 }
00333
00334 void operator++()
00335 {
00343
00344 if(next_ == 0)
00345 {
00346 std::cerr << "Error, can't increment search till you match an item" << std::endl;
00347 std::cerr << " see " << __FILE__ << ":" << __LINE__ << std::endl;
00348 exit(1);
00349 }
00350
00351 scan_ = next_;
00352 next_ = 0;
00353
00354 }
00355
00356 bool finished(ID* id)
00357 {
00362
00363 if(scan_->size() == 0)
00364 {
00365 typename id_map_type::iterator f = tree_->ids_.find(scan_);
00366
00367 if(f != tree_->ids_.end())
00368 {
00369 *id = f->data_.second;
00370 return true;
00371 }
00372
00373 }
00374
00375 return false;
00376
00377 }
00378 };
00379
00380
00381 class sequence
00382
00389 {
00390 public:
00391 typedef Sequence_Map<T,ID,H> seq_map;
00392
00393 private:
00394
00395 seq_map* tree_;
00396 ID id_;
00397 node* scan_;
00398
00399
00400 public:
00401
00402 sequence(seq_map& tree, ID const &v)
00403 : id_(v),
00404 scan_((node*)(&tree.root_))
00405 {
00407
00408 tree_ = &tree;
00409 }
00410
00411
00412 ~sequence()
00413 {
00415 }
00416
00417 bool complete() const
00418 {
00430
00431 if(scan_->size() != 0)
00432 return false;
00433
00434 tree_->ids_[scan_] = id_;
00435
00436 return true;
00437 }
00438
00439 void operator+= (T const &new_item)
00440 {
00441
00450
00451 typename id_map_type::iterator where = tree_->ids_.find(scan_);
00452
00453 if(where != tree_->ids_.end())
00454 {
00455 std::cerr << "Error, you can't extend a complete sequence" << std::endl;
00456 std::cerr << " see " << __FILE__ << ":" << __LINE__ << std::endl;
00457 exit(1);
00458 }
00459
00460 typename rest_type::iterator f = scan_->find(new_item),
00461 e = scan_->end();
00462
00463 if(f != e)
00464 {
00465
00466
00467 scan_ = f->data_.second;
00468
00469 }
00470 else
00471 {
00472
00473
00474 node* next_node = (node*)(new rest_type);
00475
00476 typedef typename rest_type::mapped_type entry_type;
00477
00478 scan_->insert( entry_type(new_item, next_node) );
00479
00480 scan_ = next_node;
00481 }
00482
00483 }
00484
00485 bool can_complete() const
00486 {
00490
00491 if(scan_->size() != 0)
00492 return false;
00493
00494 if(scan_ == &tree_->root_)
00495 return false;
00496
00497 return true;
00498 }
00499
00500 };
00501
00502
00503 private:
00504
00505 friend class sequence;
00506 friend class search;
00507
00508 rest_type root_;
00509 id_map_type ids_;
00510
00511 void destroy_tree()
00513 {
00514 typename rest_type::iterator f = root_.begin(),
00515 l = root_.end();
00516
00517 while(f != l)
00518 {
00519 typename rest_type::mapped_type &r = f->data_;
00520
00521 node* n = r.second;
00522
00523 delete n;
00524
00525 ++f;
00526
00527 }
00528 }
00529
00530 };
00531
00532 }
00533
00534
00535 #endif