Friday, October 24, 2008

google c++ coding style

 

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Header_File_Dependencies#Header_File_Dependencies

Header File Dependencies

How can we use a class Foo in a header file without access to its definition?

  • We can declare data members of type Foo* or Foo&.
  • We can declare (but not define) functions with arguments, and/or return values, of type Foo.
  • We can declare static data members of type Foo. This is because static data members are defined outside the class definition.

On the other hand, you must include the header file for Foo if your class subclasses Foo or has a data member of type Foo.

Inline Functions

A decent rule of thumb is to not inline a function if it is more than 10 lines long. Beware of destructors, which are often longer than they appear because of implicit member- and base-destructor calls!

Another useful rule of thumb: it's typically not cost effective to inline functions with loops or switch statements (unless, in the common case, the loop or switch statement is never executed).

Function Parameter Ordering

When defining a function, parameter order is: inputs, then output

Parameters to C/C++ functions are either input to the function, output from the function, or both. Input parameters are usually values or const references, while output and input/output parameters will be non-const pointers. When ordering function parameters, put all input-only parameters before any output parameters. In particular, do not add new parameters to the end of the function just because they are new; place new input-only parameters before the output parameters.

Local Variables

There is one caveat: if the variable is an object, its constructor is invoked every time it enters scope and is created, and its destructor is invoked every time it goes out of scope.

// Inefficient implementation:
for (int i = 0; i < 1000000; ++i) {
Foo f; // My ctor and dtor get called 1000000 times each.
f.DoSomething(i);
}

It may be more efficient to declare such a variable used in a loop outside that loop:

Foo f;  // My ctor and dtor get called once each.
for (int i = 0; i < 1000000; ++i) {
f.DoSomething(i);
}

Doing Work in Constructors

Do only trivial initialization in a constructor. If at all possible, use an Init() method for non-trivial initialization.

Decision: If your object requires non-trivial initialization, consider having an explicit Init() method and/or adding a member flag that indicates whether the object was successfully initialized.

Explicit Constructors

Use the C++ keyword explicit for constructors with one argument.

Definition: Normally, if a constructor takes one argument, it can be used as a conversion. For instance, if you define Foo::Foo(string name) and then pass a string to a function that expects a Foo, the constructor will be called to convert the string into a Foo and will pass the Foo to your function for you. This can be convenient but is also a source of trouble when things get converted and new objects created without you meaning them to. Declaring a constructor explicit prevents it from being invoked implicitly as a conversion.

Pros: Avoids undesirable conversions.

Cons: None.

Decision:

We require all single argument constructors to be explicit. Always put explicit in front of one-argument constructors in the class definition: explicit Foo(string name);

The exception is copy constructors, which, in the rare cases when we allow them, should probably not be explicit. Classes that are intended to be transparent wrappers around other classes are also exceptions. Such exceptions should be clearly marked with comments.

Copy Constructors

Consider adding dummy declarations for the copy constructor and assignment operator in the class' private: section, without providing definitions. With these dummy routines marked private, a compilation error will be raised if other code attempts to use them. For convenience, a DISALLOW_COPY_AND_ASSIGN macro can be used:

// A macro to disallow the copy constructor and operator= functions
// This should be used in the private: declarations for a class
#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
TypeName(const TypeName&); \
void operator=(const TypeName&)Then, in class Foo:

class Foo {
public:
Foo(int f);
~Foo();

private:
DISALLOW_COPY_AND_ASSIGN(Foo);
};

Structs vs. Classes

Use a struct only for passive objects that carry data; everything else is a class.

Declaration Order

Your class definition should start with its public: section, followed by its protected: section and then its private: section. If any of these sections are empty, omit them.

Within each section, the declarations generally should be in the following order:


  • Typedefs and Enums
  • Constants
  • Constructors
  • Destructor
  • Methods, including static methods
  • Data Members, including static data members

The DISALLOW_COPY_AND_ASSIGN macro invocation should be at the end of the private: section. It should be the last thing in the class.


Reference Arguments

All parameters passed by reference must be labeled const.

Within function parameter lists all references must be const:

void Foo(const string &in, string *out);

In fact it is a very strong convention that input arguments are values or const references while output arguments are pointers. Input parameters may be const pointers, but we never allow non-const reference parameters.

Casting

Use C++ casts like static_cast<>(). Do not use other cast formats like int y = (int)x; or int y = int(x);.

Do not use C-style casts. Instead, use these C++-style casts.


  • Use static_cast as the equivalent of a C-style cast that does value conversion, or when you need to explicitly up-cast a pointer from a class to its superclass.
  • Use const_cast to remove the const qualifier (see const).
  • Use reinterpret_cast to do unsafe conversions of pointer types to and from integer and other pointer types. Use this only if you know what you are doing and you understand the aliasing issues.
  • Do not use dynamic_cast except in test code. If you need to know type information at runtime in this way outside of a unittest, you probably have a design flaw.

sizeof

Use sizeof(varname) instead of sizeof(type) whenever possible.


Use sizeof(varname) because it will update appropriately if the type of the variable changes. sizeof(type) may make sense in some cases, but should generally be avoided because it can fall out of sync if the variable's type changes.

Struct data;
memset(&data, 0, sizeof(data));
memset(&data, 0, sizeof(Struct));

File Comments

Every file should contain the following items, in order:


  • a copyright statement (for example, Copyright 2008 Google Inc.)
  • a license boilerplate. Choose the appropriate boilerplate for the license used by the project (for example, Apache 2.0, BSD, LGPL, GPL)
  • an author line to identify the original author of the file

File Contents

Every file should have a comment at the top, below the and author line, that describes the contents of the file.

Generally a .h file will describe the classes that are declared in the file with an overview of what they are for and how they are used. A .cc file should contain more information about implementation details or discussions of tricky algorithms. If you feel the implementation details or a discussion of the algorithms would be useful for someone reading the .h, feel free to put it there instead, but mention in the .cc that the documentation is in the .h file.

Do not duplicate comments in both the .h and the .cc. Duplicated comments diverge.

Every class definition should have an accompanying comment that describes what it is for and how it should be used.

// Iterates over the contents of a GargantuanTable.  Sample usage:
// GargantuanTable_Iterator* iter = table->NewIterator();
// for (iter->Seek("foo"); !iter->done(); iter->Next()) {
// process(iter->key(), iter->value());
// }
// delete iter;
class GargantuanTable_Iterator {
...
};

Function Comments

Declaration comments describe use of the function; comments at the definition of a function describe operation.

Function Declarations

