ctreecont.cpp

ncbi源码

    //     if((n= m_cursorPot.nof()) > 1) {
    // 	// move all cursors out of src
    // 	CTreeIterator* iCursor;

    // 	for(i= 0; i < n; i++) {
    // 	    iCursor= (CTreeIterator*)(m_cursorPot.get(i));
    // 	    if((iCursor != pCursor) && (iCursor->getNode() == src)) {
    // 		iCursor->GoNode(dst); // move it to merged node
    // 	    }
    // 	}
    //     }
}

CTreeCont::~CTreeCont()
{
    //     int i, n;

    //     // delete all cursors
    //     if((n= m_cursorPot.nof()) > 1) {
    // 	// move all cursors out of deleted subtree
    // 	CTreeIterator* iCursor;

    // 	for(i= 0; i < n; i++) {
    // 	    iCursor= (CTreeIterator*)(m_cursorPot.get(i));
    // 	    delete iCursor;
    // 	}
    //     }
    if(m_root)
        DelNodeInternal(m_root);
}


bool CTreeCont::AddNode(CTreeContNodeBase* pParentNode,
                        CTreeContNodeBase* pNewNode)
{
    if(pNewNode && pParentNode) {
        pNewNode->m_parent = pParentNode;
        pNewNode->m_sibling = pParentNode->m_child;
        pNewNode->m_child = 0;
        pParentNode->m_child = pNewNode;

        return true;
    }

    return false;
}


bool CTreeConstIterator::BelongSubtree(const CTreeContNodeBase* subtree_root)
    const
{
    if(m_node == subtree_root)
        return true;
    for(const CTreeContNodeBase* pN= m_node->m_parent; pN != 0;
        pN= pN->m_parent) {
        if(pN == subtree_root)
            return true;
    }
    return false;
}

bool CTreeConstIterator::AboveNode(const CTreeContNodeBase* node) const
{
    if(node == 0)
        return false;
    do {
        if(node->m_parent == m_node)
            return true;
    }
    while((node= node->m_parent) != 0);

    return false;
}

