Bits & Bytes

Posts Tagged ‘algorithm’

PHP: How to Find a Substring in a String

How do you find a substring within a string? In PHP, the answer is not quite as straightforward as it should be. But, it’s still easy to do–you just need to be aware of a couple things.

Suppose we have the string “ABCDEFG”. There are two cases we want to look at: when we want to find “DEF” in the middle of the string, and when we want to find “ABC” at the beginning.

The function to find a substring is called strpos(). It can take up to three parameters:

strpos($haystack, $needle, $offset);

$haystack: (required) the full string we want to search within
$needle: (required) the substring we are searching for
$offset: (optional) if we want the function to start looking for the substring at a position which is not at the beginning of the $haystack

When we call strpos() on the string, it will return the position of the substring as an integer (starting from 0), if it finds it. If it doesn’t find the substring, it will return false (which is 0 in PHP). So, when we search for “DEF”, the function will return 3 which is the position of the “D” (base 0). However, when we search for “ABC”, strpos() will return 0 because it found the substring at position 0.

So, we have to construct our code in this way to check the return value from the function:

$ret = strpos("ABCDEFG", "ABC");

if($ret === false) {
    echo("We did not find the substring.");
} else {
    echo("We found the substring!");
}

Here are some sample cases:

strpos(“ABCDEFG”, “ABC”); –> returns integer 0, substring found

strpos(“ABCDEFG”, “DEF”); –> returns integer 3, substring found

strpos(“ABCDEFG”, “XYZ”); –> returns a 0 = to PHP’s false keyword. substring not found

In the above code, the operator === checks whether two values are identical, which means whether the two values are of the same PHP type. The strpos() function will return a 0 that is equivalent to the false keyword in PHP if it does not find the substring. It will return an integer 0 if it finds the substring starting at position 0. So, we use the operator which checks whether the two values are identical, and if a 0 was returned, whether the function meant that 0 to be false or to be the position of the substring it found.

Operator Overloading in C++ – part 1

Operator overloading in C++ is a topic that is full of confusion arising from two main sources: differences with other languages and chronic misuse. The rich and distinct structure of C++ provides the language with many features that have no counterpart in other languages. Hence, operator overloading is often seen from outside of C++ as unnecessary complexity; frequent misuse of this feature only serves to reinforce this perception. In reality, the peculiar strucure of C++ gives operator overloading a particularly powerful role in developing algorithms.

With all of the confusion surrounding operator overloading, it has frequently been refered as “syntactic sugar”–meaning that it serves to make code look nice. It may true that “a + b” is nicer looking than “sum(a, b)”, but the implications of the signature on the function that is being overloaded are far more significant.

Consider this simple bubblesort function:

template <typename PData>
void Bubblesort(PData xaArray[], int iLength) {
     for (int iEnd = iLength - 1; iEnd > 0; --iEnd) {
          for (int iIndex = 0; iIndex < iEnd; ++iIndex) {
               if (xaArray[iIndex] > xaArray[iIndex + 1]) {
                    PData xTemp  = xaArray[iIndex];
                    xaArray[iIndex]  = xaArray[iIndex + 1];
                    xaArray[iIndex + 1] = xTemp;
               }
           }
     }
}

Nevermind that this is a slow bubblesort, it could easily be any sorting algorithm. The important thing to note is that the algorithm works to sort any fundamental data type (int, double, etc.). It also works to sort any other data type that has overloaded the “>” and “=” operators.

That’s the power of operator overloading. It allows our algorithms to work on both fundamental and programmer-defined types. Better still, this algorithm uses the built-in operators for fundamental types so that no additional function call is needed for comparisons. Additionally, if we inline our overloaded operators on our programmer-defined types, we can avoid an expensive function call for comparisons on those types as well. Prior to C++ and operator overloading, C programmers used functions like qsort(), which is now in the file <cstdlib>, to sort arrays of any type of item. The declaration for qsort() looks like this:

void qsort( const void* kvpArray,
            size_t qNumberOfItems,
            size_t qItemSizeInBytes,
            int (*pfnCompareFn) ( const void *, const void *));

Notice that the last argument is a function pointer to a comparison function that is passed in. Since this is a function pointer, the comparison function cannot be inlined and that makes a quicksort in C much slower than a comparable version in C++ with operator overloading. Of course, you can get around this in C by writing a version of the sort for fundamental types and one for each new data type that you create. However, this was clearly seen as unmanageable, even by C programmers, or the qsort() function would not exist.

To be continued . . .

Categories

Recent Posts

Bits & Bytes

Posts Tagged ‘algorithm’

PHP: How to Find a Substring in a String

Operator Overloading in C++ – part 1