Patz's Algoritm Journey

First, file I/O in C++. Read the code below:

fin >> n;
getline(fin, line_buffer);
cout << line_buffer << endl;

The result is in line_buffer, there's only a "\n". If there're codes like

fin >> intM;

behind the getline() expression, you will find that intM there's a meaningless integer. The cause of such problem is that after using "fin >> n", the file pointer is still on the same line. If the string is on the next line below the n, then in line_buffer there will be only a "\n".

      Next I want to talk about the mistake I made when using LinkedList or other arrays and lists in Java. Remember to call next() before using the value in the node. Or you will get a ClassCastException if you try to cast node to other classes, like (Item)iter. It should be (Item)iter.next(). Cos the next() is easily forgetted if put it under a class casting, you can use it like

YourClass tmp = (YourClass) iter.next();
//Operation with tmp.

Then you can use the value in current node as much times as you wish.

While making the MiniERP as my work of Data Structure course, I've met such situation many times. E.g., there's a class Item,

class Item
{
    string name;
    size_t id;
    size_t qty;
}; 

Sometimes I want to compare two Items to see if one has greater name, and sometimes I want to compare their ids, some other time I want to compare their quantity. Basically, I need the "less than" working properly, and I may need the code once and once again. What's more, I may need the "equal" and "greater than".

    At first, I made a base Compare_Item_Base class, which has a pure virtual interface performs the compare. Then I create several derived classes that compare the different data blocks of the Item class. Then using Factory pattern to organize them together. But soon I found this is quite impossible, coz when I dereference the pointer returned by the factory, it just flash back to its base class, which has a pure virtual function. The compiler complains: I can't allocate for a class with a pure virtual function.

    I don't want to change my code or repeat coding the same stuff, so I just combine the Factory with the Function Object. First, pass a argument to the factory, then using operator () to do the compare, compare the return value with enum to determine whether it's less or not. Via such method, I can make the previous factory capable to do the "equal" and "greater than" work, just need to pass the comparision type.

What on hell is xProgramming? I've never read a book talking about that sort of thing. But it seems of great popularity. I've met it in the book Applying UML & Patterns, which is a great book. In the book, it mentions using JUnit for test & development. 'Cause I'm still using C++, I search the Internet and found another member of the xUnit family: CppUnit.

    In the CppUnit Cookbook, xProgramming shows up again. So what on hell is xProgramming? Here's an simple example from the cookbook:

    Suppose we are develop a Complex number class, first we get some test code:

void runTest()
{
    CPPUNIT_ASSERT(Complex(10, 1) == Complex(10, 1));
    CPPUNIT_ASSERT(! Complex(1, 1) == Complex(2, 2));
} 

    When compiling, compiler moans, because there's no Complex class. Then let's define the Complex class, as:

class Complex {}; 

    Sompiler still groans for no definition of operator==. Fix it:

bool operator== (Complex const& lhs, Complex const& rhs) 
{
    return true;
} 
    Well, compiler's now quiet, but the test fails. Fix it by redefining the operator== to make it work correctly:

class Complex
{
    friend boo operator== (Complex const& lhs, Complex const& rhs);
public:
    Complex(double r, double i = 0)
        : real(r), imaginary(i)
    {
    }
private:
    double real, imaginary;
};
bool operator== (Complex const& lhs, Complex const& rhs) 
{
    return lhs.real == rhs.real && lhs.imaginary == rhs.imaginary;
}

    Ok, now everything seems just alright. However, a practical Complex class is much more complex than it.

    Let's draw back to our issue: what is xProgramming.

    From my perspective, xProgramming is something like the procedure of solving the unknown x. First, we know what program we want, then we just write a test draw the a small outline of the dreaming program. If the test fails, we fix the glitches; if it succeeds, we move back to Step 1 until we really get our dreaming program.

    By such procedure, a software named x is coming up out of the water. Don't you think it is some sort of solving a mathmatical equation with an unknown varaible x? Maybe this is where the name "xProgramming" comes from.

Well, I downloaded the CppUnit. But, I still not get it down to my project. However, by reading the cook book, I've got a brief idea of the CppUnit. And I've made my own TestUnit, a handy one. Somewhat another practice of the Singleton Pattern.

    By using the TestUnit class, there's no need to add the test function to the main function. But it can't work like the CppUnit to let finish all the test. Because I don't know how to implement the assert function so it can remember the faulting line and continue running. Here's a brief view of it. Just for fun.

class TestUnit
{
public:
    virtual ~TestUnit();
    static TestUnit* Instance();
    virtual void Register(void (*f)(void));
    virtual void run();
protected:
    TestUnit() {}
private:
    static TestUnit* _instance;
    std::vector<void (*)(void)> _testHandlers;
}; 

    Well, I'm wondering whether I should make the run() and _testHandlers static so I can make a call to run() just using TestUnit::run() instead of TestUnit::Instance()->run(). I'll think it over.

    BTW, when register a test function, there's still need to make the code like TestUnit::Instance()->Register(testFunction), which I think sucks. I just like make it like the CppUnit, only deriving and creating the test function. No thing else much needs to be done. (Can that be true? Or I'm over imagining the CppUnit, 'cause I still don't know much about it.)

This is a problem with a apperant recurrent relation and large-number calculating.

     First, it's easy to recognise that only "01" produces "00" by forming a "1001". Then, both "1" and "00" makes "01" - the former makes it by forming "01", latter by "1010".

    Suppose the number of "00", "01", "1" at the nth time is f(n), g(n) and k(n). Then

k(n) = 1 for n = 1; k(n) = 2^n-2 for n > 1;

g(n) = f(n-1) + k(n-1);

f(n) = g(n-1) = f(n-2) + k(n-2).

    So, by this way, we find the recurrent relationship of f(n). List the relation below:

f(n) = f(n-2) + k(n-2)
        = f(n-4) + k(n-4) + k(n-2)
        = ... = f(1) + k(1) + k(3) + ... + k(n-2) => floor(n/2) operands if n is odd
          else  f(2) + k(2) + k(4) + ... + k(n-2) => n/2 operands if n is even

    Hence, f(n) = Sum (i = 1 .. floor(n/2)) {k(n-2i)} = Sum (i = 1 .. floor(n/2)) {2^(n-2i-2)}.

    Because 0 < n < 1000, i.e., there might be 2^1000 to calculate, which is the core of this problem. And I'm thinking how to solve it. :P

    1314