// move cursor to the nearest common ancestor
bool CTreeConstIterator::GoAncestor(const CTreeContNodeBase* node)
{
    if(BelongSubtree(node)) {
        m_node= node;
        return true;
    }
    const CTreeContNodeBase* pN= m_node;;
    while(!AboveNode(node)) {
        if(m_node->m_parent == 0) {
            m_node= pN;
            return false;
        }
        m_node= m_node->m_parent;
    }
    return true;
}

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachDownward(C4Each& cb)
// {
//     switch( cb.Execute(m_node) ) {
//     default:
//     case eCont:
//         if(!m_node->IsTerminal()) {
//             switch( cb.LevelBegin(m_node) ) {
//             case eStop: return eStop;
//             default:
//             case eCont:
//                 if(GoChild()) {
//                     do {
//                         if(ForEachDownward(cb)==eStop) return eStop;
//                     } while(GoSibling());
//                 }
//             case eSkip: // Means skip this level
//                 break;
//             }
//             GoParent();
//             if( cb.LevelEnd(m_node) == eStop )
//                 return eStop;
//         }
//     case eSkip:	break;
//     case eStop: return eStop;
//     }
//     return eCont;
// }

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachDownward(ForEachFunc ucb, void* user_data)
// {
//     switch( (*ucb)(m_node, user_data) ) {
//     default:
//     case eCont:
//         if(GoChild()) {
//             do {
//                 if(ForEachDownward(ucb, user_data)==eStop) return eStop;
//             } while(GoSibling());
//             GoParent();
//         }
//     case eSkip:	break;
//     case eStop: return eStop;
//     }
//     return eCont;
// }

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachDownwardLimited(C4Each& cb, int levels)
// {
//     if(levels > 0) {
//         switch( cb.Execute(m_node) ) {
//         default:
//         case eCont:
//             if(!m_node->IsTerminal()) {
//                 switch( cb.LevelBegin(m_node) ) {
//                 case eStop: return eStop;
//                 default:
//                 case eCont:
//                     if(GoChild()) {
//                         do {
//                             if(ForEachDownwardLimited(cb, levels-1)==eStop)
//                                 return eStop;
//                         } while(GoSibling());
//                     }
//                 case eSkip: // Means skip this level
//                     break;
//                 }
//                 GoParent();
//                 if( cb.LevelEnd(m_node) == eStop )
//                     return eStop;
//             }
//         case eSkip: break;
//         case eStop: return eStop;
//         }
//     }
//     return eCont;
// }

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachDownwardLimited( ForEachFunc ucb,
//                                             void* user_data, int levels)
// {
//     if(levels > 0) {
//         switch( (*ucb)(m_node, user_data) ) {
//         default:
//         case eCont:
//             if(GoChild()) {
//                 do {
//                     if(ForEachDownwardLimited(ucb, user_data,
//                                               levels-1)==eStop)
//                         return eStop;
//                 } while(GoSibling());
//                 GoParent();
//             }
//         case eSkip: break;
//         case eStop: return eStop;
//         }
//     }
//     return eCont;
// }

// add child preserving the sorting order
bool CTreeIterator::AddChild(CTreeContNodeBase* new_node, 
                             CTreeIterator::CSortPredicate& pred )
{
    // Temporary 
    CTreeContNodeBase* prev;
    CTreeContNodeBase* next;
    
    if( GoChild() ) {
        new_node->m_child = 0;
        new_node->m_parent = m_node->Parent();
        prev = 0;
        next = GetNode();
        while( next && pred.Execute( next, new_node ) ) {
            prev = next;
            next = prev->Sibling();
        }
        new_node->m_sibling = next;
        if( prev ) { // insert after prevtmp
            prev->m_sibling = new_node;
        } else { // insert as first child
            prev->Parent()->m_child = next;
        }
        // Restore state
        GoParent();
    } else {
        return AddChild( new_node );
    }
    return true;
}

void CTreeIterator::SortChildren( CTreeIterator::CSortPredicate& pred )
{
    // Sorting the list by insertion
    CTreeContNodeBase* prev;
    CTreeContNodeBase* next;
    CTreeContNodeBase* tmp;
    CTreeContNodeBase* prevtmp;
    
    if( GoChild() ) {
        prev = GetNode();
        if( GoSibling() ) {
            next = GetNode();
            while( next ) {
                if( !pred.Execute( prev, next ) ) { // The order is not right
                    tmp = prev->Parent()->Child();
                    prevtmp = 0;
                    while( tmp != prev && pred.Execute( tmp, next ) &&
                           (prevtmp = tmp) && (tmp = tmp->Sibling()) );
                    if( tmp ) {
                        // Move from prev place
                        prev->m_sibling = next->m_sibling;

                        if( prevtmp ) { // insert after prevtmp
                            next->m_sibling = prevtmp->m_sibling;
                            prevtmp->m_sibling = next;
                        } else { // insert as first child
                            next->m_sibling = prev->Parent()->Child();
                            prev->Parent()->m_child = next;
                        }
                    }
                } else { // the oreder is right, move to the next
                    prev = next;
                }
                next = prev->Sibling();
            }
        }
        // Restore state
        GoParent();
    }
}

class CLevelSort : public CTreeIterator::C4Each {
public:
    CLevelSort( CTreeIterator::CSortPredicate& pred, CTreeCont* tree )
        : m_pred(pred), m_tree(tree) {}
    virtual CTreeIterator::EAction Execute(CTreeContNodeBase* pNode) {
        CTreeIterator::EAction retc = CTreeIterator::eCont;
        CTreeIterator* it = m_tree->GetIterator();
        if( it->GoNode( pNode ) ) {
            it->SortChildren( m_pred );
        } else {
            retc = CTreeIterator::eSkip;
        }
        delete it;
        return retc;
    }
private:
    CTreeIterator::CSortPredicate& m_pred;
    CTreeCont*                     m_tree;
};

void
CTreeIterator::SortAllChildrenInSubtree( CTreeIterator::CSortPredicate& pred )
{
    CLevelSort sorter( pred, m_tree );
    ForEachDownward( sorter );
}

CTreeIterator::EAction
CTreeIterator::ForEachUpward(C4Each& cb)
{
    if(!m_node->IsTerminal()) {
        switch( cb.LevelBegin(m_node) ) {
        case eStop: return eStop;
        default:
        case eCont:
            if(GoChild()) {
                do {
                    if(ForEachUpward(cb)==eStop)
                        return eStop;
                } while(GoSibling());
            }
        case eSkip: // Means skip this level
            break;
        }
        GoParent();
        if( cb.LevelEnd(m_node) == eStop )
            return eStop;
    }
    return cb.Execute(m_node);
}

CTreeIterator::EAction
CTreeIterator::ForEachUpward(ForEachFunc ucb, void* user_data)
{
    if(GoChild()) {
        do {
            if(ForEachUpward(ucb, user_data)==eStop)
                return eStop;
        } while(GoSibling());
        GoParent();
    }
    return (*ucb)(m_node, user_data);
}

CTreeIterator::EAction
CTreeIterator::ForEachUpwardLimited(C4Each& cb, int levels)
{
    if(levels > 0) {
        if(!m_node->IsTerminal()) {
            switch( cb.LevelBegin(m_node) ) {
            case eStop: return eStop;
            default:
            case eCont:
                if(GoChild()) {
                    do {
                        if(ForEachUpwardLimited(cb, levels-1)==eStop)
                            return eStop;
                    } while(GoSibling());
                }
            case eSkip: // Means skip this level
                break;
            }
            GoParent();
            if( cb.LevelEnd(m_node) == eStop )
                return eStop;
        }
        return cb.Execute(m_node);
    }
    return eCont;
}

CTreeIterator::EAction
CTreeIterator::ForEachUpwardLimited(ForEachFunc ucb, void* user_data,
                                    int levels)
{
    if(levels > 0) {
        if(GoChild()) {
            do {
                if(ForEachUpwardLimited(ucb, user_data,
                                        levels-1)==eStop)
                    return eStop;
            } while(GoSibling());
            GoParent();
        }
        return (*ucb)(m_node, user_data);
    }
    return eCont;
}

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachUpward(C4Each& cb)
// {
//     if(!m_node->IsTerminal()) {
//         switch( cb.LevelBegin(m_node) ) {
//         case eStop: return eStop;
//         default:
//         case eCont:
//             if(GoChild()) {
//                 do {
//                     if(ForEachUpward(cb)==eStop)
//                         return eStop;
//                 } while(GoSibling());
//             }
//         case eSkip: // Means skip this level
//             break;
//         }
//         GoParent();
//         if( cb.LevelEnd(m_node) == eStop )
//             return eStop;
//     }
//     return cb.Execute(m_node);
// }

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachUpward(ForEachFunc ucb, void* user_data)
// {
//     if(GoChild()) {
//         do {
//             if(ForEachUpward(ucb, user_data)==eStop)
//                 return eStop;
//         } while(GoSibling());
//         GoParent();
//     }
//     return (*ucb)(m_node, user_data);
// }

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachUpwardLimited(C4Each& cb, int levels)
// {
//     if(levels > 0) {
//         if(!m_node->IsTerminal()) {
//             switch( cb.LevelBegin(m_node) ) {
//             case eStop: return eStop;
//             default:
//             case eCont:
//                 if(GoChild()) {
//                     do {
//                         if(ForEachUpwardLimited(cb, levels-1)==eStop)
//                             return eStop;
//                     } while(GoSibling());
//                 }
//             case eSkip: // Means skip this level
//                 break;
//             }
//             GoParent();
//             if( cb.LevelEnd(m_node) == eStop )
//                 return eStop;
//         }
//         return cb.Execute(m_node);
//     }
//     return eCont;
// }

// CTreeConstIterator::EAction
// CTreeConstIterator::ForEachUpwardLimited(ForEachFunc ucb, void* user_data,
//                                          int levels)
// {
//     if(levels > 0) {
//         if(GoChild()) {
//             do {
//                 if(ForEachUpwardLimited(ucb, user_data,
//                                         levels-1)==eStop)
//                     return eStop;
//             } while(GoSibling());
//             GoParent();
//         }
//         return (*ucb)(m_node, user_data);
//     }
//     return eCont;
// }


END_objects_SCOPE
END_NCBI_SCOPE



/*
 * $Log: ctreecont.cpp,v $
 * Revision 1000.1  2004/06/01 19:35:13  gouriano
 * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R6.5
 *
 * Revision 6.5  2004/05/19 17:27:10  gorelenk
 * Added include of PCH - ncbi_pch.hpp
 *
 * Revision 6.4  2003/05/06 19:53:53  domrach
 * New functions and interfaces for traversing the cached partial taxonomy tree introduced. Convenience functions GetDivisionName() and GetRankName() were added
 *
 * Revision 6.3  2002/10/22 22:15:41  vakatov
 * Get rid of a compilation warning
 *
 * Revision 6.2  2002/01/31 00:31:26  vakatov
 * Follow the renaming of "CTreeCont.hpp" to "ctreecont.hpp".
 * Get rid of "std::" which is unnecessary and sometimes un-compilable.
 * Also done some source identation/beautification.
 *
 * Revision 6.1  2002/01/30 16:13:37  domrach
 * Changes made to pass through MSVC compiler. Some src files renamed
 *
 * Revision 6.1  2002/01/28 19:56:11  domrach
 * Initial checkin of the library implementation files
 *
 */