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 // Copyright 2002, Lowell Boggs Jr.
00007 //
00008 // This file or directory, containing source code for a computer program,
00009 // is Copyrighted by Lowell Boggs, Jr.  987 Regency Drive, Lewisville
00010 // TX (USA), 75067.  You may use, copy, modify, and distribute this
00011 // source file without charge or obligation so long as you agree to
00012 // the following:
00013 //
00014 //  1.  You must indemnify Lowell Boggs against any and all financial
00015 //      obligations caused by its use, misuse, function, or malfunction.
00016 //      Further, you acknowledge that there is no warranty of any kind,
00017 //      whatsoever.
00018 //
00019 //  2.  You agree not to attempt to patent any portion of this original
00020 //      work -- though you may attempt to patent your own extensions to
00021 //      it if you so choose.
00022 //
00023 //  3.  You keep this copyright notice with the file and all copies
00024 //      of the file and do not change it anyway except language translation.
00025 //
00026 // You are responsible for enforcing your own compliance with these
00027 // conditions and may not use this source file if you cannot agree to the
00028 // above terms and conditions.
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   //  A sequence map implements a tree of nodes.  The path from the root of the tree
00170   //  to any specific node defines a sequence.  Complete sequences should end in nodes
00171   //  whose 'next' pointer is null.  Each node in the tree is an entry in a hash_list
00172   //  which defines elements which are a pair<T, node*>.  That is, the T is the 'first'
00173   //  member of the pair.  The node* is the 'second' member of the pair and it
00174   //  refers to the 'next' step in the sequence.
00175   //
00176   //  Each complete sequence -- ie one which ends in a node whose 'second' member is
00177   //  null, appears as an entry in hash_list<node*, ID>.  That is, determining the
00178   //  ID of a given complete sequence envolves looking up the final node in the
00179   //  id map to get the id value.
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     // this class MUST CONTAIN NOTHING but a rest_type!
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;  // did not find an exact match.
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;  // did not find an exact match.
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       // scan_ points to a hash_list of pair<T,node*>;  If the specified
00314       // T is the key value of any of these pairs then the specified T is
00315       // a valid member of the current sequence.
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         // we are still matching part of an existing sequence
00466         
00467         scan_ = f->data_.second;
00468         
00469       }
00470       else
00471       {
00472         // adding a new tail to an existing sequence
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 } // namespace cxxtls
00533 
00534 
00535 #endif
Generated on Wed Feb 29 22:50:04 2012 for CXXUtilities by  doxygen 1.6.3