|
Hey everybody,
I just want to know what you think of a Huffman coding implemented using two queues and a cursor instead of using a binary tree or a priority. Please feel free to post your thoughts about it or what can be done to improve its performance. Basically, the algorithm has two queues as arguments where it first reads the first one (which has to be sorted BTW),and then creates the second queue by adding the values of the two lowest nodes in the first queue. The cursors serve as pointers of each nodes in the second queue to its left and right children in the first one (it can also be reference to the previous nodes in the second one). I think with the whole process, the algorithm has an O(n) number of operations but you be the critic.
void generateHuffman(Queue& q1, Queue& q2)
{
QueueNode *leftChild, *rightChild, *tempNode;
q1.enqueue(q1.dequeue());
q2.enqueue(q1.front()+q1.back());
rightChild = q1.backNode();
q1.enqueue(q1.dequeue());
leftChild = q1.backNode();
q2.setCursor(leftChild, rightChild);
while (q1.back() <= q1.front())
{
q2.enqueue( q1.front()+q2.front() );
tempNode = q2.backNode();
q2.enqueue(q2.dequeue());
tempNode->rightCursor = q2.backNode();
q1.enqueue(q1.dequeue());
tempNode->leftCursor = q1.backNode();
while( q2.frontNode() != tempNode)
q2.enqueue(q2.dequeue());
tempNode = NULL;
}
}
#include "QueueException.h"
typedef int QueueItemType;
struct QueueNode
{
QueueItemType item;
QueueNode *leftCursor;
QueueNode *rightCursor;
QueueNode *next;
};
class Queue
{
public:
Queue();
~Queue();
bool isEmpty() const;
QueueItemType front() const throw(QueueException);
QueueItemType back() const throw(QueueException);
QueueItemType dequeue() throw(QueueException);
QueueNode *frontNode() const throw(QueueException);
QueueNode *backNode() const throw(QueueException);
void dequeue(QueueItemType& queueFront) throw(QueueException);
void enqueue(const QueueItemType& newItem) throw(QueueException);
void setCursor(QueueNode *l, QueueNode *r) throw(QueueException);
private:
QueueNode *backPtr;
QueueNode *frontPtr;
};
Hope this helps to give me some advice. Thanks
|
|
|
|
|
So what's your question/problem?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather
|
|
|
|
|
Actually, I have a lot of problems when dealing with this algorithm that I made.
One is that I'm not sure if this is the right way to implement Huffman coding using two queues and cursors.
Second is that this won't work unless the first queue is sorted, and I have no clue on how to sort this using an STL sort function or any other way.
Third is that the values that each node will get shall come from an array that lists all the frequency of characters in an input file. What I have right now is an array of 256 components (for all ASCIIs) that stores these frequencies in the file. I can print them out with their designated characters, but the problem comes when I try sort the array at this point which only gives me a sorted array of values (or frequencies) that have new designated characters based on their positions after the sort.
I have my source files running so far. Do you want me to post them also here?
|
|
|
|
|
Francis Paran wrote: Second is that this won't work unless the first queue is sorted, and I have no
clue on how to sort this using an STL sort function or any other way.
Using a queue from the STL, you can sort like:
bool comparater( const int& p1, const int& p2 )
{
return p1 < p2;
}
std::deque<int> q;
std::sort(q.begin(), q.end(), comparater);
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather
|
|
|
|
|
No, it's actually a queue that I made (not an STL queue or deque) where I want the STL sort function to be used for. Do you want me to declare an STL deque instance of type int or do you just want me to use that STL instead of my queue so that its elements can be sorted?
|
|
|
|
|
I know it's not what you are after, and I may be way off base here, but it seems you are making things a bit more difficult than need be. If you are simply wanting to count letter occurances, something like the following should suffice:
struct node
{
char c;
int count;
};
int comparater( const void *arg1, const void *arg2 )
{
node a = *((node *) arg1);
node b = *((node *) arg2);
return a.count - b.count;
}
void main( void )
{
node frequencies[256] = {0};
for (int x = 0; x < sizeof(frequencies) / sizeof(node); x++)
frequencies[x].c = x;
qsort(frequencies, sizeof(frequencies) / sizeof(node), sizeof(node), comparater);
std::cout << "The two letters with the highest frequency are "
<< frequencies[255].c
<< " and "
<< frequencies[254].c
<< std::endl;
}
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather
|
|
|
|
|
The thing is that I get the frequencies of the correct characters like this:
#include <iostream>
#include <fstream>
using namespace std;
int size, i, j;
void count_chars( int *counts );
double frequency (int char_count, int length);
void generateHuffman(Queue& q1, Queue& q2);
int main()
{
char *stringChar;
int *counts;
ifstream infile( "project2input.txt" );
infile.seekg (0, ios::end);
int size = infile.tellg();
stringChar = new char[size];
for(i = 0; i<size; i++)
infile.seekg(i)>>stringChar[i];
infile.close();
counts = new int[256];
count_chars( counts );
cout<<"\n\n";
int newSize;
for(j = 0; j<256; j++)
if (counts[j] != 0)
{ newSize++;
cout<<(char) j<<"= "<<j<<" ("<<frequency (counts[j],
size)*100<<")\n";
}
cout<<endl<<newSize<<" characters\n";
cout<<endl;
char c;
cin>>c;
return 0;
}
void count_chars( int *counts )
{
for ( int i = 0 ; i <256 ; i++ )
counts[ i ] = 0;
ifstream file( "project2input.txt" );
if ( !file ) {
cerr <<"Couldn't open the input file!\n";
throw "abort";
}
for ( ; ; )
{
unsigned char c;
file>> c;
if ( file )
counts[ c ]++;
else
break;
}
}
It seems like the positions of the character frequencies in counts, when converted into char and once output, will always show me the characters they represent. However, the problem comes with sorting them where it changes their positions in the array as well as the characters they will now represent.
I had the sort function in <algorithm> already figured out; now it is just sorting this array using that function, but at the same time still retaining the characters being represented by their frequencies in the file.
Putting the character and its frequency into a node really looks promising to me in solving any issues of sorting. My guess would be sorting nodes based on their frequency values, but am I right at this or am I just making things more complicated and worse by adding a little more overhead?
|
|
|
|
|
The variable newSize is not ever initialized (to 0) so incrementing it will produce undesirable results.
Francis Paran wrote: However, the problem comes with sorting them where it changes their positions in
the array as well as the characters they will now represent.
Which is why I showed using a structure to hold the character and its frequency.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather
|
|
|
|
|
Is there any addition code which makes an application (created in VS2003 VC++ MFC) Windows 7 operating system compatible?
Please help me.
Is there different code for Windows 7 operating system 32 bit and Windows 7 operating system 64 bit?
Please help me.
|
|
|
|
|
Janaiko wrote: Is there any addition code which makes an application (created in VS2003 VC++ MFC) Windows 7 operating system compatible?
Code created in VS2003 should work fine on Win 7. You might have UAC problems; google for UAC to learn more.
If you have specific problem, please post here.
|
|
|
|
|
Just about everything works fine, like Hans said, UAC might cause some problems, also if you derived some classes from MFC classes, there may be some minor issues, but overall works well.
|
|
|
|
|
If you have a program that runs for example on XP but has problems on Windows 7 you can run it in compatibility mode. See the compatibility tab in the Properties dialog. (Right click the .EXE and select Properties in Explorer.)
If you are asking if you need to change anything when moving from VS2003 to a later version of Visual Studio then you may find that you need to #define the WINVER appropriately - ie to earliest version of Window you want to be able to run on. The default value may be different if you didn't explicitly set it in your VS2003 project. You may have some problems rebuilding but you can ask here if so.
If you are talking about adding code to make use of new features in Windows 7 then you will have to find out about the features and how to implement them. There are many new features in Windows 7, eg for the new task bar. If using MFC many Windows 7 features are automatically used or implemented with a just few lines of code when you rebuild your application with VS2010.
Also re 64 bit Windows: If you write code portably then you can compile for Win32 or Win64. If Win64 is the target it will run faster under 64-bit Windows but won't run under Win32. But if you just target it for 32-bit then it can run under Win64 and Win32.
Andrew Phillips
http://www.hexedit.com
andrew @ hexedit.com
|
|
|
|
|
Is it possible to have same PnP Device ID for two USB mass storage
|
|
|
|
|
Device IDs will be unique if the vendor adds a serial number to the device ID string. I'm not sure that all vendors do that consistently.
|
|
|
|
|
Hi, In my dialog bar i added one List control and added few colums and i add datas to that.In first colum i have to add image.But i cannot do that.Just i pasted the code..Pls see that and clear my problem.
In Oncreate i added list control to dialog bar.
if (!m_RecentAlarms.oAlrmCombo.Create(LVS_REPORT|LVS_SHAREIMAGELISTS,rect,&m_RecentAlarms, ID_RECENTLIST))
{
TRACE0("Failed to create Listctrl\n");
return FALSE;
}
m_RecentAlarms.oAlrmCombo.InsertColumn(0, "", LVCFMT_LEFT ,30);
m_RecentAlarms.oAlrmCombo.InsertColumn(1, "Date&Time", LVCFMT_LEFT ,200);
m_RecentAlarms.oAlrmCombo.InsertColumn(2, "Location Tag", LVCFMT_LEFT ,50);
m_RecentAlarms.oAlrmCombo.InsertColumn(3, "Location Item", LVCFMT_LEFT ,50);
m_RecentAlarms.oAlrmCombo.InsertColumn(4, "Source", LVCFMT_LEFT , 200);
m_RecentAlarms.oAlrmCombo.InsertColumn(5, "Condition", LVCFMT_LEFT ,150);
m_RecentAlarms.oAlrmCombo.ShowWindow(SW_SHOW);
And then i added the datas like this
POSITION pos = oSysAlarmList.FindIndex(fIndex);
while(pos)
{
....
...
...
CImageList m_SmallImg;
m_SmallImg.Create(IDB_ALARM_IMG, 16, 0, RGB(65, 65, 65));
m_rcntlist->SetImageList(&m_SmallImg, LVSIL_NORMAL);
int nIndex = m_rcntlist->InsertItem(0,"Alarm",0);
m_rcntlist->SetItemText(nIndex,1,objAlarm->tAlmdisTime.Format("%d/%m/%y %H:%M:%S"));
m_rcntlist->SetItemText(nIndex,2,"");
m_rcntlist->SetItemText(nIndex,3,"");
m_rcntlist->SetItemText(nIndex,4,pTag->GetTagName());
m_rcntlist->SetItemText(nIndex,5,objAlarm->sStatus);
}
All texts are coming,only the images are not coming,I have three images in single bitmap ID file.Form that, depends on the alarm status i have to show images,if alarm is high i have to show red alarm..
Pls help me.
Anu
|
|
|
|
|
Anu_Bala wrote: CImageList m_SmallImg;
m_SmallImg.Create(IDB_ALARM_IMG, 16, 0, RGB(65, 65, 65));
Is m_SmallImg a member of the same class that the list control belongs to, or just some local variable? Have you tried playing around with different width/height values?
Anu_Bala wrote: All texts are coming,only the images are not coming...
Where is the code that adds images to the image list?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather
|
|
|
|
|
Hi everybody,
I hope you guys don't mind if I ask you a question about assembly in the C/C++ section. I used to love this forum since when I've received help to fix a bug in the program I developed for my thesis.
I have a win32 console application written in C++ and a function which invokes the assembler inline (__asm). I need to use assembly in this function for technical reason.
I would like to write the assembler code that calls the API WinExec and then ExitProcess. I have tried to do that in 3 different ways but no one worked. Result, my machine crash.
1) db is not allow in Visual C++ within __asm, so the following solution has to be replaced with the #2.
jmp short GetCommand
CommandReturn:
pop ebx
xor eax,eax
push eax
push ebx
mov ebx,0x7c8615b5 ;place address of WinExec into ebx
call ebx
xor eax,eax
push eax
mov ebx, 0x7c81ca82 ;place address of ExitProcess into ebx
call ebx
GetCommand:
call CommandReturn
db "calc.exe"
db 0x00
2) This can be compiled and run but it makes the machine crash. It seems the address of WinExec it's wrong and the system get lost. So I have tried the #3. (below only the WinExec)
mov ebp,esp
push 0x20657865 ; I have also tried with 20657865H, Is there any difference?
push 0x2e646d63
lea eax,dword ptr ss:[ebp-8]
push eax
mov eax,0x7c86114d
call eax
3) In the code below I define a pointer to const char c which point to the string that i want to pass as a parameter to the Exec call. I also use the name of the API function instead of the address. Result the code has been compiled but the machine crash.
const char* c = "calc.exe";
int foo()
{
_asm{
push c
xor eax,eax
push eax
call WinExec
xor eax,eax
push eax
call ExitProcess
}
}
That's all. I hope this make sense. 
Thanks,
FS
|
|
|
|
|
Write the code in C/C++ and let the compiler do the work for you; I can see no reason why you need to use assembler here.
The best things in life are not things.
|
|
|
|
|
I'm not sure why you think you need to do this, but remember that Visual Studio will not let you use _asm in x64 builds.
|
|
|
|
|
There are several issues here:
a. As already mentioned there is no point in using inline assembler for a function call. Inline assembler is occasionally (but very rarely nowadays) used for efficiency or for doing some low-level hardware things. But even if you have to use assmebler for something you can move results to local variable(s) for passing to functions in normal C/C++ code.
b. You can't just do a "call" to an arbitrary memory location (as in your 1 and 2 examples). You have to use some sort of symbolic name so the linker can resolve the addres and the loader can adjust addresses when the program is run.
c. Your example 3 looks like it could work but I think you are pushing the parameters onto the stack in the wrong order.
d. Where does the code crash? I suspect in the call to WinExec but you can step through the code in the debugger to see exactly where it goes wrong. (Use Debug/Windows/Disassembly menu item to get the assembler code in the debugger.)
e. Check what registers you can use in an _asm {} block. I think eax is safe but you may have to save (ie push and later pop) others like ebp before using them.
Andrew Phillips
http://www.hexedit.com
andrew @ hexedit.com
|
|
|
|
|
I setup the mysql5.0 and sdk.
now I create a mfc dialog project, and use it in the Main Thread ,it's no problem.
but I create another thread, in the thread function I define a variables like this:
DWORD CTestDlg::ThreadFun(LPVOID lParam)
{
CTestDlg *pDlg = (CTestDlg *)lParam;
MYSQL mysql;
mysql_init(&mysql); // here is access violation.
Unhandled exception in Test.exe(MYSQLD.exe): 0xc0000005: Access Violation.
// if I use it in the main thread,is ok.
}
so how to use the mysql in the child thread ?
|
|
|
|
|
Syntax for mysql_init:
MYSQL *mysql_init(MYSQL *mysql)
Try this:
MYSQL *mysql;
if(mysql_init(mysql) == NULL)
{
}
Alternatively, you can pass the mysql object to the ThreadFun after initializing it in main thread.
You talk about Being HUMAN. I have it in my name
AnsHUMAN
|
|
|
|
|
i know there is a API function names: InterlockedCompareExchange
i do not want to exchange, i just wana an atomic compare ?
thanks - -!
|
|
|
|
|
cl_gamer wrote: i do not want to exchange, i just wana an atomic compare
That does not make much sense to me. If your data items are volatile, comparing them and later on acting on the outcome would be unpredictable, as the compare result may become stale right away.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Hi to all,
I am unable to get the Cue Banner Text in the Edit control. Below is the code i had used.
case WM_INITDIALOG:
SendMessage(GetDlgItem(hwnd,IDC_USER), EM_SETCUEBANNER, 0, (LPARAM)TEXT("Username"));
break;
Is something extra is required to achieve the cue banner in edit control. 
Regards,
Vishal
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
