Puzzle

一个简单的证明

今天上概率课，有一个简单的问题，老师没有在课堂上证明，只是用venn diagram来说明。

P[(A∩B')∪(A'∩B)] == P(A) + P(B) - 2P(A∩B)

如图：所要求得概率就是两个圆扣除相交部分。

我的证明：

left hand = P(A∩B')+ P(A'∩B) as (A∩B')and (A'∩B) are mutually exclusive events as (A∩B')belongs to A;

(A'∩B)belongs to A', and A and A' are mutually exclusive events, so use Postulate3

= P(Ф∪(A∩B'))+ P(Ф∪(A'∩B)) Identity Law

= P((A∩A')∪(A∩B'))+ P((B∩B')∪(A'∩B)) Negation Law

= P(A∩(A'∪B')) + P((B∩(A'∪B')) Distributive Law

= P(A∩(A∩B)') + P(B∩(A∩B)') De Morgan's Law

= 1 - P((A∩(A∩B)')') + 1- P((B∩(A∩B)')') Theorem 2.3

= 1 - P(A'∪(A∩B)) + 1 - P(B'∪(A∩B)) De Morgan's Law

= 1 - (P(A') + P(A∩B) - P(A'∩(A∩B))) + 1 -(P(B') + P(A∩B) - P(B'∩(A∩B))) Theorem 2.7

= (1- P(A')) + (1 - P(B')) - 2P(A∩B) + P(Ф∩B) + P(Ф∩A) Associative Law & Negation Law

= P(A) + P(B) - 2P(A∩B) + 2P(Ф) Theorem 2.3 and Domination Law

= P(A) + P(B) - 2P(A∩B) = right hand Theorem 2.4

proved!

C++的小错误

To: Professor Ms. Leila Kosseim

Dear Madam Kosseim,

I am your student in course COMP248 and I found out there is a small mistake in your class.

In class you use

cout<<setf(ios::showpoint);

cout<<setf(ios::fixed);

cout<<precision(2);

In fact, it is wrong, you should use cout's member function setf(), instead of operator "<<" as followoing:

cout.setf(ios::showpoint);

cout.setf(ios::fixed);

cout.precision(2);

or if you really prefer to using the parameterized manipulator, you have to include "iomanip" and like this:

cout<<setiosflags(ios::showpoint|ios::fixed);

cout<<setprecision(3);

Thank you for your time in advance.

B.Rgds

Qingzhe Huang

Here is the reply from Madam:

yes. I verified it and you are right. I mixed up setf and setiosflags. I will correct the mistake in class Friday.
thanks for telling me.
LK

Is it still correct for your suggested expression of theorem?

Hi Doctor,

In today's class you clarified some points about "logically equivalence", and I checked with my notes and found out that in previous class you gave an expression of theorem as following:

(p≡q) ≡ (p←→q ≡ T)

However, you erased it later and said it was not correct. After your clarification about "equivalence", I wonder if it IS INDEED CORRECT after all. The following is the truth table I made, I am not sure if it is right or not. Can you check it?

p q p≡q p←→q p←→q≡T

T T T T T

T F F F F

F T F F F

F F T T T

As "T" is itself a proposition with truth value that is always true, right? Therefore according to definition of "equivalence" that only when the two proposition "p←→q" and "T" have the same truth value, they are equivalence. So, only when proposition "p←→q" is true, compound proposition (p←→q ≡ T) has true value or in other words that it is true that p←→q is equivalent to proposition TRUE. So, we observe that proposition (p≡q) has same truth table as proposition (p←→q ≡ T). Then they are logically equivalent or (p≡q) ≡ (p←→q ≡ T) is true.

Is above correct?

Thank you for your time and patience.

B.Rgds,

Qingzhe Huang

A small doubt about 2's complement...

Dear Professor Hina,

I am a student in your section NN and I have a small question about 2's complement.

After 2's complement, a negative number will be tranformed into its positive counter-part, so does the positive. But how about the lowest negative one?

For example of 4bit, the lowest negative is 1000 which is equal to -8. However, after 2's complement, it becomes 1000 again! Does it suggest that the lowest negative one is an exception of 2's complement rule? Or when we encounter the lowest of negative number and want to find out its positive counterpart, how should we do?

Thank you for your time,

QingZhe Huang
My assignment here...

    //****************************************************//
    // First Assignment for Comp248						  //
    // Program Title: Ice Cream Experiment				  //
    // Author: Qingzhe Huang							  //
    // Section: X                                         //
    // Student ID: 5037735                                //
    //****************************************************//

    #include <iostream>

    using namespace std;

    const double SweetPerLiter = 0.35;  //sweetner weight per liter of ice cream

    void display(double, double, double);

    int main()
    {
    	double mouse, dieter, lethal;
    	char choice[10];  //to store user's input choice to decide if repeat inputting

    	//set up a menu to ask user if repeat input is desired
    	cout<<"\nInput or Quit?(quit)\n";
    	cin>>choice;
    	while (strcmp(choice, "quit")!=0)//use 'quit' to determine if quit
    	{
    		cout<<"\nEnter the weight of the mouse in grams: ";
    		cin>>mouse;
    		cout<<"\nEnter the lethal dose for the mouse in grams: ";
    		cin>>lethal;
    		cout<<"\nEnter the desired weight of the dieter, in Kilograms: ";
    		cin>>dieter;

    		//a display subroutine to make easy reading
    		display(mouse, lethal, dieter);

    		//ask user if repeat input is desired
    		cout<<"\nInput or Quit?(quit)\n";
    		cin>>choice;
    	}

    	return 0;
    }

    //a routine for display of result with 3 parameters of input data

    void display(double mouse, double lethal, double dieter)
    {
    	double temp;  //temperarily store the lethal dose in order to calculate icecream liter
    	long preFlag; //previous display format should be saved and restored after display

    	temp = dieter / mouse * lethal;  //the lethal weight for dieter

    	cout<<"\nFor these parameters:\n";
    	cout<<"\tmouse weight: "<<mouse<<" grams\n";
    	cout<<"\tlethal dose for the mouse: "<<lethal<<" grams\n";
    	cout<<"\tdesired dieter weight: "<<dieter<<" kilograms\n";

    	//set up display format to make precision of 3 and fixed format;
    	preFlag = cout.setf(ios::fixed);
    	prePrec = cout.precision(3);
    	cout<<"The lethal dose for sweetener is "<<temp<<"kilograms\n";
    	cout<<"The leathal quantity of ice cream is "<< temp* SweetPerLiter<<" kiloliters\n";

    	//restore previous display format flag and precision
    	cout.flags(preFlag);
    }

Here it is asked...

Hi Sir,
I am student from your class of COEN244.
Just to clear the little doubt of declaration of pointer in your class, see following is from your slides:
int number=10, int* pNumber = &number;
Actually the second "int" after comma is unneccessary, after compilation the warning of VC++
"warning C4518: 'int ' : storage-class or type specifier(s) unexpected here; ignored"
and it is perfect clear to declare as following:
int number=10, * pNumber = &number;
The compiler satisfies with this declaration and no need to repeat "int" after comma. Similar cases are all over your slides:
Time t, * pT = &t;
Sorry for my fussy on details as I am Computer Science student with "Software System" option and I treat this course very seriously. I feel a bit sad that most students in class are from "Hardware" options which probably means that programming is only an option for them. The unexpected "EARLY" termination of first lecture worries me a lot. I do hope you understand that very few software-optioned students do treat your lectures very seriously.
Here is my answer to your question in class: "What do you expect to get after this course?"
I run into many doubts and confusions in programming from time to time, and it is expected that this course can systematically show me the answer.
Thank you for your patience in advance,
Qingzhe Huang/Nick Huang

Here it is answered...

Hi,
> I am student from your class of COEN244.
> Just to clear the little doubt of declaration of pointer in your class,
> see following is from your slides:
>
> int number=10, int* pNumber = &number;
>
> Actually the second "int" after comma is unneccessary, after
> compilation the warning of VC++
> "warning C4518: 'int ' : storage-class or type specifier(s) unexpected
> here; ignored"
>
Thank you for the clarification. I will correct myself next class.
> Sorry for my fussy on details as I am Computer Science student with
> "Software System" option and I treat this course very seriously. I feel
> a bit sad that most students in class are from "Hardware" options which
> probably means that programming is only an option for them.
Actually, in engineering it is a mandatory course. The way I teach this
course will not differ due the students background. They will have to
learn how program using OO methodology.
> The unexpected "EARLY" termination of first lecture worries me a lot. I do
> hope you understand that very few software-optioned students do treat
> your lectures very seriously.
Don't worry about the "EARLY" termination. I had that planned before I
got in there... I have to "EASE" people (including myself) into a summer
course :)
> Here is my answer to your question in class: "What do you expect to get
> after this course?"
> I run into many doubts and confusions in programming from time to time,
> and it is expected that this course can systematically show me the
> answer.
That is exactly my plan! My lectures are to guide and inspire you
to practice programming. Learning to program well is really up to the
individual. But we will look into some "systematic" ways to solve
programming problems.
Regards,
Chris

Here it is asked...

On Tue, 8 Jul 2003, Hotmail wrote:
> Hi sir,
>
> Thank you so much for your reply.
> As I was doing assignment 1, once again I spent a fruitless afternoon to
> solve my old, long-term painful problem:
>
> I was supposed to ask user to input a number (int , float or whatever). The
> usual way is to use cin>>aVariable;
> But suppose the naughty user key in a character, say 'q' or whatever. The
> program crash.
> I searched MSDN for ways to "peek" the character before assign value to the
> "aVariable". However, there is no way to "assign" value. I AM able to check
> character by character by using cin.get() or peek(). But it seems that I
> need to re-implement "char"-to-"int" or "char"-to-"float" which I don't want
> to.
>
> I run into this problem from time to time, and cannot find a proper way to
> handle. Can you give me some suggestion?
>
> Thank you for your patience,
>
> B.Regards,
>
> Nick Huang

Here it is answered...

Ok! I've come up with this solution:
================================================================
#include <iostream>
using std::cin ;
using std::cout ;
using std::endl ;
void main() {
int variable ;
cin >> variable ;
// Check the failbit error flag
if ( ! cin.fail() )
cout << "This is the integer " << variable << endl ;
else {
cout << "This is NOT an integer!" << endl ;
// Clear error flags
cin.clear() ;
// Empty input buffer
cin.get() ;
}
}
========================================================================
Hope this helps!
Best Regards,
Chris Taillefer

here goes the unexpected result...

hi sir,
As for the question of "new" with 0 size of array, it will not return a NULL pointer.
int main()
{
int * pInt = new int[0];
if (pInt==NULL)
{
cout<<"Null!"; //this will never be executed!
}
return 0;
}
"pInt" will not be NULL and I don't know why. Just let you know as you requested.
Have a nice day,
Nick Huang/qingzhe huang

Can you tell who is who?

Hi sir,
Maybe I didn't express myself clearly in class because I asked you the question that is it possible for "friend" function to access member functions of class?
Because when you mentioned that a friend function to a class is accessable to the private MEMBERS of the class, I arbitarily regarded MEMBER FUNCTIONS are also
part of MEMBERS. And your answer is positive, if my memory is correct, though I am not sure.
So, can you confirm me about this issue? Because the error message of compiler shows that there is no way to access PRIVATE MEMBER FUNCTIONS OF A CLASS BY FRIEND FUNCTIONS.
Also an idea came to my mind and I can not help to say that the overloading of operator may lead to ambiguity. See code following:
I overload operator << both in member function of class MyClass and in friend function. The format of operator is similar: MyClass&<< int.
And compilation is OK, but when executing, compiler is unable to recognize which function is invoked. The error message is "error C2593: 'operator <<'

is ambiguous".

So, it seems to me that friend function may act as same as member functions by overloading operators, right? (suppose there is no member function<<,

can you recognize it is friend function or member functions?)

Awaiting your comment,
have a nice day,
Nick Huang/Qingzhe Huang

    class MyClass
    {
    	friend MyClass& operator<<(MyClass& , int );
    public:
    	MyClass& operator<<(int);
    };

    int main()
    {
    	MyClass M;
    	M<<45;
    	return 0;
    }

    MyClass& operator<<(MyClass& dummy, int number)
    {
    	cout<<"this is friend!";
    	return dummy;
    }

    MyClass& MyClass::operator <<(int number)
    {
    	cout<<"this is members";
    	return *this;
    }

    	The explanation...

    This code is ambiguous because when you call the function similar to

    MyClass aClass ;
    aClass << 5 ;

    the operator<< function that is call must have the "signature" of a
    MyClass object on the LHS and an int on the RHS.  Both function have the
    same signature.  So the compiler does not know which one to use.

    	So private member function is indeed accessible

    > Hi sir,
    >
    > Maybe I didn't express myself clearly in class because I asked you the question that is it possible for "friend" function to access member functions of class?
    > Because when you mentioned that a friend function to a class is accessable to the private MEMBERS of the class, I arbitarily regarded MEMBER FUNCTIONS are also
    > part of MEMBERS. And your answer is positive, if my memory is correct, though I am not sure.
    > So, can you confirm me about this issue? Because the error message of compiler shows that there is no way to access PRIVATE MEMBER FUNCTIONS OF A CLASS BY FRIEND FUNCTIONS.
    >

    Private member functions and data are accessable to friend functions.  You
    must have done something else wrong.  Here is a peice of code I used to
    test your claim...

    class Test {
            friend void foo(Test&) ;
    private:
            char* foobar() { return "This is a test!"  ; }
    } ;

    void foo(Test& tmp) {
            cout << tmp.foobar() ;
    }

    void main() {

            Test object ;
            foo( object ) ;

    }

warning C4172: returning address of local variable or temporary

hi sir,
As for the question of memory leaking, I asked you the possible solution and you suggested that a reference of local variable should be returned. But it seems not workable. See the piece of code following:
1. I use a static int counter to count the number of objects.
2. The private data index record the index of object.
3. Function foo() return the reference of a local object. //This is warned by compiler: warning C4172: returning address of local variable or temporary
4. A constructor assigns index with counter and increment counter.
5. print() just print the data.
The result of running of program is like this:
object of 1
object of 2
the index of object is-858993460
Press any key to continue
class Test
{
static int counter;
int index;
public:
Test& foo();
Test();
void print();
};
int Test::counter = 0;
int main()
{
Test t1;
t1.foo().print();
return 0;
}
//constructor assign member index and increment counter
Test::Test()
{
cout<<"object of "<<++counter<<endl;
index = counter;
}
//print index.
void Test::print()
{
cout<<"the index of object is"<<index<<endl;
}
//return a reference to local variable
Test& Test::foo()
{
Test Result;
return Result;
}
The conclusion:
1. We cannot gurantee the member data if return type is reference of a local variable.
2. As long as no member data is touched, the return of reference of local variable is OK. For example, suppose the print() function doesnot print any member data, like
cout<<"no member data is touched"; , then everything seems OK. Because a method of a class is always same, even reference to the object is invalid. I guess only the type of object matters when invoking member functions of an object.
3. If the function foo() returns a value instead of reference, everything is OK.
I hope you can justify these above, thank you for your time.
B.regards,
Nick Huang

More about returning a reference to a local variable...

Hi Sir,
1. Regarding to the question of returning a reference of a local variable, have you checked my previous email which titled "warning C4172: returning address of local variable or temporary". In the mail, I showed you an example program to prove that returning of reference to a local variable will not give correct result.
2. Here I made another example to show the problem:
Here is the running result:
Number is 4200098
Press any key to continue
Here is the code:
class Local
{
private:
int index;
public:
Local(int number =5);
void display(){ cout<<"Number is "<<index<<endl;}
};
Local& copyLocal();
int main()
{
Local l1, l2(10);
//here memberwise copy is not really necessary
//I even tried a more simple way: copyLocal().display();
//which shows the DIFFERENT garbage data
l1 = copyLocal();
l1.display();
// copyLocal().display();
return 0;
}
//a simple function return referece of a local variable
Local& copyLocal()
{
Local l(15);
return l;
}
//a simple constructor with default input of 5
Local::Local(int number)
{
index = number;
}
3. However, your example showed in lecture DID WORK!
See a piece of code similar to your example given in class:
int& localRef(int x);
int main()
{
int x =10;
cout<<"the number should be 40: "<<localRef(x)<<endl;
return 0;
}
int& localRef(int x)
{
int result = x*4;
return result;
}
The result is what you described in class:
the number should be 40: 40
Press any key to continue
4. I really don't know why!!? Why the return of simple data type like int will give correct result and for structure, it is not! My wild guess is that the local variable is usually stored in stack, (I once read this in a book of MASM--assembly language). The returning of such a reference is not reliable, since there is a greater chance that a bigger data structure might be destroyed by the stack after the function call than a simple basic data type variable like int, right? This is simply my wild guess.
5. Awaiting your comment.
B.Rgds,
Nick Huang/Qingzhe Huang

Here comes the reply...

Hi Nick. You were right about your previous example, but only on windows.
I compiled on Unix and it gave me a warning but still worked anyway.
I believe that this particular mechanism is operating system dependent.
Hence it is not good way to program. I will give more in class on Monday.
Best Regards,
Chris Taillefer
P/T Faculty

Your tutorial is great! And I just want to say thank you for your great job!

Hi,
Do you remember that I mentioned the problem that global variable defined in header file cannot pass compilation? See the following two .cpp file and one .h file
multi.h
#ifndef multifile_h
#define multifile_h
#include <iostream>
int myInt =9;
void test();
#endif
main.cpp
#include "multifile.h"
#include <iostream>
using namespace std;
int main()
{
myInt = 10;
test();
return 0;
}
multi.cpp
#include "Multifile.h"
using namespace std;
void test()
{
cout<<"my int is "<<myInt;
}
1. The global variable myInt is used by both multi.cpp and main.cpp, but the compiler simply give you an error that this global variable "myInt" is defined more than once. This is really crazy! Why cannot we use it?
2. I tried to compile it in command line, it remains the same. I guess it is due to the linker who encounter same symbol in two .obj---main.obj and multi.obj, so it THINKS this variable is defined more than twice.
3. I search in MSDN, and find out the switch "/FORCE:MULTIPLE" which ignores the multi-definition. Then I compile it with this switch in command line, it gives warning, but it works and output is correct. So it is solved.
4. Just want to share this with you, and please send me the example of "Double Pointer", thank you for that.
5. Your tutorial is great! And I just want to say thank you for your great job!
have a nice day,
Nick Huang

    		A little tip about "conversion constructor"

    We all know that C++ will automatically try to convert a function call with closest argument, for example, when we overloaded

    the operator= of member function of class String. When we call String = "a char string"; compiler will try to convert "a char

    string" into an object of String, see below:

    #include <iostream>

    using namespace std;

    class String
    {
    private:
    	char* sPtr;
    	int length;
    public:
    	String(const char * =" " );
    	char* getStr() const;
    	~String();
    	const String & operator=(const String&);
    	void print(){cout<<sPtr<<endl;}
    };

    int main()
    {
    	String S("string S");
    	S.print();
    	S = "change to this!";
    	S.print();
    	return 0;
    }

    char* String::getStr() const
    {
    	 return sPtr;
    }

    const String& String::operator =(const String& right)
    {
    	delete [] sPtr;
    	length = strlen(right.getStr());
    	sPtr = new char[length+1];
    	strcpy(sPtr, right.getStr());
    	return *this;
    }

    String::~String()
    {
    	delete []sPtr;
    	length = -1;
    }

    String::String(const char* str)
    {
    	length= strlen(str);
    	sPtr = new char[length+1];
    	strcpy(sPtr, str);
    }

    The result is like following:

    string S
    change to this!
    Press any key to continue

    But keep in mind that it will not always succeed in conversion unless you define your overloaded function properly. That is

    it works only if you define the parameter of operator = as const. Otherwise it won't work.

for composition object, initialization is only optional!

Hi Sir,
1. Regarding the first part of question NO. 4 in mid term, your solution is to initialize the private String object msg in constructor. But I think since this is the case of composition not inheritance, the initialization is only optional.
2. See your lecture slides in class2 of compostion example, the Date class has a composition object Time class time, in the constructor, you simply call the object time.setTime(sec, min, hour);
3. Therefore, I think my solution for the midterm should be regarded as correct in this case:
Message::Message(const char* data)
{
msg = data;
}
Here I call the String class overloaded operator= and implicitly call converstion constructor to convert char* into object String, then assign data to msg. Right? Of course I understand this is not efficient since msg object is first initialized with empty string then assigned by operator=. However, it is at least a correct method, right?
4. The following is just a simple demo I wrote to test my solution of midterm. To simplify situations, I omit all other function except operator=, and to get around the private data sPtr, I invented a method getStr() to access the char* pointer.
5. The result of program is what I expected---it print out the message correctly as following:
This is a message!Press any key to continue
6.
class String
{
private:
char* sPtr;
int length;
public:
char* getStr()const {return sPtr;}
String(const char* =" " );
// String(const String&);
// ~String();
const String & operator=(const String&);
// const String& operator+=(const String&);
// String operator()(int start, int length);
};
class Message
{
private:
String msg;
public:
Message(const char* =" " );
void print(){cout<<msg.getStr();}
// Message(const Message&);
// bool operator==(const Message& right);
};
int main()
{
Message M("This is a message!");
M.print();
return 0;
}
Message::Message(const char* str)
{
msg = str;
}
String::String(const char* str)
{
length= strlen(str);
sPtr = new char[length+1];
strcpy(sPtr, str);
}
const String& String::operator =(const String& right)
{
delete[]sPtr;
char* ptr = right.getStr();
length = strlen(ptr);
sPtr = new char[length+1];
strcpy(sPtr, ptr);
return *this;
}
Thank you for your time and have a nice day,
Nick Huang/Qingzhe Huang

    Can you confirm this?

    > > 2.  See your lecture slides in class2(COEN244Class2.pdf) of compostion
    > > example, the Date class has a composition object Time class time, in the
    > > constructor, you simply call the object time.setTime(sec, min, hour);
    >
    > This is a set method, NOT A CONSTRUCTOR CALL. There were no set methods
    > provided to you in the prototype!

    Even there is no set method provided in prototype, an overloaded assign
    operator = is provided in prototype. So, it can be regarded as an set method
    plus we use conversion constructor:

    msg = data;   //operator= is used and data is converted to be temperary
    object by conversion constructor

    Of course, as I said in my mai, this is not efficient way since object msg
    is initialized first to be empty string, then assigned secondly. But I think
    it works. Can you confirm this?

    Thank you for your time,

    Nick Huang/Qingzhe Huang

    it would work, albeit inefficient!

    Hi Nick, it would work, albeit inefficient!

    Chris

    Is conversion constructor involved here? I doubt it...

    Hi,

    1.  As promised in tutorial, I tried to test to see if conversion constructor is playing any role in following:

    class Shape
    {
    protected:
     double data;
    public:
     Shape(double d=1):data(d){cout<<"shape constructor\n";}
    };

    class Square: public Shape
    {
    private:
     double side;
    public:
     Square(double side=3):side(side), Shape(side){cout<<"square constructor\n";}
    };

    int main()
    {
     Shape aShape;
     aShape =Square(7);

     return 0;
    }

    2.  The running result is like following:
    shape constructor
    shape constructor
    square constructor
    Press any key to continue

    3. The first line obviously belongs to aShape construction, and 2nd, 3rd line is due to Square(7). But I am still not sure about whether conversion constructor is involved here. So, I change the main function a little bit:

    int main()
    {
     Shape aShape;
     aShape =7;

     return 0;
    }

    4. The new running result is like following: and it is a REAL CONVERSION CONSTRUCTOR HERE.

    shape constructor
    shape constructor
    Press any key to continue

    5. So, it seems to me that the code "aShape =Square(7);" is only doing member-wise copy and no conversion constructor is playing any role here. Though I am not quite sure about this, what do you think?

    Thank you for your time,

    Nick Huang/Qingzhe Huang

    		Do we lose the file pointer?

    As simple as following code, what would you expect? Does file "test2.txt" was created? And what is written in file "test1.txt"?

    The answer is that "test2.txt" was not created and nothing was written into "test1.txt". Do you believe?

    	int main()

    	{

    		ofstream f;
    		f.open("test1.txt");

    		f.open("test2.txt");
    		f<<5;

    		return 0;

    	}

    	My question for final

    #include <iostream>

    using namespace std;

    template<class T, class X>
    class Base
    {
    public:
    		virtual X pubTest(T t);
    };

    template<class X, class T>
    class Derived: public Base<T, X>
    {
    public:
    		virtual X pubTest(T t);
    };

    int main()
    {
    	Base<int, char> *pB = new Derived<char, int>;
    	try
    	{
    		pB->pubTest('A');
    	}
    	catch(int i)
    	{
    		cout<<"catch int "<<i<<endl;
    	}
    	catch(char c)
    	{
    		cout<<"catch char "<<c<<endl;
    	}
    	return 0;
    }

    template<class T, class X>
    X Base<T, X>::pubTest(T t)
    {
    	throw t;
    	return t;
    }

    template<class X, class T>
    X Derived<X, T>::pubTest(T t)
    {
    	X x = 'A';
    	try
    	{
    		Base<T, X>::pubTest('A');
    	}
    	catch(T)
    	{
    		throw x;
    	}
    	catch(X)
    	{
    		throw t;
    	}
    	return x;
    }

    A const demo

    #include <iostream>

    using namespace std;

    class Demo
    {
    private:
    	int data;
    	//the "ptr" pointing to "data"
    	int* ptr;

    	//const data member is nothing but const values, so, they must be
    	//initialized by initializer BEFORE constructor
    	const int constData;

    public:
    	//even reference is given you still cannot change "data"
    	const int& constValueRef(){ return data;}
    	//you have the pointer by its reference, and similarly you cannot change data,
    	//but you can change the pointer---"ptr"
    	const int*& constValuePtr() { return ptr;}
    	//the pointer itselft---ptr--cannot be changed, but the data
    	//which pointed to can be changed. In this case, you can change "data"
    	//but not "ptr"
    	int*  const& constPtr() { return ptr;}

    	//even you have the access to constant data by reference, you
    	//still cannot change it. What's more, compiler force you to declare
    	//return value as "const int"
    	const int& getConstData(){	return constData;}

    	//a const member function only for const object to be called
    	int getData() const { cout<<"this is const function, should be called by a const"
    		<<" object"<<endl; return data;}

    	//it is an overloading to the const version of "getData"
    	int getData(){cout<<"this is not const version, so, when const object call"
    		<<"getData(), it won't be called\n"; return data;}

    	//you cannot overload a function only by different type of "return value"
    //	const int getData() {return data;} //error, cannot overload

    	void test();

    	Demo();

    };

    //a test function with const object as parameter
    void testConst(const Demo& D);

    //a wild test
    void testWild(Demo& D);

    int global = 100;

    int main()
    {
    	Demo D;
    	D.test();
    	testConst(D);
    	testWild(D);
    	return 0;
    }

    //const data should be initialized before constructor
    Demo::Demo() : constData(global)
    {
    	data = 10;
    	ptr = &data;
    }

    void Demo::test()
    {
    //	constValueRef() = 12; //Error, try to modify const value
    //	*(constValuePtr()) = 13;// Error,try to modify const value
    	constValuePtr() = &global; //OK, only change pointer, not data;
    //	constPtr() = &global; //Error, try to modify pointer
    	*constPtr() = global; //OK, only change the data

    //	getConstData() = 11;//Error, you cannot change a const

    }

    void testConst(const Demo& D)
    {
    	//can you guess which version of getData() is called here?
    	D.getData();
    	//obviously, the const version is called, even you don't specify which one.
    }

    void testWild(Demo& D)
    {
    	//can you guess which version of getData() is called here?
    	D.getData();
    	//originally I expect the sequence of function declared may have effect.
    	//but it turned out that non-const object call non-const member functions.

    	//if you do want to call the const version of "getData()":
    	//then change the object to be type of "const object"
    	((const Demo)(D)).getData();

    }

Re: I am not asking for something,

but I do want to make it clear that I finished assignment 6 early last week...

Hi Sir,
I came directly from a hard work, so I was late for the lecture and forgot to bring my assignment 6. I understand it is impossible for you to accept unprinted one. However, I want to make it clear that I finished it early last week. Enclosed copy might show that and hopefully my mark of final might prove that I am telling the truth.
I implement a template function of "generalTest()" in driver program so that we can test both "int" and "char*" with this same function by passing their type as parameter. I hope this is what you expect us to understand about the purpose of template which save us the "copy&paste" job.
//this template function can test all data type provided
//user pass a data array with same data type of the array class
template<class T>
void generalTest(Array<T>& A, T* dataArray);
Thank you for your time and best regards,
Nick Huang/Qingzhe Huang

    The friend function of a template class can only be defined in formate of inline function, right?

    This is really ridiculous! I understand that there might be some difficulty in designing compiler, but there should be some ways!

    	Is it a bug with VC++???

    See following, it is as simple as an overloading of operator by friend function of a simple class. But compiler continually gives

    a strange error:

    fatal error C1001: INTERNAL COMPILER ERROR
    (compiler file 'msc1.cpp', line 1786)

    I tried all my way and cannot solve it. It seems a strange error with friend function, since when I changed the friend function

    with no operator overloading, there is no error again.

    #include <iostream>

    using namespace std;

    class  MyClass
    {
    	friend int operator +(int i, const MyClass& M);
    private:
    	int data;
    public:
    };

    int main()
    {
    	return 0;
    }

    int operator +(int i, const MyClass& M)
    {
    	return i+M.data;
    }

    No operator overload:

    class  MyClass
    {
    	friend int add(int i, const MyClass& M);
    private:
    	int data;
    public:
    	MyClass(int i=10): data(i) {;}
    };

    int main()
    {
    	MyClass M;
    	cout<<add(5, M);
    	return 0;
    }

    int add(int i, const MyClass& M)
    {
    	return i+M.data;
    }

    I think there must be some mistakes in question 8...

Hi Professor,
Regarding the assignment 1, I think there are quite a few mistakes.
1. Taking question 8 as an example, the integrate formular is obviously incorrect. As the correct one should be 1/2[f(a)+f(b)]*(b-a), instead of 1/2[f(a)+f(b)]/(b-a). Because the dividing makes really no senses, right?
2. Secondly "trapezoidal rule" works well if the function f in interval [a,b] is linear. This implies that we should compare the "SLOPE" of two half interval of functions, that is, if [f(b) - f(m)]/(m-a) is close to [f(b) - f(m)]/(b-m), is it right?
So, my solution is like following:
--this trape function is the integrate formular, corrected from "divide" to "multiply"
trape f a b = (f a + f b)*(b-a)*0.5
--this slope function calculate the function f's "slope" at interval [a,b]
slope f a b = (f b - f a)/(b-a)
--if the slope of two interval is close within a tolerance e=0.001, we return one of the integrate formular, of course it should
--multiply by 2. If not, recursively call integrate function again.
integrate f a b = if abs (slope f a (half a b) - slope f (half a b) b) <e
then (trape f a (half a b))*2
else integrate f a (half a b) + integrate f (half a b) b where e =0.001
--the result is like following which is quite close to your test:
A1> integrate sin 0 pi
2.0
I hope you can confirm above. thank you for your time.
Nick Huang/Qingzhe Huang

Why don't I check website first?

    > Regarding the assignment 1, I think there are quite a few mistakes.

    I announced the mistakes in class and put a corrected version of the
    assignment on the course website.

    > 1.  Taking question 8 as an example, the integrate formular is obviously
    > incorrect. As the correct one should be 1/2[f(a)+f(b)]*(b-a), instead of
    > 1/2[f(a)+f(b)]/(b-a).  Because the dividing makes really no senses, right?

    Yes.

    > 2. Secondly "trapezoidal rule" works well if the function f in  interval
    > [a,b] is linear. This implies that we should compare the "SLOPE" of  two
    > half interval  of functions, that is,  if [f(b) - f(m)]/(m-a) is close
    > to [f(b) - f(m)]/(b-m), is it right?

    The trapezoidal rule assumes that the function is linear.  However,
    computing the slope is not a good way of finding out whether it is accurate.

    > So, my solution is like following:
    >
    > --this trape function is the integrate formular, corrected from "divide"
    > to "multiply"
    > trape f a b = (f a + f b)*(b-a)*0.5

    Yes.

    > --this slope function calculate the function f's "slope" at interval [a,b]
    > slope f a b = (f b - f a)/(b-a)

    Not needed: compare the results of integrating the whole interval [a,b]
    with the sum of the integrals of the half intervals [a,m] and [m,b].

    > --if the slope of two interval is close within a tolerance e=0.001, we
    > return one of the integrate formular, of course it should
    > --multiply by 2. If not, recursively call integrate function again.

    This might work; I am not sure.

    > integrate f a b =  if abs (slope f a (half a b) - slope f (half a b) b) <e
    >    then (trape f a (half a b))*2
    >    else integrate f a (half a b) + integrate f (half a b) b  where e =0.001
    > --the result is like following which is quite close to your test:
    >
    > A1> integrate sin 0 pi
    > 2.0

    If you can get answers as close as that, go for it.

    Peter

    So it is mentioned in class...

    Hi,

    Actually our prof. corrected this mistake in Q8 in the
    class, together with 2 other mistakes in Q1 and Q2.
    You can get the corrected version of assignment from
    his web.
    I use a slightly different algorithm with yours: my
    first approximation simply uses the trapeziodal rule;
    second(better) approximation is to split the interval
    into two equal parts, then apply trapeziodal rule to
    both and then take their summation -- I don't mutiply
    the result of one half by 2 and take it as result --
    that's the difference from yours.  The rest of the
    algorithm is same.  In case of e=0.001, I got the same
    result also.

    Cheers,
    Linda

The declaration of an object should not add parentheses after constructor

Hi Professor,
As I asked you in class the VC++ simply won't recognize the declaration of an object with parentheses added after constructor.
See following simple code:
#include <iostream>
using namespace std;
class MyClass
{
public:
void test() { cout<<"This is a test!";}
};
int main()
{
MyClass M();
M.test(); //If M is an object, M should be able to invoke test()
//function, but it won't pass compilation simply because
//compiler recognize it as a function name.
//However, if we use the following syntax, it works.
MyClass* temp = new MyClass();
temp->test();
return 0;
}
This won't pass compilation for statement M.test(); And compiler gives out an error:
error C2228: left of '.test' must have class/struct/union type
Error executing cl.exe.
It confirms my idea that compiler will treat M() as a sort of function name or whatever (making no senses here). But for the dynamic memory allocation, it works fine.
Just to inform you the result.
Thank you for your time.
Nick Huang/Qingzhe Huang

Re:Question no. 6: Since your prototype is using pointer instead of reference of pointer, I don't think we can delete the head, because...

Hi Professor,
Regarding the question 6, in my solution of exam I assumed that we are not allowed to delete "head" because the prototype of function is passing "head" as pointer instead of "reference to pointer". So, suppose the head contains Key, and we delete it, we have no way to modify the "head" and pass it back. Then the whole list is simply lost of track.
So, based on your prototype of passing the "pointer" instead of "reference of pointer", I assumed that "head" never contains key value which is written as an assumption in my exam paper. During the exam, I tried to ask you the question and the time and your rule of "no question" prevented me to explain in details.
For this question, I got only half mark and my name is "Qingzhe Huang", ID: 5037735. And I hope you can look into it.
I wrote a simple test program to show you that if you pass the "head" of list by a pointer, then if the "head" be deleted the whole list is lost which is obvious not the purpose of this question.
Thank you for your time,
Nick Huang/Qingzhe Huang
p.s. The following is the result of program, the last attempt of deleting key of head leading to lost of list and there is an error of memory access:
index no.:0 and value:1
index no.:1 and value:3
index no.:2 and value:2
index no.:3 and value:9
index no.:4 and value:4
index no.:5 and value:5
index no.:6 and value:8
index no.:7 and value:7
index no.:8 and value:0
index no.:9 and value:6
now delete key=3:
index no.:0 and value:1
index no.:1 and value:2
index no.:2 and value:9
index no.:3 and value:4
index no.:4 and value:5
index no.:5 and value:8
index no.:6 and value:7
index no.:7 and value:0
index no.:8 and value:6
now delete key=2:
index no.:0 and value:1
index no.:1 and value:9
index no.:2 and value:4
index no.:3 and value:5
index no.:4 and value:8
index no.:5 and value:7
index no.:6 and value:0
index no.:7 and value:6
can we actually delete the head of which the key=1?
index no.:0 and value:-572662307
Press any key to continue
//the following is the test program:

    #include <iostream>

    using namespace std;

    struct Node
    {
    	Node* next;
    	int data;
    };

    int dataArray[10] = {1, 3, 2, 9, 4, 5, 8, 7, 0, 6};

    Node* initialize(int array[], int size);
    void print(Node* head);
    void deleteKey(Node* head, int K);

    int main()
    {
    	Node* head;
    	head = initialize(dataArray, 10);
    	print(head);
    	cout<<"now delete key=3:\n";
    	deleteKey(head, 3);
    	print(head);
    	cout<<"now delete key=2:\n";
    	deleteKey(head, 2);
    	print(head);
    	cout<<"can we actually delete the head of which the key=1?\n";
    	deleteKey(head, 1);
    	print(head);//is head still OK?
    	return 0;
    }

    //establish a link list and assign value by input int array to each node
    Node* initialize(int array[], int size)
    {
    	Node* head=NULL, * ptr;

    	for (int i=0; i<size; i++)
    	{
    		//first item
    		if (head ==NULL)
    		{
    			head = new Node;
    			ptr = head;
    			ptr->data = array[i];
    			ptr->next = NULL;
    		}
    		else
    		{
    			//all other node is the next one.
    			ptr->next = new Node;
    			ptr = ptr->next;
    			ptr->data = array[i];
    			ptr->next = NULL;
    		}
    	}
    	return head;
    }

    void print(Node* head)
    {
    	Node* ptr=head;
    	int index=0;
    	while (ptr!=NULL)
    	{
    		cout<<"index no.:"<<index<<" and value:"<<ptr->data<<endl;
    		ptr = ptr->next;
    		index++;
    	}
    }

    void deleteKey(Node* head, int K)
    {
    	Node* first=head, *second, *temp;

    	while (first!=NULL)
    	{
    		//first is the one to be deleted
    		if (first->data==K)
    		{
    			temp = first;
    			first=first->next;
    			delete temp;
    		}
    		else
    		{
    			break;
    		}
    	}
    	//the ends of link list
    	if (first==NULL)
    	{
    		return;
    	}

    	//now first is not the key
    	second = first->next;
    	while (second!=NULL)
    	{
    		if (second->data==K)
    		{
    			temp = second;//hold it then delete it.
    			first->next = second->next;
    			second = first->next;
    			delete temp;
    		}
    		else
    		{
    			first=second;
    			second=first->next;
    		}
    	}
    }

                             So, I am correct.

    Hi,
    You're correct. I overlooked this detail. Please give me your
    midterm and I'll correct this error in marking.

    Thomas.

    Can you show me something?

Hi,
I just wonder if you could show me something like following in next tutorial:
1. List all sorting algorithm like bubble, select, insert, merge ... which are stable.
2. I just wonder if it is possible we change all sorting algorithm to be descending from ascending by passing different "Comp" class:
ex: void bubsort<int, CompAscend>(array, size); //this is default for ascending
and we change the "CompAscend" to "CompDescend":
ex: void bubsort<int, CompDescend>(array, size);
where "CompAscend" and "CompDescend" may be defined like following:
class CompAscend
{
public:
static bool lt(int x, int y) { return x < y; } //this is normal for ascending
...
};
class CompDescend
{
public:
static bool lt(int x, int y) { return x>y;} //this is opposite for descending
...
};
Will above work? I have not tried it yet. And what I concerned is that will this change the property of stable of sorting algorithm?
I mean suppose "mergesort" is stable by default in ascending, suppose we use above method to sort it in descending order, will it be unstable or not?
Thank you for your time.
Nick Huang/Qingzhe Huang

How can I find the threshold?

Hi sir,
Regarding assignment 4, the experiment with "threshold" is very time-consumption! And I am not sure if I understand the question correctly.
You asked us first to try to test from threshold =1 until the N, right? And for every trial of threshold, I need to do a 10-test to get the average. Only after all trials, I can be sure of what value the threshold can minimize the average numbers of comparison and movements. The so-called "Qsort2" is actually not exactly quicksort as it is a sort of similar to "shell" sort as it needs insertsort to do the finalize job which is very slow.
I just don't understand how I should find an accurate threshold at such large number of array, say 80000. Because my first test for size of 10000 is already unbearable. My computer is celeron 1.2g notebook.
By the way, the "Shaffer" code for merge sort has a little problem for memory allocation, see below:
template <class Elem, class Comp>
void mersort(Elem* array, int n) {
static Elem* temp = NULL;
if (temp == NULL) //for repeating call, it won't be NULL after first sorting, and you cannot change size of array any more!!!
{
temp = new Elem[n]; // Declare temp array
}
.....
Shaffer uses a static pointer for temp array, suppose you want to repeat call merge sort with different size of array, it won't allocate new size of temp array for you. That is the problem I run into which I asked you in class. At that time, I haven't got time to trace it. Now, I already correct it and hope it help others.
template <class Elem, class Comp>
void mersort(Elem* array, int n) {
Elem* temp = NULL;
if (temp == NULL)
{
temp = new Elem[n]; // Declare temp array
}
mergesort<Elem,Comp>(array, temp, 0, n-1);
delete [] temp; //release memory for new call.
}
Thank you for your time,
Nick Huang/Qingzhe Huang

Template function array...

    Hi sir,

    Thank you for your praise and I wish in future you might be kind enough to
    give me some advice if I run into some problems in programming.

    By the way, just at the time I write this message, I solved a small problem
    of my doubt with template functions.
    http://www.staroceans.com/templateArray.htm

    The question is like this: suppose we have a series of template functions,
    say various sorting algorithms, all with same parameter type. It is
    convenient for us to put them in a function array for continual calling
    during the comparison of different algorithms. (This is actually an
    assignment of comp352.) But for VC++, compiler simply won't compile or even
    check template function until the last minute. So, there is no way to
    initialize function array with these template functions. See following:

    //three different sorting function declared in template
    template <class Elem>
    void bubbleSort(Elem array[], int size);

    template <class Elem>
    void selectSort(Elem array[], int size);

    template <class Elem>
    void quickSort(Elem array[], int size);

    And the following won't work! We cannot initialize array with these template
    functions.
    void (*sortFun[3])(int array[], int size)={bubbleSort<int>, selectSort<int>,
    quickSort<int>};

    I have to declare 3 function pointers to represent these template functions.
    And then put these pointers into array:
    //here I have to declare function pointer to "instanciate the template"
    //otherwise compiler won't start compile template until it is in use
    void (*fun1)(int array[], int size)=bubbleSort<int>;
    void (*fun2)(int array[], int size)=selectSort<int>;
    void (*fun3)(int array[], int size)=quickSort<int>;

    //this is really what I intend to use---to declare a function array to
    //hold the function pointer to
    void (*sortFun[3])(int array[], int size)={fun1, fun2, fun3};

    Conclusion: I remembered in your notes, you asked a question that is C++
    template really passing type as parameter? (Something like this, I am not
    sure.)  Any relation between these?

    Thank you for your time,

    Have a nice day,

    Nick Huang/Qingzhe Huang

Template, Template, Template...

(This is still a bit far from my approach.)

> Conclusion: I remembered in your notes, you asked a question that is C++
> template really passing type as parameter? (Something like this, I am not
> sure.) Any relation between these?
The template facility is very powerful but it is also something of an
'add-on' that doesn't always fit comfortably with the rest of the
language. It is not always obvious how or when to instantiate
templates, which leads to lack of portability and the sort of problems
you described.
I believe that a better approach is to allow classes to accept classes
as parameters and require the compiler to do complete type-checking.
For example, if 'T' is a type parameter and the class assumes that T
provides a function 'f', then the compiler should check that T does
indeed provide f. (C++ does this, sometimes at link time but also,
unfortunately, sometimes at run-time.)
C++ expands templates for every different type. If the template appears
in a header file, it may be expanded many times. This is unnecessary,
because the code may be identical even when the types are different.
Static type checking could detect this and not generate redundant code,
avoiding 'code bloat'.
Because the C++ compiler doesn't really 'understand' templates, it
cannot give helpful error messages. I am sure you have seen some. I
like this one:
Compile error:
44: declaration of
`template <class W_1, class W_2>
T<Ydy,ph::Dimensionless_Entity>::
operator T<W_1,W_2><W_1, W_2>() const'
14: conflicts with previous declaration
`template <class W_1, class W_2>
T<Ydy,ph::Dimensionless_Entity>::
operator T<W_1,W_2><W_1, W_2>() const'
The argument is not all one-sided. C++ templates have flexibility that
other systems lack, and any sophisticated type system tends to give
verbose error messages.
I hope this answers your question.
Peter
很有意思的程序,告诉c++的程序员程序运行的内幕

hi,
这个程序很有意思的，它告诉c++的程序员程序运行的内幕。
1。 Test a(3, 'a');
不用说，constructor 会被调用。
2。 Test b = fun(a);
这一行代码实在是昂贵啊！
a)因为，函数fun是传值的参数，需要copy constructor来copy a 到参数
b)现在进入函数fun了，
t = Test(5); 会声明一个临时变量。注意这里是用member-wise copy，不是copy constructor,因为，这个临时对象马上就会被消灭的。所以，这里紧接着就是destructor消灭临时的Test(5).
c)return t;
这里执行的顺序不是我们所想象的！因为，Test b = fun(a);声明了b并且初始化为fun地返回值，所以，要调用copy constructor 为b赋值。
d)return t;
函数结束t被消灭，调用destructor.
e) main结束，a,b按照声明顺序被消灭，分别调用destructor.
所以，你看到的两个"Delete 3 5 N"， 一个是临时变量Test(5), 另一个是t.
不过，对于delete 对象b的时候，name没有显示，我不是很确定，就是delete 4 5 (空缺)
我不能理解b的copy constructor的传入参数，即fun地返回值为什么不存在了，你有什么想法？
程序代码：

    #include <iostream>
    using namespace std;

    class Test
    {
    public:
    	Test(int n, char c='N') : val(n), name(c)
    	{
    		id = ++idNum;
    		cout << "Construct " << id << " " << val <<"     "<<name<< endl;
    	}

    	Test(const Test & x) : val(x.val)
    	{
    		id = ++idNum;
    		cout << "Copy " << id << " " << val <<"     "<<x.name<< endl;
    	}

    	~Test()
    	{
    		cout << "Delete " << id << " " << val <<"     "<<name<< endl;
    	}
    private:
    	int id;
    	int val;
    	static int idNum;
    	char name;
    };

    int Test::idNum = 0;

    Test fun(Test t)
    {
    	t = Test(5);
    	cout<<"-----------------\n";
    	return t;
    }

    void main()
    {
    	Test a(3, 'a');
    //	fun(a);
    	cout<<"-----------------\n";
    	Test b = fun(a);
    }

    运行结果：

    Construct 1 3 a
    -----------------
    Copy 2 3 a
    Construct 3 5 N
    Delete 3 5 N
    -----------------
    Copy 4 5 N
    Delete 3 5 N
    Delete 4 5
    Delete 1 3 a
    Press any key to continue

    问题：Could you figure out why there are two lines of "Delete 3 5 N"?

    Is template in C++ implemented by a preprocessor?

    Templates are expanded more or less like macros, that is, with no
    semantic processing.  Roughly, variables like <class T> are replaced by
    actual class names.  Then the whole mess is paased over to the compiler.

    The problem with this is that the compiler's error messages relate to
    the expanded text.  If you write tricky template code, the error
    messages can be hard to understand.

    <example>
    error C2440: 'initializing' : cannot convert from 'class
    std::_Tree<class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> >,class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> >,struct std::set<class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> >,struct std::less<class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> > >,class std::allocator<class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> > > >::_Kfn,struct std::less<class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> > >,class std::allocator<class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> > > >::const_iterator' to 'class std::_Tree<class
    std::basic_string<char,struct std::char_traits<char>,class
    std::allocator<char> >,class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> >,struct
    std::set<class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> >,struct
    std::less<class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> > >,class
    std::allocator<class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> > > >::_Kfn,struct
    std::less<class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> > >,class
    std::allocator<class std::basic_string<char,struct
    std::char_traits<char>,class std::allocator<char> > > >::iterator'

    No constructor could take the source type, or constructor overload
    resolution was ambiguous
    </example>

    Another problem with templates is that there is no standard way that
    compilers handle them.  As you say, some compilers require template
    declarations to be in the .h file, but this is not always true.

    Blitz++ is a modern template library for numeric programming:

    http://www.oonumerics.org/blitz/

    If you click on "supported platforms", you will see that only some
    compilers can handle blitz code.  For Visual C++ 6.0, it says:

    "Does not support member templates outside of class declarations, and
    crashes (CRASHES!) if you try to do so. Definitely not recommended."

    A problem with tempates in header files is that the compiler may expand
    them every time it reads the header file, leading to the well-known
    phenomenon of "code bloat".

    Hope this helps,
    Peter

    Hotmail wrote:
    > Hi Professor,
    >
    > I remembered that you said "c++ compiler doesn't understand template".
    > As I am taking comp442 compiler design, it hits me that maybe template
    > is only implemented with a preprocessor of c++ which treats template
    > more or less like a complicated Macro. Because only the semantic
    > analyzer understand the meaning of  program and the preprocessor is only
    > a scanner and parser. And what's more, the template part of codes can
    > never be compiled to object code for others. If we want to include a
    > template, we have to write it in the .h file. Whileas for other code, we
    > can compile the code to be .obj file and give out .h file for
    > interface.  Therefore, I highly suspect that template is only a kind of
    > Macro by a special preprocessor to convert.
    >
    > I have a blur impression that you mentioned something about this in
    > lecture, but not quite sure.
    >
    > Thank you for your time,
    >

    If it is our professor's typical, luxury method of wasting precious memory by declaring useless

    data structures as usual,  then just forget my question.

