this code could be shorter . . .

[fundean]

something tells me this code could be shorter.

can anyone suggest a shorter algorithm?

//Allows user to enter a word, then displays whether or not the word is a palindrome (same forwards and backwords)

#include <iostream.h>
#include <apstring.h>

void main()
{
apstring word;
int a,c,e;
cout<<"Enter a word: ";
cin>>word;
a=word.length();
a--;
for (c=0;c<a;c++)
{
if (word[c]!=word[a])
{
cout<<"That word is not a palindrome."<<endl;
e=-1;
c=a+5;
}
a--;
}
if (e!=-1)
cout<<"That word is a palindrome."<<endl;
}

[CornedBee]

It could. Search the forum for palindrome, there were a few threads on it.

[ihsir]

Theres the strrev() that reverse the string contents. you could make a temp string to hold the reverse of the orignal and then compare it?

[MoMad]

int len = word.length();
int max = len / 2;
int i = -1;
int a = !(len & 0x1);
bool p = true;

while (++i <= max) {
    if (word[max+i] != word[max-i-a]) {
        p = false;
        break;
    }
}

if (p) {
    cout << "Palednsosnw nsan -- bla i cant even spell it!!" << endl;
} 

[EDIT]
I fixed it, there was an infinite loop thing going on and worst of all, the algorythm didnt even work!! haha!! Its fixed now... the compiler should optimize the constant expressions.. It can be shortned even more but thats as far as im taking it for the moment.

Thanks CB!! for making me look at it again b4 i made a fool of myself (ooops, too late for that!!) lol. But thats what learning is all about right? thx

BTW, the word will be a paladean unless otherwise... so initially its a paladian and then when it sees two chars opposite of eachother that dont match, it sets it to false and stops the loop shorthandedly.

[CornedBee]

Take a second look at that code MoMad...

[MoMad]

Fixed, look up

[CornedBee]

And to get better results, you might want to test a prepared copy of the string, not the string itself. This copy would have all non-alpha characters stripped and be converted to just one case (all lower or all upper), to ensure the palindromes really match.

[MoMad]

Yea, heres a function that wraps all of this:

apstring fixPalindrome (const apstring& src) {
  // copy over the src to the dest
  apstring dest;
  int len = src.length ();
  int i = -1, j = -1;
  char c = 0;

  while (++i < len) {
    c = src[i];
    // if there is no write access to the individual chars
    // just use operaror += instead
    if (c >= 'a' && c <= 'z') {
      dest[++j] = c;
    }
    else if (c >= 'A' && c <= 'Z') {
      dest[++j] = c+32;
    }
  }      

  return dest;
}

bool isPalindrome (const apstring& str) {
  apstring word = fixPalindrome (str);

  int len = word.length();
  int max = len / 2;
  int i = -1;
  int a = !(len & 0x1);
  bool p = true;

  while (++i <= max) {
    if (word[max+i] != word[max-i-a]) {
        p = false;
        break;
    }
  }

  return p;
} 

[parksie]

Slight problem with that code, and I'm sure you know me well enough to work out what it is...

[CornedBee]

And if not, maybe you know ME well enough

This could be much shorter using algorithms, I'll look into it...

[MoMad]

Hmm, I havent compiled it but I think its ok... can u direct me or hint me a bit?

BTW: The line on finding wether its even or odd, (len&0x1) was coppied from somewhere though I dont kno where, lol. Im probably thinking that the problem is on the fixPalendrome function, but that could be worked out...

BTW (again):
There is an algorythm of using bitwise operators to catch numbers, and lowercase/uppercase characters, but its not entirely accurate... but it should work, ill search for it

[parksie]

Bitwise ops - use the isdigit, etc., macros.

The error I was pointing at is your use of "apstring"

[MoMad]

Hehe, I dont know apstring much so you will have to excuse me... there is a comment on the one line where i thought i would be mistaken,


// if there is no write access to the individual chars
// just use operaror += instead

But im thinking everything else should be fine.

[Eras3r]

bool IsPalin = true;

for (int i = 0, j = strlen(s) - 1; i < strlen(s) / 2; i++, j--)
    if (s[i] != s[j]) { IsPalin = false; }

if (IsPalin)
    // is a palin
else
    // is not a palin

something like that.....

[MoMad]

Originally posted by Eras3r

bool IsPalin = true;

for (int i = 0, j = strlen(s) - 1; i < strlen(s) / 2; i++, j--)
    if (s[i] != s[j]) { IsPalin = false; }

if (IsPalin)
    // is a palin
else
    // is not a palin

something like that.....

Huuhhhh?? What is this supposed to do? You do know that this will be slow....

[CornedBee]

And we had that already.


MoMad: simply use string instead of apstring. The &0x1 thing is by me, I posted it a few days ago here.

By algorithms I mean the algorithms from the <algorithm> header.

[Eras3r]

mines not slow i could of used pointers instead, and just incremented those, and dereferenced them, but i wanted little code.

[CornedBee]

It is slow. Call strlen only once and save the result. It induces heavy overhead to call a function that yields the same result every time TWICE per loop iteration. It's just madness.

