Changes - j0ke.net Open Build Service

Changes of Revision 14

[-] [+]	Changed	lfc.changes
@@ -1,4 +1,9 @@ ------------------------------------------------------------------- +Fri Feb 8 19:39:52 UTC 2013 - cs@linux-administrator.com + +- Update to version 1.4.1 + +------------------------------------------------------------------- Mon Jan 7 21:03:12 UTC 2013 - cs@linux-administrator.com - Update to version 1.3.7
[-] [+]	Changed	lfc.spec ^
@@ -2,7 +2,7 @@ %define libname lib%{pkgname} %define soname %{libname}1 Name: %{soname} -Version: 1.3.7 +Version: 1.4.1 Release: 1 Group: Development Summary: Lemke Foundation Classes
[-] [+]	Changed	lfc-1.4.1.tar.bz2/README ^
@@ -4,7 +4,7 @@ ------------------------------ A collection of basic c++ classes - Version 1.3.7 + Version 1.4.1 (C)opyright 2005,2006,2007,2008,2009,2010,2011,2012,2013 Bjoern Lemke @@ -27,6 +27,7 @@ Tested compilers -------------- g++ ( 3.x, 4.x ) +clang 4.2 Forte C++ Installation
[-] [+]	Added	lfc-1.4.1.tar.bz2/samples/AVLTreeTest.cc ^
@@ -0,0 +1,104 @@ +/////////////////////////////////////////////////////////////////////////////// +// +// AVLTreeTest.cc - Testing the AVLTreeT template +// +// Design and Implementation by Bjoern Lemke +// +// (C)opyright 2013 by Bjoern Lemke +// +// IMPLEMENTATION MODULE +// +// Description: Testing the AVLTreeT class +// +/////////////////////////////////////////////////////////////////////////////// + +#pragma implementation "AVLTreeT.h" + +#include "Exception.h" +#include "AVLTreeT.h" + +int main(int argc, char *argv) +{ + + + try { + + + / + AVLTreeT<int> bTree; + + int i=1; + + while ( i > 0 ) + { + i=0; + cin >> i; + cout << "Insert " << i << endl; + bTree.Insert(i); + + bTree.printTree(); + + } + + int* pI = bTree.First(); + + while ( pI ) + { + cout << "Element is " << pI << endl; + pI = bTree.Next(); + } + + / + + cout << "------------------------" << endl; + cout << "Testing class TreeT ..." << endl; + cout << " Constructors and Destructors..."; + if ( 1 ) + { + AVLTreeT<int> t; + + } + + cout << "ok" << endl; + + srandom(time(0)); + + AVLTreeT<int> bTree; + + + unsigned long count = 1000; + while (count) + { + int elem = random() % (100 * count); + bTree.Insert(elem); + count--; + } + + int* pI = bTree.First(); + + while ( pI ) + { + cout << "Element is " << *pI << endl; + pI = bTree.Next(); + } + + + + // exit(0); + // bTree.Size(); + + // cout << "TreeSize = " << bTree.Size() << endl; + + cout << "------------------------" << endl; + + } + catch ( Exception e) + { + cout << "failed" << endl; + } + + +} + + +
[-] [+]	Changed	lfc-1.4.1.tar.bz2/samples/Makefile ^
@@ -10,10 +10,10 @@ # ################################################################################ -CC = g++ +CC = clang LIBS = -lpthread -lcurses -lreadline -lpthread -lncurses DEFS = -DPACKAGE_NAME=\"FULL-PACKAGE-NAME\" -DPACKAGE_TARNAME=\"full-package-name\" -DPACKAGE_VERSION=\"VERSION\" -DPACKAGE_STRING=\"FULL-PACKAGE-NAME\ VERSION\" -DPACKAGE_BUGREPORT=\"BUG-REPORT-ADDRESS\" -DHAVE_LIBNCURSES=1 -DHAVE_LIBPTHREAD=1 -DHAVE_LIBREADLINE=1 -DHAVE_LIBCURSES=1 -DHAVE_LIBPTHREAD=1 -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DHAVE_FCNTL_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_SYS_TIME_H=1 -DHAVE_UNISTD_H=1 -DTIME_WITH_SYS_TIME=1 -DHAVE_UNION_SEMUN=1 -DHAVE_STDLIB_H=1 -DHAVE_MALLOC=1 -DHAVE_GETTIMEOFDAY=1 -DHAVE_MACH_TIMEBASE_INFO=1 -LDFLAGS = -m64 -L../src/ +LDFLAGS = -m64 -lstdc++ -L../src/ CFLAGS = -I../src/ -O2 -m64 RANLIB = ranlib AR = ar @@ -36,7 +36,7 @@ all: samples samples: datetimetest chaintest timertest getopttest getlongopttest settest filetest \ - shmtest semtest threadtest treetest stacktest tokentest netserver netclient \ + shmtest semtest threadtest avltest treetest stacktest tokentest netserver netclient \ listtest logtest matchtest bmtest exceptest biginttest bigdectest \ crypttest aescrypttest cmdexetest versiontest \ @@ -51,6 +51,7 @@ ./shmtest ./semtest ./threadtest + ./avltest ./treetest ./stacktest ./tokentest @@ -65,10 +66,10 @@ ./aescrypttest ./cmdexetest ./versiontest - + clean: rm -f datetimetest chaintest getopttest getlongopttest settest filetest shmtest semtest \ - threadtest treetest logtest stacktest tokentest listtest netserver netclient \ + threadtest treetest logtest stacktest tokentest listtest netserver netclient avltest \ timertest matchtest bmtest exceptest biginttest bigdectest crypttest aescrypt cmdexetest versiontest rm -f .o rm -f ~ @@ -86,9 +87,13 @@ settest: SetTest.o $(CC) $(LDFLAGS) -o settest SetTest.o ../src/Chain.o ../src/BigInteger.o +avltest: AVLTreeTest.o ../src/AVLTreeT.h + $(CC) $(LDFLAGS) -o avltest AVLTreeTest.o ../src/Chain.o + treetest: TreeTest.o $(CC) $(LDFLAGS) -o treetest TreeTest.o ../src/Chain.o + logtest: LogTest.o $(CC) $(LDFLAGS) -o logtest LogTest.o ../src/Logger.o ../src/Chain.o ../src/Tokenizer.o ../src/File.o ../src/Datetime.o @@ -159,7 +164,7 @@ $(CC) $(LDFLAGS) -o aescrypttest AESCryptTest.o ../src/AESCrypt.o ../src/Chain.o $(LIBS) cmdexetest: CmdExeTest.o - $(CC) $(LDFLAGS) -o cmdexetest CmdExeTest.o ../src/CommandExecuter.o ../src/Chain.o ../src/SigHandler.o $(LIBS) + $(CC) $(LDFLAGS) -o cmdexetest CmdExeTest.o ../src/CommandExecuter.o ../src/Chain.o ../src/SigHandler.o ../src/File.o ../src/Tokenizer.o $(LIBS) versiontest: VersionTest.o $(CC) $(LDFLAGS) -o versiontest VersionTest.o ../src/Version.o @@ -187,6 +192,6 @@ ListTest.o: ListTest.cc FileTest.o: FileTest.cc TimerTest.o: TimerTest.cc - +AVLTreeTest.o: AVLTreeTest.cc ../src/AVLTreeT.h
[-] [+]	Changed	lfc-1.4.1.tar.bz2/samples/Makefile.in ^
@@ -36,7 +36,7 @@ all: samples samples: datetimetest chaintest timertest getopttest getlongopttest settest filetest \ - shmtest semtest threadtest treetest stacktest tokentest netserver netclient \ + shmtest semtest threadtest avltest treetest stacktest tokentest netserver netclient \ listtest logtest matchtest bmtest exceptest biginttest bigdectest \ crypttest aescrypttest cmdexetest versiontest \ @@ -51,6 +51,7 @@ ./shmtest ./semtest ./threadtest + ./avltest ./treetest ./stacktest ./tokentest @@ -65,10 +66,10 @@ ./aescrypttest ./cmdexetest ./versiontest - + clean: rm -f datetimetest chaintest getopttest getlongopttest settest filetest shmtest semtest \ - threadtest treetest logtest stacktest tokentest listtest netserver netclient \ + threadtest treetest logtest stacktest tokentest listtest netserver netclient avltest \ timertest matchtest bmtest exceptest biginttest bigdectest crypttest aescrypt cmdexetest versiontest rm -f .o rm -f ~ @@ -86,9 +87,13 @@ settest: SetTest.o $(CC) $(LDFLAGS) -o settest SetTest.o ../src/Chain.o ../src/BigInteger.o +avltest: AVLTreeTest.o ../src/AVLTreeT.h + $(CC) $(LDFLAGS) -o avltest AVLTreeTest.o ../src/Chain.o + treetest: TreeTest.o $(CC) $(LDFLAGS) -o treetest TreeTest.o ../src/Chain.o + logtest: LogTest.o $(CC) $(LDFLAGS) -o logtest LogTest.o ../src/Logger.o ../src/Chain.o ../src/Tokenizer.o ../src/File.o ../src/Datetime.o @@ -159,7 +164,7 @@ $(CC) $(LDFLAGS) -o aescrypttest AESCryptTest.o ../src/AESCrypt.o ../src/Chain.o $(LIBS) cmdexetest: CmdExeTest.o - $(CC) $(LDFLAGS) -o cmdexetest CmdExeTest.o ../src/CommandExecuter.o ../src/Chain.o ../src/SigHandler.o $(LIBS) + $(CC) $(LDFLAGS) -o cmdexetest CmdExeTest.o ../src/CommandExecuter.o ../src/Chain.o ../src/SigHandler.o ../src/File.o ../src/Tokenizer.o $(LIBS) versiontest: VersionTest.o $(CC) $(LDFLAGS) -o versiontest VersionTest.o ../src/Version.o @@ -187,6 +192,6 @@ ListTest.o: ListTest.cc FileTest.o: FileTest.cc TimerTest.o: TimerTest.cc - +AVLTreeTest.o: AVLTreeTest.cc ../src/AVLTreeT.h
	Added	lfc-1.4.1.tar.bz2/samples/aescrypttest ^
