testcore.cpp

独立于AVL库的存储媒体 虽现在有不少可用的AVL树库

/////////////////////////////////////////////////////////////////////////////
// Name:        testcore.cpp
// Version:		1.0.0
// Purpose:     AVL Sample Program - Test 2
// Author:      Wu Yuh Song
// Modified by:
// Created:     08/25/1999
// Copyright:   (c) Wu Yuh Song
// Licence:   	Wu Yuh Song's Library Licence, Version 1
/////////////////////////////////////////////////////////////////////////////


#include "StdAfx.h"

#include <stdlib.h>

#define ___AVL_LINKLIST_SUPPORT___
#include "avl_node_file.h"
#include "../AVL_Libraries/avl.h"

AVL< avl_node_hnd_mem<long,avl_node_hnd_file::tagDataCore*> > avl_node_hnd_file::lookup_tree;
AVL<avl_node_hnd_file>* pTree;


struct info_block
{
	long			posRoot;

#ifdef ___AVL_LINKLIST_SUPPORT___
	long			posListHead;
	long			posListTail;
#endif

	unsigned int	nNodeNumber;
	int				nHeight;
};

void ReadInfoBlock();
void WriteInfoBlock();
void AddEntry(char* szKey, char* szValue);
void SearchEntry(char* szKey);
void ListAll();

int _avl_file_test_main()
{
	
	pTree = new AVL<avl_node_hnd_file>;

	OpenDB();
	ReadInfoBlock();

	while(1) {
		int choice;
		char key[500], value[500];

		printf ( "1. Insert  2. Search  3. List 4. Quit : ");
		scanf("%d",&choice);

		if ( choice >= 1 && choice <= 2) {
			printf ( "\nEnter key : ");
			getchar();
			gets(key);
			
			if ( choice == 1) {
				printf ( "Enter value : ");
				gets(value);
			}

			if ( choice == 1) {
				AddEntry(key,value);				
			}
			else {
				SearchEntry(key);
			}

		}
		else if ( choice == 4)
			break;
		else if ( choice == 3) {
			ListAll();
		}

		printf("\n");
	}
	
	WriteInfoBlock();
	delete pTree;
	CloseDB();


	return 0;
}


void ReadInfoBlock()
{
	long pos;
	info_block ib;
	AVL<avl_node_hnd_file>::TreeInfo tf;

	if ( pos = GetInfoBlockPos() ) {
		fseek(fpDB, pos,SEEK_SET);
		fread(&ib, sizeof(info_block),1, fpDB);
	
		if ( ib.posRoot ) {	//database is not empty
			tf.nHeight = ib.nHeight;
			tf.nhndRoot.SetToNode(ib.posRoot);
			tf.nhndListHead.SetToNode(ib.posListHead);
			tf.nhndListTail.SetToNode(ib.posListTail);
			tf.nNodeNumber = ib.nNodeNumber;
			pTree->Attach(tf);
		}
	}
}

void WriteInfoBlock()
{
	long pos;
	info_block ib;
	AVL<avl_node_hnd_file>::TreeInfo tf;

	if ( pTree->GetInfo(tf) ) {
		if ( ! (pos = GetInfoBlockPos()) ) {
			pos = NewBlock(sizeof(info_block));
			SetInfoBlockPos(pos);
		}
		
		ib.nHeight = tf.nHeight;
		ib.nNodeNumber = tf.nNodeNumber;
		ib.posRoot = tf.nhndRoot.peek_pos();
		ib.posListHead = tf.nhndListHead.peek_pos();
		ib.posListTail = tf.nhndListTail.peek_pos();
		
		fseek(fpDB, pos, SEEK_SET);
		fwrite(&ib, sizeof(info_block),1,fpDB);
	}
}


void AddEntry(char* szKey, char* szValue)
{
	avl_node_hnd_file node;
	AVL<avl_node_hnd_file>::SearchResult sr;

	sr.nhndSearch.NewNode(1);
	sr.nhndSearch.SetKey(szKey);
	
	if ( !pTree->Search(sr) ) {
		//insert new

		avl_node_hnd_file nhndInsert;
		
		nhndInsert.NewNode(0);
		nhndInsert.SetKey(szKey);
		nhndInsert.SetValue(szValue);

		pTree->Insert(nhndInsert, &sr);
		printf("\n\tkey : '%s' value : '%s' inserted...\n", szKey,szValue);		
	}
	else {
		printf("\n\tcollision occured...\n");		
	}

}

void SearchEntry(char* szKey)
{

	AVL<avl_node_hnd_file>::SearchResult sr;


	sr.nhndSearch.NewNode(1);
	sr.nhndSearch.SetKey(szKey);
	
	if ( pTree->Search(sr) ) {
		printf("\n\tkey : '%s' value : '%s' found.\n", szKey, sr.nhndSearch.GetValue() );
		printf ( "\n\t\tDo you want to delete this node (0 = y/ 1 = n) ? ");
		int c;
		scanf("%d", &c);
		
		
		if (c == 0 &&  pTree->Delete(sr.nhndSearch, &sr) ) {
			//free the file space occupied by the node.
			sr.nhndSearch.DeleteNode();
			printf ( "node deleted...\n");
		}

	}
	else {
		printf ( "\n\tNot found...\n");
	}


}

void ListAll()
{
	avl_node_hnd_file node;

	if ( pTree->GetListHead(node) ) {
		printf ( "\n");
		do {
			printf("\tkey : '%s' value : '%s'\n", node.GetKey(), node.GetValue());			
		}while(node.StepToRightSibling() );
	}

}