Fast Binary Tree Operations

// BinaryTreeDemoDlg.cpp : implementation file
//

#include "stdafx.h"
#include "BinaryTreeDemo.h"
#include "BinaryTreeDemoDlg.h"
#include ".\binarytreedemodlg.h"
#include "FolderBrowse.h"
#include "Anchor.h"

#include <fcntl.h>
#include <sys/stat.h>
#include <io.h>

#pragma warning(disable:4311)

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

#define DELIMITERS		" \r\n\t!@#$%^&*()_+-={}|\\:\"'?�/.,<>������;"
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support

// Implementation
protected:
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// CBinaryTreeDemoDlg dialog



CBinaryTreeDemoDlg::CBinaryTreeDemoDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CBinaryTreeDemoDlg::IDD, pParent)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	m_strFolder = AfxGetApp()->GetProfileString("Options", "Folder");
	m_strExt = AfxGetApp()->GetProfileString("Options", "Extension", "cpp,c,h,txt,log");
	m_bRedBlack = AfxGetApp()->GetProfileInt("Options", "Read Black", 0);

	m_rbTree.NoRepeat = true;
	m_size = CSize(0, 0);
}

void CBinaryTreeDemoDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Control(pDX, IDC_STATUS, m_staticStatus);
	DDX_Control(pDX, IDC_TREE1, m_tree);
	DDX_Text(pDX, IDC_EDIT1, m_strFolder);
	DDX_Text(pDX, IDC_EDIT2, m_strExt);
	DDX_Check(pDX, IDC_CHECK1, m_bRedBlack);
}

BEGIN_MESSAGE_MAP(CBinaryTreeDemoDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_BROWSE, OnBnClickedBrowse)
	ON_BN_CLICKED(IDOK, OnBnClickedOk)
	ON_BN_CLICKED(IDC_CLEAR, OnBnClickedClear)
	ON_BN_CLICKED(IDC_DELETE, OnBnClickedDelete)
	ON_BN_CLICKED(IDC_SUCCESSOR, OnBnClickedSuccessor)
	ON_BN_CLICKED(IDC_PREDECESSOR, OnBnClickedPredecessor)
	ON_BN_CLICKED(IDC_MIN, OnBnClickedMin)
	ON_BN_CLICKED(IDC_MAX, OnBnClickedMax)
	ON_NOTIFY(TVN_ITEMEXPANDING, IDC_TREE1, OnTvnItemexpandingTree1)
	ON_WM_SIZE()
	ON_BN_CLICKED(IDC_CHECK1, OnBnClickedCheck1)
	ON_WM_DESTROY()
END_MESSAGE_MAP()


// CBinaryTreeDemoDlg message handlers

BOOL CBinaryTreeDemoDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon

	m_imageList.Create(16, 16, ILC_MASK, 0, 2);	
	m_imageList.Add(AfxGetApp()->LoadIcon(IDI_RED));
	m_imageList.Add(AfxGetApp()->LoadIcon(IDI_BLACK));
	if (m_bRedBlack)
		m_tree.SetImageList(&m_imageList, TVSIL_NORMAL);
	else
		m_tree.SetImageList(NULL, TVSIL_NORMAL);
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CBinaryTreeDemoDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CBinaryTreeDemoDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this function to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CBinaryTreeDemoDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CBinaryTreeDemoDlg::OnBnClickedBrowse()
{
	CFolderBrowse browse;
	if(browse.Browse(m_strFolder) == false)
		return;
	m_strFolder = browse.m_strFolder;
	AfxGetApp()->WriteProfileString("Options", "Folder", m_strFolder);
	UpdateData(false);
}

CString GetExt(CString strName)
{
	int nIndex = strName.Find('.');
	strName.MakeLower();
	return nIndex > 0 ? strName.Mid(nIndex) : "";
}

CString Commas(int nValue)
{
	CString str;
	str.Format("%d", nValue);
	nValue = str.GetLength()-3;
	while(nValue > 0)
		str.Insert(nValue, ','), nValue -= 3;
	return str;
}

