袁峰

面试问题: Rotate a bitmap by 90 degrees

On August 9th, I posted the following problem on community.csdn.net, under VC/MFC 基础类:

Problem: Write code to generate a bitmap rotated 90 degrees clockwise from the original bitmap, without using any graphics library.

If you want to post your code here, write on your own, do not refer to anything else, no copy/paste, write your code here, review your code before submitting, and include how much time you spend. Add comments in English when possible.

I want to see who can give a good enough answer.

There have been lots of responses to this simple programming problem and some quite interesting discussions. Here is the link to the CSDN thread: http://community.csdn.net/Expert/topic/3254/3254627.xml?temp=.7896845

Here is the link to my comments, including my code: http://blog.joycode.com/fyuan/articles/30945.aspx

posted on 2004-08-19 10:12:00 by fyuan  评论(10) 阅读(5773)

程序义诊 第一号 CSV Parser

程序义诊开张几天, 无人问津. 终于邻国 Koye Li 送来了第一笔生意. 感激不尽.

Koye Li's email and program fit perfectly to my submission requirement. The code is quite well written, but I still need to find problems as I promised to. So you can say it's 鸡蛋里挑骨头.

Comments:

1. When dealing with parsing, define the syntax of input data in something like BNF first. Although this case is very simple, there are still places which could generate confusion. The first issue is how to embed '“' within a string. If you do not think about it when designing it, most likely it will not be handled and not tested. The second issue is Europe countries may use comma instead of period in decimal numbers, then the places of command and period may be switched. Also, add syntax description and sample data to the code as comments, to keep it together with source code.
2. infile is an object, not a pointer. So “if (infile)” is either wrong or not needed.
3. There is no allocation failure check for csv = new CsvParser(sep). It will generate access violation unless new throws exception on failure.
4. SplitLine returns number of items parsed. It should be important to the caller.
5. csv is not freed. Memory leak.

#ifndef MY_CSV_PARSER
#define MY_CSV_PARSER
 
#pragma once
#pragma warning(disable:4786) // disable vc STL complains
 
#include <iostream>
using namespace std;
 
#include <vector>
#include <string>
 
#include "stdafx.h"
 
class CsvParser 
{
public:
    CsvParser(string& fieldSep) :
        m_sFieldSep(fieldSep), m_nField(0) {} 
 
    virtual ~CsvParser() {};
 
    int GetNumberOfFields();
 
    string GetField(int n);
 
    int SplitLine(string& str);
 
protected:
 
    ExtractStringField(string& source, string& field, int start_pos);
    ExtractNumericField(string& source, string& field, int istart_pos);
    int Split();
 
    string         m_sLine;
    vector<string> m_vsField;
    string         m_sFieldSep;
    int            m_nField;
};
#endif 

Comments:

1. It looks like other places of your program uses STL too, so put <vector>, <string> and <iostream> into stdafx.h to avoid compiling them multiple times.
2. Normally stdafx.h should be included by every .cpp file, then there is no need to include it in header files.
3. Virtual destructor is not need unless CsvParser has derived classes. The cost of having a virtual destructor is a pointer for each object allocated and a virtual function table.
4. GetNumberOfFields and GetFields can be const function.
5. GetField should return const reference. 
6. SplitLine parameter can be const reference.
7. ExtractStringField and ExtraNumericField, first parameter can be const reference, add something out OUT to second parameter, 3rd number needs to be consistent in name. Both functions should return int, they can all be const function.
8. m_sLine does not need to be member variable as it's always passed to ExtractStringField and ExtraNumericField, as currently designed.

// CSV.cpp: implementation of the CSV class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "CSV.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//
// SplitLine()
//
int CsvParser::SplitLine(string& str)
{
    m_sLine = str;

    // clear old buffer
    m_vsField.erase(m_vsField.begin(), m_vsField.end());

    return Split();
}

//
// CsvParser::GetField(int n)
//
string CsvParser::GetField(int n)
{
    if (n<0 || n > m_vsField.size())
        return "";
    else
        return m_vsField[n];
}

//
// GetNumberOfFields()
//
int CsvParser::GetNumberOfFields()
{
    return m_nField;
}

