From 940d36d8a1521f171674e358dada3305e66d48da Mon Sep 17 00:00:00 2001 From: "admin@omencraft.com" Date: Sun, 30 Oct 2011 18:15:44 +0000 Subject: put the timer and quicksort functions into their own files. Made a few changes to the converter. Converter doesn't understand Entity tags and some chunks cause it to segfault for a currently unknown reason. git-svn-id: http://mc-server.googlecode.com/svn/trunk@28 0a769ca7-a7f5-676a-18bf-c427514a06d6 --- converter/cConvert.cpp | 238 +++++++++++------------------------------------- converter/cNBTData.cpp | 74 +++++++-------- converter/cNBTData.h | 12 +-- converter/denotch | Bin 169472 -> 165672 bytes converter/quicksort.cpp | 88 ++++++++++++++++++ converter/quicksort.h | 9 ++ converter/timer.cpp | 9 ++ converter/timer.h | 8 ++ 8 files changed, 210 insertions(+), 228 deletions(-) create mode 100644 converter/quicksort.cpp create mode 100644 converter/quicksort.h create mode 100644 converter/timer.cpp create mode 100644 converter/timer.h (limited to 'converter') diff --git a/converter/cConvert.cpp b/converter/cConvert.cpp index e31730bf3..445d38796 100644 --- a/converter/cConvert.cpp +++ b/converter/cConvert.cpp @@ -1,4 +1,3 @@ -// reading a complete binary file #include #include #include @@ -6,14 +5,9 @@ #include #include #include "zlib.h" -#include #include "cNBTData.h" - -void quicksort(int*, int, int); -int partition(int*, int, int, int); -int median3(int*,int,int); -void swap(int &, int &); -double diffclock(clock_t, clock_t); +#include "timer.h" +#include "quicksort.h" using namespace std; @@ -48,9 +42,9 @@ int main () { unsigned char byte1 = 0; unsigned char byte2 = 0; unsigned char byte3 = 0; - unsigned char byte4 = 0; - unsigned char byte5 = 0; - unsigned char trash = 0; + unsigned char byte4 = 0; + unsigned char byte5 = 0; + unsigned char trash = 0; unsigned int frloc = 0; int toffset = 0; int compdlength = 0; @@ -72,7 +66,7 @@ int main () { toffset = 4096 * ((byte1*256*256) + (byte2*256) + byte3);//find the chunk offsets using the first three bytes of each long; toffarr[i] = toffset;//array of chunk offset locatiosn in the fle. } - for ( short i = 0; i < 4096; i++ ) {//loop through next 4096 bytes of the header. + for ( short i = 0; i < 4096; i++ ) {//loop through next 4096 bytes of the header. //keeping this code here in case we need it later. not using it right now. if( fread( &trash, sizeof(byte4), 1, f) != 1 ) { cout << "ERROR 2jkd READING FROM FILE " << SourceFile; fclose(f); return false; } } @@ -80,65 +74,38 @@ int main () { quicksort(toffarr, 0, 1023); //sort the array from smallest to larget offset locations so we only have to read through the file once. for ( short ia = 0; ia < 1024; ia++ ) {//a region file can hold a maximum of 1024 chunks (32*32) + if (ia == 31) { ia++; } if (toffarr[ia] < 8192) { //offsets of less than 8192 are impossible. 0 means there is no chunk in a particular location. if (toffarr[ia] > 0) { cout << "ERROR 2s31 IN COLLECTED CHUNK OFFSETS " << toffarr[ia]; fclose(f); return false; } //values between 0 and 8192 should be impossible. //This file does not contain the max 1024 chunks, skip until we get to the first } else { // found a chunk offset value //Chunk data begins with a (big-endian) four-byte length field which indicates the exact length of the remaining chunk data in bytes. The following byte indicates the compression scheme used for chunk data, and the remaining (length-1) bytes are the compressed chunk data. + printf("Working on chunk %i\n", ia); if( fread( &byte1, sizeof(byte1), 1, f) != 1 ) { cout << "ERROR 2t32 READING FROM FILE " << SourceFile; fclose(f); return false; } if( fread( &byte2, sizeof(byte2), 1, f) != 1 ) { cout << "ERROR 2y51 READING FROM FILE " << SourceFile; fclose(f); return false; } if( fread( &byte3, sizeof(byte3), 1, f) != 1 ) { cout << "ERROR 3424 READING FROM FILE " << SourceFile; fclose(f); return false; } if( fread( &byte4, sizeof(byte4), 1, f) != 1 ) { cout << "ERROR sd22 READING FROM FILE " << SourceFile; fclose(f); return false; } compdlength = ((byte1*256*256*256) + (byte2*256*256) + (byte3*256) + byte4 - 0); //length of compressed chunk data if( fread( &byte5, sizeof(byte5), 1, f) != 1 ) { cout << "ERROR 2341 READING FROM FILE " << SourceFile; fclose(f); return false; } //compression type, 1 = GZip (RFC1952) (unused in practice) , 2 = Zlib (RFC1950) - //printf("byte1: %x \n", byte1); - //printf("byte2: %x \n", byte2); - //printf("byte3: %x \n", byte3); - //printf("byte4: %x \n", byte4); - - frloc += 5; //moved ahead 5 bytes while reading data. - //cout << compdlength << endl; return 1; - //unsigned char* comp_data = new unsigned char[ compdlength ]; - //cout << "size of comp_data: " << compdlength << endl; - //cout << "size of comp_data2: " << sizeof(comp_data) << endl; - //fread( comp_data, sizeof(unsigned char), compdlength, f); - //if( fread( &comp_data, sizeof(unsigned char), compdlength, f) != 1 ) { cout << "ERROR 1234 READING FROM FILE " << SourceFile; fclose(f); return false; } //actual compressed chunk data - //cout << "frloc: " << frloc << endl; + //printf("byte1: %i\n", byte1); + //printf("byte2: %i\n", byte2); + //printf("byte3: %i\n", byte3); + //printf("byte4: %i\n", byte4); + //printf("byte5: %i\n", byte5); + frloc += 5; //moved ahead 5 bytes while reading data. // TODO - delete [] temparr after you're done with it, now it's a memory leak - char* temparr = new char[compdlength]; //can't get fread to read more than one char at a time into a char array... so that's what I'll do. :( At least it works. - if( fread( temparr, compdlength, 1, f) != 1 ) { cout << "ERROR rf22 READING FROM FILE " << SourceFile; fclose(f); return false; } + char* compBlockData = new char[compdlength]; //can't get fread to read more than one char at a time into a char array... so that's what I'll do. :( At least it works. + if( fread( compBlockData, compdlength, 1, f) != 1 ) { cout << "ERROR rf22 READING FROM FILE " << SourceFile; fclose(f); return false; } frloc = frloc + compdlength; - /* - int re = 0; - char tempbyte = 0; - while (re < compdlength) { //loop through file and read contents into char array a byte at a time. - if( fread( &tempbyte, sizeof(tempbyte), 1, f) != 1 ) { cout << "ERROR rf22 READING FROM FILE " << SourceFile; fclose(f); return false; } - temparr[re] = tempbyte; - re++; - frloc++; - } - - */ - //if( fread( comp_data, compdlength, sizeof(unsigned char), f) != 1 ) { cout << "ERROR 1234 READING FROM FILE " << SourceFile <cNBTCompound << endl; - //cout << BlockDataString << endl; //testing of nbtparser. cNBTData* NBTData = new cNBTData(BlockData, (testr)); - //NBTData->m_bDecompressed = true; NBTData->ParseData(); - NBTData->PrintData(); - - //NBTData->GetByteArray("Blocks"); - //for(unsigned int i = 0; i < 111; i++) {//re - //printf("Blocks?: %i\n", NBTData->cNBTCompound::GetByteArray("Blocks")[0]); - NBTData->OpenCompound(""); - NBTData->OpenCompound("Level"); // You need to open the right compounds before you can access the data in it - printf("xPos: %i\n", NBTData->GetInteger("xPos") ); - //will print - //xPos: 0 - printf("test: %i\n", NBTData->GetByteArray("Blocks")[0] ); + //NBTData->PrintData(); + NBTData->OpenCompound(""); + NBTData->OpenCompound("Level"); // You need to open the right compounds before you can access the data in it + + //NBT Data for blocks should look something like this: + //==== STRUCTURED NBT DATA ==== + // COMPOUND ( ) + // COMPOUND + // COMPOUND (Level) + // LIST (Entities) + // LIST (TileEntities) + // INTEGER LastUpdate (0) + // INTEGER xPos (0) + // INTEGER zPos (0) + // BYTE TerrainPopulated (1) + // BYTE ARRAY BlockLight (length: 16384) + // BYTE ARRAY Blocks (length: 32768) + // BYTE ARRAY Data (length: 16384) + // BYTE ARRAY HeightMap (length: 256) + // BYTE ARRAY SkyLight (length: 16384) + //============================= + + + for(unsigned int i = 0; i < 16384; i++) { + //printf("array HM: %i\n", NBTData->GetByteArray("HeightMap")[i]); + } + for(unsigned int i = 0; i < 32768; i++) { + //printf("array Blocks: %i\n", NBTData->GetByteArray("Blocks")[i]); + } + + //printf("xPos: %i\n", NBTData->GetInteger("xPos") ); NBTData->CloseCompound();// Close the compounds after you're done NBTData->CloseCompound(); - //} - return 1; + fwrite( BlockData, DestSize, 1, wf ); //write contents of uncompressed block data to file to check to see if it's valid... It is! :D - //fwrite( &temparr, compdlength, sizeof(unsigned char), wf ); - //cin >> n; //just to see screen output - //delete [] comp_data; - //return 0; + delete [] compBlockData; delete [] BlockData; + while ( (frloc < toffarr[ia+1]) && (ia<1023) ) { //loop through Notch's junk data until we get to another chunk offset possition to start the loop again if( fread( &trash, sizeof(byte4), 1, f) != 1 ) { cout << "ERROR 2nkd READING FROM FILE " << SourceFile; fclose(f); return false; } frloc ++; @@ -206,18 +177,7 @@ int main () { //if (ia == 30) { break; } } //return 0; -/* - for( short i = 0; i < 1024 ; ++i ) { - if( fread( &byte1, sizeof(byte1), 1, f) != 1 ) { cout << "ERROR READING FROM FILE " << SourceFile; fclose(f); return false; } - if( fread( &byte2, sizeof(byte2), 1, f) != 1 ) { cout << "ERROR READING FROM FILE " << SourceFile; fclose(f); return false; } - if( fread( &byte3, sizeof(byte3), 1, f) != 1 ) { cout << "ERROR READING FROM FILE " << SourceFile; fclose(f); return false; } - if( fread( &byte4, sizeof(byte4), 1, f) != 1 ) { cout << "ERROR READING FROM FILE " << SourceFile; fclose(f); return false; } - - } - //printf("value: %x \n",trash); - -*/ for ( short i = 0; i < 1024; i++ ) { //cout << toffarr[i] << endl; } @@ -238,95 +198,3 @@ int main () { } - - -double diffclock(clock_t clock1,clock_t clock2) -{ - double diffticks=clock1-clock2; - double diffms=(diffticks*10)/CLOCKS_PER_SEC; - return diffms; -} - -// Quicksort controller function, it partitions the different pieces of our array. -void quicksort(int *arIntegers, int left, int right) -{ -/* cout << "quicksort ([" << arIntegers[0] << "," - << arIntegers[1] << "," - << arIntegers[2] << "," - << arIntegers[3] << "," - << arIntegers[4] << "," - << arIntegers[5] << "," - << arIntegers[6] << "]," - << left << "," - << right << ")\n"; -*/ - if (right > left) - { - int pivotIndex = median3(arIntegers,left,right); - int pivotNewIndex = partition(arIntegers, left, right, pivotIndex); - - // Recursive call to quicksort to sort each half. - quicksort(arIntegers, left, pivotNewIndex-1); - quicksort(arIntegers, pivotNewIndex+1, right); - } -} - -int median3(int *arIntegers,int left,int right) -{ - int center = (left+right)/2; - - if(arIntegers[center] < arIntegers[left]) - swap(arIntegers[left],arIntegers[center]); - if(arIntegers[right] < arIntegers[left]) - swap(arIntegers[left],arIntegers[right]); - if(arIntegers[right] < arIntegers[center]) - swap(arIntegers[center],arIntegers[right]); - - swap(arIntegers[center],arIntegers[right-1]); - - return center; -} - -// This function takes an array (or one half an array) and sorts it. -// It then returns a new pivot index number back to quicksort. - -int partition(int *arIntegers, int left, int right, int pivot) -{ -/* cout << "partition ("<< arIntegers[0] << "," - << arIntegers[1] << "," - << arIntegers[2] << "," - << arIntegers[3] << "," - << arIntegers[4] << "," - << arIntegers[5] << "," - << arIntegers[6] << "]," - << left << "," - << right << ")\n"; -*/ - int pivotValue = arIntegers[pivot]; - - // Swap it out all the way to the end of the array - // So we know where it always is. - swap(arIntegers[pivot], arIntegers[right]); - int storeIndex = left; - - // Move through the array from start to finish comparing each to our - // pivot value (not index, the value that was located at the pivot index) - for (int i = left; i < right; i++) - { - if (arIntegers[i] <= pivotValue) - { - swap(arIntegers[i], arIntegers[storeIndex]); - storeIndex++; - } - } - swap(arIntegers[storeIndex], arIntegers[right]); - return storeIndex; -} - -// Simple swap function for our in place swapping. -void swap(int &val1, int &val2) -{ - int temp = val1; - val1 = val2; - val2 = temp; -} diff --git a/converter/cNBTData.cpp b/converter/cNBTData.cpp index fc0dd628e..c54f7d74e 100644 --- a/converter/cNBTData.cpp +++ b/converter/cNBTData.cpp @@ -145,7 +145,7 @@ void cNBTData::Compress() if( ret != Z_STREAM_END ) { - printf("WARNING: Compressing didn't go to end of stream\n");//re + //printf("WARNING: Compressing didn't go to end of stream\n");//re } if(m_Buffer) @@ -249,7 +249,7 @@ void cNBTCompound::AppendInteger( std::string & a_Buffer, int a_Value ) void cNBTCompound::Serialize(std::string & a_Buffer) { - printf("cNBTCompound::Serialize()\n");//re + //printf("cNBTCompound::Serialize()\n");//re for( CompoundMap::iterator itr = m_Compounds.begin(); itr != m_Compounds.end(); itr++ ) { if( itr->second == 0 ) continue; @@ -357,10 +357,10 @@ void cNBTCompound::PrintData( int a_Depth, std::string a_Name ) printf("%s BYTE %s (%i)\n", Prefix, itr->first.c_str(), itr->second ); } - for( ByteArrayMap::iterator itr = m_ByteArrays.begin(); itr != m_ByteArrays.end(); itr++ ) - { - printf("%s BYTE ARRAY %s (length: %i)\n", Prefix, itr->first.c_str(), sizeof(itr->second) ); - } + for( ByteArrayMap::iterator itr = m_ByteArrays.begin(); itr != m_ByteArrays.end(); itr++ ) + { + printf("%s BYTE ARRAY %s (length: %li)\n", Prefix, itr->first.c_str(), sizeof(itr->second) ); + } delete Prefix; } @@ -383,7 +383,7 @@ void cNBTData::Serialize() memcpy( m_Buffer, Buffer.c_str(), Buffer.size() ); m_BufferSize = Buffer.size(); -printf("m_BufferSize1: %i\n", m_BufferSize);//re + //printf("m_BufferSize1: %i\n", m_BufferSize);//re //for(unsigned int i = 0; i < m_BufferSize; i++)//re //{//re @@ -400,18 +400,18 @@ void cNBTData::ParseData() } m_Index = 0; - printf("m_BufferSize2: %i\n", m_BufferSize);//re - printf("cNBTData::ParseData()\n");//re + //printf("m_BufferSize2: %i\n", m_BufferSize);//re + //printf("cNBTData::ParseData()\n");//re //for(unsigned int i = 0; i < m_BufferSize; i++)//re - for(unsigned int i = 0; i < 70; i++)//re - {//re - printf("echo%02i %02x %3i %c\n", i, (unsigned char)m_Buffer[i], (unsigned char)m_Buffer[i], m_Buffer[i] );//re - }//re + //for(unsigned int i = 0; i < 70; i++)//re + //{//re + // printf("echo%02i %02x %3i %c\n", i, (unsigned char)m_Buffer[i], (unsigned char)m_Buffer[i], m_Buffer[i] );//re + //}//re while( m_Index < m_BufferSize ) { - printf("m_BufferSize3: %i\n", m_BufferSize); - printf("m_Index: %i\n", m_Index); + //printf("m_BufferSize3: %i\n", m_BufferSize); + //printf("m_Index: %i\n", m_Index); ParseTags(); } } @@ -420,20 +420,20 @@ void cNBTData::ParseTags() { if( m_Index < m_BufferSize ) { - printf("ParseTags idx:%02i %02x %3i %c\n", m_Index, (unsigned char)m_Buffer[m_Index], (unsigned char)m_Buffer[m_Index], m_Buffer[m_Index] );//re + //printf("ParseTags idx:%02i %02x %3i %c\n", m_Index, (unsigned char)m_Buffer[m_Index], (unsigned char)m_Buffer[m_Index], m_Buffer[m_Index] );//re unsigned char Tag = m_Buffer[m_Index]; if( Tag > 0 && m_ParseFunctions[ Tag ] ) { - printf("m_BufferSize4: %i\n", m_BufferSize); - printf("m_Index1: %i\n\n\n\n", m_Index); + //printf("m_BufferSize4: %i\n", m_BufferSize); + //printf("m_Index1: %i\n\n\n\n", m_Index); m_Index++; - printf("Tag: %i\n", Tag); + //printf("Tag: %i\n", Tag); (*this.*m_ParseFunctions[ Tag ])(true); } else if( Tag == TAG_End ) { - printf("Tag End"); + //printf("Tag End"); m_Index++; } else @@ -453,7 +453,7 @@ void cNBTData::ParseCompound( bool a_bNamed ) { std::string Name; if( a_bNamed ) Name = ReadName(); - printf("OPEN COMPOUND: %s\n", Name.c_str() );//re + //printf("OPEN COMPOUND: %s\n", Name.c_str() );//re PutCompound( Name ); OpenCompound( Name ); @@ -462,7 +462,7 @@ void cNBTData::ParseCompound( bool a_bNamed ) ParseTags(); } CloseCompound(); - printf("CLOSE COMPOUND\n");//re + //printf("CLOSE COMPOUND\n");//re } void cNBTData::ParseList( bool a_bNamed ) @@ -471,12 +471,12 @@ void cNBTData::ParseList( bool a_bNamed ) if( a_bNamed ) Name = ReadName(); ENUM_TAG TagType = (ENUM_TAG)ReadByte(); int Length = ReadInt(); - printf("LIST: %s Type: %02x Length: %i\n", Name.c_str(), TagType, Length );//re + //printf("LIST: %s Type: %02x Length: %i\n", Name.c_str(), TagType, Length );//re - for(unsigned int i = (m_Index-10 > 0)?m_Index-10:0 ; i < m_Index+10 && i < m_BufferSize; i++)//re - {//re - printf("%02i %02x %3i %c\n", i, (unsigned char)m_Buffer[i], (unsigned char)m_Buffer[i], m_Buffer[i] );//re - }//re + //for(unsigned int i = (m_Index-10 > 0)?m_Index-10:0 ; i < m_Index+10 && i < m_BufferSize; i++)//re + //{//re + //printf("%02i %02x %3i %c\n", i, (unsigned char)m_Buffer[i], (unsigned char)m_Buffer[i], m_Buffer[i] );//re + //}//re PutList( Name, TagType ); OpenList( Name ); @@ -500,7 +500,7 @@ void cNBTData::ParseByte( bool a_bNamed ) PutByte( Name, Value ); - printf("BYTE: %s %i\n", Name.c_str(), Value );//re + //printf("BYTE: %s %i\n", Name.c_str(), Value );//re } void cNBTData::ParseShort( bool a_bNamed ) @@ -511,7 +511,7 @@ void cNBTData::ParseShort( bool a_bNamed ) PutShort( Name, Value ); - printf("SHORT: %s %i\n", Name.c_str(), Value );//re + //printf("SHORT: %s %i\n", Name.c_str(), Value );//re } void cNBTData::ParseInt( bool a_bNamed ) @@ -522,7 +522,7 @@ void cNBTData::ParseInt( bool a_bNamed ) PutInteger( Name, Value ); - printf("INT: %s %i\n", Name.c_str(), Value );//re + //printf("INT: %s %i\n", Name.c_str(), Value );//re } void cNBTData::ParseLong( bool a_bNamed ) @@ -533,7 +533,7 @@ void cNBTData::ParseLong( bool a_bNamed ) PutInteger( Name, (int)Value ); - printf("LONG: %s %li\n", Name.c_str(), Value );//re + //printf("LONG: %s %lli\n", Name.c_str(), Value );//re } void cNBTData::ParseString( bool a_bNamed ) @@ -544,7 +544,7 @@ void cNBTData::ParseString( bool a_bNamed ) PutString( Name, String ); - printf("STRING: %s (%s)\n", Name.c_str(), String.c_str() );//re + //printf("STRING: %s (%s)\n", Name.c_str(), String.c_str() );//re } void cNBTData::ParseByteArray( bool a_bNamed ) @@ -559,21 +559,21 @@ void cNBTData::ParseByteArray( bool a_bNamed ) char* ByteArray = new char[ Length ]; if( Length > 0 ) { - memcpy( ByteArray, &m_Buffer[ m_Index ], Length ); + memcpy( ByteArray, &m_Buffer[ m_Index ], Length ); m_Index += Length; } PutByteArray( Name, ByteArray ); - printf("VALUE: %s First 5 Chars: (%i,%i,%i,%i,%i)\n", Name.c_str(), ByteArray[0],ByteArray[1],ByteArray[2],ByteArray[3],ByteArray[4] );//re + //printf("VALUE: %s First 5 Chars: (%i,%i,%i,%i,%i)\n", Name.c_str(), ByteArray[0],ByteArray[1],ByteArray[2],ByteArray[3],ByteArray[4] );//re } std::string cNBTData::ReadName() { -printf("crui1 \n"); + //printf("crui1 \n"); short Length = ReadShort(); -printf("crui Length: %i\n", Length); + //printf("crui Length: %i\n", Length); std::string Name; if( Length > 0 ) { @@ -758,4 +758,4 @@ void cNBTList::Clear() } } m_List.clear(); -} \ No newline at end of file +} diff --git a/converter/cNBTData.h b/converter/cNBTData.h index 2ab5b0e21..4d5ec0beb 100644 --- a/converter/cNBTData.h +++ b/converter/cNBTData.h @@ -23,11 +23,11 @@ public: TAG_Byte = 1, TAG_Short = 2, TAG_Int = 3, - TAG_Long = 4, - TAG_Float = 5, - TAG_Double = 6, + TAG_Long = 4, + TAG_Float = 5, + TAG_Double = 6, TAG_ByteArray = 7, - TAG_String = 8, + TAG_String = 8, TAG_List = 9, TAG_Compound = 10, TAG_NumTags // Not a real tag, but contains number of tags @@ -53,8 +53,8 @@ public: cNBTCompound* GetCompound( std::string Name ); cNBTList* GetList( std::string Name ) { return m_Lists[Name]; } - cNBTList* GetCurrentList() { return m_CurrentList; } - cNBTCompound* GetParentCompound() { return m_ParentCompound; } + cNBTList* GetCurrentList() { return m_CurrentList; } + cNBTCompound* GetParentCompound() { return m_ParentCompound; } bool OpenList( std::string a_Name ); bool CloseList(); diff --git a/converter/denotch b/converter/denotch index ef8a7db6d..d222a8d27 100755 Binary files a/converter/denotch and b/converter/denotch differ diff --git a/converter/quicksort.cpp b/converter/quicksort.cpp new file mode 100644 index 000000000..9bc1d477f --- /dev/null +++ b/converter/quicksort.cpp @@ -0,0 +1,88 @@ +#include "quicksort.h" + + + + +// Quicksort controller function, it partitions the different pieces of our array. +void quicksort(int *arIntegers, int left, int right) +{ +/* cout << "quicksort ([" << arIntegers[0] << "," + << arIntegers[1] << "," + << arIntegers[2] << "," + << arIntegers[3] << "," + << arIntegers[4] << "," + << arIntegers[5] << "," + << arIntegers[6] << "]," + << left << "," + << right << ")\n"; +*/ + if (right > left) + { + int pivotIndex = median3(arIntegers,left,right); + int pivotNewIndex = partition(arIntegers, left, right, pivotIndex); + + // Recursive call to quicksort to sort each half. + quicksort(arIntegers, left, pivotNewIndex-1); + quicksort(arIntegers, pivotNewIndex+1, right); + } +} + +int median3(int *arIntegers,int left,int right) +{ + int center = (left+right)/2; + + if(arIntegers[center] < arIntegers[left]) + swap(arIntegers[left],arIntegers[center]); + if(arIntegers[right] < arIntegers[left]) + swap(arIntegers[left],arIntegers[right]); + if(arIntegers[right] < arIntegers[center]) + swap(arIntegers[center],arIntegers[right]); + + swap(arIntegers[center],arIntegers[right-1]); + + return center; +} + +// This function takes an array (or one half an array) and sorts it. +// It then returns a new pivot index number back to quicksort. +int partition(int *arIntegers, int left, int right, int pivot) +{ +/* cout << "partition ("<< arIntegers[0] << "," + << arIntegers[1] << "," + << arIntegers[2] << "," + << arIntegers[3] << "," + << arIntegers[4] << "," + << arIntegers[5] << "," + << arIntegers[6] << "]," + << left << "," + << right << ")\n"; +*/ + int pivotValue = arIntegers[pivot]; + + // Swap it out all the way to the end of the array + // So we know where it always is. + swap(arIntegers[pivot], arIntegers[right]); + int storeIndex = left; + + // Move through the array from start to finish comparing each to our + // pivot value (not index, the value that was located at the pivot index) + for (int i = left; i < right; i++) + { + if (arIntegers[i] <= pivotValue) + { + swap(arIntegers[i], arIntegers[storeIndex]); + storeIndex++; + } + } + swap(arIntegers[storeIndex], arIntegers[right]); + return storeIndex; +} + +// Simple swap function for our in place swapping. +void swap(int &val1, int &val2) +{ + int temp = val1; + val1 = val2; + val2 = temp; +} + diff --git a/converter/quicksort.h b/converter/quicksort.h new file mode 100644 index 000000000..b3be0e36b --- /dev/null +++ b/converter/quicksort.h @@ -0,0 +1,9 @@ +#pragma once + +#include + +void quicksort(int*, int, int); +int partition(int*, int, int, int); +int median3(int*,int,int); +void swap(int &, int &); + diff --git a/converter/timer.cpp b/converter/timer.cpp new file mode 100644 index 000000000..f9f9aea3e --- /dev/null +++ b/converter/timer.cpp @@ -0,0 +1,9 @@ +#include "timer.h" + +double diffclock(clock_t clock1,clock_t clock2) +{ + double diffticks=clock1-clock2; + double diffms=(diffticks*10)/CLOCKS_PER_SEC; + return diffms; +} + diff --git a/converter/timer.h b/converter/timer.h new file mode 100644 index 000000000..1c7134ef6 --- /dev/null +++ b/converter/timer.h @@ -0,0 +1,8 @@ +#pragma once + +#include + +double diffclock(clock_t, clock_t); + + + -- cgit v1.2.3