int CBinaryTreeDemoDlg::ParseFolder(LPCSTR lpcsFolder)
{
	int nParsedSize = 0;
	CString strFolder = lpcsFolder;
	CString strExt = '.'+m_strExt+'.', str;
	strExt.Replace(',', '.');
	_finddata_t ff;
	int nFound = (int)_findfirst(strFolder+"\\*.*", &ff);
	while(nFound != -1)
	{
		if(ff.attrib&_A_SUBDIR)
		{
			if(ff.name[0] != '.')
				nParsedSize += ParseFolder(strFolder+"\\"+ff.name);
		}
		else
		{
			str = GetExt(ff.name)+'.';
			if(ff.size > 0 && str.IsEmpty() == false && strExt.Find(str) != -1)
			{
				nParsedSize += ff.size;
				m_staticStatus.SetWindowText(strFolder+"\\"+ff.name);

				int nFile = _open(strFolder+"\\"+ff.name, _O_BINARY|_O_RDONLY, 0);
				int nLength = _filelength(nFile);
				char* pBuffer = new char[nLength+1];
				_read(nFile, pBuffer, nLength);
				_close(nFile);
				pBuffer[nLength] = 0;

				char *pToken = strtok(pBuffer, DELIMITERS);
				while(pToken)
				{
					if(m_bRedBlack)
						m_rbTree.Insert(pToken)->Data = 0;
					else
						m_rbTree.CBinaryTree<string, LPCSTR, HTREEITEM, HTREEITEM>::Insert(pToken)->Data = 0;
					pToken = strtok(NULL, DELIMITERS);
				}
				delete pBuffer;
			}
		}
		if(_findnext(nFound, &ff) == -1)
			break;
	}
	return nParsedSize;
}

void CBinaryTreeDemoDlg::OnBnClickedOk()
{
	UpdateData();

	m_tree.DeleteAllItems();

	DWORD dw = ::GetTickCount();
	int nParsedSize = ParseFolder(m_strFolder);
	dw = ::GetTickCount()-dw;

	if(m_rbTree.Root)
	{
		CString str;
		str.Format("%s (%s)", m_rbTree.Root->Key.c_str(), Commas(m_rbTree.Root->Count));
		InsertItem(-1, m_rbTree.Root, TVI_ROOT);
	}

	m_staticStatus.SetWindowText("Parsing "+Commas(nParsedSize/1024)+" KB, Found "+Commas(m_rbTree.GetCount())+" tokens, in "+Commas(dw/1000)+" secs");
}

void CBinaryTreeDemoDlg::OnBnClickedClear()
{
	m_tree.DeleteAllItems();
	m_rbTree.RemoveAll();
}

void CBinaryTreeDemoDlg::OnBnClickedDelete()
{
	UpdateData(TRUE);

	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	TNODE* pParent = pNode->Parent;
	if(m_bRedBlack)
		m_rbTree.Delete((CRBTreeNode<string, HTREEITEM>*)pNode);
	else
		m_rbTree.CBinaryTree<string, LPCSTR, HTREEITEM, HTREEITEM>::Delete(pNode);

	m_tree.DeleteAllItems();
	if(m_rbTree.Root)
	{
		InsertItem(-1, m_rbTree.Root, TVI_ROOT);
		Expand(pParent?pParent:m_rbTree.Root);
	}
}

void CBinaryTreeDemoDlg::OnBnClickedSuccessor()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Successor(pNode));
}

void CBinaryTreeDemoDlg::OnBnClickedPredecessor()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Predecessor(pNode));
}

void CBinaryTreeDemoDlg::OnBnClickedMin()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Min(pNode));
}

void CBinaryTreeDemoDlg::OnBnClickedMax()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Max(pNode));
}

