searchtree.h

Go to the documentation of this file.

/*
 * This file is part of the Code::Blocks IDE and licensed under the GNU General Public License, version 3
 * http://www.gnu.org/licenses/gpl-3.0.html
 */

#ifndef SEARCHTREE_H
#define SEARCHTREE_H

#include "prep.h"
#include <wx/string.h>

#include <vector>
#include <map>
#include <set>

typedef size_t nSearchTreeNode;
typedef size_t nSearchTreeLabel;

class SearchTreeNode;
class BasicSearchTree;
class SearchTreePoint;

typedef std::map<wxChar, nSearchTreeNode, std::less<wxChar> > SearchTreeLinkMap;


typedef std::vector<SearchTreeNode*> SearchTreeNodesArray;

typedef std::vector<SearchTreePoint> SearchTreePointsArray;

typedef std::map<size_t,size_t, std::less<size_t> > SearchTreeItemsMap;

typedef std::vector<wxString> SearchTreeLabelsArray;

class BasicSearchTreeIterator
{
public:
    BasicSearchTreeIterator();

    BasicSearchTreeIterator(BasicSearchTree* tree);

    virtual ~BasicSearchTreeIterator() {}

    bool IsValid();

    bool FindPrev(bool includechildren = true);

    bool FindNext(bool includechildren = true);

    const nSearchTreeNode& operator* () const { return m_CurNode; }

    const BasicSearchTreeIterator& operator++() { FindNext(); return *this; }

    const BasicSearchTreeIterator& operator--() { FindPrev(); return *this; }

    bool FindNextSibling();

    bool FindPrevSibling();

    bool FindSibling(wxChar ch);

    bool Eof() { return (!IsValid() || m_Eof); }

protected:
    nSearchTreeNode  m_CurNode;        
    bool             m_Eof;            
    BasicSearchTree* m_Tree;           
    size_t           m_LastTreeSize;   
    SearchTreeNode*  m_LastAddedNode;  
};

class SearchTreePoint
{
public:
    nSearchTreeNode n;  
    size_t depth;       
    SearchTreePoint(): n(0), depth(0) {}
    SearchTreePoint(nSearchTreeNode nn, size_t dd) { n = nn; depth = dd; }
};

class SearchTreeNode
{
    friend class BasicSearchTree;
    friend class BasicSearchTreeIterator;
public:
    SearchTreeNode();
    SearchTreeNode(unsigned int depth,
                   nSearchTreeNode parent,
                   nSearchTreeLabel label,
                   unsigned int labelstart,
                   unsigned int labellen);
    virtual ~SearchTreeNode();
    nSearchTreeNode GetParent() const { return m_Parent; }

    void SetParent(nSearchTreeNode newparent) { m_Parent = newparent; }

    nSearchTreeNode GetChild(wxChar ch);

    size_t GetItemNo(size_t depth);

    size_t AddItemNo(size_t depth, size_t itemno);

    SearchTreeNode* GetParent(const BasicSearchTree* tree) const;

    SearchTreeNode* GetChild(BasicSearchTree* tree,wxChar ch);

    wxString GetLabel(const BasicSearchTree* tree) const;

    wxChar GetChar(const BasicSearchTree* tree) const;

    const wxString& GetActualLabel(const BasicSearchTree* tree) const;

    nSearchTreeLabel GetLabelNo() const { return m_Label; }

    unsigned int GetLabelStart() const { return m_LabelStart; }

    unsigned int GetLabelLen() const { return m_LabelLen; }

    void SetLabel(nSearchTreeLabel label, unsigned int labelstart, unsigned int labellen);

    unsigned int GetDepth() const { return m_Depth; }

    void RecalcDepth(BasicSearchTree* tree);

    void UpdateItems(BasicSearchTree* tree);

    unsigned int GetLabelStartDepth() const;

    bool IsLeaf() const { return m_Children.empty() && (m_Depth != 0); }

    unsigned int GetDeepestMatchingPosition(BasicSearchTree* tree, const wxString& s, unsigned int StringStartDepth);

    wxString Serialize(BasicSearchTree* tree, nSearchTreeNode node_id, bool withchildren = false);
    void Dump(BasicSearchTree* tree, nSearchTreeNode node_id, const wxString& prefix, wxString& result);

    static wxString SerializeString(const wxString& s);
    static wxString U2S(unsigned int u);
    static wxString I2S(int i);
    static bool UnSerializeString(const wxString& s,wxString& result);
    static bool S2U(const wxString& s,unsigned int& u);
    static bool S2I(const wxString& s,int& i);

protected:
    unsigned int       m_Depth;

    nSearchTreeNode    m_Parent;

    nSearchTreeLabel   m_Label;

    unsigned int       m_LabelStart;

    unsigned int       m_LabelLen;

    SearchTreeLinkMap  m_Children;
    SearchTreeItemsMap m_Items;
};

class BasicSearchTree
{
    friend class SearchTreeNode;
    friend class BasicSearchTreeIterator;
public:
    BasicSearchTree();
    virtual ~BasicSearchTree();
    virtual size_t size() const { return m_Points.size(); }     
    virtual size_t GetCount() const { return m_Points.size(); } 
    virtual void clear(); 

    size_t insert(const wxString& s);

    bool HasItem(const wxString& s);