Every function declaration should have comments immediately preceding it that describe what the function does and how to use it. These comments should be descriptive ("Opens the file") rather than imperative ("Open the file"); the comment describes the function, it does not tell the function what to do. In general, these comments do not describe how the function performs its task. Instead, that should be left to comments in the function definition.

Types of things to mention in comments at the function declaration:


  • What the inputs and outputs are.
  • For class member functions: whether the object remembers reference arguments beyond the duration of the method call, and whether it will free them or not.
  • If the function allocates memory that the caller must free.
  • Whether any of the arguments can be NULL.
  • If there are any performance implications of how a function is used.
  • If the function is re-entrant. What are its synchronization assumptions?

Here is an example:

// Returns an iterator for this table.  It is the client's
// responsibility to delete the iterator when it is done with it,
// and it must not use the iterator once the GargantuanTable object
// on which the iterator was created has been deleted.
//
// The iterator is initially positioned at the beginning of the table.
//
// This method is equivalent to:
// Iterator* iter = table->NewIterator();
// iter->Seek("");
// return iter;
// If you are going to immediately seek to another place in the
// returned iterator, it will be faster to use NewIterator()
// and avoid the extra seek.
Iterator* GetIterator() const;

Thursday, October 23, 2008

random programs

摘几个programming pearls 上提到的random function.

1. knuth version. 从1-n之间生成有序的m个不同的随机数( the output is a sorted list of m random integers in the range 0...n-1 in which no integer occurs more than once).

void genknuth(int m, int n) {
for (int i = 0; i < n; ++i) {
/* select m of remaining n-i */
if ((bigrand() % (n-i)) < m) {
cout << i << "\n";
--m;
}
}
}

2. shuffle the first m elements of the array. output the sorted list of the m random numbers.

void genshuf(int m, int n) {
int i, j;
int *x = new int[n];
for(i = 0; i < n; ++i)
x[i] = i;
for(i = 0; i < m; ++i) {
j = randint(i, n-1);
int t = x[i]; x[i] = x[j]; x[j] = t;
}
sort(x, x+m);
for(i = 0; i < m; ++i)
cout << x[i] << "\n";
}

3. floyd. This algorithm uses only m random numbers, even in the worst case.

void genfloyd(int m, int n) {
set<int> S;
set<int>::iterator i;
for(int j = n-m; j < n; ++j) {
int t = bigrand() % (j+1);
if(S.find(t) == S.end())
S.insert(t); // t not in S
else
S.insert(j); // t in S
}
for(i = S.begin(); i != S.end(); ++i)
cout << *i << "\n";
}

4. reservoir sampling. when we do not know the length of the data ( we see the data sequentially. )


We always select the first line, we select the second line with probability one half, the third line with probability one third, and so on. At the end of the process, each line has the same probability of being chosen (1/n, where n is the total number of lines in the article).

Sunday, October 19, 2008

counting sort + bit operation

UVa problem: Bridge Hands

每一花色牌不超过13张,4种花色,用一个long long表示,每16位一组表示一个花色

#include <stdio.h>
#include <string.h>

long long player[4];
int p[90];
char ip[4] = {'C', 'D', 'S', 'H'};
int seat[90];
char iseat[4] = {'S','W','N','E'};
int idx[90];
char inverse_idx[15] = {'0','1','2','3','4','5','6','7','8','9','T','J','Q','K','A'};
//int __builtin_ctz(long long);
int main() {
char buff[60];
seat['S'] = p['C'] = 0;
seat['W'] = p['D'] = 1;
seat['N'] = p['S'] = 2;
seat['E'] = p['H'] = 3;
int i, j;
for(i = 2; i <= 9; ++i)
idx[i+48] = i;
idx['T'] = 10;
idx['J'] = 11;
idx['Q'] = 12;
idx['K'] = 13;
idx['A'] = 14;
char t;
while((t = getchar()) != '#') {
while(gets(buff) && strlen(buff)==0){};
int side = seat[t];
memset(player, 0, sizeof(player));
for(i = 0; i < 52; i += 2) {
if(++side == 4) side = 0;
/* get card, set its bit */
player[side] |= 1LL<< (p[buff[i]]<<4LL) + idx[buff[i+1]];
}
gets(buff);
for(i = 0; i < 52; i += 2) {
if(++side == 4) side = 0;
player[side] |= 1LL<< (p[buff[i]]<<4LL) + idx[buff[i+1]];
}

for(i = 0; i < 4; ++i) {
int printed = 0;
printf("%c: ", iseat[i]);
for(j = 0; j < 4; ++j) {
/* get current color */
int c = player[i] & 0xffff;
player[i] >>= 16; /* next color */
while(c) {
int pos = __builtin_ctz(c);
c ^= 1LL << pos; /* clear printed bit */
printf("%c%c", ip[j], inverse_idx[pos]);
if(++printed < 13) printf(" ");
}
}
printf("\n");
}
}
}
/* gcc has built in __builtin_ctz, vc not*/ 
/*
int __builtin_ctz(long long c) {

for(int i = 0; i < 64; ++i)
if(c & (1LL<<i)) return i;
}*/

Maximum interval sum

Or maximum contiguous subvector of the input.

Do a linear sweep from left to right, accumulate the sum. Start new interval whenever you encounter partial sum < 0.

/* 1-d linear alg O(n) */
inline int mis1d(int line[], int size) {
int maxv = -INF;
int p = 0;
for(int i = 0; i < size; ++i) {
p += line[i];
if(p < 0) p = 0;
if(p > maxv) maxv = p;
}
return maxv;
}
In a 2D problem, we are expected to find a maximum sum subrectangle in a mxn matrix. 


  • We first calculate the accumulative sum in the dimension of length m (smaller dim).

  • We then use the above technique in the dimension of length n.

  • The total running time is O(m^2 n). (for nxn matrix, that is O(n^3) )
UVa problem: 108, 836

#include <iostream>
using namespace std;

#define INF 999999999
int M[101][101];
int partialSum[101][101];
int line[101];

/* 1-d linear alg O(n) */
inline int mis1d(int line[], int size) {
int maxv = -INF;
int p = 0;
for(int i = 0; i < size; ++i) {
p += line[i];
if(p < 0) p = 0;
if(p > maxv) maxv = p;
}
return maxv;
}

/* 2-D O(n^3) */
int mis2d(int size) {
int maxv = -INF;
for(int j = 0; j < size; ++j) {
partialSum[0][j] = M[0][j];
for (int i = 1; i < size; i++)
partialSum[i][j] = partialSum[i-1][j] + M[i][j];
}
for(int i = 0; i < size; ++i) { // use from the i-th row
for(int j = i; j < size; ++j) { // to the j-th row
if(i == j)
memcpy(line, M[i], size*sizeof(int));
else {
// generate the data i to j-th row
for(int k = 0; k < size; ++k)
line[k] = partialSum[j][k] - partialSum[i][k];
}
int v = mis1d(line, size);
if(v > maxv) maxv = v;
}
}
return maxv;
}