Hi,
The programming assignment 2 puzzles me a bit ONLY FOR the variable "logP". Because according to definition of "prefix sum", we only need a two-row 2-dimension-array to calculate, right? Then why we need this "logP"? And does "logarithm" have anything to do with "prefix sum"?
If it is our professor's typical, luxury method of wasting precious memory by declaring useless data structures as usual, then just forget my question.
By the way, I feel extremely uncomfortable with our Professor's anti-C++ "indexing" method, so, I basically modified all his "omit-zero-index" declaration. I mean I removed those useless "logP=3;", "Pplus1 = 9;" "logPplus1=4". Is this Ok?
Enclosed pls find my program, can you justify if this is what our assignment expected result?
Thank you so much for your time,
Nick Huang/Qingzhe Huang

operator void*()

Please see following code segment:

    	ifstream in("fileName");
    	if (!in)
    	{
    		cout<<"file fileName  cannot open\n";
    	}
    	char buffer[256];
    	while (in)
    	{
    		in.getline(buffer, 256);
    		if (!in)
    		{
    			break;
    		}
    		cout<<buffer<<endl;
    	}

This is quite simple code, and I believe almost everybody can tell me what is going on except for the "red line" part---- while (in)

Can anybody explain this line? ((///Disregard the following paragraph because what I want to say is not here.)

It is not so simple after you think carefully. You see a name for an instance is just like a variable which by

default has value of its address. We all know this by "cout<<in;" which will output an address. How can we break

the while loop by this "if" statement. The address of variable "in" never changes and will never become 0 unless

the file open operation fails. But if it DID FAIL, then it would never enter "while" loop, right?

It seems to make no sense, but this code works!!!

So, what on earth is going on? (The following is true even the above paragraph looks like garbage.)

The answer is overloading of "operator void*", I guess most of you have never heard about that because it is the

first time I hear about it today. :) Let's use a simple example to explain it:

#include <iostream>

using namespace std;

    class myTest
    {
    private:
    	int data;
    public:
    	myTest(int num=5);
    	void setData(int num){ data=num;}
    	operator void*();  //operator void*
    };

    myTest::myTest(int num)
    {
    	data=num;
    }

    myTest::operator void *()
    {
    	if (data=4)
    	{
    		return NULL;
    	}
    	return this;
    }

int main()

{

    	myTest T;
    	cout<<"ususally T will return its address---'this' pointer:"<<T<<endl;
    	cout<<"but if you set data to be 4 and it will return NULL"<<endl;
    	T.setData(4);
    	cout<<(T==NULL?"it is NULL":"it is not null")<<endl;

return 0;

}

1. There is such kind of "operator void*" that it almost makes the function like an variable itself. This is

also called "user-defined convertion operator". This member function will only be invoked if you try to

evaluate it as an pointer. So, the "if" statement actually invoked the function.

2. IOSTREAM overloading the "operator void*" member function to make it return "NULL" ONLY IF the read operation

fails or the internal "failbit" is set. You can get detail about this by browsing the help on "basic_ios::fail".

(The following are also true...) Sorry, I made some mistakes about above question...

if (!in) ... and while(in) are calling completely different functions of "ifstream" class:

"if (!in)" is calling "operator !()" and will return same value of "fail()" which is a bool-value-member method.

"while(in)" calling "operator void*()" which is only converted to 0 when "fail()&rdstate()".

how to merge two sorted link list ?

    void List::mergeTwoSortedLinkedLists(const List& aList,const List& bList)
    {
    	ListNode* mPtr, *aPtr=aList.head, *bPtr=bList.head, *nxtPtr;
    	bool first=true;
    	head=NULL;//you don't have to, but it is safe
    	while (aPtr!=NULL||bPtr!=NULL)//at least one is not null
    	{
    		//to determine the next ptr to be inserted
    		if (aPtr==NULL)//
    		{
    			nxtPtr=bPtr;
    			bPtr=bPtr->next;//move to next
    		}
    		else
    		{
    			if (bPtr==NULL)
    			{
    				nxtPtr=aPtr;
    				aPtr=aPtr->next;
    			}
    			else
    			{
    				//both are not NULL
    				if (aPtr->item<bPtr->item)//suppose you have overloaded operator "<"
    				{
    					nxtPtr=aPtr;
    					aPtr=aPtr->next;
    				}
    				else
    				{
    					nxtPtr=bPtr;
    					bPtr=bPtr->next;
    				}
    			}
    		}
    		//we have to do the first specially
    		if (first)
    		{
    			head=new ListNode;
    			head->item=nxtPtr->item;
    			head->next=NULL;//initialize
    			mPtr=head;
    			first=false;
    		}
    		else
    		{
    			mPtr->next=new ListNode;
    			mPtr=mPtr->next;
    			mPtr->item=nxtPtr->item;
    			mPtr->next=NULL;
    		}
    	}//end while
    }

    A simple example of initializing constant in class

    #include <iostream>

    using namespace std;

    const int DefaultRoomNumber=10;

    class Room
    {
    private:
    	const int RoomNumber;
    public:
    	Room(int roomNumber=DefaultRoomNumber);
    	void display();
    };

    class Floor
    {
    private:
    	const int FloorNumber;
    	Room room;
    public:
    	Floor(int floorNumber, int roomNumber);
    	void display();
    };

    class APT
    {
    private:
    	Floor floors;
    	const int APTNumber;
    public:
    	APT(int aptNumber, int floorNumber, int roomNumber);
    	void display();
    };

    int main()
    {
    	APT apt(6644, 2, 4);
    	apt.display();
    	return 0;
    }

    Floor::Floor(int floorNumber, int roomNumber):room(roomNumber), FloorNumber(floorNumber)
    {
    	;
    }

    void Floor::display()
    {
    	cout<<"My floor number is "<<FloorNumber<<endl;
    	room.display();
    }

    Room::Room(int roomNumber):RoomNumber(roomNumber)
    {
    	;
    }

    void Room::display()
    {
    	cout<<"My room number is "<<RoomNumber<<endl;
    }

    APT::APT(int aptNumber, int floorNumber, int roomNumber):
    APTNumber(aptNumber), floors(floorNumber, roomNumber)
    {
    	;
    }

    void APT::display()
    {
    	cout<<"my address is apt# "<<APTNumber<<endl;
    	floors.display();
    }

    The running result is like following:

    my address is apt# 6644
    My floor number is 2
    My room number is 4
    Press any key to continue

    	The base class usually need a default constructor, but not always...

    Question: Do you need a default constructor for your base class?

    Answer: You do need a default constructor for your base class as your derived class need to choose a constructor of his

    "father's" unless you make some adjustment in constructor of derived class. See below:

    #include <iostream>

    using namespace std;

    class Father
    {
    protected:
    	char* name;
    public:
    	Father(const char* theName);
    	void display();
    	//Father();//you don't need a default constructor
    };

    class Son : public Father
    {
    public:
    	Son(const char* theName);
    };

    int main()
    {
    	Son S("nick huang");
    	S.display();
    	return 0;
    }

    Father::Father(const char* theName)
    {
    	name=new char[strlen(theName)+1];
    	strcpy(name, theName);
    }

    void Father::display()
    {
    	cout<<name<<endl;
    }

    //You need to initialize the base class's constructor properly
    Son::Son(const char* theName):Father(theName)
    {

    }

    The running result:

    nick huang
    Press any key to continue

    	How to reverse a linked list?

    question: You are given a linked list, or more precisely the pointer of type Link which points to the beginning of a linked list.

    Write a function to reverse the elements in list.

    void reverse(Node* head);

    for example, the linked list is originally -1,41,67,34,0,69,24,78,58,62,64,
    now reverse -1,64,62,58,78,24,69,0,34,67,41.

    The -1 represents the head pointer.

    answer: There are many possible ways to solve this simple question, however, I found I am completely rely on compiler and tracer.

    #include <iostream>

    using namespace std;

    struct Node
    {
    	Node* next;
    	int data;
    };

    const int MaxNumber=10;

    ostream& operator<<(ostream& out, Node* ptr);

    void createNode(Node* head);
    void destroyNode(Node* head);
    void reverse(Node* ptr);

    int main()
    {
    	Node head;
    	head.data=-1;
    	createNode(&head);
    	cout<<&head<<endl;
    	cout<<"now reverse\n";
    	reverse(&head);
    	cout<<&head<<endl;
    	destroyNode(&head);

    	return 0;
    }

    //to reverse a linked list, you first need to find the
    //new head and insert one by one.
    void reverse(Node* ptr)
    {
    	//there are three cases that you don't have to do anything:
    	//1. there is no head
    	//2. there is no element in linked list
    	//3. there is only one element in total linked list
    	if (ptr==NULL ||ptr->next==NULL||ptr->next->next==NULL)
    	{
    		return;
    	}
    	Node* head, *tail, *oldTail, *oldHead;
    	//tail is pointing to the first of linked list
    	tail=ptr->next;
    	head=ptr;
    	//try to pin point head to the end of linked list
    	while (head->next!=NULL)
    	{
    		head=head->next;
    	}
    	//remember the head
    	ptr->next=head;
    	//loop until the tail meets head...
    	while (tail!=head)
    	{
    		//you need to remeber the sublist after new head
    		oldHead=head->next;
    		//you also need to remember the old sublist after tail
    		oldTail=tail->next;
    		//insert tail after head
    		head->next=tail;
    		tail->next=oldHead;
    		//tail goes to next
    		tail=oldTail;
    	}
    	//head->next=NULL;
    }

    //this is a good habit to release all those
    //dynamic memory allocation
    void destroyNode(Node* head)
    {
    	Node* temp1=head->next, *temp2;
    	if (temp1==NULL)
    	{
    		return;
    	}
    	temp2=temp1->next;
    	while (temp2!=NULL)
    	{
    		delete temp1;
    		temp1=temp2;
    		temp2=temp1->next;
    	}
    	delete temp1;
    	head->next=NULL;
    }

    void createNode(Node* head)
    {
    	Node* temp=head;
    	for (int i=0; i<MaxNumber; i++)
    	{
    		temp->next=new Node;
    		temp=temp->next;
    		temp->data=rand()%100;
    		temp->next=NULL;
    	}
    }

    ostream& operator<<(ostream& out, Node* ptr)
    {
    	Node* temp=ptr;
    	while (temp!=NULL)
    	{
    		out<<temp->data<<",";
    		temp=temp->next;
    	}
    	return out;
    }

    The running result is like following:

    -1,41,67,34,0,69,24,78,58,62,64,
    now reverse
    -1,64,62,58,78,24,69,0,34,67,41,

        Even C++ forbids you to create instance of abstract class, but they don't forbid you to do it by array...

    	See below, I can even instantiate it!

    #include <iostream>

    using namespace std;

    const int DefaultAge=20;
    const int ArraySize=3;

    class Father
    {
    protected:
    	char* name;
    public:
    	Father(const char* theName);
    	virtual void display()=0;
    	void speak(){cout<<name<<endl;}
    	//Father();//you don't need a default constructor
    };

    class Son : public Father
    {
    private:
    	int age;
    public:
    	Son(const char* theName);
    	void setAge(int theAge){age=theAge;}
    	void display();
    };

    int main()
    {
    	Father fatherArray[ArraySize]=
    	{
    		Son("zhu chunming"), Son("huang yong"), Father("nick huang")
    	};
    	for (int i=0; i<ArraySize; i++)
    	{
    		fatherArray[i].speak();
    	}

    	//Father F("okok");
    	return 0;
    }

    Father::Father(const char* theName)
    {
    	name=new char[strlen(theName)+1];
    	strcpy(name, theName);
    }

    /*
    void Father::display()
    {
    	cout<<name<<endl;
    }
    */

    void Son::display()
    {
    	//Father::display();
    	cout<<"my age is:"<<age<<endl;
    }

    //You need to initialize the base class's constructor properly
    Son::Son(const char* theName):Father(theName)
    {
    	age=DefaultAge;
    }

    The running result is like this:

    zhu chunming
    huang yong
    nick huang
    Press any key to continue

The template of VC6.0 has many problems, at least it is my personal view

The following simple example shows you how to pass with undetermined number of parameters and how to get them.

The macro in VC6.0 simply hide you the way they cope with different platform and compiler. In win32, vc6.0, you

can simply treat the parameter as null-terminated string and move the pointer with size of type, if the

alignment is what you immagined.

    /* VA.C: The program below illustrates passing a variable
     * number of arguments using the following macros:
     *      va_start            va_arg              va_end
     *      va_list             va_dcl (UNIX only)
     */

    #include <stdio.h>
    #include <stdarg.h>

    const int MaxItemLength=20;

    class IntTest
    {
    public:
    	void set(int first, ...);
    };

    class sonTest: public IntTest
    {

    };

    int main()
    {
    	sonTest I;
    	I.set(23, 45, 67, 3, -1);
    	return 0;
    }

    void IntTest::set(int first, ...)
    {
    	int count = 0, i = first, test;
    	va_list marker;
    	char* ptr;
    	ptr=(char*)(&first);

    	//printf("%s\n", ptr);
    	va_start( marker, first );     // Initialize variable arguments.
    	while( i != -1 )
    	{
    		test=*((int*)(ptr));
    		printf("no. %d is:%d\n", count+1, i);
    		printf("no. %d is:%d\n", count+1, test);
    		ptr+=sizeof(int);
    		count++;
    		i = va_arg( marker, int);
    	}
    	va_end( marker );              // Reset variable arguments.

    }

The result is like this:

no. 1 is:23
no. 1 is:23
no. 2 is:45
no. 2 is:45
no. 3 is:67
no. 3 is:67
no. 4 is:3
no. 4 is:3
Press any key to continue

However, when I try to use template class, there is a problem. See the below code, the trick of char pointer

doesn't work!!! You will be only retrieve the first parameter. I have no idea why it happens except to attribute

it to the bugs of VC6.0.

    /* VA.C: The program below illustrates passing a variable
     * number of arguments using the following macros:
     *      va_start            va_arg              va_end
     *      va_list             va_dcl (UNIX only)
     */

    #include <stdio.h>
    #include <stdarg.h>

    const int MaxItemLength=20;

    template<class T>
    class VarList
    {
    private:
    	T buffer[MaxItemLength];
    protected:
    	virtual bool isEnd(T& item) =0;
    public:
    	T* set(const T& items, ...);
    	virtual void display(T* list)=0;
    };

    class IntList : public VarList<int>
    {
    protected:
    	virtual bool isEnd(int& item){ return item==-1;}
    public:
    	virtual void display(int* list);
    };

    int main( )
    {

    	IntList L;
    	int* temp;
    	temp=L.set(34,45, 23, 0, 9, -1);

    	L.display(temp);

    	return 0;
    }

    void IntList::display(int* list)
    {
    	int count=0;
    	//item=list[count];
    	while (!isEnd(list[count]))
    	{
    		printf("no. %d is: %d\n", count+1, list[count]);
    	}
    }

    template<class T>
    T* VarList<T>::set(const T& items, ...)
    {
    	int count=0;
    	char* ptr;
    	ptr=(char*)(&items);

    	//buffer[count]=items;
    	//va_list marker;
    	//va_start(marker, items);
    	while (!isEnd(buffer[count]))
    	{

    		for (int i=1; i<10; i++)
    		{
    			char* temp=ptr;
    			int j;
    			temp+=i;
    			j=*((T*)(temp));
    			printf("offset %d is:%d\n", i, j);
    		}
    		ptr+=sizeof(T)*2;
    		buffer[++count]=*((T*)(ptr));

    		//buffer[++count]=va_arg(marker, T);
    	}
    	//va_end(marker);
    	return buffer;
    }

     It is my greatest honour to receive encouragement from respectable professor Mr. Cliff Shaffer

Sorry to be so long in replying to your email!
Thank you for sharing your project code with me. I hope you learned from
doing this, and from the book.
Its a bit of a struggle to decide what to include in the book and what not
to include. Space is of course an issue. So is keeping focus for the
students by limiting what I include. One consideration is that I leave
enough potential exercises for students to work on. There's a lot of data
structures that I do not include code for in the book, but which I
mention. AVL trees is one of those. Certainly there are implementations of
AVL trees on the Internet. But I don't, and wouldn't, gather together a
collection of implementations for all of the data structures I mention.
Because if I did, that would reduce the number of good projects that
students could work on to learn things. 2-3 trees is another example where
I include some code but deliberately leave parts out. Because I, or
another instructor, might need a project to give out to the students. Or
an energetic student like yourself might wish to do the work on their own
so as to learn more.
Good luck with your studies!
--
Cliff Shaffer, Associate Professor Phone: (540) 231-4354
Department of Computer Science Email: shaffer@cs.vt.edu
Virginia Tech, Blacksburg, VA 24061-0106 WWW: www.cs.vt.edu/~shaffer
-------------------------------------------------------------------------
On Wed, 14 Jul 2004, nick huang wrote:

Re: It is said that everyone can contribute a word, so my version of AVLTree maybe has some usage for others...

> Dear Professor Shaffer,
>
> It is difficult and disturbing to make a decision on whether to write to you or not.
> It has been almost one year since I study your book <A Practical Introduction to Data Structures and Algorithm Analysis> for my undergraduate "data structure" course in Concordia University, Montreal, Canada. I was so deeply impressed by your sample code which is so compact and concise, clear and clean that I practised for a lot. However, for the AVLTree, you didn't give a sample code for implementation and I try to write some code following your theme. The insertion operation is OK, but the deletion is quite beyond my ability since no algorithm is introduced in your book. My modest wish is just to share my little experience and work with other students. Of course I realized how naive the idea seems to be, however, it is the enthusiasm for C++ programming and computer science that encourage me to do this.
> The following link is my little code page of AVL tree:
> http://www.staroceans.com/AVLTree-remove.htm
>
> Thank you for your time and attention,
>
> have a nice day,
>
> Nick Huang/Qingzhe Huang
>
> Undergraduate, Computer Science Dept.
> Concordia University, Montreal, Canada
>
>
> 我的征尘是星辰大海。。。(Chinese)
> http://www.staroceans.com/
>
> The dirt and dust from my pilgrimage become oceans of stars...(English)
> http://www.staroceans.com/english.htm

The approach seems beyond ability of compiler...

Hi professor,
Thank you so much for your reply and it is my greatest honour to receive a
message from whom I respect so much in programming! I simply don't know how
to express myself properly in English which is my second language.
It is the obvious reason for you to deliberately "hide" some wonderful code
from students and I didn't realize that. :) Thank you so much for your
explanation!
I understand you are very busy. However, still I am curious if you can give
me some advice on this particular question on "template" of VC++6.0 which is
so powerful.
Yesterday I am trying to write a little program on "set" using template so
that my "set class" would be flexible for any type. And I found your way of
"passing a class as function pointer" quite useful. It allows user to define
the "comparison method" for their own type of set. see below:
template<class T, class methods>//method defines comparison and displaying
methods of elements
class MySet
{
private:
T members[MaxSetMember];
int size;
....
};
It seems quite perfect and then it came my problem: How to define "power
set" which is the set of all its sub sets? For the above example, its power
set should be defined as:
template<class T,class methods>
MySet<MySet<T,methods>, someOtherMethods> powerSet;
It seems the compiler cannot handle such kind of definition even though I
managed to make "methods" to be same as "someOtherMethods" like:
MySet<MySet<T,methods>, methods> powerSet;
Still compiler won't recognize my intention. My preliminary conclusion is
that this question is beyond ability of compiler. I am sure you have full
experience of template and could you possibly enlighten me on some way?
Thank you so much for your time and attention,
Nick Huang/Qingzhe Huang

Find the maximum matching (A simple DFS)

The problem: Find a largest matching and a smallest vertex cover (called

simply

covering by Bondy and Murty) in the graph with vertices

1

, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F, G,H, J

and edges

1

B, 1C, 1E, 2F, 2J, 3B, 3E, 3H, 4F, 4G, 5D, 5E,

5

H, 6C, 6D, 6H, 7A, 7F, 7J, 8A, 8G, 9A, 9G, 9J.

    #include <stdio.h>
    #include <stdlib.h>

    const int Row=9;
    const int Col=9;

    int graph[Row][Col]={0};
    int result[Row]={-1};

    void initialize();
    bool doSearch(int index);
    void printResult();

    int main()
    {
    	initialize();
    	doSearch(0);

    	return 0;
    }

    void printResult()
    {
    	for (int i=0; i<Row; i++)
    	{
    		if (result[i]!=-1)
    		{
    			if (result[i]==8)
    			{
    				printf("%c%c,", i+'1', 'J');
    			}
    			else
    			{
    				printf("%c%c,", i+'1', result[i]+'A');
    			}
    		}

    	}
    	printf("\n");
    }

    bool isColFull(int col)
    {
    	for (int i=0; i<Row; i++)
    	{
    		if (result[i]==col)
    		{
    			return true;
    		}
    	}
    	return false;
    }

    bool doSearch(int index)
    {
    	bool isColFull(int col);

    	if (index==Row-1)
    	{
    		printResult();
    		//return true;
    	}
    	for (int i=0; i<Col; i++)
    	{
    		if (graph[index][i]==1)
    		{
    			if (!isColFull(i))
    			{
    				result[index]=i;

    				if (doSearch(index+1))
    				{
    					return true;
    				}
    				else
    				{
    					result[index]=-1;
    				}
    			}
    		}
    	}
    	return false;
    }

    void initialize()
    {
    	FILE* stream;
    	char num, ch;
    	stream=fopen("graph.txt", "r");

    	while (true)
    	{
    		fscanf(stream, "%c%c,", &num, &ch);
    		graph[num-'1'][ch-'A']=1;
    		if (feof(stream))
    		{
    			break;
    		}
    	}
    	fclose(stream);
    	for (int i=0; i<Row; i++)
    	{
    		result[i]=-1;
    	}
    }

    The input file "graph.txt"

1B,1C,1E,2F,2I,3B,3E,3H,4F,4G,5D,5E,5H,6C,6D,6H,7A,7F,7I,8A,8G,9A,9G,9I,

And the result: (I only print the matching of size of 8 because there is no matching of size of 9)

1B,2F,3E,4G,5D,6C,7J,8A,
1B,2F,3E,4G,5D,6H,7J,8A,
1B,2F,3E,4G,5H,6C,7J,8A,
1B,2F,3E,4G,5H,6D,7J,8A,
1B,2F,3H,4G,5D,6C,7J,8A,
1B,2F,3H,4G,5E,6C,7J,8A,
1B,2F,3H,4G,5E,6D,7J,8A,
1B,2J,3E,4F,5D,6C,7A,8G,
1B,2J,3E,4F,5D,6H,7A,8G,
1B,2J,3E,4F,5H,6C,7A,8G,
1B,2J,3E,4F,5H,6D,7A,8G,
1B,2J,3E,4G,5D,6C,7F,8A,
1B,2J,3E,4G,5D,6H,7F,8A,
1B,2J,3E,4G,5H,6C,7F,8A,
1B,2J,3E,4G,5H,6D,7F,8A,
1B,2J,3H,4F,5D,6C,7A,8G,
1B,2J,3H,4F,5E,6C,7A,8G,
1B,2J,3H,4F,5E,6D,7A,8G,
1B,2J,3H,4G,5D,6C,7F,8A,
1B,2J,3H,4G,5E,6C,7F,8A,
1B,2J,3H,4G,5E,6D,7F,8A,
1C,2F,3B,4G,5D,6H,7J,8A,
1C,2F,3B,4G,5E,6D,7J,8A,
1C,2F,3B,4G,5E,6H,7J,8A,
1C,2F,3B,4G,5H,6D,7J,8A,
1C,2F,3E,4G,5D,6H,7J,8A,
1C,2F,3E,4G,5H,6D,7J,8A,
1C,2F,3H,4G,5E,6D,7J,8A,
1C,2J,3B,4F,5D,6H,7A,8G,
1C,2J,3B,4F,5E,6D,7A,8G,
1C,2J,3B,4F,5E,6H,7A,8G,
1C,2J,3B,4F,5H,6D,7A,8G,
1C,2J,3B,4G,5D,6H,7F,8A,
1C,2J,3B,4G,5E,6D,7F,8A,
1C,2J,3B,4G,5E,6H,7F,8A,
1C,2J,3B,4G,5H,6D,7F,8A,
1C,2J,3E,4F,5D,6H,7A,8G,
1C,2J,3E,4F,5H,6D,7A,8G,
1C,2J,3E,4G,5D,6H,7F,8A,
1C,2J,3E,4G,5H,6D,7F,8A,
1C,2J,3H,4F,5E,6D,7A,8G,
1C,2J,3H,4G,5E,6D,7F,8A,
1E,2F,3B,4G,5D,6C,7J,8A,
1E,2F,3B,4G,5D,6H,7J,8A,
1E,2F,3B,4G,5H,6C,7J,8A,
1E,2F,3B,4G,5H,6D,7J,8A,
1E,2F,3H,4G,5D,6C,7J,8A,
1E,2J,3B,4F,5D,6C,7A,8G,
1E,2J,3B,4F,5D,6H,7A,8G,
1E,2J,3B,4F,5H,6C,7A,8G,
1E,2J,3B,4F,5H,6D,7A,8G,
1E,2J,3B,4G,5D,6C,7F,8A,
1E,2J,3B,4G,5D,6H,7F,8A,
1E,2J,3B,4G,5H,6C,7F,8A,
1E,2J,3B,4G,5H,6D,7F,8A,
1E,2J,3H,4F,5D,6C,7A,8G,
1E,2J,3H,4G,5D,6C,7F,8A,
Press any key to continue

Is it semantically reasonable?

Look at the following simple code which is OK in vc++6.0 and cannot compile in g++ in Linux. In function "increment" which takes an argument of reference of class First. And g++ considers there is a mismatch of type because the return type of "first+second" is "value" of class First.

I argued fiercely with Mr. Zhang who considers this is semantically unreasonable for vc++ and it maybe some source of bugs. My argument is that since expression is always evaluated as a temporary variable internally there can never be any problem for compiler to pass this temporary object as parameter. We cannot persuade each other.

From perspective of reference as in/out parameter, he is right. This is semantically wrong as expression can never be used as in/out parameter. However, from perspective of mode of passing parameter, reference is simply an efficient way of passing by value and reference has nothing to do with in/out parameter. Just imagine that all functions with return value can always be called without using that return value. Therefore the temporary value is discarded. Passing a parameter by reference is not ALWAYS expected to get a result from it. And this is always true for expression which acts as a parameter.

Notes: For those who are not familiar with OOP of C++, the following code will be executed like this:

1. Friend function of operator + overloading will be executed to generate a temporary object class First.

2. The temporary object will be passed by reference to friend function "increment".

3. The function "increment" increments the temporary object.

However, I also agree with Mr. Zhang that it is not very good for vc++ to allow such flexibility. For example,

void test(int&) is the function "test" and you cannot pass an expression like "a+5" where a is an integer variable. So, vc++ is inconsistent with its theme in allowing you to pass temporary object as reference.

    #include <stdio.h>

    class First
    {
    	friend First operator+(First&, First&);
    	friend void increment(First& );
    private:
    	int data;
    public:
    	First(int mydata=5);
    	void display();
    };

    int main()
    {
    	First first(6), second(19);
    	first.display();
    	second.display();
    	increment(first+second);
    	first.display();
    	second.display();

    	return 0;
    }

    void First::display()
    {
    	printf("data=%d\n", data);
    }

    First::First(int mydata)
    {
    	data=mydata;
    }

    First operator+(First& first, First& second)
    {
    	First result;
    	result.data=first.data+second.data;
    	return result;
    }

    void increment(First& first)
    {
    	first.data++;
    }

Running result:

data=6
data=19
data=6
data=19
Press any key to continue

关于弹性碰撞的讨论

（我犯了一个低级错误，李向东关于勾股定理的证明是对的，即一个球静止，碰撞后的夹角必定为90度。但是我其他的结论保持不变，即其他情况不一定是直角。）

这个问题看起来非常简单，而我们也过度相信自己的不可靠的知觉。我花了一个晚上时间终于认识到向东同学的运用勾股定理证明的错误，这是一个非常诱人的陷阱：速度是矢量，当一个运动的球碰撞一个静止的球时候，他们碰撞后的速度的“绝对值”的平方和的确是等于原来速度的平方，这是根据能量守恒定律，是正确的。但是我们的错误在于由此导出结论速度的方向也就是要符合这个所谓的“勾股定理”却是毫无意义的，因为速度的绝对值符合勾股定理并不代表速度的“方向”也符合勾股定理，这是毫无逻辑可言的。（真正的结论是这是完全符合逻辑的，我的批评是毫无逻辑可言的。我收回我的评论。）速度的方向要用动量守恒定律结合能量守恒定律一起求解，并且还有一个小小的细节就是我昨天说的碰撞的那一刻两个球的接触点一定在当时两个球的球心连线上，这可以用简单的几何定理证明，此处略。

1。求解碰撞时刻的两球的位置。

这个很容易，就是计算两个球飞行时间市的两个球心间距离恰好等于半径之和。

其中两个球的坐标分别为(x1,y1)，(x2,y2)，他们的速度分别为(vx1,vy1)，(vx2,vy2)。因为可以把速度分解为x,y坐标得分速度。

assume P{(x1,y1),(vx1,vy1)}, Q{(x2,y2),(vx2,vy2)}

假定飞行时间为 t
flying time t

飞行后的坐标变为：
P{x1+vx1*t, y1+vy1*t}, Q{x2+vx2*t,y2+vy2*t}

两球心这时候的距离为半径之和 r1+r2：
The distance between P,Q should be (r1+r2)

运用两点之间距离公式：
So, square(x2-x1+t(vx2-vx1))+square(y2-y1+t(vy2-vy1))=square(r1+r2)

化简后是一个关于t的一元二次方程，因为有可能有两个点都满足以上条件，我们只取碰撞发生的“前点”，也就是t>0并且取t较小的那个根。以下为一元二次方程的三个系数a,b,c
a=square(vx2-vx1)+square(vy2-vy1)
b=2*((vy2-vy1)(y2-y1)+(vx2-vx1)(x2-x1))
c=square(x2-x1)+square(y2-y1)-square(r1+r2)

t1=(-b+sqrt(b*b-4*a*c))/2/a

t2=(-b-sqrt(b*b-4*a*c))/2/a

2。运用两个守恒定律求解碰撞后的速度方向和大小。

假定两个球现在处于碰撞位置，则作用力与反作用力一定在球心的连线上，可以把这个冲量表达为一个矢量，就是两个球心坐标所组成的“矢量”在乘以某一个系数，因此我们的问题归结于求这个系数，因为，求出了冲量，自然可以运用矢量的加法来求解球的速度。

球心坐标

assume the collision point is p1(x1,y1), p2(x2,y2)

这就是冲量delta
the delta speed vector should be on the line of p1_p2
delta=scalor*(x1-x2,y1-y2) is exerted on Quantum Q
-delta should be exerted on Quantum P

动量守恒定律自动得到满足，只要分别作用在两个球上的冲量方向相反，绝对值相等。
the conservation of moment is satisfied since |delta|=|-delta|
or delta+(-delta)=0 moment

现在只要满足动能守恒定律就可以了，请注意，运用矢量的概念自动解决了符号问题。
the conservation of energy should also be satisfied
(sq stands for square):
sq(vx1)+sq(vy1)+sq(vx2)+sq(vy2)=sq(vx1+scalor*(x1-x2))+sq(vy1+scalor*(y1-y2))
+sq(vx2+(scalor*(x2-x1))+sq(vy2+(scalor*(y2-y1))
simplify and get:

化简后，scalor也就是我们要求的系数由两个解，忽略0解，得到：
a=(sq(x1-x2)+sq(y1-y2))
b=(x1-x2)(vx2-vx1)+(y1-y2)(vy2-vy1)
scalor=b/a

这里我全部运用自定义的矢量类的操作符重载，比如(x1-x2)，(y1-y2)等价于球心坐标的两个矢量之差。

(vx2-vx1)，(vy2-vy1)等价于两个球的速度的矢量之差。我有重载了矢量的乘法操作符定义为矢量对应元素乘积之和，我记得这应该是线性代数里面的dot product，中文也许叫做内乘积吧？

delta=coord-other.coord;
scalor= ((other.speed-speed)*delta)/(delta.sqrLength());

3。设计让两个小球以任意的速度方向飞行期待着他们在某一点相撞是一件很繁琐的事情，于是我就写了一个简单的控制程序，让若干个小球在一个固定大小的长方形区域飞行，追踪他们的碰撞事件，当然更多的是他们撞墙的事件，我并且输出他们碰撞前后的夹角，经过观察否定了郑署昭同学的直觉，我不记得我是否观察到台球碰撞后的夹角是否为直角，但是，可以肯定地说，这不是真实地感觉。以下为一些运行结果。

elapsed=0.000000,
****************************************
**1*************************************
****************************************
****************************************
*******1********************************
****************************************
****************************************
***********1***************1************
****************************************
****************************************
****************************************
***********1****************************
************************1***************
*****1**********1***********************
****************************************
**********1************************1****
****************************************
****************************************
****************************************
****************************************
one quantum speed is zero
Angle after collision:90.002654 degree
elapsed=0.812902,collision{11.260000,7.480000}collision{9.803221,6.109674}
****************************************
**1*************************************
****************************************
****************************************
****************************************
****************************************
*********1******************************
***********1***************1************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
***************1************************
**********1************************1****
*****************1*********1************
*******1********************************
****************************************
****************************************
elapsed=1.042105,bounce{8.425789, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
****************************************
*********1******************************
***************************1************
***********1****************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1******1*****************1****
****************************************
*****************1*********1************
****************************************
********1*******************************
elapsed=1.283168,bounce{28.730297, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
************1***************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1*******1****************1****
****************************************
*********1******************************
*****************1**********************
****************************1***********
elapsed=1.334831,bounce{17.914831, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
************1***************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1************************1****
******************1*********************
*********1******************************
****************************1***********
*****************1**********************
one quantum speed is zero
Angle after collision:90.002654 degree
elapsed=1.407472,collision{10.120000,15.040000}collision{9.430549,16.917407}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
****************************************
************1***************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1************************1****
*********1*********1********************
****************************************
*****************1***********1**********
****************************************
elapsed=2.264516,bounce{24.280968, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
****************************************
***********1****************************
****************************************
***************1************************
****************************************
****************************************
******************1************1********
***********************************1****
****************************************
*********1******************************
****************************************
************************1***************
elapsed=3.782093,bounce{15.275988, 1.000000}
****************************************
**1************1************************
****************************************
****************************************
***********1****************************
****************************************
************************************1***
***************************1************
********************1*******************
****************************************
****************************************
****************************************
****************************************
****************************************
*********************************1******
*******************1***************1****
****************************************
**********1*****************************
****************************************
****************************************
elapsed=4.443077,bounce{39.000000, 3.042462}
****************************************
**1*************************************
****************************************
***************************************1
***********1****1***********************
*********************1******************
****************************************
***************************1************
****************************************
****************************************
****************************************
****************************************
************************************1***
****************************************
****************************************
***********************************1****
****************************************
***********1*********1******************
****************************************
****************************************
elapsed=4.824348,bounce{39.000000, 11.064522}
****************************************
**1**********************************1**
****************************************
*********************1******************
***********1****************************
****************************************
****************************************
*****************1*********1************
****************************************
****************************************
****************************************
***************************************1
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1****************************
**********************1*****************
****************************************
elapsed=4.847525,bounce{37.685545, 1.000000}
****************************************
**1**********************************1**
****************************************
*********************1******************
***********1****************************
****************************************
****************************************
*****************1*********1************
****************************************
****************************************
**************************************1*
****************************************
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1****************************
***********************1****************
****************************************
elapsed=4.999554,bounce{23.506791, 19.000000}
****************************************
**1**********************************1**
*********************1******************
****************************************
***********1****************************
****************************************
****************************************
***************************1************
*****************1**********************
****************************************
*************************************1**
****************************************
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1****************************
****************************************
***********************1****************
elapsed=5.379775,bounce{21.959775, 1.000000}
****************************************
**1******************1******************
****************************************
***********************************1****
***********1****************************
****************************************
****************************************
***************************1************
****************************************
***********************************1****
******************1*********************
****************************************
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1************1***************
****************************************
****************************************
Angle before collision:274.441524 degree
Angle after collision:82.054012 degree
elapsed=5.906837,collision{34.242780,6.349526}collision{32.775688,7.708806}
****************************************
**1*************************************
****************************************
***********1**********1*****************
****************************************
****************************************
**********************************1*****
***************************1****1*******
****************************************
****************************************
****************************************
****************************************
****************************************
*******************1********************
****************************************
***********************************1****
**************************1*************
************1***************************
****************************************
****************************************
one quantum speed is zero
Angle after collision:89.992037 degree
elapsed=6.240128,collision{29.953400,7.514897}collision{27.980000,7.840000}
****************************************
**1*************************************
****************************************
************1***************************
**********************1*****************
****************************************
****************************************
***************************1*1****1*****
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
********************1******1*******1****
****************************************
************1***************************
****************************************
****************************************
Angle before collision:273.312783 degree
Angle after collision:93.699242 degree
elapsed=6.679754,collision{23.259754,6.784903}collision{24.396670,8.430327}
****************************************
**1*************************************
****************************************
************1***************************
****************************************
****************************************
***********************1*****1**********
****************************************
************************1********1******
****************************************
****************************************
****************************************
****************************************
****************************************
****************************1***********
***********************************1****
****************************************
****************************************
************1********1******************
****************************************
elapsed=6.826479,bounce{21.886230, 19.000000}
****************************************
**1*************************************
****************************************
************1***************************
****************************************
****************************************
**********************1******1**********
****************************************
*********************************1******
***********************1****************
****************************************
****************************************
****************************************
****************************1***********
****************************************
***********************************1****
****************************************
****************************************
************1***************************
*********************1******************
Angle before collision:5.676226 degree
Angle after collision:2.434235 degree
elapsed=7.432483,collision{23.202040,15.416987}collision{21.580977,14.245597}
****************************************
**1*************************************
****************************************
************1***************************
****************************************
********************1********1**********
****************************************
****************************************
****************************************
****************************************
*********************************1******
****************************************
******************************1*********
****************************************
*********************1******************
***********************1***********1****
****************************************
****************************************
************1***************************
****************************************
Angle before collision:34.879093 degree
Angle after collision:18.731812 degree
elapsed=7.700319,collision{33.288529,10.890265}collision{31.407066,11.568571}
****************************************
**1*************************************
************1***************************
****************************************
*******************1*********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
*********************************1******
*******************************1********
****************************************
****************************************
************************1***************
*******************1***************1****
****************************************
****************************************
*************1**************************
****************************************
elapsed=8.244684,bounce{16.438874, 19.000000}
****************************************
**1*************************************
************1***************************
*****************1***********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
******************************1****1****
***************************1************
****************************************
****************************************
***********************************1****
****************************************
****************************************
*************1**************************
****************1***********************
Angle before collision:22.586885 degree
Angle after collision:97.764464 degree
elapsed=8.400496,collision{15.452419,18.087920}collision{13.477487,18.403587}
****************************************
**1*************************************
*************1**************************
*****************1***********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
******************************1*********
***************************1********1***
****************************************
****************************************
****************************************
***********************************1****
****************************************
****************************************
*************1*1************************
****************************************
Angle before collision:289.922483 degree
Angle after collision:75.775825 degree
elapsed=8.458620,collision{28.088211,11.270706}collision{30.026903,10.779306}
****************************************
**1*************************************
*************1**************************
*****************1***********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
******************************1*********
****************************1*******1***
****************************************
****************************************
****************************************
***********************************1****
****************************************
***************1************************
*************1**************************
****************************************
elapsed=8.924433,bounce{10.745949, 19.000000}
****************************************
**1*************************************
*************1*1*************1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
********************************1*******
***************************1************
**************************************1*
****************************************
****************************************
***************1************************
***********************************1****
****************************************
****************************************
****************************************
**********1*****************************
Angle before collision:283.708612 degree
Angle after collision:85.467110 degree
elapsed=9.018499,collision{15.284104,2.264615}collision{13.288968,2.404013}
****************************************
**1*************************************
*************1*1*************1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**************************1*****1*******
****************************************
**************************************1*
****************************************
***************1************************
****************************************
***********************************1****
****************************************
****************************************
**********1*****************************
****************************************
elapsed=9.055931,bounce{39.000000, 12.003266}
****************************************
**1*************************************
*************1*1*************1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**************************1******1******
****************************************
****************************************
***************************************1
***************1************************
****************************************
***********************************1****
****************************************
****************************************
**********1*****************************
****************************************
elapsed=9.595360,bounce{15.458999, 1.000000}
****************************************
**1************1************1***********
***********1****************************
****************************************
****************************************
****************************************
****************************************
***********************************1****
*************************1**************
**************1*************************
****************************************
****************************************
************************************1***
****************************************
****************************************
***********************************1****
****************************************
****************************************
*******1********************************
****************************************
elapsed=9.625199,bounce{28.880118, 1.000000}
****************************1***********
**1************1************************
***********1****************************
****************************************
****************************************
****************************************
****************************************
***********************************1****
*************************1**************
**************1*************************
****************************************
****************************************
************************************1***
****************************************
****************************************
***********************************1****
****************************************
****************************************
*******1********************************
****************************************
elapsed=10.225379,bounce{39.000000, 5.850923}
****************************************
**1*************************************
*********1*****1************1***********
****************************************
****************************************
**************1************************1
****************************************
************************1***************
****************************************
****************************************
****************************************
****************************************
**********************************1*****
****************************************
****************************************
***********************************1****
****************************************
***1************************************
****************************************
****************************************
这是一个关于template-template的参数的demo，你可以想象你针对一大堆的container想再写一个类这个类实用所有他们通用的方法，比如insert.这个是我暑假买的关于模板的经典的书里看到这样一个匪夷所思的做法，就是模板也可以嵌套模板，当时兴奋地在vc++6.0上法像不支持，现在vc++2005总算可以了！

    // dummy.cpp : Defines the entry point for the console application.
    //

    #include "stdafx.h"
    #include <list>
    #include <iostream>

    using namespace std;

    template <class Type>
    class MyContainer
    {
    public:
    	int number;
    	Type array[10];
    	void insert(Type data)
    	{
    		array[number++]=data;
    	}
    	Type pop()
    	{
    		return array[--number];
    	}
    	MyContainer<Type>()
    	{
    		number=0;
    	}
    };

    template < class Type,  template <typename Type> class Container >
    class Algo
    {
    public:
    	//Type array[10];
    	Container<Type> container;
    	void insert(Type data)
    	{
    		container.insert(data);
    	}
    	void print()
    	{
    		//int temp;
    		//temp=container.begin();
    		cout<<container.pop()<<endl;
    	}
    };

    int _tmain(int argc, _TCHAR* argv[])
    {
    	//printf("hello world!");

    	Algo<int,MyContainer> algo;
    	algo.insert(5);
    	algo.print();
    	return 0;
    }

      Proposition(trivial)

    Can you imagine that I define such a complicated data structure for boolean value? Is it really

    necessary? I am not sure, either. But previous experience told me that internally a proposition

    will be treated like variable rather than constant since we need to "deduct" and there will be

    a period that proposition is unset. Therefore a third value for "truth" value is needed.

    The only remarkable thing is that I overloaded operator "," which will be handy.

    proposition.h

    #include <iostream>
    #include <string>
    //#include <stdarg.h>

    using namespace std;

    enum TruthState
    {
    	TRUE=1, UNKNOWN=0, FALSE=-1
    };

    struct Truth
    {
    	Truth operator &&(const Truth& right) const;
    	Truth operator = (bool right);
    	Truth operator !();
    	Truth operator==(const Truth& right) const;
    	Truth operator==(bool right) const;
    	Truth(TruthState theTruth=UNKNOWN);
    	TruthState truth;
    };

    class Proposition
    {
    	friend Proposition and(const Proposition& first, const Proposition& second)
    	{
    		Proposition result=first;
    		//result.name+=" ";
    		result.name+=second.name;
    		result.truth=result.truth&&second.truth;
    		return result;
    	}
    	friend ostream& operator<<(ostream& os, const Proposition& prop)
    	{
    		os<<prop.name<<":";
    		switch (prop.truth.truth)
    		{
    		case UNKNOWN:
    			os<<"UNKNOWN";
    			break;
    		case TRUE:
    			os<<"TRUE";
    			break;
    		case FALSE:
    			os<<"FALSE";
    			break;
    		}
    		os<<"\n";
    		return os;
    	}
    	//friend Proposition operator,(const Proposition& left, const Proposition& right);
    public:
    	Proposition(const string& theName="", Truth theTruthValue=Truth(UNKNOWN));
    	Proposition(const string& theName, TruthState truthState);
    	Proposition(const string& theName, bool theTruthValue);
    	Proposition operator ,(const Proposition& other);

    	Proposition operator&&(const Proposition& other);
    	const string& getName() const;
    	Truth operator()() const;

    protected:
    	string name;
    	Truth truth;
    };

    proposition.cpp

    #include <string>
    //#include <stdarg.h>
    #include "Proposition.h"
    using namespace std;

    ////////////////////////////////////////////////////////////////////
    //It is a bit unbelieveable that I overload a simple truth struct with
    //so many operator overloading. and do we need these seemingly-redundant
    //Truth struct?
    ///////////////////////////////////////////////////////////////////////

    Truth::Truth(TruthState theTruth)
    {
    	truth=theTruth;
    }

    Truth Truth::operator &&(const Truth& right) const
    {
    	if (truth==0||right.truth==0)
    	{
    		return Truth(UNKNOWN);
    	}
    	else
    	{
    		return (truth<right.truth)?*this:Truth(right);
    	}
    }

    Truth Truth::operator = (bool right)
    {
    	truth= right?TRUE:FALSE;
    	return *this;
    }

    Truth Truth::operator !()
    {
    	if (truth!=UNKNOWN)
    	{
    		truth=(truth==TRUE)?FALSE:TRUE;
    	}
    	return *this;
    }

    Truth Truth::operator ==(const Truth& right) const
    {
    	if (truth!=UNKNOWN&&right.truth!=UNKNOWN)
    	{
    		return (truth==right.truth)?Truth(TRUE):Truth(FALSE);
    	}
    	else
    	{
    		return Truth(UNKNOWN);
    	}
    }

    Truth Truth::operator == (bool right) const
    {
    	if (truth!=UNKNOWN)
    	{
    		if (truth==TRUE&&right||truth==FALSE&&!right)
    		{
    			return Truth(TRUE);
    		}
    		else
    		{
    			return Truth(FALSE);
    		}
    	}
    	else
    	{
    		return *this;
    	}
    }

    //have at least one arguments

    //constructor
    Proposition::Proposition(const string& theName, TruthState truthState)
    {
    	name=theName;
    	truth.truth=truthState;
    }

    Proposition::Proposition(const string& theName, bool theTruthValue)
    {
    	name=theName;
    	truth=theTruthValue;
    }

    Proposition::Proposition(const string& theName, Truth theTruth)
    {
    	name=theName;
    	truth=theTruth;
    }

    Truth Proposition::operator () () const
    {
    	return truth;
    }

    const string& Proposition::getName() const
    {
    	return name;
    }

    Proposition Proposition::operator &&(const Proposition& other)
    {
    	return and(*this, other);
    }

    Proposition Proposition::operator ,(const Proposition& other)
    {
    	return and(*this, other);
    }

    main.cpp

    #include <iostream>
    #include <string>
    #include "proposition.h"

    using namespace std;

    int main()
    {
    	Proposition p("p", true), q("q", false), r("r", UNKNOWN);

    	cout<<(p&&q&&r)<<endl;

    	//cout<<and((p, q), Proposition("new name"), Proposition("I am false", false))<<endl;

    	return 0;
    }

The recursion version of permutation in the order of minimal change.

    #include <iostream>
    #include <ctime>

    using namespace std;

    const int MaxNumber=4;

    int counter=0;

    void recurPerm();
    void visit(int* array, int size, bool left2right);

    int lexRank(int* array, int size);

    int factor(int n);

    int main()
    {
    	//int array[MaxNumber]={4,3,2,1};
    	//cout<<lexRank(array, 4)<<endl;
    	recurPerm();
    	return 0;
    }

    //assume contents in array starts from 1 instead of 0
    int lexRank(int* array, int size)
    {
    	int local[MaxNumber];
    	int result=0;
    	memcpy(local, array, sizeof(int)*size);
    	for (int i=0; i<size; i++)
    	{
    		result+=(local[i]-1)*factor(size-i-1);
    		for (int j=i+1; j<size; j++)
    		{
    			if (local[j]>local[i])
    			{
    				local[j]--;
    			}
    		}
    	}
    	return result;
    }

    int factor(int n)
    {
    	int result=1;
    	for (int i=1; i<=n; i++)
    	{
    		result*=i;
    	}
    	return result;
    }

    void recurPerm()
    {
    	time_t start, finish;
    	int data[1]={1};
    	start=time(0);
    	visit(data, 1, false);
    	finish=time(0);

    	cout<<"\nthe total number of permutation is:"<<counter<<endl;
    	cout<<"the total running time in seconds is:"<<finish-start<<endl;
    }

    void insert(int* array, int size, int pos, int value)
    {
    	//right shift by one from pos
    	for (int i=size; i>pos; i--)
    	{
    		array[i]=array[i-1];
    	}
    	array[pos]=value;
    }

    void displayArray(int* array, int size)
    {
    	cout<<"[";
    	for (int i=0; i<size; i++)
    	{
    		cout<<array[i];
    		if (i!=size-1)
    		{
    			cout<<",";
    		}
    	}
    	cout<<"]\n";
    }

    void visit(int* array, int size, bool left2right)
    {
    	if (size==MaxNumber)
    	{
    		counter++;
    		if (MaxNumber<6)
    		{
    			displayArray(array, size);
    		}

    		return ;
    	}
    	int local[MaxNumber];
    	int pos=left2right?0:size;
    	int shift=left2right?1:-1;
    	int boundary=left2right?size+1:-1;
    	//this is the most tricky part and I cannot figure it out for one hour
    	//finally I tried and tested and get this unexplanable format
    	bool temp=size%2==0?left2right:false;

    	do
    	{
    		memcpy(local, array, size*sizeof(int));
    		insert(local, size, pos, size+1);
    		//visit(local, size+1, (size+pos)%2==1);
    		visit(local, size+1, temp);
    		temp=!temp;
    		pos+=shift;
    	}
    	while (pos!=boundary);
    	/*
    	if (size==MaxNumber-1)
    	{
    		cout<<"\n";
    	}
    	*/
    }

The running result:

[1,2,3,4]
[1,2,4,3]
[1,4,2,3]
[4,1,2,3]
[4,1,3,2]
[1,4,3,2]
[1,3,4,2]
[1,3,2,4]
[3,1,2,4]
[3,1,4,2]
[3,4,1,2]
[4,3,1,2]
[4,3,2,1]
[3,4,2,1]
[3,2,4,1]
[3,2,1,4]
[2,3,1,4]
[2,3,4,1]
[2,4,3,1]
[4,2,3,1]
[4,2,1,3]
[2,4,1,3]
[2,1,4,3]
[2,1,3,4]
the total number of permutation is:24
the total running time in seconds is:0
Press any key to continue

And the discussion between students and professor is more interesting than the program itself.

One student wrote:
> Dear Sir,
>
> I wanted to ask you about the largest number which your recursive
> program can accept to generate all permutations. You told us in last
> session that if we get a stack overflow then the recursive algorithm is
> not correct, but there is a point, to generate p(n) (let us consider p
> as a recursive implementation of algorithm p of knuth) based on p(n-1),
> we should have at least (n-1)! objects in the stack, so because
> (obviously) the stack does not have an infinite memory so in some point
> we would have a stack overflow, is there anything wrong whit this
> observation?

Professor wrote:

The generation of the Trotter-Johnson sequence of permutation is easiest
to define recursive as adding the number n in a systematic manner to all
the sequences on n-1 letters. However, this is NOT a good way to
implement the algorithm, because one should avoid having to store all
the (n-1)! permutations before generating the permutations on n letters.
I just tried some experiment with my own recursive implementation of
Knuth's alg P. With n=10, it finishes almost instantenously. With n=11,
it takes a few seconds. With n=12, it looks like a minute. The largest
n is bounded by the amount of CPU time I wish to spend, and is not
bounded by the stack size.
In my implementation, the arrays, c, o and a are all global variables.
There are only 3 local int variables in the actual recursive function.
With n=12, the deepest recursive level is 13, and the amount of stack
space used is minimal, probably less than 1 kilobyte.

I wrote:

My version runs a little bit slower than your case, 96seconds for n=12. And I guess it is due to that I pass array as parameter in each recursive call. It uses up a bit more memory but the maximum usage memory is only the maximum depth of stack. i.e. my array is fixed size of x and maximum recursion deption is d, then the memory is d*x.
My question is that if you don't pass array as parameter in recursive call, does that mean you pre-allocate a collection of arrays with number of maximum number of stack depth? Because I think in each stack frame or recursion call, you have to maintain a local array, right? If you want to save stack memory space by declaring them as global, you need to declare one for each depth of recursion, is it?
I am just curious about your implementation.
Thank you for your time,

note about understanding N-Queen problem

Once a month, I spend a few hours thinking about problems in comb. algo. which is always like puzzles to me, especially when I try to understand Knuth's notes. Sometimes I do feel annoyed against Knuth because like all genius he just simply assume everybody else understand those simple facts like himself without even giving out basic definition of what he is talking about. For example, in his unique way of solving N-Queen problem, he is trying his beautiful idea of "dancing links" which is intended to defeat sparse matrix by using doubly link data structure to "link" those isolated elements in sparse matrix. This is a very general idea to fight huge sparse matrix during operations like back track which repeatedly pass-in and return-out these data structures. However, what he is doing is more than this. He transforms N-Queen problem to an exact-cover problem which is a more profound idea in my view point because almost all of our searching problem is done by "matching exact conditions to guarantee deterministic property" otherwise we are living a chaotic world. And all these strictly constraint searching conditions can be transformed to an exact cover problem by using these conditions as row and column in a relation matrix. The only problem is that for most of cases, this huge matrix is a huge sparse matrix as many of the conditions are not so "close" related. So, this generalization seems impractical to use unless we convert our sparse matrix representation to such a "compact" data structure like what Knuth has done. In 4-Queen problem, Knuth gives an example of doing this. And please note that a simple "commonsense" that we are supposed to cover all row, column, diagonals exactly once. This can be naively translate to a 22x22 matrix. (4rows+4column+7primary-diagonal+7reverse-diagonal=22 and it takes me more than half hours to understand this simple assumption because Knuth doesn't bother to spend a single word to explain this, not mention that he doesn't give definition of primary-diagonal, reverse-diagonal.) To solve exact cover problem, you can also use "live-vector" technique to solve it as a max-clique problem. However, this matrix is too big and has so many empty places. It is not worthwhile to translate classic problem into such matrix unless you can "reduce" matrix. And this is why he introduces the doubly link structure to "reduce" matrix.

There will be no magic unless you see what Knuth has seen about doubly link structure. I now copy his idea as following:

Let's define L(x) R(x) as pointer to left and right of a node, then R(L(x))=R(x), L(R(x))=L(x) will remove node x from link. However, you can rejoin the node as long as the link is not further damaged by R(L(x))=x, L(R(x))=x

This is a beautiful operation if you are comfortable with pointers.

But I haven't touched the hardcore of N-Queen problem yet. Maybe I should write a demo program...

Sometimes...

Sometimes I feel myself like those invincible heroes who can see through nature with keen eyes. Sometimes I wake up and realize what I see is exactly common senses that every one with average IQ can figure out. However, this is the process of understanding because if this never happens to you it simply means that either you can never learn or you never need to learn.

I try to answer myself the question that why we need majority replies from a group of replicated servers when using "wrapper" technique which maintains a dynamic group view acting as an agent between client and the group of replicated servers. If Byzantine-failure is non-detectable to this wrapper then we can always choose one of any reply from replicates without waiting a consensus of majority. Then I realized during my jogging that this majority is the upper bound of error-correcting mechanism which is exactly like those used in Hamming-code or whatever. We actually take this advantage to tolerate up to maximum Byzantine failure by waiting a consensus from majority of replies from replicates. Crash-failure is benign and easy to be detected by "wrapper" or group manager, but Byzantine failure is "almost only" possible to be sure at application level by differentiate the "traitor" from "patriots". The only suitable timing is at examination of collected replies from replicates. We sacrifice performance a little by waiting redundant number of replies in order to "catch" spies up to a maximum number. Of course a natural operation after spies are spotted is to expel spies out of group. This is not mentioned in slides, but it is an implication.

However another question float up when I am satisfied with my explanation. It is said that there is only one "updator" who multicast his updates to all members of replicates. Then what if this sender fails? This seems to be no solution because when we suspect everyone is a possible "spy" we can trust no one even including ourselves. At least I need one reliable stone to step on.

Another senseless question is that if there is difference between these two kinds of men: One kind is a common man with a common wish to want to look like uncommon. The other kind is an uncommon man with an uncommon wish to want to look like common. (I am joking.)

Sometimes when I feel my mind is as clear as the blue sky and I want to write down what is in my mind. Suddenly clouds cover the sky and I am in chaos.

Sometimes when I feel I am in chaos and I try to write down my puzzle. Suddenly the clouds are wiped away and I am under the sunshine and the blue sky.

So, just write down whatever you think may help.

The Great Mokhov figures out the riddle...

Nick writes:

By the way, I am working to migrate my windows project to Linux and I have a
question about "g++" compiler. You see, I did some "dangerous" type-casting
in windows and the compiler of VC6 gives warning and allow me to do that.
However, it seems GCC is more strict in syntax and simply gives error. Is
there compiler options to relax g++ to not to give error like VC6 compiler?
For example, I am using STL vector and for efficiency purpose I treat
"iterator.begin()" like starting address of array. I know this is not the
purpose of vector, but I check the source of vector and it seems ok to do
that. It works fine also in windows. But now g++ simply gives error in this
type-casting.

Nick writes:

I write a simple test indicating the problem. See the attached source code
file.
Here is the compilation error in "alamanni":
[qingz_hu@alamanni ~/linux] % g++ arrayTest.cpp -o arrayTest.exe
arrayTest.cpp:51:2: warning: no newline at end of file
arrayTest.cpp: In function 'int main()':
arrayTest.cpp:24: error: invalid cast from type
'__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> >
>' to type 'int*'

Mokhov:

Ah, I see. This works:
...
display(&intVector.begin()[0], intVector.size());
...
No wonder I hate C++.

Nick writes:

You are amazing! How do you figure it out? I mean this seems like
meaningless. It reminds me what Dr. Grogono commented some examples of
difference between VC6 and G++ I sent to him a couple of years ago. He said
it was "nuisance".
VC6 basically always works whatever I make changes on any type, say int
array[] or int*array.
And I made it a bit easy reading based on your way like this:
display(&(*intVector.begin()), intVector.size());
Can you give me some clue why it behaviors like this? Thank you in advance.
Thanks so much and I really appreciate your help!!!

And here is the riddle:

    #include <vector>
    #include <cstdio>

    using namespace std;

    typedef vector<int> IntVector;

    void display(IntVector& intVector);

    void display(int array[], int size);

    int main()
    {
    	int arraySize=rand()%100+1;//make it at least one
    	int i;
    	IntVector intVector;
    	for (i=0; i<arraySize; i++)
    	{
    		intVector.push_back(rand()%100);
    	}

    	display(intVector);
    	display(&(*intVector.begin()), intVector.size());

    	return 0;
    }

    void display(IntVector& intVector)
    {
    	printf("display as vector\n");
    	for (int i=0; i<intVector.size(); i++)
    	{
    		printf("%d#%d\n", i, intVector[i]);
    	}
    }

    void display(int array[], int size)
    {
    	printf("display as int array\n");
    	for (int i=0; i<size; i++)
    	{
    		printf("%d#%d\n", i, array[i]);
    	}
    }

    	The Silly Simple Find

    I feel frustrated with the "find" command. In most cases, I can't understand what the man page is talking about. It seems the easiest way

    is just writing my own simple tool. And I find a strange thing in Linux that the command line parameter cannot have string with "*" which

    will confuse the "argc". This is insane!

    <<<<<<<<Actually this is a BUGGY program in linux and you should know that if you are familiar with Linux. There are at least two big

    problems with Linux version. What is it? I will post the correct one tomorrow below and also keep the following buggy one for comparsion.>>>>

    #ifndef LINUX_VERSION

    #include <windows.h>
    #include <stdio.h>

    //assume dir is directory
    void genericFind(char* dir, char* pattern)
    {
    	HANDLE handle;
    	char*src, *tgt;
    	char curFileName[256];
    	char wildFileName[256];

    	WIN32_FIND_DATA ffd;

    	sprintf(wildFileName, "%s\\*.*", dir);
    	handle=FindFirstFile(wildFileName, &ffd);
    	if (handle==INVALID_HANDLE_VALUE)
    	{
    		printf("findfirst failed of error code =%d\n", GetLastError());
    		exit(19);
    	}
    	do
    	{
    		if (strcmp(ffd.cFileName, ".")!=0 && strcmp(ffd.cFileName, "..")!=0)
    		{
    			sprintf(curFileName, "%s\\%s", dir, ffd.cFileName);
    			if  (GetFileAttributes(curFileName)&FILE_ATTRIBUTE_DIRECTORY)
    			{
    				genericFind(curFileName, pattern);
    			}
    			else
    			{
    				src=ffd.cFileName;
    				tgt=pattern;
    				while (*src && *tgt && *src==*tgt)
    				{
    					src++;
    					tgt++;
    				}
    				if (*tgt==0 || *tgt=='*')
    				{
    					printf("find matching %s\n", ffd.cFileName);
    				}
    			}
    		}
    	}
    	while (FindNextFile(handle, &ffd));

    	FindClose(handle);
    }

    #else

    #include <cstdio>
    #include <cstdlib>
    #include <dirent.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <sys/mman.h>

    void genericFind(char* dirName, char* pattern)
    {
    	struct stat buf;
    	char curFileName[256];
    	int nameLen;

    	char* src, *tgt;
    	DIR* dirPtr;
    	struct dirent* direntPtr;
    	printf("begin searching %s...\n", dirName);

    	if ((dirPtr=opendir(dirName))==NULL)
    	{
    		//perror("read dir");
    		//exit(1234);
    		//printf("unable open %s\n", dirName);
    		return;
    	}
    	nameLen=strlen(dirName);
    	strcpy(curFileName, dirName);
    	while ((direntPtr=readdir(dirPtr))!=NULL)
    	{
    		if (strcmp(direntPtr->d_name, ".")!=0&&strcmp(direntPtr->d_name, "..")!=0)
    		{
    			curFileName[nameLen]='/';
    			strcpy(curFileName+nameLen+1, direntPtr->d_name);
    			lstat(curFileName, &buf);

    			if (S_ISREG(buf.st_mode))
    			{
    				src=direntPtr->d_name;
    				tgt=pattern;
    				while (*src && *tgt && *tgt!='*'&& toupper(*src)==toupper(*tgt))
    				{
    					src++;
    					tgt++;
    				}
    				if (*tgt==0 || *tgt=='*')
    				{
    					printf("find matching of %s\n", curFileName);
    				}
    			}
    			else
    			{
    				if (S_ISDIR(buf.st_mode))
    				{
    					genericFind(curFileName, pattern);

    				}
    			}
    		}
    	}
    }

    #endif

    int main(int argc, char** argv)
    {
    	int i;
    	if (argc==3)
    	{
    		genericFind(argv[1], argv[2]);
    	}
    	else
    	{
    		printf("argc=%d error\n", argc);
    		for (i=0; i<argc; i++)
    		{
    			printf("[%d]=%s\n", i, argv[i]);
    		}
    	}

    	return 0;
    }

<<<<<<<<<<<<<<<<<<<<<<<<<<This is the correct version for linux.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Originally I plan to do the "quiet" mode by hide error message options. but NBD(no big deal)

    #define LINUX_VERSION 1

    #ifndef LINUX_VERSION

    #include <windows.h>
    #include <stdio.h>

    //assume dir is directory
    void genericFind(char* dir, char* pattern)
    {
    	HANDLE handle;
    	char*src, *tgt;
    	char curFileName[256];
    	char wildFileName[256];

    	WIN32_FIND_DATA ffd;

    	sprintf(wildFileName, "%s\\*.*", dir);
    	handle=FindFirstFile(wildFileName, &ffd);
    	if (handle==INVALID_HANDLE_VALUE)
    	{
    		printf("findfirst failed of error code =%d\n", GetLastError());
    		exit(19);
    	}
    	do
    	{
    		if (strcmp(ffd.cFileName, ".")!=0 && strcmp(ffd.cFileName, "..")!=0)
    		{
    			sprintf(curFileName, "%s\\%s", dir, ffd.cFileName);
    			if  (GetFileAttributes(curFileName)&FILE_ATTRIBUTE_DIRECTORY)
    			{
    				genericFind(curFileName, pattern);
    			}
    			else
    			{
    				src=ffd.cFileName;
    				tgt=pattern;
    				while (*src && *tgt && *tgt!='*'&& toupper(*src)==toupper(*tgt))
    				{
    					src++;
    					tgt++;
    				}
    				if (*tgt==0 || *tgt=='*')
    				{
    					printf("find matching %s\n", ffd.cFileName);
    				}
    			}
    		}
    	}
    	while (FindNextFile(handle, &ffd));

    	FindClose(handle);
    }

    #else

    #include <cstdio>
    #include <cstdlib>
    #include <dirent.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <sys/mman.h>

    void genericFind(char* dirName, char* pattern)
    {
    	struct stat buf;
    	char curFileName[256];
    	int nameLen;
    	int startPos;

    	char* src, *tgt;
    	DIR* dirPtr;
    	struct dirent* direntPtr;
    	//printf("begin searching %s...\n", dirName);

    	if ((dirPtr=opendir(dirName))==NULL)
    	{
    		perror("read dir");
    		//exit(1234);
    		printf("unable open %s\n", dirName);
    		return;
    	}
    	nameLen=strlen(dirName);
    	strcpy(curFileName, dirName);
    	while ((direntPtr=readdir(dirPtr))!=NULL)
    	{
    		if (strcmp(direntPtr->d_name, ".")!=0&&strcmp(direntPtr->d_name, "..")!=0)
    		{
    			if (nameLen>1)
    			{
    				curFileName[nameLen]='/';
    				startPos=nameLen+1;
    			}
    			else
    			{
    				startPos=1;
    			}
    			strcpy(curFileName+startPos, direntPtr->d_name);
    			lstat(curFileName, &buf);

    			if (S_ISREG(buf.st_mode))
    			{
    				src=direntPtr->d_name;
    				tgt=pattern;
    				while (*src && *tgt && *tgt!='*' && *src==*tgt)
    				{
    					src++;
    					tgt++;
    				}
    				if (*tgt==0 || *tgt=='*')
    				{
    					printf("find matching of %s\n", curFileName);
    				}
    			}
    			else
    			{
    				if (S_ISDIR(buf.st_mode))
    				{
    					genericFind(curFileName, pattern);

    				}
    			}
    		}
    	}
    	closedir(dirPtr);
    }

    #endif

    int main(int argc, char** argv)
    {
    	int i;
    	if (argc==3)
    	{
    		printf("begin search directory %s for pattern %s...\n\n", argv[1], argv[2]);
    		genericFind(argv[1], argv[2]);
    	}
    	else
    	{
    		printf("argc=%d error\n", argc);
    		for (i=0; i<argc; i++)
    		{
    			printf("[%d]=%s\n", i, argv[i]);
    		}
    	}

    	return 0;
    }

Copy or Reference?

This is a small question. (Don't blame me, the original code style is like this.)

here it comes...

    the result:

    <1,2,0> <1,2,0> <1,2,0>
    but I expect:
    <0,0,0><1,0,0><1,2,0>

    import java.util.*;

    public class ArrayListTest {

    public static void main(String[] args){

    ArrayList<int[]> events_da0 = new ArrayList<int[]>();

    int[] eventID_da0={0,0,0};

    events_da0.add(eventID_da0);

    eventID_da0[0]=1;

    events_da0.add(eventID_da0);

    eventID_da0[1]=2;

    events_da0.add(eventID_da0);

    for (int i = 0; i < events_da0.size(); i++){

    int[] event=(int [])events_da0.get(i);

    System.out.print("\t"+"<"+event[0]+","+event[1]+","+event[2]+">");

    }

    System.out.print("\n");

    }

    }

    here it goes...

    It is very simple. Without running your program, I think you are confused with "copy" and "reference" in java. Actually all objects in java are using "reference" which means unless you use "new", you are referring to same object.

    The "eventID_da0" is an object and you add the "reference" of this object three times to your "events_da0". So, you are just printing three times of the same object in final display.

    The correct way is to declare a simple "pointer" without "new" until you are going to add it to your "events_da0 ".

    for example,
    //int[] eventID_da0={0,0,0};

    int[] eventID_da0; //don't initialize

    ...

    eventID_da0=new int[3]; //exact syntax,you can check by yourself, I don't use java for many months.

    eventID_da0[0]=1;

    events_da0.add(eventID_da0);

    ...

    eventID_da0=new int[3]; //exact syntax,you can check by yourself, I don't use java for many months.

    eventID_da0[1]=2;

    events_da0.add(eventID_da0);

    ...

    by doing this, you are actually creating new objects every time and add them into your "list".

    If it is not like this, let me know.