    size_t count(const wxString& s) { return HasItem(s) ? 1 : 0; }

    size_t GetItemNo(const wxString& s);

    const wxString GetString(size_t n) const;

    size_t FindMatches(const wxString& s, std::set<size_t>& result, bool caseSensitive, bool is_prefix);

    wxString SerializeLabels();

    wxString dump();

protected:
    virtual SearchTreeNode* CreateNode(unsigned int depth,
                                       nSearchTreeNode parent,
                                       nSearchTreeLabel label,
                                       unsigned int labelstart,
                                       unsigned int labellen);

    wxString GetString(const SearchTreePoint& nn, nSearchTreeNode top = 0) const;

    SearchTreeNode* GetNode(nSearchTreeNode n, bool NullOnZero = false);

    bool FindNode(const wxString& s, nSearchTreeNode nparent, SearchTreePoint* result);

    SearchTreePoint AddNode(const wxString& s, nSearchTreeNode nparent = 0);

    wxString SerializeLabel(nSearchTreeLabel labelno);

private:
    void CreateRootNode();

    nSearchTreeNode SplitBranch(nSearchTreeNode n, size_t depth);

protected:
    SearchTreeLabelsArray m_Labels;
    SearchTreeNodesArray  m_Nodes;
    SearchTreePointsArray m_Points;
};
template <class T> class SearchTree : public BasicSearchTree
{
public:
    SearchTree();
    virtual ~SearchTree();
    virtual void clear(); 
    size_t GetCount() const; 
    virtual size_t size() const; 
    bool SaveCacheTo(const wxString& filename); 
    bool LoadCacheFrom(const wxString& filename); 
    wxString Serialize();

    T GetItem(const wxString& s);

    T GetItem(const wxChar* s);

    size_t AddItem(const wxString& s, T item, bool replaceexisting = false);

    T& GetItemAtPos(size_t i);

    void SetItemAtPos(size_t i,T item);

    T& operator[](const wxString& s);

    virtual wxString SerializeItem(cb_unused size_t idx) { return wxString(_T("")); }

    virtual void* UnserializeItem(cb_unused const wxString& s) { return NULL; }

protected:
    std::vector<T> m_Items;   

    virtual void ClearItems();

    virtual bool AddFirstNullItem();
};

template <class T> SearchTree<T>::SearchTree() : BasicSearchTree()
{
    m_Items.clear();
    AddFirstNullItem();
}

template <class T> SearchTree<T>::~SearchTree()
{
    ClearItems();
}

template <class T> void SearchTree<T>::clear()
{
    ClearItems();
    BasicSearchTree::clear();
    AddFirstNullItem();
}

template <class T> size_t SearchTree<T>::GetCount() const
{
    size_t result = m_Items.size() -1;
    return result;
}

template <class T> size_t SearchTree<T>::size() const
{
    size_t result = m_Items.size() -1;
    return result;
}

template <class T> bool SearchTree<T>::SaveCacheTo(const wxString& filename)
{
    return true;
}

template <class T> bool SearchTree<T>::LoadCacheFrom(const wxString& filename)
{
    return true;
}

template <class T> T SearchTree<T>::GetItem(const wxChar* s)
{
    wxString tmps(s);
    return GetItem(tmps);
}

template <class T> T SearchTree<T>::GetItem(const wxString& s)
{
    size_t itemno = GetItemNo(s);
    if (!itemno && !s.empty())
        return T();
    return GetItemAtPos(itemno);
}

template <class T> size_t SearchTree<T>::AddItem(const wxString& s, T item, bool replaceexisting)
{
    size_t itemno = insert(s);

    if (itemno > m_Items.size())
        m_Items.resize(itemno);
    else if (itemno == m_Items.size())
        m_Items.push_back(item);
    else if (replaceexisting)
        m_Items[itemno] = item;

    return itemno;
}

template <class T> T& SearchTree<T>::GetItemAtPos(size_t i)
{
    if (i>=m_Items.size() || i < 1)
        i = 0;
    return m_Items[i];
}

template <class T> void SearchTree<T>::SetItemAtPos(size_t i,T item)
{
    m_Items[i]=item;
}

template <class T> void SearchTree<T>::ClearItems()
{
    m_Items.clear();
}

template <class T> bool SearchTree<T>::AddFirstNullItem()
{
    T newvalue;
    m_Items.push_back(newvalue);
    return true;
}

template <class T> T& SearchTree<T>::operator[](const wxString& s)
{
    size_t curpos = GetItemNo(s);
    if (!curpos)
    {
        T newitem;
        curpos = AddItem(s, newitem);
    }

    return m_Items[curpos];
}

template <class T> wxString SearchTree<T>::Serialize()
{
    wxString result;
    result << _T("<SearchTree>\n");
    result << SerializeLabels();
    result << _T("<nodes>\n");
    for (size_t i = 0; i < m_Nodes.size(); ++i)
        result << m_Nodes[i]->Serialize(this, i, false);
    result << _T("</nodes>\n");
    result << _T(" <items>\n");
    for (size_t i = 1; i < m_Items.size(); ++i)
        result << SerializeItem(i);
    result << _T(" </items>\n");
    result << _T("</SearchTree>\n");
    return result;
}

#endif // SEARCHTREE_H