[-] [+]	Added	lfc-1.4.1.tar.bz2/src/AVLTreeT.h ^
@@ -0,0 +1,1280 @@ +#ifndef _AVLTREET_H_INCLUDED_ +#define _AVLTREET_H_INCLUDED_ +/////////////////////////////////////////////////////////////////////////////// +// +// AVLTreeT.h +// ------- +// +// Design and Implementation by Bjoern Lemke +// +// (C)opyright 2013 Bjoern Lemke +// +// This program is free software; you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation; either version 2, or (at your option) +// any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; see the file COPYING. If not, write to +// the Free Software Foundation, 59 Temple Place - Suite 330, +// Boston, MA 02111-1307, USA. +// +// INTERFACE MODULE +// +// Class: AVLTreeT template class +// +// Description: template native binary tree implementation (not balanced) +// +// Status: IMPLEMENTED +/////////////////////////////////////////////////////////////////////////////// + +#include <iostream> +using namespace std; + +template <class T> +class AVLTreeT { + +public: + + AVLTreeT(); + AVLTreeT(const AVLTreeT<T>& x); + ~AVLTreeT(); + bool isEmpty(); + void Empty(); + void Insert(const T& element); + bool Remove(const T& element); + T* Find(const T& element) const; + T* First(); + T* Next(); + + unsigned long Size(); + + void* getTreePointer(); + void setTreePointer(void* treePointer); + + AVLTreeT<T>& operator = (const AVLTreeT<T>& x); + bool operator == (const AVLTreeT<T>& x); + bool operator < (const AVLTreeT<T>& x); + bool operator > (const AVLTreeT<T>& x); + + void printTree(); + +private: + + class AVLElement { + + public: + + AVLElement() + { + parent=0; + left=0; + right=0; + height=0; + } + + ~AVLElement() + { + if ( left ) + delete left; + if ( right ) + delete right; + } + + T element; + AVLElement* parent; + AVLElement* left; + AVLElement* right; + int height; + }; + + + void balanceTree(AVLElement* pElement); + void rotateRR(AVLElement* pElement); + void rotateLL(AVLElement* pElement); + void rotateRL(AVLElement* pElement); + void rotateLR(AVLElement* pElement); + + void printNode(AVLElement pNode, int level); + + AVLElement getFirst() const + { + AVLElement* pElement = _rootElement; + + if (pElement) + { + while (pElement->left) + { + pElement = pElement->left; + } + if (pElement) + { + return pElement; + } + else + { + return (AVLElement)0; + } + } + return (AVLElement)0; + } + + + AVLElement* getNext(AVLElement* pElement) const + { + if (pElement) + { + if (pElement->right) + { + pElement = pElement->right; + while (pElement->left) + { + pElement = pElement->left; + } + return pElement; + } + else + { + if (pElement->parent) + { + if (pElement->parent->left == pElement) + { + pElement = pElement->parent; + return pElement; + } + else + { + while (pElement->parent->left != pElement) + { + pElement = pElement->parent; + if (!pElement->parent) + { + return (AVLElement)0; + } + } + pElement = pElement->parent; + return pElement; + } + } + else + { + return (AVLElement)0; + } + } + } + return (AVLElement)0; + } + + AVLElement _rootElement; + AVLElement* _treePointer; + unsigned long _size; +}; + + +template<class T> AVLTreeT<T>::AVLTreeT() +{ + _rootElement = 0; + _treePointer = 0; + _size = 0; +} + +template<class T> AVLTreeT<T>::AVLTreeT(const AVLTreeT<T>& x) +{ + _rootElement = 0; + _treePointer = 0; + _size = 0; + + if (x._rootElement) + { + _rootElement = new AVLElement; + _rootElement->parent=0; + _rootElement->left=0; + _rootElement->right=0; + _rootElement->element = x._rootElement->element; + _size++; + } + AVLElement* sourcePointer = x._rootElement; + AVLElement* targetPointer = _rootElement; + + while (sourcePointer) + { + if (sourcePointer->left) + { + sourcePointer = sourcePointer->left; + targetPointer->left = new AVLElement; + targetPointer->left->parent = targetPointer; + targetPointer = targetPointer->left; + targetPointer->element = sourcePointer->element; + targetPointer->left = 0; + targetPointer->right = 0; + _size++; + } + else if (sourcePointer->right) + { + sourcePointer = sourcePointer->right; + targetPointer->right = new AVLElement; + targetPointer->right->parent = targetPointer; + targetPointer = targetPointer->right; + targetPointer->element = sourcePointer->element; + targetPointer->left = 0; + targetPointer->right = 0; + _size++; + } + else + { + if (sourcePointer->parent) + { + while(sourcePointer->parent->right == sourcePointer) + { + sourcePointer = sourcePointer->parent; + targetPointer = targetPointer->parent; + if (!sourcePointer->parent) + { + return; + } + } + AVLElement* parentPointer=sourcePointer; + sourcePointer = sourcePointer->parent; + targetPointer = targetPointer->parent; + while (sourcePointer->right == parentPointer \|\| sourcePointer->right == 0) + { + parentPointer = sourcePointer; + sourcePointer = sourcePointer->parent; + targetPointer = targetPointer->parent; + if (!sourcePointer) + { + return; + } + } + sourcePointer = sourcePointer->right; + targetPointer->right = new AVLElement; + targetPointer->right->parent = targetPointer; + targetPointer = targetPointer->right; + targetPointer->element = sourcePointer->element; + targetPointer->left = 0; + targetPointer->right = 0; + _size++; + } + else + { + return; + } + } + } + return; +} + +template<class T> AVLTreeT<T>::~AVLTreeT() +{ + if (_rootElement) + delete _rootElement; + _rootElement = 0; + + _size = 0; + _treePointer = 0; +} + +template<class T> bool AVLTreeT<T>::isEmpty() +{ + if (_rootElement == 0) + { + return true; + } + return false; +} + +template<class T> void AVLTreeT<T>::Empty() +{ + if ( _rootElement ) + delete _rootElement; + _rootElement = 0; + + _size = 0; + _treePointer = 0; +} + +template<class T> void AVLTreeT<T>::Insert(const T& element) +{ + if (_rootElement) + { + AVLElement* pElement = _rootElement; + AVLElement* pParentElement; + + bool inserted = false; + + while ( ! inserted ) + { + if ( pElement->element > element ) + { + if ( pElement->left == 0 ) + { + pElement->left = new AVLElement; + pElement->left->element = element; + pElement->left->parent = pElement; + pElement->left->height = 1; + inserted=true; + } + else + { + pElement = pElement->left; + } + } + else + { + if ( pElement->right == 0 ) + { + // insert at right + pElement->right = new AVLElement; + pElement->right->element = element; + pElement->right->parent = pElement; + pElement->right->height = 1; + inserted = true; + } + else + { + pElement = pElement->right; + } + } + } + + if ( pElement->height == 1 ) + { + pElement->height = 2; + balanceTree(pElement); + } + } + else + { + _rootElement = new AVLElement; + _rootElement->element = element; + _rootElement->height = 1; + } + _size++; +} + + + +template<class T> void AVLTreeT<T>::balanceTree(AVLElement pElement) +{ + + bool doBalance = true; + + AVLElement pParent = pElement->parent; + + bool wasLeft = false; + + if ( pParent ) + wasLeft = pParent->left == pElement; + + + + while ( doBalance && pParent ) + { + int leftHeight = 0; + if ( pParent->left ) + leftHeight = pParent->left->height; + + int rightHeight = 0; + if ( pParent->right ) + rightHeight = pParent->right->height; + + /* + cout << "Balance at " << pParent->element << endl; + if ( wasLeft ) + cout << "Sub node is left" << endl; + cout << "RH=" << rightHeight << endl; + cout << "LH=" << leftHeight << endl; + / + + if ( wasLeft ) + { + pElement = pParent->left; + + if ( rightHeight > leftHeight ) + { + // right tree still higher, no need to rotate + // pParent->height = rightHeight; + + doBalance=false; + / + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + pParent = pParent->parent; + / + } + else if ( leftHeight == rightHeight ) + { + if ( leftHeight != pParent->height ) + { + pParent->height = leftHeight + 1; + + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + pParent = pParent->parent; + } + else + { + doBalance = false; + } + } + else + { + if ( rightHeight + 1 < leftHeight ) + { + int subLeftHeight = 0; + if ( pElement->left ) + subLeftHeight = pElement->left->height; + + int subRightHeight = 0; + if ( pElement->right ) + subRightHeight = pElement->right->height; + + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + AVLElement pRotate = pParent; + pParent = pParent->parent; + + if (subLeftHeight > subRightHeight) + { + rotateRR(pRotate); + } + else + { + rotateRL(pRotate); + } + } + else + { + + // just propagte height + pParent->height = leftHeight + 1; + + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + pParent = pParent->parent; + } + } + } + else + { + + pElement = pParent->right; + + if ( leftHeight > rightHeight ) + { + // pParent->height = rightHeight + 1; + + doBalance=false; + + /* + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + pParent = pParent->parent; + / + } + else if ( leftHeight == rightHeight ) + { + if ( leftHeight != pParent->height ) + { + pParent->height = leftHeight + 1; + + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + pParent = pParent->parent; + } + else + { + doBalance = false; + } + } + else + { + + if ( leftHeight + 1 < rightHeight ) + { + + int subLeftHeight = 0; + if ( pElement->left ) + subLeftHeight = pElement->left->height; + + int subRightHeight = 0; + if ( pElement->right ) + subRightHeight = pElement->right->height; + + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + + AVLElement pRotate = pParent; + pParent = pParent->parent; + + if (subLeftHeight < subRightHeight) + { + rotateLL(pRotate); + } + else + { + rotateLR(pRotate); + } + } + else + { + + // just propagte height + pParent->height = rightHeight + 1; + + if ( pParent->parent ) + wasLeft = pParent->parent->left == pParent; + + pParent = pParent->parent; + + } + } + } + + /* + cout << "Tree Status" << endl; + printTree(); + / + } +} + + +template<class T> bool AVLTreeT<T>::Remove(const T& element) +{ + AVLElement pElement = _rootElement; + + bool found = false; + + while (pElement && !found) + { + if (pElement->element < element) + { + pElement = pElement->right; + } + else if (pElement->element > element) + { + pElement = pElement->left; + } + else + { + found = true; + } + } + + if (found) + { + // TODO + cout << "Remove method for AVLTreeT still not implemented" << endl; + return false; + } + else + { + return false; + } +} + +template<class T> T* AVLTreeT<T>::Find(const T& element) const +{ + AVLElement* pElement = _rootElement; + + while (pElement) + { + if (pElement->element < element) + { + pElement = pElement->right; + } + else if (pElement->element > element) + { + pElement = pElement->left; + } + else + { + return (&(pElement->element)); + } + } + return (T)0; +} + +template<class T> T AVLTreeT<T>::First() +{ + _treePointer = getFirst(); + if (_treePointer) + { + return (&(_treePointer->element)); + } + else + { + return (T)0; + } +} + + +template<class T> T AVLTreeT<T>::Next() +{ + _treePointer = getNext(_treePointer); + + if (_treePointer) + { + return (&(_treePointer->element)); + } + else + { + return (T)0; + } +} + +template<class T> unsigned long AVLTreeT<T>::Size() +{ + return _size; +} + +template<class T> void AVLTreeT<T>::getTreePointer() +{ + return (void)_treePointer; +} + +template<class T> void AVLTreeT<T>::setTreePointer(void treePointer) +{ + _treePointer = (AVLElement)treePointer; +} + +template<class T> AVLTreeT<T>& AVLTreeT<T>::operator=(const AVLTreeT<T>& x) +{ + + // Empty(); // do we need this ? + _rootElement = 0; + _treePointer = 0; + _size=0; + + if (x._rootElement) + { + _rootElement = new AVLElement; + _rootElement->parent=0; + _rootElement->left=0; + _rootElement->right=0; + _rootElement->element = x._rootElement->element; + _size++; + } + AVLElement sourcePointer = x._rootElement; + AVLElement* targetPointer = _rootElement; + + while (sourcePointer) + { + if (sourcePointer->left) + { + sourcePointer = sourcePointer->left; + targetPointer->left = new AVLElement; + targetPointer->left->parent = targetPointer; + targetPointer = targetPointer->left; + targetPointer->element = sourcePointer->element; + targetPointer->left = 0; + targetPointer->right = 0; + _size++; + } + else if (sourcePointer->right) + { + sourcePointer = sourcePointer->right; + targetPointer->right = new AVLElement; + targetPointer->right->parent = targetPointer; + targetPointer = targetPointer->right; + targetPointer->element = sourcePointer->element; + targetPointer->left = 0; + targetPointer->right = 0; + _size++; + } + else + { + if (sourcePointer->parent) + { + while(sourcePointer->parent->right == sourcePointer) + { + sourcePointer = sourcePointer->parent; + targetPointer = targetPointer->parent; + if (!sourcePointer->parent) + { + return (this); + } + } + AVLElement parentPointer=sourcePointer; + sourcePointer = sourcePointer->parent; + targetPointer = targetPointer->parent; + while (sourcePointer->right == parentPointer \|\| sourcePointer->right == 0) + { + parentPointer = sourcePointer; + sourcePointer = sourcePointer->parent; + targetPointer = targetPointer->parent; + if (!sourcePointer) + { + return (this); + } + } + sourcePointer = sourcePointer->right; + targetPointer->right = new AVLElement; + targetPointer->right->parent = targetPointer; + targetPointer = targetPointer->right; + targetPointer->element = sourcePointer->element; + targetPointer->left = 0; + targetPointer->right = 0; + _size++; + } + else + { + return (this); + } + } + } + return (this); +} + +template<class T> bool AVLTreeT<T>::operator==(const AVLTreeT<T>& x) +{ + + AVLElement pElement1 = getFirst(); + AVLElement* pElement2 = x.getFirst(); + + while (pElement1 && pElement2) + { + if (pElement1->element == pElement2->element) + { + pElement1 = getNext(pElement1); + pElement2 = x.getNext(pElement2); + } + else + { + return false; + } + } + + if (pElement1 \|\| pElement2) + { + return false; + } + else + { + return true; + } +} + +template<class T> bool AVLTreeT<T>::operator < (const AVLTreeT<T>& x) +{ + + AVLElement* pElement1 = getFirst(); + AVLElement* pElement2 = x.getFirst(); + + while (pElement1 && pElement2) + { + + if (pElement1->element < pElement2->element) + { + return true; + } + else if (pElement1->element > pElement2->element) + { + return false; + } + else + { + pElement1 = getNext(pElement1); + pElement2 = x.getNext(pElement2); + } + } + + if (pElement1) + { + return false; + } + else if (pElement2) + { + return true; + } + else + { + return false; + } + +} + +template<class T> bool AVLTreeT<T>::operator > (const AVLTreeT<T>& x) +{ + + AVLElement* pElement1 = getFirst(); + AVLElement* pElement2 = x.getFirst(); + + while (pElement1 && pElement2) + { + if (pElement1->element > pElement2->element) + { + return true; + } + else if (pElement1->element < pElement2->element) + { + return false; + } + else + { + pElement1 = getNext(pElement1); + pElement2 = x.getNext(pElement2); + } + } + + if (pElement1) + { + return true; + } + else if (pElement2) + { + return false; + } + else + { + return false; + } +} + + +template<class T> void AVLTreeT<T>::rotateLL(AVLElement* pNode) +{ + + // cout << "Rotate LL at " << pNode->element << endl; + + AVLElement pNodeP = 0; + AVLElement pNodeA = 0; + AVLElement pNodeB = 0; + + // setting up required nodes + + pNodeP = pNode->parent; + pNodeA = pNode->right; + if ( pNodeA ) + { + pNodeB = pNodeA->left; + } + + // making rotation + + if ( pNodeA ) + { + pNodeA->left = pNode; + pNodeA->parent = pNodeP; + } + + if ( pNodeB ) + { + pNodeB->parent = pNode; + } + + pNode->right = pNodeB; + pNode->parent = pNodeA; + + if ( pNodeP ) + { + if ( pNodeP->right == pNode ) + { + pNodeP->right = pNodeA; + } + else + { + pNodeP->left = pNodeA; + } + } + else + { + _rootElement = pNodeA; + } + + + int leftHeight = 0; + int rightHeight = 0; + + if ( pNode->left ) + leftHeight = pNode->left->height; + if ( pNode->right ) + rightHeight = pNode->right->height; + pNode->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + + if ( pNodeA ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeA->left ) + leftHeight = pNodeA->left->height; + if ( pNodeA->right ) + rightHeight = pNodeA->right->height; + + pNodeA->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } + + if ( pNodeP ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeP->left ) + leftHeight = pNodeP->left->height; + if ( pNodeP->right ) + rightHeight = pNodeP->right->height; + pNodeP->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } +} + +template<class T> void AVLTreeT<T>::rotateRR(AVLElement pNode) +{ + + // cout << "Rotate RR at " << pNode->element << endl; + + AVLElement pNodeP = 0; + AVLElement pNodeA = 0; + AVLElement* pNodeB = 0; + + // setting up required nodes + pNodeP = pNode->parent; + pNodeA = pNode->left; + if ( pNodeA ) + { + pNodeB = pNodeA->right; + } + + // making rotation + if ( pNodeA ) + { + pNodeA->right = pNode; + pNodeA->parent = pNodeP; + } + + if ( pNodeB ) + { + pNodeB->parent = pNode; + } + + pNode->parent = pNodeA; + pNode->left = pNodeB; + + if ( pNodeP ) + { + if ( pNodeP->right == pNode ) + { + pNodeP->right = pNodeA; + } + else + { + pNodeP->left = pNodeA; + } + } + else + { + _rootElement = pNodeA; + } + + + int leftHeight = 0; + int rightHeight = 0; + + if ( pNode->left ) + leftHeight = pNode->left->height; + if ( pNode->right ) + rightHeight = pNode->right->height; + + pNode->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + + if ( pNodeA ) + { + leftHeight = 0; + rightHeight = 0; + if ( pNodeA->left ) + leftHeight = pNodeA->left->height; + if ( pNodeA->right ) + rightHeight = pNodeA->right->height; + + pNodeA->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } + + if ( pNodeP ) + { + leftHeight = 0; + rightHeight = 0; + if ( pNodeP->left ) + leftHeight = pNodeP->left->height; + if ( pNodeP->right ) + rightHeight = pNodeP->right->height; + pNodeP->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } +} + +template<class T> void AVLTreeT<T>::rotateLR(AVLElement* pNode) +{ + + // cout << "Rotate LR at " << pNode->element << endl; + + AVLElement pNodeP = 0; + AVLElement pNodeA = 0; + AVLElement* pNodeB = 0; + AVLElement* pNodeC = 0; + AVLElement* pNodeD = 0; + + pNodeP = pNode->parent; + pNodeA = pNode->right; + + if ( pNodeA ) + { + pNodeB = pNodeA->left; + + } + if ( pNodeB ) + { + pNodeD = pNodeB->right; + pNodeC = pNodeB->left; + } + + if ( pNodeA ) + { + pNodeA->left = pNodeD; + pNodeA->parent = pNodeB; + } + + if ( pNodeB ) + { + pNodeB->left = pNode; + pNodeB->parent = pNodeP; + pNodeB->right = pNodeA; + } + + if ( pNodeC ) + pNodeC->parent = pNode; + + if ( pNodeD ) + pNodeD->parent = pNodeA; + + if ( pNodeP ) + { + if ( pNodeP->right == pNode ) + { + pNodeP->right = pNodeB; + } + else + { + pNodeP->left = pNodeB; + } + } + else + { + _rootElement = pNodeB; + } + + pNode->parent = pNodeB; + pNode->right = pNodeC; + + int leftHeight = 0; + int rightHeight = 0; + + if ( pNode->left ) + leftHeight = pNode->left->height; + if ( pNode->right ) + rightHeight = pNode->right->height; + pNode->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + + if ( pNodeA ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeA->left ) + leftHeight = pNodeA->left->height; + if ( pNodeA->right ) + rightHeight = pNodeA->right->height; + pNodeA->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } + + if ( pNodeB ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeB->left ) + leftHeight = pNodeB->left->height; + if ( pNodeB->right ) + rightHeight = pNodeB->right->height; + pNodeB->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } + + if ( pNodeP ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeP->left ) + leftHeight = pNodeP->left->height; + if ( pNodeP->right ) + rightHeight = pNodeP->right->height; + pNodeP->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } +} + + + +template<class T> void AVLTreeT<T>::rotateRL(AVLElement* pNode) +{ + + // cout << "Rotate RL at " << pNode->element << endl; + + AVLElement pNodeP = 0; + AVLElement pNodeA = 0; + AVLElement* pNodeB = 0; + AVLElement* pNodeC = 0; + AVLElement* pNodeD = 0; + + pNodeP = pNode->parent; + pNodeA = pNode->left; + + if ( pNodeA ) + pNodeB = pNodeA->right; + + if ( pNodeB ) + { + pNodeC = pNodeB->left; + pNodeD = pNodeB->right; + } + + if ( pNodeC ) + pNodeC->parent = pNodeA; + + if ( pNodeP ) + { + if ( pNodeP->right == pNode) + { + pNodeP->right = pNodeB; + } + else + { + pNodeP->left = pNodeB; + } + } + else + { + _rootElement = pNodeB; + } + + if ( pNodeB ) + { + pNodeB->parent = pNodeP; + pNodeB->left = pNodeA; + pNodeB->right = pNode; + } + + if ( pNodeA ) + { + pNodeA->parent = pNodeB; + pNodeA->right = pNodeC; + } + + if ( pNodeD ) + pNodeD->parent = pNode; + + pNode->parent = pNodeB; + pNode->left = pNodeD; + + // set up balance + + int leftHeight = 0; + int rightHeight = 0; + + if ( pNode->left ) + leftHeight = pNode->left->height; + + if ( pNode->right ) + rightHeight = pNode->right->height; + + pNode->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + + if ( pNodeA ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeA->left ) + leftHeight = pNodeA->left->height; + if ( pNodeA->right ) + rightHeight = pNodeA->right->height; + + pNodeA->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } + + if ( pNodeB ) + { + leftHeight = 0; + rightHeight = 0; + + if ( pNodeB->left ) + leftHeight = pNodeB->left->height; + if ( pNodeB->right ) + rightHeight = pNodeB->right->height; + + pNodeB->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } + + if ( pNodeP ) + { + + leftHeight = 0; + rightHeight = 0; + + if ( pNodeP->left ) + leftHeight = pNodeP->left->height; + if ( pNodeP->right ) + rightHeight = pNodeP->right->height; + + pNodeP->height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; + } +} + +template<class T> void AVLTreeT<T>::printTree() +{ + cout << "-------------------------" << endl; + printNode(_rootElement, 0); + cout << "-------------------------" << endl; +} + +template<class T> void AVLTreeT<T>::printNode(AVLElement *pNode, int level) +{ + + if (pNode) + { + + if ( pNode->right) + { + printNode(pNode->right,level+1); + } + + int i=level; + while ( i ) + { + cout << " "; + i--; + } + + cout << pNode->element << "/" << pNode->height; + if ( pNode->parent ) + cout << "/" << pNode->parent->element << endl; + else + cout << " nil " << endl; + + if ( pNode->left) + { + printNode(pNode->left, level+1); + } + } +} + +#endif +
[-] [+]	Changed	lfc-1.4.1.tar.bz2/src/Makefile.in ^
@@ -73,6 +73,7 @@ $(INSTALL_DATA) SetT.h $(DESTDIR)$(INCLUDEPREFIX) $(INSTALL_DATA) StackT.h $(DESTDIR)$(INCLUDEPREFIX) $(INSTALL_DATA) TreeT.h $(DESTDIR)$(INCLUDEPREFIX) + $(INSTALL_DATA) AVLTreeT.h $(DESTDIR)$(INCLUDEPREFIX) $(INSTALL_DATA) Datetime.h $(DESTDIR)$(INCLUDEPREFIX) $(INSTALL_DATA) Bitmap.h $(DESTDIR)$(INCLUDEPREFIX) $(INSTALL_DATA) BigInteger.h $(DESTDIR)$(INCLUDEPREFIX)
[-] [+]	Changed	lfc-1.4.1.tar.bz2/src/Version.cc ^
@@ -32,4 +32,4 @@ // Status: IMPLEMENTED /////////////////////////////////////////////////////////////////////////////// -char __lfcVersionString[] = "1.3.7"; +char __lfcVersionString[] = "1.4.1";