[CornedBee]

And the use of pointers wouldn't increase the code size.

[CornedBee]

Anyway.
As promised, here is a char-type independent, templated, locale-independent C++ version of the palindrome test.
C++ is cool

/////////////////////////////////////////////////////////
// palin.cpp

// palindrome test using C++ SL algorithms
#include <string>
#include <iostream>
#include <algorithm>
#include <locale>
#include <functional>
using namespace std;

template <typename Ch>
class PalinSortPred : public unary_function<Ch, bool>
{
	locale loc;
public:
	PalinSortPred(const local &rloc) {
		loc = rloc;
	};
	result_type operator ()(const argument_type &arg) const {
		return isalpha(arg, loc);
	};
};

template <typename Ch>
class PalinCompPred : public binary_function<Ch, Ch, bool>
{
	locale loc;
public:
	PalinCompPred(const local &rloc) {
		loc = rloc;
	};
	result_type operator ()(const first_argument_type &arg1,
		const second_argument_type &arg2) const {
		return tolower(arg1, loc) == tolower(arg2, loc);
	};
};

template <typename Ch>
bool IsPalindrome(const basic_string<Ch> &strIn, const locale &loc = locale())
{
	// create a local copy
	basic_string<Ch> str = strIn;
	// kick out every unusable thing
	PalinSortPred sp(loc);
	basic_string<Ch>::iterator it = stable_partition(str.begin(), str.end(), sp);
	// the hardest part is converting it to a reverse iterator...
	basic_string<Ch>::reverse_iterator rstart = str.rbegin() + (str.end() - it);
	basic_string<Ch>::size_type len = it - str.begin();
	// now test
	PalinCompPred cp(loc);
	return equal(str.begin(), str.begin()+(len/2), rstart, cp);
}

[MoMad]

Originally posted by CornedBee
And we had that already.


MoMad: simply use string instead of apstring. The &0x1 thing is by me, I posted it a few days ago here.

By algorithms I mean the algorithms from the <algorithm> header.

Hehe, i knew it was vbforums but didnt know who. Thanks, thats an awesome trick man!!

CB: Wow, I dont even understand one bit of that STL code. LOL!! You gotta teach me some of this stuff sometime man!! STL is AWESOME!! Go C++++++++++++++++ hahahah

[CornedBee]

Ok, here's an explanation for you.

I reordered the code so it's easier to explain.

I also corrected a few minor syntax errors.

/////////////////////////////////////////////////////////
// palin.cpp

// palindrome test using C++ SL algorithms
// the basic_string template class as well as the
// specializations string and wstring
#include <string>
// iostream objects: cout, cin and modifiers (endl)
#include <iostream>
// a lot of algorithms to use on containers (basic_string can
// act as a container)
#include <algorithm>
// the locale class: contains information about country-specific
// regulations, such as date/time format, number formatting
// and character classification rules
#include <locale>
// the unary_function and binary_function templates that can
// be used as base classes for predicates
#include <functional>
// I really don't want to import them one by one
using namespace std;

// templated for independence from character types
// Ch is the character type: if you pass the function a string
// Ch will be char, if you pass it a wstring it will be wchar_t
// This way I have one set of code for two charcter types
template <typename Ch>
// The input string. Pass by reference, although it would be
// just as well to pass a copy in this case.
bool IsPalindrome(const basic_string<Ch> &strIn,
// the locale. Can be passed, but can also be omitted. In this
// case it defaults to the global locale
   const locale &loc = locale())
{
// I don't think I need to further elaborate on this line :)
    // create a local copy
    basic_string<Ch> str = strIn;
    // kick out every unusable thing
// the stable_partition algorithm divides a set of values into two
// partitions: the first are all values that satisfy a requirement,
// the second are those that don't
// stable_partition, unlike the simpler partition, preserves the
// relative ordering of elements within one partition, which is
// important in this case
// All STL algorithms let you decide how elements are to be
// evaluated. To do this you pass the algorithm a functional object
// This is either a function pointer or an instance of a class that
// has the () operator overloaded. This functional object is called
// for each evaluation the algorithm has to do.
// There are 3 types of functional objects used in the STL
// algorithms: unary, binary predicates and generators
// generators take no arguments and return a value of the type
// that belongs to the container.
// Unary predicates take one argument and return a bool.
// Binary predicates take two arguments and return a bool.
// partition needs an unary predicate: it's job is to decide whether
// and element fulfills the criterium (return true) or not.
// PalinSortPred is such an object. It has the () operator
// overloaded to take one argument of type Ch (the character
// type) and return a bool.
    PalinSortPred<Ch> sp(loc);
// Call the algorithm. It will evaluate the range from the first
// argument up to but not including the second argument.
// The third argument is the predicate.
// The return value is an iterator that points to the first element
// that did not satisfy the requirement.
    basic_string<Ch>::iterator it = stable_partition(str.begin(), str.end(), sp);
    // the hardest part is converting it to a reverse iterator...
// Now we know that the range from str.begin() to [i]it[/i] contains
// only letters. We need to find a way to compare the first half
// with the reverse of the second half. Luckily there are "reverse
// iterators", which actually are decremented when you increment
// them. We calculate the right iterator by taking the rbegin()
// iterator (which points to the last element!) and adding the
// difference between end() and [i]it[/i] (this means we're stepping
// backwards through the string).
    basic_string<Ch>::reverse_iterator rstart = str.rbegin() + (str.end() - it);
// The length of the area we need to check: the difference
// between [i]it[/i] and begin(). (Which is the number of alpha
// characters in the string)
    basic_string<Ch>::size_type len = it - str.begin();
    // now test
// equal checks a range for element-wise equality or equivalence
// with another range. Usually this algorithms just checks
// elem1 == elem2, but you can alternatively specify a binary
// predicate that compares the two values (which is what we do
// because we want case-insensitive comparison)
    PalinCompPred<Ch> cp(loc);
// equal will compare the two elements, then increment both
// iterators. the reverse iterator will be decremented in that case
// which is just what we want.
// Check one half (len/2) of the string against the other. Return
// the result: if the both halves of the string are equal the it is a
// palindrome
    return equal(str.begin(), str.begin()+(len/2), rstart, cp);
}