int main() {
int n;
while(scanf("%d ", &n) == 1) {
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", &M[i][j]);
printf("%d\n", mis2d(n));
}
}
Related problems:


  • find the subvector with the sum closest to zeros


    • calc the accumulative sum so that cum[i] = x[0] + ... + x[i]

    • The subvector x[l ... u] sums to zeros if cum[l-1] = cum[u]

    • the subvector with the sum closest to zeros is found by locating the two closest elements in cum

    • which can be done in O(nlogn) by sorting

  • find the subvector with the sum closest to a given real number t.


    • a simple extension from the above case

    • The subvector x[l ... u] sums to t if cum[l-1] + t = cum[u] and l-1<u

    • first nlogn sorting

    • then for each element, do a (log n) binary search for closest to (cum[i]+t)
 

initialize upon the first use

This is a technique coverd in Programming Pearls.  (Chap 1, Problems 9)

This method use constant time for initialization and for each vector access, and use extra space proportional to the size of the vector. Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is deer and the vector is sparse.

My test code here ( #define COL   to enable 2-D matrix test case)

#include <iostream>
#include <ctime>
using namespace std;

// max row and col size
#define ROW 8000
// if 1-d, just comment the next line
#define COL 8000
int top = 0;

#ifndef COL
int data[ROW];
#define MAXE ROW
#else
int data[ROW][COL];
#define MAXE ROW*COL
#endif

// two additional array to implement a simple signature
int from[MAXE];
int to[MAXE];

// if element i in the array is initialised
inline bool exist(int i, int j=0) {
#ifdef COL
int idx = COL*i+j;
#else
int idx = i;
#endif
if(from[idx] < top && to[from[idx]] == idx)
return true;
return false;
}

// assign data value to the i-th element
#ifndef COL
inline void setdata(int i, int v) {
if(!exist(i)) {
from[i] = top;
to[top] = i;
++ top;
}
data[i] = v;
}

#else
inline void setdata(int i, int j, int v) {
if(!exist(i, j)) {
int idx = COL*i+j;
from[idx] = top;
to[top] = idx;
++ top;
}
data[i][j] = v;
}
#endif

int main(int argc, char* argv[]) {
int startt = clock();
printf("initialize at start time--\n");
memset(data, 0, sizeof(data));

int n;
if(argc < 2 || atoi(argv[1]) > ROW) n = 100;
else n = atoi(argv[1]);

#ifndef COL
for(int i = 0; i < n; ++i)
data[i] = (i*i-i)/(i+1);
int starts = clock();
printf("use %d\n", starts-startt);

printf("no initialization--\n");
for(int i = 0; i < n; i++)
setdata(i, (i*i-i)/(i+1));
printf("use %d\n", clock()-starts);

#else
for(int i = 0; i < n; i++)
for(int j = 0; j < n; ++j)
data[i][j] = (i*j-i)/(i+1);

int starts = clock();
printf("use %d\n", starts-startt);

printf("no initialization--\n");
for(int i = 0; i < n; i++)
for(int j = 0; j < n; ++j)
setdata(i, j, (i*j-i)/(i+1));

printf("use %d\n", clock()-starts);
#endif
}
From the test result: 

  • When the operations overhead is much less than the initialization cost, use init upon the first use.
  • When the vector/matrix is not sparse (e.g., > 10% full), memset is fast enough.
  • It seems the access speed of alg2 is 10 times slower than direct access speed
    +------------+----------+-----------+----------+
    |matrix dim |# op |alg 1 (ms) |alg 2 (ms)|
    |8000 x 8000 |10 x 10 |312 |0 |
    |8000 x 8000 |100x100 |312 |0 |
    |8000 x 8000 |1000x1000 |328 |187 |
    |8000 x 8000 |4000x4000 |531 |2922 |
    +------------+----------+-----------+----------+
  • Saturday, October 18, 2008

    bit operation again SRM 422


    topcder: BirthdayCake

    用gcc的__builtin_popcount()速度快了两倍多。

    由于cake 那个是50位的,用了long long,然后调用__builtin_popcount两次分别处理高低32位然后求和。注意给常数1加上LL后缀。

    // couting 1's
    inline int count_bit(long long n) {
    return __builtin_popcount(n>>32) + __builtin_popcount(n &((1LL<<32)-1LL));
    }
    void checkmax(int &a, int b) {
    if(a < b) a = b;
    }

    int BirthdayCake::howManyFriends(vector <string> availableFruits, vector <string> f, int K) {

    int N = availableFruits.size(); // total number of available fruit
    int m = f.size(); // friend number
    map<string,int> fruit;
    for(int i = 0; i < N; ++i)
    fruit.insert(make_pair(availableFruits[i], fruit.size()));

    long long mask = (1LL<<N)-1LL;
    vector<long long> like(m, mask);
    for(int i = 0; i < m; ++i) {
    stringstream ss;
    ss << f[i];
    string tmp;
    while(ss >> tmp) {
    if(!fruit.count(tmp)) continue;
    like[i] &= ~(1LL<< fruit[tmp]); // clear uliked bits
    }
    }
    int max = (1<<(m))-1; // all friends included

    int maxnf = 0; // max number of friends included
    // brute force traversal of all subsets
    for(int i = max; i >=0 ; --i) {
    long long cake = mask;
    for(int j = 0; j < m; ++j) if( i & (1<<j) ) {
    cake &= like[j];
    if( count_bit(cake) < K )
    goto next;
    }
    checkmax(maxnf, count_bit(i));
    next: continue;
    }
    return maxnf;
    }

    Friday, October 17, 2008

    closest pair problem

    Closest pair of points problem on wiki

    nearest neighbor problem

    k-d tree on wiki

    Sweeping: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPair1D.htmlimageimage

    every time the sweep line encounters a point p, we will perform the following actions:

    1. Remove the points further than d to the left of p from the ordered set D that is storing the points in the strip.  
    2. Determine the point on the left of p that is closest to it
    3. If the distance between this point and p is less than d (the current minimum distance), then update the closest current pair and d.

    The summary and analysis of the plane sweep algorithm goes something like this:

    • sort the set according to x-coordinates (this is necessary for a plane sweep approach to determine the coordinates of the next point), which takes O(nlogn) time
    • inserting and removing each point once from the ordered set D (each insertion takes O(logn) time as shown in the section on (2,4)-trees), which takes a total of O(nlogn) time
    • comparing each point to a constant number of its neighbors (which takes O(n) time in total )

    K-D Tree

    Animation: http://donar.umiacs.umd.edu/quadtree/points/kdtree.html

    Complexity

    • Building a static kd-tree from n points takes O(n log 2 n) time if an O(n log n) sort is used to compute the median at each level. The complexity is O(n log n) if a linear median-finding algorithm such as the one described in Cormen et al[3] is used.
    • Inserting a new point into a balanced kd-tree takes O(log n) time.
    • Removing a point from a balanced kd-tree takes O(log n) time.
    • Querying an axis-parallel range in a balanced kd-tree takes O(n1-1/d +k) time, where k is the number of the reported points, and d the dimension of the kd-tree.
    • Finding the nearest point is an O(log N) operation.

    Bit operations hacks

    I find a few more interesting sites:

    Bit Twiddling Hacks

    The Aggregate Magic Algorithms

    Thursday, October 16, 2008

    Design Patterns (4) - Factory method and Abstract Factory

     Factory methodimage
    Define an interface for creating an object, but let subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclasses.

     

    Why would anybody use such a design pattern?

    Imagine you are writing the code for the “Client” object. The “client” object needs to use the “Product” object. You hard code the object creation process in the “Client” Now any changes in the object creation procedure would mean that you need to change the “client” too. The sole purpose of the “Factory” object is to create “Product” This gives us a certain amount of flexibility. The “client” delegates that task to “Factory”. Any changes in the object creation process do not affect the “client” and changes to “Factory” should be fairly simple as that is the only thing it does.

    ref: http://vorleakchy.wordpress.com/2008/08/15/factory-method-design-pattern/

    Principles:

    No variable should hold a reference to  a concrete class. If you use new, you' ll be holding a reference to a concrete class. Use a factory to get around that!

    No class should derive from a concrete class. If you derive from a concret class, you're depending on a concrete class. Derive from an abstraction, like an interface or an abstract class.

    No method should override an implemented method of any its base class.  If you override an implemented method, then your base class wasn't really an abstraction to start with. Those methods implemented in the base class are meant to be shared by all your subclasses.image

    My simple factory method example:

    //Pizza example:

    #include <string>
    #include <iostream>
    class Pizza {
    public:
    virtual void get_price() = 0;
    };

    class HamAndMushroomPizza: public Pizza {
    public:
    virtual void get_price(){
    std::cout << "Ham and Mushroom: $8.5" << std::endl;
    }
    };

    class DeluxePizza : public Pizza {
    public:
    virtual void get_price() {
    std::cout << "Deluxe: $10.5" << std::endl;
    }
    };

    class SeafoodPizza : public Pizza {
    public:
    virtual void get_price(){
    std::cout << "Seafood: $11.5" << std::endl;
    }
    };

    class PizzaFactory {
    public:
    static Pizza* create_pizza(const std::string type) {
    if (type == "Ham and Mushroom")
    return new HamAndMushroomPizza();
    else if (type == "Seafood Pizza")
    return new SeafoodPizza();
    else
    return new DeluxePizza();
    }
    };
    //usage
    int main() {
    PizzaFactory factory;
    Pizza *pz = factory.create_pizza("Default");
    pz->get_price();

    Pizza *ph = factory.create_pizza("Ham and Mushroom");
    ph->get_price();

    delete pz;
    pz = factory.create_pizza("Seafood Pizza");

    pz->get_price();
    delete pz;
    delete ph;
    }

    Design Patterns (3) - Decorator

    Decorator: Attach additional responsibilities to an object dynamically keeping the same interface. Decorators provide a flexible alternative to subclassing for extending functionality.

    image

    The idea:

    • Start with a basic component and "decorate" it with condiments at runtime.
    • Decorators have the same supertype as the objects they decorate.
    • Given that the decorator has the same supertype as the object it decorates, we can pass around a decorated object in place of the original object.
    • The decorator adds its own behavior either before and/or after delegating to the object it decorates to do the rest of the job.
    • Objects can be decorated at any time, so we can decorate objects dynamically at runtime with as many decorators as we like.

     

     

    image

    Design Patterns (2) - Observer

    Observer :image

    Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.

    Design principles of Observer ( from head first Design Pattern Chap 2)

    1. The thing that varies in the Observer Pattern is the state of the Subject and the number and types of Observers. With this pattern, you can vary the objects that are dependent on the state of the Subject, without having to change that Subject. That's called planning ahead!
    2. Both the Subject and Observer use interfaces. the subject keeps track of objects implementing the Observer interface, while the observers register with, and get notified by the Subject interface. As we've seen, this keeps things nice and loosely coupled.
    3. The Observer Pattern uses composition to compose any number of Observers with their Subjects. These relationships aren't set up by some kind of inheritance hierarchy. No, they are set up at runtime by composition!

    wiki's c++ example shows an implementation of head first's chap 2 problem. It is a nice example.

    Just refer to it for deep understanding of the pattern.

    Design Patterns (1) - Strategy

    book reference:

    1. Gang-of-four: Design Patterns
    2. Head first design patterns

    resource reference:

    1. wiki - design pattern
    2. source-making
    3. http://www.dofactory.com/Patterns/Patterns.aspx
    4. http://blog.cumps.be/design-patterns-strategy-pattern/
    5. http://www.patterndepot.com/put/8/JavaPatterns.htm
    6. http://www.codeguru.com/forum/showthread.php?t=327982

    Strategy Pattern:

    Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.

    • The Context has-a behavior of Strategy, which can be implemented with different algorithms.
    • We define a private member in Context: a pointer to the general superclass Strategy.
    • We have a set_strategy method in Context class to change behavior at runtime.
    • We also have a superclass: Strategy and a bunch of subclass : ConcreteStrategy to implement the behavior.
    • In client code, we have one or multiple instances of Context.
    • At any given time, only one ConcreteStrategy is availabe to be executed a single Context object.

    Strategy Pattern example:   

    #include <iostream>
    image
    using namespace std;

    class StrategyInterface
    {
    public:
    virtual void execute() = 0;
    };

    class ConcreteStrategyA: public StrategyInterface
    {
    public:
    virtual void execute()
    {
    cout << "Called ConcreteStrategyA execute method" << endl;
    }
    };

    class ConcreteStrategyB: public StrategyInterface
    {
    public:
    virtual void execute()
    {
    cout << "Called ConcreteStrategyB execute method" << endl;
    }
    };

    class ConcreteStrategyC: public StrategyInterface
    {
    public:
    virtual void execute()
    {
    cout << "Called ConcreteStrategyC execute method" << endl;
    }
    };

    class Context
    {
    private:
    StrategyInterface *_strategy;

    public:
    Context(StrategyInterface *strategy):_strategy(strategy)
    {
    }
    void set_strategy(StrategyInterface *strategy)
    {
    _strategy = strategy;
    }
    void execute()
    {
    _strategy->execute();
    }
    };

    int main(int argc, char *argv[])
    {
    ConcreteStrategyA concreteStrategyA;
    ConcreteStrategyB concreteStrategyB;
    ConcreteStrategyC concreteStrategyC;

    Context contextA(&concreteStrategyA);
    Context contextB(&concreteStrategyB);
    Context contextC(&concreteStrategyC);

    contextA.execute();
    contextB.execute();
    contextC.execute();

    contextA.set_strategy(&concreteStrategyB);
    contextA.execute();

    return 0;
    }

    Tuesday, October 14, 2008

    interprocess communication IPC (2) - shared memory

    I use the IPC-shared memory to help solve UVa problem 495: fib freeze.
    The same algorithm is ranked 3rd ! 
    The idea is as follows:


    • the main process fork a child to precompute the Fib numbers up to 5000.

    • the main process at the same time read in all input n!

    • as soon as the child finish, main process begin table-lookup and output

    • the shared memory is a char [][], each char[] contains a factorial for the corresponding n

    • i use semaphore (here actually act as a mutex) to synchronize the shared memory access


      • the child process get resource and release until it finishes computing 5000!

      • the main process then access the resource to lookup the result
    The program flow:


    1. shmget: to request a shared memory block from the system

    2. shmat: to link the pointer to the shared memory

    3. semget: to create a semaphore (IPC_CREAT)

    4. semctl: to initialize the semaphore (SET_VAL)

    5. fork: to generate a child process

    6. semop: to use semaphore to maintain the resource access

    7. semctl: to remove semaphore ( IPC_RMID)

    8. shmdt: to detatch the pointer from the shared memory

    9. shmctl: to delete the shared memory ( IPC_RMID)

    shmget很容易出错,如果是异常退出,可能需要更换key,重新run, (考虑用ipcrm -m #shmid kill)


    最大可分配的memory及相关的参数可在man shmget中找到


    e.g., /proc/sys/kernal/shmmax  maximum memory

    #include <stdio.h>
    #include <unistd.h>
    #include <vector>
    #include <sys/shm.h>
    #include <errno.h>
    #include <sys/types.h>
    #include <sys/ipc.h>
    #include <sys/sem.h>
    #include "BigInt.h"
    #define MAXSZ  5000

    struct databuf {
    char memo [MAXSZ+1][1050];
    };

    int main(int argc, char *argv[])
    {
    key_t key = 0x18845;
    int shmid;
    int semid;
    int mode;

    /* make the key: */
    /*
    if ((key = ftok("plotter.c", 'R')) == -1) {
    perror("ftok");
    exit(1);
    }*/


    /* connect to (and possibly create) the segment: */
    if ((shmid = shmget(key, sizeof(databuf), 0600 |IPC_CREAT)) == -1) {
    printf("shmid %d %d\n", shmid,errno);
    perror("shmget");
    switch(errno) {
    case EACCES:
    printf("access permit\n");break;
    case EEXIST:
    printf("segment exist\n"); break;
    case EINVAL:
    printf("einval\n");break;
    case ENFILE:
    printf("enfile\n");break;
    case ENOENT:
    printf("enoent\n");break;
    case ENOMEM:
    printf("no memory\n");break;
    case ENOSPC:
    printf("enospc\n");break;
    case EPERM:
    printf("eperm\n");break;
    default:
    printf("other\n");break;
    }

    exit(1);
    }
    /* attach to the segment to get a pointer to it: */
    databuf* data = (databuf*)shmat(shmid, (void *)0, 0);

    if (data == (databuf *)(-1)) {
    perror("shmat");
    exit(1);
    }
    //memset(data, 0, sizeof(data));

    struct sembuf P = {0, -1, 0}; /* set to allocate resource */
    struct sembuf V = {0, 1, 0}; /* free resource */

    /*
    if ((key = ftok("fibfreeze.c", 'J')) == -1) {
    perror("ftok");
    exit(1);
    }*/


    /* create a semaphore set with 1 semaphore: */
    if ((semid = semget(0x99543, 1, 0666 | IPC_CREAT)) == -1) {
    perror("semget");
    exit(1);
    }
    //printf("sem id %d\n", semid);

    /* initialize semaphore #0 to 1: */
    if (semctl(semid, 0, SETVAL, 1) == -1) {
    perror("semctl");
    exit(1);
    }

    pid_t kid = fork();
    if(kid == 0) {
    //printf("kid process \n");
    //kid process, computer fib number up to 5000
    BigInt a1(0), a2(1), a;
    semop(semid, &P, 1);
    strcpy(data->memo[0], "0");
    strcpy(data->memo[1], "1");

    for(int i = 2; i <= MAXSZ; ++i){
    a = a1 + a2;
    strcpy(data->memo[i], a.toString().c_str());
    //printf("calc m[%d]=%s\n", i, data->memo[i] );
    //printf("calc %d, len %d\n", i, strlen(data->memo[i]));
    a1 = a2;
    a2 = a;
    }
    semop(semid, &V, 1);
    exit(0);
    } else {
    //printf("parent process\n");
    std::vector<int> n;
    int tmp;

    while(scanf("%d ", &tmp) != EOF)
    n.push_back(tmp);

    //wait();
    semop(semid, &P, 1);
    int N = n.size();
    for(int i = 0; i < N; ++i)
    printf("The Fibonacci number for %d is %s\n", n[i], data->memo[n[i]]);
    semop(semid, &V, 1);
    }

    /* remove semaphore */
    if (semctl(semid, 0, IPC_RMID, 0) == -1) {
    perror("semctl");
    exit(1);
    }
    //printf("free semaphores done\n");

    /* detach from the segment: */
    if (shmdt(data) == -1) {
    perror("shmdt");
    exit(1);
    }
    /* remove shared memory */
    if (shmctl(shmid, IPC_RMID, 0) == -1) {
    perror("shmctl shmid");
    exit(1);
    }
    //printf("free memory segment done\n");
    return 0;
    }

    interprocess communication IPC (1) - message queue

    Beej's Guide
    Advanced Linux Programming

    IPC methods:
    • Signal
    • Pipe
    • Named Pipe
    • Message Queue
    • Shared Memory
    Message Queue:

    /* use ftok(...) to generate a key */
    /* key_t ftok(const char* path, int id) */

    key_t key = ftok("/home/someone/somefile", 'b');

    /* create or connect to an existing queue */
    /* int msgget(key_t key, int msgflg) */
    /* 666 -> rw-rw-rw- */
    int msqid = msgget(key, 0666|IPC_CREAT);

    /* each message is made up of two parts */
    /* mtype is set to any positive number as a message type */
    /* mdata is any data struct that will be added to the queue */
    struct pirate_msgbuf {
    long mtype; /* must be positive */
    char name[30];
    char ship_type;
    int notoriety;
    int cruelty;
    int booty_value;
    };

    /* pass the message to the queue */
    /* int msgsnd(int msqid, const void *msgp, size_t msgsz, int msgflg);
    struct pirate_msgbuf pmb = {2, "L'Olonais", 'S', 80, 10, 12035};
    msgsnd(msqid, &pmb, sizeof(pmb), 0);

    /* retrieve message from the queue */
    struct pirate_msgbuf pmrecv;
    /* int msgrcv(int msqid, void *msgp, size_t msgsz, long msgtyp, int msgflg); */
    msgrcv(msqid, &pmrecv, sizeof(pmb), 2, 0);

    /* destroy a message queue */
    msgctl(msqid, IPC_RMID, NULL);


    beej's guide provides a pair of nice example source
    kirk.c spock.c
    start kirk and spock, you can send text through kirk and receive them through spock.
    Also you can try to add mtype to enable multiple kirks and spocks.

    Here is a little piece of code of my test:
    I am using fork() to create a kid process to read characters from stdin,
    then using the parent process to simulate running a simple algorithm based on the message read by kid.

    /* interprocess communication: Message Queue */

    #include < stdio.h >
    #include < stdlib.h >
    #include < ctype.h >
    #include < sys/ipc.h >
    #include < sys/msg.h >
    #include < unistd.h >
    #include < time.h >

    const int ARR_SIZE = 8;


    struct mymsgbuf{
    long mtype; // a positive integer:
    int a[ARR_SIZE];
    };

    int main(int argc, char* argv[]) {

    int N = 0;
    if(argc < 2)
    N = 100;
    else
    N = atoi(argv[1]);

    printf("number of computations = %d\n", N*N);

    key_t key = ftok("ab.", 'm');
    int msgq_id; // message queue id

    //initializes a new message queue
    if((msgq_id = msgget(key, IPC_CREAT|0660)) == -1) {
    printf("msgget error\n");
    exit(1);
    } else {
    printf("msg queue id %d created\n", msgq_id);
    }

    if(fork() == 0) {
    printf("this is child process\n");
    mymsgbuf qbuf;
    qbuf.mtype = 1;

    int j = 0;
    while(!feof(stdin)) {
    for(int i = 0; i < ARR_SIZE; ++i) {
    scanf("%d ", &qbuf.a[i]);
    }
    if((msgsnd(msgq_id, &qbuf, sizeof(mymsgbuf)-sizeof(long), 0)) == -1) {
    printf("error in msgsnd\n");
    exit(1);
    }
    ++j;
    }
    // the last message
    // use mtype = 2 to notify the parent process
    qbuf.mtype = 2;
    msgsnd(msgq_id, &qbuf, sizeof(mymsgbuf)-sizeof(long),0);
    printf("send %d\n", j);
    return 0;
    } else { // in parent process
    printf("this is parent process\n");
    mymsgbuf qbuf;
    int j = 0;
    while(msgrcv(msgq_id, &qbuf, 200, 0, 0)) {
    if(qbuf.mtype == 2) break;

    int total = 0;
    int t = N;

    /* just doing some work */
    while(t--) {
    for(int i = 0; i < ARR_SIZE; ++i)
    for(int k = 0; k < ARR_SIZE; ++k)
    total += qbuf.a[i] * qbuf.a[k];
    }
    ++j;
    }
    wait(); // wait until the child process finish
    printf("recv %d\n", j);
    msgctl(msgq_id, IPC_RMID, 0); // delete the message queue
    printf("msg q removed\n");
    }

    // printf("time taken %d\n", clock()-startt);
    return 0;
    }

    running output:time ./msgq 100 < tmp
    number of computations = 10000
    msg queue id 557057 created
    this is child process
    this is parent process
    send 39036
    recv 39036
    msg q removed

    real 0m1.452s
    user 0m1.384s
    sys 0m0.064s

    Monday, October 13, 2008

    C++ notes

    From Wikipedia, the free encyclopedia

    Sunday, October 12, 2008

    numeric_limits

    #include <iostream>
    #include <limits>

    using namespace std;
    int main() {

    cout << "max(short): " << numeric_limits<short>::max() << endl;
    cout << "max(int): " << numeric_limits<int>::max() << endl;
    cout << "max(long long): " << numeric_limits<long long>::max() << endl;
    cout << "max(unsigned long long): " << numeric_limits<unsigned long long>::max() << endl;

    cout << "max(double): " << numeric_limits<double>::max() << endl;

    return 0;
    }
    output:

    max(short): 32767
    max(int):   2147483647
    max(long long):  9223372036854775807
    max(unsigned long long):  18446744073709551615
    max(double):  1.79769e+308

    C++ FAQ Lite

    http://www.parashift.com/c++-faq-lite/

    [18] Const correctness

    Constness means using the keyword const to prevent const objects from getting mutated. Declaring the const-ness of a parameter is just another form of type safety.

    For example, if you wanted to create a function f() that accepted a std::string, plus you want to promise callers not to change the caller's std::string that gets passed to f(), you can have f() receive its std::string parameter...

    • void f1(const std::string& s);     // Pass by reference-to-const
    • void f2(const std::string* sptr);  // Pass by pointer-to-const
    • void f3(std::string s);            // Pass by value

    You have to read pointer declarations right-to-left.

    • const Fred* p means "p points to a Fred that is const" — that is, the Fred object can't be changed via p.
    • Fred* const p means "p is a const pointer to a Fred" — that is, you can change the Fred object via p, but you can't change the pointer p itself.
    • const Fred* const p means "p is a const pointer to a const Fred" — that is, you can't change the pointer p itself, nor can you change the Fred object via p.
    "const member function" inspects (rather than mutates) its object.
    "const-overloading"

    class Fred { ... };
    class MyFredList {
    public:
       const Fred& operator[] (unsigned index) const; 
    subscript operators often come in pairs
       Fred&       operator[] (unsigned index);       
    subscript operators often come in pairs
          ...
    };

    Friday, October 10, 2008

    POSIX Thread

    A nice posix thread tutorial.
    Also google a pdf pthread tutorial by Peter Chapin.

    Here I am trying to do a very trivial UVa problem: 11172 Relational Operators using multi-threading.
    But UVa compiler does not do g++ -pthread. We just play here instead of submission. :)
    Two threads:
    1. the first thread read fron stdin
    2. the second thread compare the two numbers and output
    3. both thread access the two buffers using semaphore to synchronize

    #include <stdio.h>
    #include <stdlib.h>
    #include <pthread.h>
    #include <sys/ipc.h>
    #include <sys/sem.h>
    #include <sys/types.h>
    #include <errno.h>

    struct MYDATA{
    int a;
    int b;
    };

    MYDATA data[2];

    struct sembuf p1 = {0, -1, 0}; // request buf 0
    struct sembuf p2 = {1, -1, 0}; // request buf 1
    struct sembuf v1 = {0, 1, 0}; // release buf 0
    struct sembuf v2 = {1, 1, 0}; // release buf 1

    int ndata;
    int semid;


    void* read(void*) {
    int c = ndata;
    while(1) {
    scanf("%d %d ", &data[0].a, &data[0].b);
    //printf("read %d %d, c %d \n", data[0].a, data[0].b, c);
    if(c-- == 0) break;
    semop(semid, &v1, 1);

    semop(semid, &p2, 1);
    scanf("%d %d ", &data[1].a, &data[1].b);
    //printf("read %d %d, c %d \n", data[1].a, data[1].b, c);
    if(c--==0) break;
    semop(semid, &v2, 1);
    semop(semid, &p1, 1);
    }
    //printf("read thread end\n");
    pthread_exit((void*)0);
    }

    inline void cmp(int a, int b) {
    if(a > b) printf(">\n");
    else if(a < b) printf("<\n");
    else printf("=\n");
    }

    void* compare(void*) {
    int c = ndata;
    while(1) {
    //semop(semid, &p2, 1);
    //printf("compare %d %d \n", data[1].a, data[1].b);
    cmp(data[1].a, data[1].b);
    if(c-- == 0) break;
    semop(semid, &v2, 1);

    semop(semid, &p1, 1);
    //printf("compare %d %d \n", data[0].a, data[0].b);
    cmp(data[0].a, data[0].b);
    if(c--==0) break;
    semop(semid, &v1, 1);
    semop(semid, &p2, 1);
    }
    pthread_exit((void*)0);
    }

    int main() {
    pthread_attr_t attr;

    /* create threads */
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

    scanf("%d ", &ndata);
    scanf("%d %d ", &data[1].a, &data[1].b);
    ndata --;

    if((semid = semget(0x3332, 2, 0600 |IPC_CREAT)) == -1) {
    perror("semget");
    exit(1);
    }

    if(semctl(semid, 0, SETVAL, 0) == -1) {
    perror("semctl");
    exit(1);
    }

    if(semctl(semid, 1, SETVAL, 0) == -1) {
    perror("semctl");
    exit(1);
    }

    pthread_t readThd, compareThd;
    pthread_create(&readThd, &attr, read, (void*)0);
    pthread_create(&compareThd, &attr, compare, (void*)0);


    void * status;
    pthread_join(readThd, &status);
    pthread_join(compareThd, &status);

    pthread_exit(NULL);
    }

    The IPC shared memory version is as follows:
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <sys/shm.h>
    #include <errno.h>
    #include <sys/types.h>
    #include <sys/ipc.h>
    #include <sys/sem.h>


    struct databuf {
    int a1;
    int b1;
    int a2;
    int b2;
    };

    inline void cmp(int a, int b) {
    if(a > b) printf(">\n");
    else if(a < b) printf("<\n");
    else printf("=\n");
    }

    int main(int argc, char *argv[])
    {
    key_t key = 0x18875;
    int shmid;
    int semid;
    int mode;

    /* make the key: */
    /*
    if ((key = ftok("plotter.c", 'R')) == -1) {
    perror("ftok");
    exit(1);
    }*/


    /* connect to (and possibly create) the segment: */
    if ((shmid = shmget(key, sizeof(databuf), 0600 |IPC_CREAT)) == -1) {
    perror("shmget");
    exit(1);
    }
    /* attach to the segment to get a pointer to it: */
    databuf* data = (databuf*)shmat(shmid, (void *)0, 0);

    if (data == (databuf *)(-1)) {
    perror("shmat");
    exit(1);
    }
    //memset(data, 0, sizeof(data));

    struct sembuf p1 = {0, -1, 0}; /* set to allocate resource */
    struct sembuf p2 = {1, -1, 0};
    struct sembuf v1 = {0, 1, 0}; /* free resource */
    struct sembuf v2 = {1, 1, 0};

    /*
    if ((key = ftok("fibfreeze.c", 'J')) == -1) {
    perror("ftok");
    exit(1);
    }*/


    /* create a semaphore set with 1 semaphore: */
    if ((semid = semget(0x1543, 2, 0666 | IPC_CREAT)) == -1) {
    perror("semget");
    exit(1);
    }
    //printf("sem id %d\n", semid);

    /* initialize semaphore #0 to 1: */
    if (semctl(semid, 0, SETVAL, 0) == -1) {
    perror("semctl");
    exit(1);
    }
    if (semctl(semid, 1, SETVAL, 0) == -1) {
    perror("semctl");
    exit(1);
    }

    int ndata;
    scanf("%d ", &ndata);
    scanf("%d %d ", &(data->a2), &(data->b2));

    pid_t kid = fork();
    if(kid == 0) {
    while(1) {
    if(feof(stdin)) {
    semop(semid, &v1, 1);
    break;
    }
    scanf("%d %d ", &data->a1, &data->b1);
    //printf("read %d %d \n", data->a1, data->b1);

    semop(semid, &v1, 1);
    semop(semid, &p2, 1);
    if(feof(stdin)) {
    semop(semid, &v2, 1);
    break;
    }
    scanf("%d %d ", &data->a2, &data->b2);
    //printf("read %d %d \n", data->a2, data->b2);

    semop(semid, &v2, 1);
    semop(semid, &p1, 1);
    }
    //printf("kid exit\n");
    exit(0);
    } else {
    int c = ndata;
    while(1) {
    //printf("cmp %d %d, c %d\n", data->a2, data->b2, c);
    cmp(data->a2, data->b2);
    if(--c ==0) break;
    semop(semid, &v2, 1);
    semop(semid, &p1, 1);

    //printf("cmp %d %d, c %d\n", data->a1, data->b1, c);
    cmp(data->a1, data->b1);
    if(--c ==0) break;
    semop(semid, &v1, 1);
    semop(semid, &p2, 1);
    }
    }

    /* remove semaphore */
    if (semctl(semid, 0, IPC_RMID, 0) == -1) {
    perror("semctl");
    exit(1);
    }
    //printf("free semaphores done\n");

    /* detach from the segment: */
    if (shmdt(data) == -1) {
    perror("shmdt");
    exit(1);
    }
    /* remove shared memory */
    if (shmctl(shmid, IPC_RMID, 0) == -1) {
    perror("shmctl shmid");
    exit(1);
    }
    //printf("free memory segment done\n");
    return 0;
    }

    RPN and evaluation tree

    First, here is a very good article on "An expression evaluator" with source code. It also gives detailed introduction on RPN (Reverse Polish Notation).
    Here is the algorithm to parse in RPN's manner:


    for each char of the expression
    decide if the char is part of an operand or of an operator
    if the char is part of an operand,
    append it to the list of operands
    else if the char is part of an operator,
    look up the operator
    match it with supported operators
    compare operator with the preceding operators
    if this operator is prevalent,
    store the operator in a stack
    otherwise, unstack the preceding operator,
    append the preceding operator to the list of operands
    stack the new operator
    end if
    end if
    end for

    Wiki's article on RPN.

    For example: an math expression: 9+8x5-20^3

    list 1 (operand) | list 2 (operator)
    9 |
    9 | +
    9 8 | +
    9 8 | + x ( x has precedence over +, so just append x)
    9 8 5 | + x
    9 8 5 x | + - ( x has precedence over -, so remove x, append x to operand list, then append - to operator list)
    9 8 5 x 20 | + -
    9 8 5 x 20 | + - ^ (of course, ^ has precedence over -, just append ^ on operator list)
    9 8 5 x 20 3 | + - ^
    9 8 5 x 20 3 ^ | + - (now start from the tail, remove all elements from operator list and append then to the operand list one by one)
    9 8 5 x 20 3 ^ - | +
    9 8 5 x 20 3 ^ - + |

    RPN parsing done!

    Calculation starts from the left, push elements onto calc stack.
    Whenever you get one operator, do the calculation immediately. push the result onto the stack.

    Calculation stack | comment
    9 |
    9 8 5 x | 8 x 5 = 40
    9 40 |
    9 40 20 |
    9 40 20 3 |
    9 40 20 3 ^ | 20 ^ 3 = 8000
    9 40 8000 |
    9 40 8000 - | 40 - 8000 = -7960
    9 -7960 |
    9 -7960 + | 9 + (-7960) = -7951
    -7951

    done! so 9+8x5-20^3 = -7951


    Problem UVa 288: Arithmetic Operations With Large Integers

    I used BigInt library from shygypsy.com
    Just modified the operator ^ to support "repeated squaring".
    i.e.,

    BigInt BigInt::operator^ (BigInt n){

    BigInt result = 1;
    BigInt base = *this;
    while(n > 0) {
    if(n % 2 == 1) {
    result *= base;
    }
    base *= base;
    n /= 2;
    }

    return result;
    }

    // operator precedence
    // + - 2+3-4-5+4, use left -> right
    // 2*3*4*5, use left->right
    // 6^7^8^9, use right->left
    bool precedence(int z1, int z2) {
    if(z1 == -10) return true;
    if(z2 == -10) return false;

    if(z1 == z2) return false;
    if(z1 == -5) return true;
    if(z2 == -5) return false;
    return false;
    }

    char buff[35000];
    int main() {
    while(gets(buff) && !feof(stdin)) {
    string b(buff);
    // since op is positive, we use
    // - negative integer to represent operator,
    // - positive integer to represent operand

    // so we define
    // ** = ^ = -10
    // * = -5
    // + = -1
    // - = -2

    deque number;
    deque op;
    int pos = 0;
    for(int i = 0; i < b.size(); ++i) {
    if(b[i]>='0' && b[i]<='9') continue;

    // append previous numbers
    number.push_back(BigInt(b.substr(pos, i-pos).c_str()));

    int v;
    // power has highest priority
    if(b[i]=='*' && b[i+1] == '*') {
    v = -10;
    ++i;
    } else {
    if(b[i] == '*') v = -5;
    else if(b[i] == '+') v = -1;

    else if(b[i] == '-') v = -2;

    if(!op.empty() && !precedence(v, op.back())) {
    number.push_back(BigInt(op.back()));
    op.pop_back();
    }
    }

    op.push_back(v);
    pos = i + 1;
    }
    // append the last number
    number.push_back(BigInt(b.substr(pos).c_str()));

    while(!op.empty()) {
    number.push_back(BigInt(op.back()));
    op.pop_back();
    }

    /*
    deque tmp(number);
    while(!tmp.empty()){
    cout << tmp.front()<< " ";
    tmp.pop_front();
    }
    printf("\n");*/

    // parse into reverse polish format
    stack calc;
    while(!number.empty()) {
    BigInt t = number.front();
    number.pop_front();

    // t is an operator
    if( t < 0) {
    BigInt right = calc.top(); calc.pop();
    BigInt left = calc.top(); calc.pop();
    BigInt res;
    if(t == -1) res = left+right;
    else if(t == -2) res = left-right;
    else if(t == -5) res = left*right;
    else res = left^right;

    calc.push(res);
    } else {
    calc.push(t);
    }
    }
    cout << calc.top()<< endl;
    }
    return 0;
    }

    Thursday, October 09, 2008

    Tree Recovery

    Problem UVa: 536 - Tree Recovery

    给了pre-order 和 in-order traversal 序列,要求输出post-order

    The idea behind the code below is this:
    1) The root is first element of the pre-order traversal
    2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
    3) The children of the current root are the first elements of the sub-pre-order-traversals.
    4) recurse and put the numbers of the children in an array
    5) recurse in post-order traversal through the new tree

    /* 536 - Tree Recovery */
    /* recursion */

    #include <iostream>
    char preorder[30];
    char inorder[30];

    void recover(int x1, int y1, int x2, int y2) {

    char t = preorder[x1];
    if(x1 == y1) {
    printf("%c", t);
    return;
    }

    // locate the root position in in-order
    // which split the travel seq into two halves
    int pos;
    for(int i = x2; i <= y2; ++i)
    if(inorder[i] == t) {
    pos = i;
    break;
    }

    int p = x1+pos-x2;
        // visit left sub-tree
    if(pos-1 >= x2)
    recover(x1+1, p , x2, pos-1);
    // visit right sub-tree
    if(y2 >= pos+1)
    recover(p+1, y1, pos+1, y2);

    // postorder -> print root at last
    printf("%c", t);
    }
    int main() {

    while(scanf("%s %s ",preorder, inorder) != EOF) {
    int L = strlen(preorder) - 1;
    recover(0, L, 0, L); // first <0,L> is preorder index, second <0,L> is in-order index
    printf("\n");
    }
    }
    Problem UVa: 10410 Tree Reconstruction
    给了BFS和DFS traversal序列,要输出每个节点和它相应的叶子结点