Main Page Modules Class Hierarchy Data Structures File List Data Fields Globals Related Pages

# oscl_tagtree.h

Go to the documentation of this file.

    00001 // -*- c++ -*-
    00002 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    00003
    00004 //                     O S C L _ T A G T R E E
    00005
    00006 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    00007
    00018 #ifndef OSCL_TAGTREE_H_INCLUDED
    00019 #define OSCL_TAGTREE_H_INCLUDED
    00020
    00021 #ifndef OSCL_BASE_H_INCLUDED
    00022 #include "oscl_base.h"
    00023 #endif
    00024
    00025 #ifndef OSCL_MAP_H_INCLUDED
    00026 #include "oscl_map.h"
    00027 #endif
    00028
    00029 #ifndef OSCL_VECTOR_H_INCLUDED
    00030 #include "oscl_vector.h"
    00031 #endif
    00032
    00033 #ifndef OSCL_STDSTRING_H_INCLUDED
    00034 #include "oscl_stdstring.h"
    00035 #endif
    00036
    00037 #define OSCL_DISABLE_WARNING_TRUNCATE_DEBUG_MESSAGE
    00038 #include "osclconfig_compiler_warnings.h"
    00039
    00040
    00041 struct Oscl_Tag_Base
    00042 {
    00043     typedef char tag_base_unit;
    00044     typedef tag_base_unit* tag_base_type;
    00045     typedef uint32 size_type;
    00046
    00047     bool operator()(const tag_base_type& x, const tag_base_type& y) const
    00048     {
    00049         return tag_cmp(x, y) < 0;
    00050     }
    00051     size_type tag_len(const tag_base_type& t) const
    00052     {
    00053         return (size_type)oscl_strlen(t);
    00054     }
    00055     tag_base_type tag_copy(tag_base_type& dest, const tag_base_type& src) const
    00056     {
    00057         return oscl_strncpy(dest, src, oscl_strlen(src) + 1);
    00058     }
    00059     int32 tag_cmp(const tag_base_type& x, const tag_base_type& y) const
    00060     {
    00061         return oscl_strncmp(x, y, oscl_strlen(x) + 1);
    00062     }
    00063     OSCL_IMPORT_REF tag_base_type tag_ancestor(tag_base_type& dest, const tag_base_type& src) const;
    00064     OSCL_IMPORT_REF size_type tag_depth(const tag_base_type& t) const;
    00065 };
    00066
    00067 template <class Alloc>
    00068 struct Oscl_Tag : public Oscl_Tag_Base
    00069 {
    00070
    00071     Oscl_Tag(const Oscl_Tag<Alloc>& t)
    00072     {
    00073         tag = tagAllocator.ALLOCATE(tag_len(t.tag) + 1);
    00074         tag_copy(tag, t.tag);
    00075     }
    00076
    00077     Oscl_Tag(const tag_base_type& t)
    00078     {
    00079         tag = tagAllocator.ALLOCATE(tag_len(t) + 1);
    00080         tag_copy(tag, t);
    00081     }
    00082
    00083     ~Oscl_Tag()
    00084     {
    00085         tagAllocator.deallocate(tag);
    00086     }
    00087
    00088     bool operator<(const Oscl_Tag<Alloc>& x) const
    00089     {
    00090         return (tag_cmp(tag, x.tag) < 0);
    00091     }
    00092
    00093     Oscl_TAlloc<tag_base_unit, Alloc> tagAllocator;
    00094     tag_base_type tag;
    00095 };
    00096
    00100 template <class T, class Alloc>
    00101 class Oscl_TagTree
    00102 {
    00103
    00104     public:
    00105         typedef Oscl_Tag<Alloc> tag_type;
    00106         typedef typename tag_type::tag_base_type tag_base_type;
    00107
    00108
    00109         struct Node
    00110         {
    00111             typedef Oscl_Vector<Node*, Alloc> children_type;
    00112             Node() {}
    00113
    00114             tag_type tag;
    00115             T value;
    00116             Node* parent;
    00117             children_type children;
    00118
    00119             void sort_children()
    00120             {
    00121                 bool tryagain;
    00122                 if (children.empty()) return;
    00123                 do
    00124                 {
    00125                     tryagain = 0;
    00126                     for (typename children_type::iterator it = children.begin(); it != (children.end() - 1); it++)
    00127                     {
    00128                         typename children_type::iterator it2 = it + 1;
    00129                         if ((*it2)->tag < (*it)->tag)
    00130                         {
    00131                             // swap em
    00132                             Node* tmp = *it;
    00133                             *it = *it2;
    00134                             *it2 = tmp;
    00135                             tryagain = 1;
    00136                         }
    00137                     }
    00138                 }
    00139                 while (tryagain);
    00140             }
    00141
    00142             typename tag_type::size_type depth()
    00143             {
    00144                 return tag.tag_depth(tag.tag);
    00145             }
    00146         };
    00147
    00148         typedef Oscl_Vector<Node*, Alloc> children_type;
    00149
    00150         typedef Node node_type;
    00151         typedef node_type* node_ptr;
    00152         typedef Oscl_Map<const tag_base_type, node_ptr, Alloc , Oscl_Tag_Base> map_type;
    00153         typedef typename map_type::size_type size_type;
    00154         typedef typename map_type::value_type value_type;
    00155
    00156         struct iterator
    00157         {
    00158             typedef node_type& reference;
    00159             typedef node_type* pointer;
    00160             typedef typename map_type::iterator mapiter;
    00161             typedef iterator self;
    00162
    00163             iterator() {}
    00164             iterator(mapiter x)
    00165             {
    00166                 mapit = x;
    00167             }
    00168             iterator(const iterator& it)
    00169             {
    00170                 mapit = it.mapit;
    00171             }
    00172
    00173             reference operator*() const
    00174             {
    00175                 return *((*mapit).second);
    00176             }
    00177             pointer operator->() const
    00178             {
    00179                 return &(operator*());
    00180             }
    00181
    00182             bool operator==(const self& x)
    00183             {
    00184                 return mapit == x.mapit;
    00185             }
    00186
    00187             bool operator!=(const self& x)
    00188             {
    00189                 return mapit != x.mapit;
    00190             }
    00191
    00192             self& operator++()
    00193             {
    00194                 mapit++;
    00195                 return *this;
    00196             }
    00197
    00198             self operator++(int)
    00199             {
    00200                 self tmp = *this;
    00201                 ++*this;
    00202                 return tmp;
    00203             }
    00204
    00205             self& operator--()
    00206             {
    00207                 mapit--;
    00208                 return *this;
    00209             }
    00210
    00211             self operator--(int)
    00212             {
    00213                 self tmp = *this;
    00214                 --*this;
    00215                 return tmp;
    00216             }
    00217
    00218             mapiter mapit;
    00219         };
    00220
    00221         struct const_iterator
    00222         {
    00223             typedef const node_type& reference;
    00224             typedef const node_type* pointer;
    00225             typedef typename map_type::const_iterator mapiter;
    00226             typedef const_iterator self;
    00227
    00228             const_iterator() {}
    00229             const_iterator(mapiter x)
    00230             {
    00231                 mapit = x;
    00232             }
    00233             const_iterator(const const_iterator& it)
    00234             {
    00235                 mapit = it.mapit;
    00236             }
    00237
    00238             reference operator*() const
    00239             {
    00240                 return *((*mapit).second);
    00241             }
    00242             pointer operator->() const
    00243             {
    00244                 return &(operator*());
    00245             }
    00246
    00247             bool operator==(const self& x)
    00248             {
    00249                 return mapit == x.mapit;
    00250             }
    00251
    00252             bool operator!=(const self& x)
    00253             {
    00254                 return mapit != x.mapit;
    00255             }
    00256
    00257             self& operator++()
    00258             {
    00259                 mapit++;
    00260                 return *this;
    00261             }
    00262
    00263             self operator++(int)
    00264             {
    00265                 self tmp = *this;
    00266                 ++*this;
    00267                 return tmp;
    00268             }
    00269
    00270             self& operator--()
    00271             {
    00272                 mapit--;
    00273                 return *this;
    00274             }
    00275
    00276             self operator--(int)
    00277             {
    00278                 self tmp = *this;
    00279                 --*this;
    00280                 return tmp;
    00281             }
    00282
    00283             mapiter mapit;
    00284         };
    00285
    00286     public:
    00287
    00291         Oscl_TagTree(size_type max_depth = 0) : maxDepth(max_depth)
    00292         {
    00293             // insert the root node
    00294             node_ptr node = create_node((char*)"", T());
    00295             node->parent = NULL;
    00296             typename map_type::value_type pair(node->tag.tag, node);
    00297             nodeMap.insert(pair);
    00298         }
    00302         Oscl_TagTree(const Oscl_TagTree<T, Alloc>& x) : maxDepth(x.maxDepth)
    00303         {
    00304             for (const_iterator it = x.begin(); it != x.end(); it++)
    00305             {
    00306                 insert(it->tag.tag, it->value);
    00307             }
    00308         }
    00312         Oscl_TagTree<T, Alloc>& operator=(const Oscl_TagTree<T, Alloc>& x)
    00313         {
    00314             maxDepth = x.maxDepth;
    00315             // clear the current tree
    00316             clear();
    00317             // insert nodes from assigned tree
    00318             for (const_iterator it = x.begin(); it != x.end(); it++)
    00319             {
    00320                 insert(it->tag.tag, it->value);
    00321             }
    00322             return *this;
    00323         }
    00327         ~Oscl_TagTree()
    00328         {
    00329             // destroy all nodes stored in the map
    00330             for (iterator it = begin(); it != end(); it++)
    00331             {
    00332                 destroy_node(&(*it));
    00333             }
    00334         }
    00338         iterator begin()
    00339         {
    00340             return iterator(nodeMap.begin());
    00341         }
    00345         const_iterator begin() const
    00346         {
    00347             return const_iterator(nodeMap.begin());
    00348         }
    00352         iterator end()
    00353         {
    00354             return iterator(nodeMap.end());
    00355         }
    00359         const_iterator end() const
    00360         {
    00361             return const_iterator(nodeMap.end());
    00362         }
    00366         bool empty() const
    00367         {
    00368             return nodeMap.empty();
    00369         }
    00373         size_type size() const
    00374         {
    00375             return nodeMap.size();
    00376         }
    00381         T& operator[](const tag_base_type& t)
    00382         {
    00383             return (*((insert(t, T())).first)).value;
    00384         }
    00385
    00386         typedef Oscl_Pair<iterator, bool> pair_iterator_bool;
    00402         pair_iterator_bool insert(const tag_base_type& t, const T& x)
    00403         {
    00404
    00405             tag_type currenttag(t);
    00406             pair_iterator_bool result(end(), false);
    00407             node_ptr child = NULL;
    00408             size_type ii;
    00409             size_type maxloops;
    00410
    00411             // if it exceeds the max depth, then truncate it to the max depth size
    00412             if (maxDepth > 0 && currenttag.tag_depth(currenttag.tag) > maxDepth)
    00413             {
    00414                 maxloops = currenttag.tag_depth(currenttag.tag) - maxDepth;
    00415                 for (ii = 0; ii < maxloops; ii++)
    00416                 {
    00417                     currenttag.tag_ancestor(currenttag.tag, currenttag.tag);
    00418                 }
    00419             }
    00420
    00421             maxloops = currenttag.tag_depth(currenttag.tag) + 1;
    00422             for (ii = 0; ii < maxloops; ii++)
    00423             {
    00424                 // check if tag already exists; if so then no need to continue creating nodes
    00425                 typename map_type::iterator mit = nodeMap.find(currenttag.tag);
    00426                 if (mit != nodeMap.end())
    00427                 {
    00428                     // set child parent relationship
    00429                     if (child)
    00430                     {
    00431                         child->parent = (*mit).second;
    00432                         child->parent->children.push_back(child);
    00433                     }
    00434                     // if this is the first pass node, then set it for the return value
    00435                     if (result.first == end()) result.first = iterator(mit);
    00436                     break;
    00437                 }
    00438                 // otherwise create a new node, insert it into map, and set parent/child relationship
    00439                 else
    00440                 {
    00441                     // insert the new node
    00442                     // first pass sets the node to the given value, all others are default value
    00443                     node_ptr node;
    00444                     if (result.first == end())
    00445                     {
    00446                         node = create_node(currenttag.tag, x);
    00447                     }
    00448                     else
    00449                     {
    00450                         node = create_node(currenttag.tag, T());
    00451                     }
    00452
    00453                     typename map_type::value_type pair(node->tag.tag, node);
    00454                     typename map_type::pair_iterator_bool mapresult = (nodeMap.insert(pair));
    00455
    00456                     // if this is the first pass node to insert, save it for the return value
    00457                     if (result.first == end())
    00458                     {
    00459                         result.first = iterator(mapresult.first);
    00460                         result.second = mapresult.second;
    00461                     }
    00462                     // set child/parent relationship
    00463                     if (child)
    00464                     {
    00465                         child->parent = (*(mapresult.first)).second;
    00466                         child->parent->children.push_back(child);
    00467                     }
    00468                     child = node;
    00469                 }
    00470
    00471                 currenttag.tag_ancestor(currenttag.tag, currenttag.tag);
    00472             }
    00473
    00474             return result;
    00475         }
    00484         void erase(iterator position)
    00485         {
    00486             // if node has children, then replace it with default node value
    00487             if (!(position->children.empty()))
    00488             {
    00489                 position->value = T();
    00490                 return;
    00491             }
    00492
    00493             // destroy the node since only the pointer is stored
    00494             destroy_node(&(*position));
    00495             nodeMap.erase(position.mapit);
    00496         }
    00507         size_type erase(const tag_base_type& x)
    00508         {
    00509             iterator it = find(x);
    00510             if (it != end())
    00511             {
    00512                 erase(it);
    00513                 return 1;
    00514             }
    00515             return 0;
    00516         }
    00520         void clear()
    00521         {
    00522             // destroy all nodes stored in the map
    00523             for (iterator it = begin(); it != end(); it++)
    00524             {
    00525                 destroy_node(&(*it));
    00526             }
    00527             // clear the map
    00528             nodeMap.clear();
    00529         }
    00535         iterator find(const tag_base_type& x)
    00536         {
    00537             return iterator(nodeMap.find(x));
    00538         }
    00542 //Removed this version due to ADS 1.2 compile problem
    00543 //    const_iterator find(const tag_base_type& x) const { return const_iterator(nodeMap.find(x)); }
    00547         size_type count(const tag_base_type& x) const
    00548         {
    00549             return nodeMap.count(x);
    00550         }
    00551
    00552     private:
    00553         node_ptr create_node(const tag_base_type& t, const T& x)
    00554         {
    00555             node_ptr n = nodeAllocator.ALLOCATE(1);
    00556             new(&n->tag) tag_type(t);
    00557             new(&n->value) T(x);
    00558             new(&n->children) Oscl_Vector<Node*, Alloc>();
    00559             return n;
    00560         }
    00561
    00562         void destroy_node(node_ptr x)
    00563         {
    00564             x->tag.OSCL_TEMPLATED_DESTRUCTOR_CALL(tag_type, Oscl_Tag);
    00565             x->value.T::~T();
    00566             x->children.OSCL_TEMPLATED_DESTRUCTOR_CALL(children_type, Oscl_Vector);
    00567             nodeAllocator.deallocate(x);
    00568         }
    00569
    00570         map_type nodeMap;
    00571         Oscl_TAlloc<node_type, Alloc> nodeAllocator;
    00572         size_type maxDepth;
    00573 };
    00574
    00578 #endif
    00579