//
// CsvParser::Split()
//
int CsvParser::Split()
{
    m_nField = 0;

    int line_length = m_sLine.length();
    if (line_length == 0)
        return 0;

    string field;

    int cur_pos = 0;
    int next_pos = 0;
    do {
        // skip spaces
        for (; isspace(m_sLine[cur_pos]); cur_pos++);
        
        if (m_sLine[cur_pos] == '"')  
            next_pos = ExtractStringField(m_sLine, field, cur_pos);
        else
            next_pos = ExtractNumericField(m_sLine, field, cur_pos);

        m_vsField.push_back(field);
        m_nField++;

        cur_pos = next_pos + 1; // skip current ',' and start looking for the next

    } while (cur_pos < line_length);

    return m_nField;

}

int CsvParser::ExtractStringField(string& source, string& field, int start_pos)
{
    field = "";

    int cur_pos = 0;
    int line_length = source.length();
        
    start_pos++;   // skip first '"'

    // find next '"'
    cur_pos = source.find_first_of("\"", start_pos);
    if (cur_pos < 0 )
    {
        cur_pos = line_length;
    }

    field = string(source, start_pos, cur_pos-start_pos);

    // find next ','
    cur_pos = source.find_first_of(m_sFieldSep, cur_pos);
    if (cur_pos < 0 )
    {
        cur_pos = line_length;
    }
            
    return cur_pos;
}


int CsvParser::ExtractNumericField(string& source, string& field, int start_pos)
{
    field = "";

    int cur_pos = 0;
    int line_length = source.length();
    
    // find first ','
    cur_pos = source.find_first_of(m_sFieldSep, start_pos);
    if (cur_pos < 0 )
    {
        cur_pos = line_length;
    }
    
    field = string(source, start_pos, cur_pos-start_pos);

    return cur_pos;
}   

Comments:

1. GetField method, the out of bound condition should be (n < 0 || (n >= m_vsField.Size()). Add a debug assert to out of bound case to catch possible bugs in caller's code.
2. Split method, field and next_pos can be moved inside the loop.
3. Split mehod, what is a field is neither string field nor numeric field?
4. ExtractStringField method, file = ““ is not needed.
5. Embedding '“' within string is not supported. Document it.
6. Anything after a string and before a seperator is skipped. If this is intended, document it.
7. find next ',' does not match code which fields the next seperator.
8. What if m_sFieldSep is null, or not single character?
9. ExtractNumericField, source.length is calcualted first, but only used when cur_pos is less than 0.
10. The routines does not really find numeric numbers, it just returns anything before the next seperator.
11. source.length is calculated multiple times. It may be worthwhile to store it as member variable and do not pass m_sLine to two extraction functions.

Thanks Koye Li for sharing the code.

posted on 2004-04-07 14:07:00 by fyuan  评论(24) 阅读(6072)

程序义诊 开业告示

Write programs is easy, write good, production quality code is hard. Two years ago, I gave my son, then 12, a C++ programming text book. He started to type in "#include ... main() ..." after a while. He can certain programs, but you would not expect him to write good code.

It's like playing Weiqi(Go). It's so easy to put stones on the grids. Total amature and professional may put stones are the same place from time to time. But the amount of thinking and the degree of certainty is totally different between the two.

At Microsoft, every line of production code gets reviewed by an often more experienced engineer before check-in. Any one can comments on other people's code, raise issues and report defects. Every one learns during this process, which improves product quality and make people better programmers.

If you're not shy, show me your code. I would see how your code can be improved. If you want to submit your code for reviewing, please notice the following:

1) Sumbit your own code, not other people's code, your company's copyrighted material or trade secrets.

2) Submit code which has some data structure design or algorithm inside, not just calling some API to achieve some thing simple.

3) Submit code which is not too small and not too large either, 100-200 lines will be ideal. Do not use large resource files. Submit in a .zip file.

4) Use Visual C/C++ or C# as programming language. Include all original files, not files generation by compiler.

5) Add comments to your code to explain what it does and how it works. No black magic.

6) Submit by commenting on this posting and include link to your project, or send email to fyuan at fengyuan dot com.

7) I may not be able to review all submissions because of time, domain knowledge, complexity, or duplication.

8) Once I post my comments here, everyone can add comments.

Remember the goal is learning as a community.

posted on 2004-04-03 17:01:00 by fyuan  评论(45) 阅读(4517)