/************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * *************************************************************/ #ifndef ARY_SYMTREE_NODE_HXX #define ARY_SYMTREE_NODE_HXX // USED SERVICES // BASE CLASSES // OTHER namespace ary { namespace symtree { /** Represents a node in a tree of symbols like a namespace tree or a directory tree. @tpl NODE_TRAITS Needs to define the types: entity_base_type: The type of the entities in that storage, e.g. ->ary::cpp::CodeEntity. id_type: The type of the ids of those entities, e.g. ->ary::cpp::Ce_id. Needs to define the functions: 1. static entity_base_type & EntityOf_( id_type i_id ); 2. static symtree::Node * NodeOf_( const entity_base_type & i_entity ); 3. static const String & LocalNameOf_( const entity_base_type & i_entity ); 4. static entity_base_type * ParentOf_( const entity_base_type & i_entity ); 5. template static id_t Search_( const entity_base_type & i_entity, const KEY & i_localKey ); */ template class Node { public: typedef Node node_self; typedef typename NODE_TRAITS::entity_base_type entity_t; typedef typename NODE_TRAITS::id_type id_t; // LIFECYCLE /// @attention Always needs to be followed by ->Assign_Entity()! Node(); explicit Node( entity_t & i_entity ); void Assign_Entity( entity_t & i_entity ); ~Node(); // INQUIRY id_t Id(); const String Name() const; int Depth() const; const entity_t & Entity() const; const node_self * Parent() const; /** Gets a child with a specific name and of a specific type. There may be more childs with the same name. @return id_t(0), if no matching child is found. */ template typename NODE_TRAITS::id_type Search( const KEY & i_localKey ) const { // Inline here to workaround SUNW8 compiler bug, works in SUNW12. return NODE_TRAITS::Search_(Entity(), i_localKey); } /** Gets a child with a specific qualified name below this node. The child may not exists. */ template void SearchBelow( id_t & o_return, // Workaround SUNW8 compiler bug StringVector::const_iterator i_qualifiedSearchedName_begin, StringVector::const_iterator i_qualifiedSearchedName_end, const KEY & i_localKey ) const; /** Gets a child with a specific qualified name, either below this node or below any of the parent nodes. The child may not exists. */ template void SearchUp( id_t & o_return, // Workaround SUNW8 compiler bug StringVector::const_iterator i_qualifiedSearchedName_begin, StringVector::const_iterator i_qualifiedSearchedName_end, const KEY & i_localKey ) const; // ACCESS entity_t & Entity(); node_self * Parent(); private: // Forbid copying: Node(const node_self&); node_self& operator=(const node_self&); // Locals void InitDepth(); node_self * Get_Parent() const; node_self * NodeOf( id_t i_id ) const; // DATA entity_t * pEntity; int nDepth; }; // IMPLEMENTATION template inline const typename Node::entity_t & Node::Entity() const { csv_assert(pEntity != 0); return *pEntity; } template inline Node * Node::NodeOf(id_t i_id) const { if (i_id.IsValid()) return NODE_TRAITS::NodeOf_(NODE_TRAITS::EntityOf_(i_id)); return 0; } template inline Node * Node::Get_Parent() const { entity_t * parent = NODE_TRAITS::ParentOf_(Entity()); if (parent != 0) return NODE_TRAITS::NodeOf_(*parent); return 0; } template Node::Node() : pEntity(0), nDepth(0) { } template Node::Node(entity_t & i_entity) : pEntity(&i_entity), nDepth(0) { InitDepth(); } template void Node::Assign_Entity(entity_t & i_entity) { pEntity = &i_entity; InitDepth(); } template Node::~Node() { } template inline typename Node::id_t Node::Id() { return NODE_TRAITS::IdOf(Entity()); } template inline const String Node::Name() const { return NODE_TRAITS::LocalNameOf_(Entity()); } template inline int Node::Depth() const { return nDepth; } template inline const Node * Node::Parent() const { return Get_Parent(); } template template void Node::SearchBelow( id_t & o_return, // Workaround SUNW8 compiler bug StringVector::const_iterator i_qualifiedSearchedName_begin, StringVector::const_iterator i_qualifiedSearchedName_end, const KEY & i_localKey ) const { if (i_qualifiedSearchedName_begin != i_qualifiedSearchedName_end) { id_t next = Search(*i_qualifiedSearchedName_begin); if (next.IsValid()) { const node_self * subnode = NodeOf(next); if (subnode != 0) { subnode->SearchBelow( o_return, i_qualifiedSearchedName_begin+1, i_qualifiedSearchedName_end , i_localKey ); return; } } o_return = id_t(0); return; } o_return = Search(i_localKey); } template template void Node::SearchUp( id_t & o_return, // Workaround SUNW8 compiler bug StringVector::const_iterator i_qualifiedSearchedName_begin, StringVector::const_iterator i_qualifiedSearchedName_end, const KEY & i_localKey ) const { SearchBelow( o_return, i_qualifiedSearchedName_begin, i_qualifiedSearchedName_end, i_localKey ); if (o_return.IsValid()) return; node_self * parent = Get_Parent(); if (parent != 0) { parent->SearchUp( o_return, i_qualifiedSearchedName_begin, i_qualifiedSearchedName_end, i_localKey ); } } template typename Node::entity_t & Node::Entity() { csv_assert(pEntity != 0); return *pEntity; } template inline Node * Node::Parent() { return Get_Parent(); } template void Node::InitDepth() { Node * pp = Get_Parent(); if (pp != 0) nDepth = pp->Depth() + 1; else nDepth = 0; } } // namespace symtree } // namespace ary #endif