void CBinaryTreeDemoDlg::OnTvnItemexpandingTree1(NMHDR *pNMHDR, LRESULT *pResult)
{
	LPNMTREEVIEW pNMTreeView = reinterpret_cast<LPNMTREEVIEW>(pNMHDR);
	
	HTREEITEM hIT = pNMTreeView->itemNew.hItem;
	if((TVIS_EXPANDED&pNMTreeView->itemNew.state) == 0 
		&& (TVIS_EXPANDEDONCE&pNMTreeView->itemNew.state) == 0
		&& pNMTreeView->hdr.code == TVN_ITEMEXPANDING)
	{
		TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
		for(int nChild = 0; nChild < 2; nChild++)
			if(pNode != m_rbTree.Nil && pNode->Childs[nChild] != m_rbTree.Nil)
				InsertItem(nChild, pNode->Childs[nChild], hIT);

	}
	*pResult = 0;
}

void CBinaryTreeDemoDlg::OnSize(UINT nType, int cx, int cy)
{
	CDialog::OnSize(nType, cx, cy);

	if(m_size.cx > 0 && nType != SIZE_MINIMIZED)
	{
		Anchor(this, IDCANCEL, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDOK, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_CLEAR, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_BROWSE, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_DELETE, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_SUCCESSOR, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_PREDECESSOR, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_MIN, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_MAX, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_EDIT1, A_LEFT|A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_EDIT2, A_LEFT|A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_TREE1, A_BOTTOM|A_LEFT|A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_STATUS, A_BOTTOM|A_LEFT|A_RIGHT, m_size, CSize(cx, cy));
		Anchor(this, IDC_CHECK1, A_BOTTOM|A_LEFT, m_size, CSize(cx, cy));
	}	
	m_size = CSize(cx, cy);	
}

void CBinaryTreeDemoDlg::InsertItem(int nChild, TNODE* pNode, HTREEITEM hParent)
{
	if(pNode == m_rbTree.Nil || pNode == NULL)
		return;
	TV_ITEM Item;
	Item.mask = TVIF_CHILDREN;
	Item.cChildren = 1;

	CString str;
	str.Format("[%s] %s (%s)", nChild < 0 ? "Root":(nChild?"R":"L"), pNode->Key.c_str(), Commas(pNode->Count));
	HTREEITEM itemNew;
	if(m_bRedBlack)
		itemNew	= m_tree.InsertItem(str, ((RBTNODE*)pNode)->Color, ((RBTNODE*)pNode)->Color, hParent, TVI_LAST);
	else
		itemNew	= m_tree.InsertItem(str, hParent, TVI_LAST);
	pNode->Data = itemNew;
	m_tree.SetItemData(itemNew, (DWORD)pNode);
	if(pNode->Childs[0] != m_rbTree.Nil || pNode->Childs[1] != m_rbTree.Nil)
	{
		Item.hItem = itemNew;
		m_tree.SetItem(&Item);
	}
}

void CBinaryTreeDemoDlg::Expand(TNODE* pNode)
{
	TNODE* node = m_rbTree.Root;
	int nResult;
	while(node && (nResult = node->Key.compare(pNode->Key)) != 0)
	{
		m_tree.Expand(node->Data, TVE_EXPAND);
		node = node->Childs[nResult < 0];
	}
	m_tree.Expand(pNode->Data, TVE_EXPAND);
	m_tree.SelectItem(pNode->Data);
}

void CBinaryTreeDemoDlg::Select(TNODE* pNode)
{
	if(pNode)
		Expand(pNode);
}

void CBinaryTreeDemoDlg::OnBnClickedCheck1()
{
	UpdateData();

	if (m_bRedBlack)
		m_tree.SetImageList(&m_imageList, TVSIL_NORMAL);
	else
		m_tree.SetImageList(NULL, TVSIL_NORMAL);
}

void CBinaryTreeDemoDlg::OnDestroy()
{
	UpdateData();

	AfxGetApp()->WriteProfileString("Options", "Folder", m_strFolder);
	AfxGetApp()->WriteProfileString("Options", "Extension", m_strExt);
	AfxGetApp()->WriteProfileInt("Options", "Read Black", m_bRedBlack);

	CDialog::OnDestroy();
}