l3lib/l3lib_vc2005/llqueue_tree.h

//
// G A M E.O.N.E - LOW LEVEL LIB V1.0
// Copyright (C) 2001 LEVEL ONE ENTERTAINMENT, 
// Licensed under the terms of LGPL.
//:---------------------------------------------------------------------------
//:Description
//
// LOW LEVEL QUEUE_TREE HEADERFILE
//

#ifndef _LLQUEUE_TREE_H
#define _LLQUEUE_TREE_H

#include "sys_assert.h"

class queue_treenode;
class queue_treehead;

/*
 * Tree NODE
 */
class queue_treenode {

public:
	queue_treenode();
    ~queue_treenode();

	
    queue_treenode *GetPrev() const;
    queue_treenode *GetNext() const;
    queue_treenode *GetParent() const;
    queue_treenode *GetLeft() const;
    queue_treenode *GetRight() const;
    queue_treehead *GetBase() const;
	
    bool	IsInserted() const;
    int		GetCount() const;
    void	Extract();
    int		CalcIdx() const;
    int		Validate(const queue_treenode *Prev,
		             const queue_treenode *Next) const;

    void UpdateRec();
    virtual void Update();
	
private:
    queue_treenode *m_Prev, *m_Next;
    queue_treenode *m_Parent;
    queue_treenode *m_Left, *m_Right;
    queue_treehead *m_Base;
    int m_Balance;
    int m_Count;
	
    enum
    {
        Balance_Equal   = 0,
		Balance_Left    = -1,
		Balance_Right   = 1,
    };
	
    friend class queue_treehead;
};



/*
 * Tree Header
 */

class queue_treehead {

public:
	typedef queue_treenode CNode;

	queue_treehead();
    ~queue_treehead();

    queue_treenode *GetFirst() const;
    queue_treenode *GetLast() const;
    queue_treenode *GetRoot() const;
    queue_treenode *GetPrev(queue_treenode *Node) const;
    queue_treenode *GetNext(queue_treenode *Node) const;

    bool	IsEmpty() const;
    int		GetCount() const;
    int		CalcIdx(queue_treenode *Node) const;
    queue_treenode *
			SearchByIdx(int Idx) const;
	
    void InsertFront(queue_treenode *Node);
    void InsertBack(queue_treenode *Node);
    void InsertAfter(queue_treenode *Node, queue_treenode *Pos);
    void InsertBefore(queue_treenode *Node, queue_treenode *Pos);

    void ExtractAll();
    void CopyFrom(const queue_treehead &Base);
    void Validate() const;

private:
    queue_treenode *m_First, *m_Last;
    queue_treenode *m_Root;

    void ChangeChild(queue_treenode *Node, 
                     queue_treenode *Old, queue_treenode *New);
    queue_treenode *RotateLeft(queue_treenode *Node);
    queue_treenode *RotateRight(queue_treenode *Node);
    queue_treenode *OverweightLeft(queue_treenode *Node);
    queue_treenode *OverweightRight(queue_treenode *Node);

    void Extract(queue_treenode *Node);
    void InsertBetween(queue_treenode *Prev, queue_treenode *Next, 
                queue_treenode *Node);

    friend class queue_treenode;

    queue_treehead(const queue_treehead &Tree);
    queue_treehead &operator=(const queue_treehead &Tree);
};

/*
 * Implementation
 */

inline queue_treenode::queue_treenode() 
{ 
    SYS_ASSERT_PTR(this);
    m_Prev = m_Next = 0;
    m_Parent = m_Left = m_Right = 0; 
    m_Base = 0; 
    m_Balance = Balance_Equal; 
    m_Count = 1;
}

inline queue_treenode::~queue_treenode()
{ 
    SYS_ASSERT_PTR(this);
    queue_treehead *Base = m_Base;
    if(Base)
        Base->Extract(this);
}

inline queue_treenode *queue_treenode::GetPrev() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Prev; 
}

inline queue_treenode *queue_treenode::GetNext() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Next; 
}

inline queue_treenode *queue_treenode::GetParent() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Parent; 
}

inline queue_treenode *queue_treenode::GetLeft() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Left; 
}

inline queue_treenode *queue_treenode::GetRight() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Right; 
}

inline queue_treehead *queue_treenode::GetBase() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Base; 
}

inline bool queue_treenode::IsInserted() const 
{ 
    SYS_ASSERT_PTR(this); 
    return m_Base != 0; 
}

inline int queue_treenode::GetCount() const
{ 
    return m_Count; 
}

inline void queue_treenode::Extract()
{
    SYS_ASSERT_PTR(this);
    queue_treehead *Base = m_Base;
    if(Base)
        Base->Extract(this);
}

/*
 * Implementation Treehead
 */

inline queue_treehead::queue_treehead()
{
    SYS_ASSERT_PTR(this);
    m_First = m_Last = 0;
    m_Root = 0;
}

inline queue_treehead::~queue_treehead()
{
    SYS_ASSERT_PTR(this);
    ExtractAll();
}

inline queue_treenode *queue_treehead::GetFirst() const
{
    SYS_ASSERT_PTR(this);
    return m_First;
}

inline queue_treenode *queue_treehead::GetLast() const
{
    SYS_ASSERT_PTR(this);
    return m_Last;
}

inline queue_treenode *queue_treehead::GetRoot() const
{
    SYS_ASSERT_PTR(this);
    return m_Root;
}

inline queue_treenode *queue_treehead::GetPrev(
                                queue_treenode *Node) const
{
    if(Node)
        return Node->m_Prev;
    else
        return m_Last;
}

inline queue_treenode *
queue_treehead::GetNext(queue_treenode *Node) const
{
    if(Node)
        return Node->m_Next;
    else
        return m_First;
}

inline bool 
queue_treehead::IsEmpty() const
{
    SYS_ASSERT_PTR(this);
    return m_Root == 0;
}

inline int 
queue_treehead::GetCount() const
{
    SYS_ASSERT_PTR(this);
    return m_Root ? m_Root->m_Count : 0;
}

inline void 
queue_treehead::InsertFront(queue_treenode *Node)
{
    SYS_ASSERT_PTR(this);
    InsertBetween(0, m_First, Node);
}

inline void 
queue_treehead::InsertBack(queue_treenode *Node)
{
    SYS_ASSERT_PTR(this);
    InsertBetween(m_Last, 0, Node);
}


#endif // _LLQUEUE_TREE_H