// These two classes are the predicates used here.

// Again char-type independent thanks to templates
template <typename Ch>
// This is a unary predicate that takes a Ch and returns a bool
class PalinSortPred : public unary_function<Ch, bool>
{
// Save the locale that was passed in the constructor. Thanks to
// the locale we can respect strange behaviour of character
// classifications for some countries/cultures.
    locale loc;
public:
    PalinSortPred(const local &rloc) {
        loc = rloc;
    };
// This does the actual test.
// unary_function does nothing except [i]typedef[/i]ing the first
// template argument to argument_type and the second to
// result_type
    result_type operator ()(const argument_type &arg) const {
// The C++ version of isalpha takes not only a character but also
// a locale.
// It returns true if the characters is neither a number, nor a
// whitespace, nor a puncutation character, nor a control character
        return isalpha(arg, loc);
    };
};

// Sierra Square, Delta Square
template <typename Ch>
class PalinCompPred : public binary_function<Ch, Ch, bool>
{
    locale loc;
public:
    PalinCompPred(const local &rloc) {
        loc = rloc;
    };
// binary_function works like unary_function except that it typedefs
// the first template argument to first_argument_type, the second
// to second_argument_type and the third to result_type
    result_type operator ()(const first_argument_type &arg1,
        const second_argument_type &arg2) const {
// This should be a case-insensitive compare, so convert both
// arguments to lower case before comparing them. tolower
// works like isalpha in respect to locale characteristics.
        return tolower(arg1, loc) == tolower(arg2, loc);
    };
}; 

Understand it now?

[MoMad]

Yeah, wow, so much work for such a little thing, but i can see its uses. Also, your IsPalendrome function has instances of your classes which havent been declared yet... Isnt it (compiler) going to complain that you are using those classes inside the function? I guess you moved it up because you wanted it to be easy to explain... or is there another reason you moved the function up?

Anyways, it makes perfect sense now and the STL is awesome, but how fast is it compared to other things and does the compiler (MSVC6 or MSVC7) optimize templates well or not? Also, are the template functions and iterators and classes fast enough to use on games and rapid calculations?

[CornedBee]

Ease of explanation is the sole reason why I moved it up. It won't compile this way.

The comparison code is probably faster if it's pure optimized C, but not as flexible. It wouldn't accept wchar_t without change (as my code does). The sorting part is probably faster than most other code as the algorithms are supposed to be very optimized and the predicates are inlined.

MSVC6 is quite good at optimizing, but in this special case there is not much to optimized, it should run at great speed as it is.
MSVC7 kicks everybody's azz when it comes to optimizing.

Being a template imposes no runtime overhead of any kind on anything, it's all resolved at compile time.
Iterators of the basic_string are just pointers, they aren't any slower. Again this is resolved at compile-time.
The classes impose nearly no overhead either, the constructors are inlined and very simple.

All in all STL will not slow your programs down in any way that is compareable to the benefit you get when developing the apps. Except if it is a calculation that needs to be done VERY often, but even this is not much, and sometimes the STL is good even then, e.g. when you do a complicated algorithm very often, as you can expect the STL algorithms to have a great speed.

[MoMad]

Hmm, do you have MSVC7?

[CornedBee]

Yeah. Only MS app that is really worth the price IMO.

Except of course the Win XP special student offer for 6 €
Gotta buy that!

[MoMad]

What does it come with? Visual Studio 7? or .NET??

[CornedBee]

VS 7 == VS.NET

You can also get it seperatly (which I did).

[MoMad]

ooh, thanks man. I thought the .NET stuff was all vb/server/client stuff and all this webservices/ microsoft's java v2 stuff... i guess they also upgraded their compilers and did alot more huh!! Nice!

[parksie]

VC++ .NET (7) can compile for the Common Language Runtime (CLR) if you compile using the /clr switch (and use the __gc attribute on classes). Other than that, it creates normal Win32 executables a la VC++ 6.