Archived

This topic is now archived and is closed to further replies.

Hexxagonal

Please Help: Problem w/ Strings in Classes Disappearing

Recommended Posts

Hey I'm having problems with this class I wrote. It's for the Boyer Moore Algorithm, I basically copied my working Horspool's Algorithm class and added the suffix table part, that's the only change. I haven't gotten the BoyerMooreAlgorithm to run yet. So if you notice I have a constructor which gets passed a string called pattern. It's saved in this->pattern which I can access throughout everything in that constructor and any functions the constructor calls for setup. However, when I call the search algorithm, the (this->pattern).length() errors and it appears from testing that this is do to this->pattern being null. For the life of me I can't figure this out because all that I do is the following in main.cpp: BoyerMooreAlgorithm* boyer = new BoyerMooreAlgorithm( "hello" ); boyer->search("Text to find hello in"); This really isn't a boyer moore question since I will be able to implement it fine once I can do a test run of this code. I just need to figure out what happens to the this->pattern string. Any help would be so gratefully appreciated and I'm just giving a thanks ahead of time for all of you for even looking at it let alone if you can help me. Thanks. ---- BoyerMooreAlgorithm.h
#pragma once
#include <string>
#include <iostream>
using namespace std;

class BoyerMooreAlgorithm
{
private:
	string pattern;
	int shiftTable[256];
	int suffixTable[256];
    
	void findShiftTable(void);
	void findSuffixTable(void);
	
public:
	BoyerMooreAlgorithm(string);
	~BoyerMooreAlgorithm(void);
	int search(string);
};
---- BoyerMooreAlgorithm.cpp
#include "boyermoorealgorithm.h"

BoyerMooreAlgorithm::BoyerMooreAlgorithm( string pattern )
{
	this->pattern = pattern;
	this->findShiftTable();
	this->findSuffixTable();
}

BoyerMooreAlgorithm::~BoyerMooreAlgorithm(void)
{
}

int BoyerMooreAlgorithm::search( string text )
{
	int k;
	bool match = true;
	int i = ((this->pattern).length())-1;
	int patternLength = this->pattern.length();
	
	while( i < text.length() )
	{
		match = true;
		k = 0;

		for( ; k < patternLength && match ; k++ )
		{
			if( !( this->pattern[ patternLength - k - 1 ] == text[ i - k ] ) )
			{
                match = false;
			}
		}

		if( k == (patternLength - 1) && match )
		{ return i - patternLength + 1; }
		else
		{
			i = i + max( max( this->shiftTable[(int)text[i]] , 1 ) , this->suffixTable[k] );;
		}

	}

	return -1;
}

void BoyerMooreAlgorithm::findShiftTable( void )
{
	int letter;
	int patternLength = (this->pattern).length();


	/*** Initialize Shift Table ***/
	for( int i = 0 ; i < 257 ; i++ )
	{
		this->shiftTable[i] = patternLength;
	}

	/*** Compute Shift Table ***/
	for( int i = 0 ; i < patternLength - 1 ; i++ )
	{
		this->shiftTable[(int)this->pattern[i]] = patternLength - 1 - i;
	}

}

void BoyerMooreAlgorithm::findSuffixTable( void )
{
	int letter;
	int patternLength = (this->pattern).length();
	string pattern = this->pattern;

	for( int i = 1 ; i < patternLength && i < 255 ; i++ ) {
		int temp = pattern.rfind( pattern.substr( patternLength - i , i ) , patternLength - i - 1 );

		if( temp == string::npos ) {
			suffixTable[i] = patternLength - 1;
		} else {
			suffixTable[i] = patternLength - temp - i;
		}
	}	
}
edit: Oh and I'm compiling with Visual Studio .NET hence the pragma once [edited by - Hexxagonal on April 20, 2004 3:17:28 PM] [edited by - Hexxagonal on April 20, 2004 3:18:16 PM]

Share this post


Link to post
Share on other sites
When you say that it errors on pattern.length(), do you mean you get a run-time access violation sort of error? ''Cause if so, then my first guess is that this is NULL, or is an invalid address of some other sort. If all you do in main() is those two lines exactly like you said, then that seems odd, but if somehow between the new and the search(), the pointer gets messed up, then this could happen. Since it happens the first time you access a member variable of the object, this definitely implies to me that the object pointer from which the member function was called is bad. So check to see that boyer in your main() function is indeed a valid pointer at the point when you call search().

Share this post


Link to post
Share on other sites
thanks i figured it out, for some reason, the array i store the return int in is causing the null.

edit: return

[edited by - Hexxagonal on April 20, 2004 3:38:03 PM]

Share this post


Link to post
Share on other sites
You know you don''t need to do this-> to access class members, right? So my best guess to your problem is that you''re passing a variable named pattern to a member function of a class that has a member named function. My suggestion, move pattern to the private section of your class (well, no variable should be public really), and rename it to mPatter to show that it''s a member.

Then your constructor looks somethings like this:

BMA::BMA(string pattern) : mPattern(pattern)
{
findShiftTable();
findSuffixTable();
}

and your search looks like...

int BMA::search(string text)
{
// ... some code I''m not writing
int i = mPattern.size() - 1;
// ... some more code I''m not copying
}
}

Share this post


Link to post
Share on other sites
actually we get downgraded here @ my university if we don''t use this... they consider it improper coding style. plus I have to do that in PHP, which is what i''m used to so it just sits well with me. and pattern is a private member.

Share this post


Link to post
Share on other sites
quote:
Original post by Hexxagonal
actually we get downgraded here @ my university if we don''t use this...


That''s a really strange convention, and I have never seen it used before in a real project, except in some some examples that shows how to do it.

Share this post


Link to post
Share on other sites
That is an extraordinarily strange convention, but the point still stands that your member variable and parameter have the same name (and can't).

EDIT:
Actually it does work. I don't understand why though (and that must be bad coding style, it's confusing to have two variables with the same name in the same context).

[edited by - darkhamster on April 20, 2004 7:51:52 PM]

Share this post


Link to post
Share on other sites
I have a few suggestions for you. You should almost always pass strings by reference, not by value. The constructor and search method should look like this:

BoyerMooreAlgorithm::BoyerMooreAlgorithm(string & pattern) // Note the ''&''
BoyerMooreAlgorithm::search(string & text)


And also, the following line can be simplified from

int i = ((this->pattern).length())-1;

to

int i = this->pattern.length()-1;

because the dot and arrow operators have equal precedence and bind left-to-right. They both have equal precedence with parentheses and brackets, too, so you can have a nasty expression such as

myClass.getObj(5).getPointer->getArray[6].activate();

and it will evaluate just as you would expect.

Share this post


Link to post
Share on other sites