Blog of Meng Yan

Interesting topic, right? One of my friends encounter this problem when he’s applying software engineer position in a company.

Suppose we have only stack available

Stack* stack_init();
void push(Stack*, int);
int pop(Stack*);
void stack_free();

Please implement the following interface of queue

Queue* queue_init();
void inq(Queue*, int);
int outq(Queue*);
void queue_free();

Any idea, buddy? Here come 3 solutions:

1) By Winters Mi

So, it’s a O(N) solution.

2) By Green Wang

If the operation of the queue is consecutive "in" or "out", it’s O(1); Or else O(n). This algorithm overcomes the shortcoming of the first one. Because if the operation is consecutive, we don’t need to reverse the stack back.

3) By Changzheng Liu

Changzheng got these code from Google. . It’s really good. The idea is very simple, 2 stacks, one for in and one for out. For the "in" operation, just push all into the stack_in. For the "out" operation, if stack_out is empty, reverse the stack_in to stack_out, or else just pop the value.

So for "in" operation O(1); for "out" operation, if stack_out is empty, it’s O(n), else O(1).

More entries about : Algorithm, Stack, Queue, Interview

A useful tip to share with you.

I need to read the file from the current directory (same directory with the main jar file). In my code, I just use "new File("test")", and it works quite well.

But in my colleague’s machine, it throws the FileNotFound exception. Oh, we I saw the exception in his screen, I know that it’s a careless fault.
The problem is I accessed files in a given
location without an absolute path prefix.

In my case:

cd /home/elan/test/
java -jar test.jar

So, the current working directory is "/home/elan/test/", and we can access the file by a relative path.

My colleague’s case:

cd /usr/java/bin
java -jar /home/elan/test/test.jar

The working directory is "/usr/java/bin", and no "test" existed in this folder.

Ok, then how to get the current directory?

As we know, System.getProperty("user.dir") will get the working directory and System.getProperty("user.home") will get the home directory ("/home/elan/" for linux and "$:/document and settings/elan/" for windows case), but I cannot get any clue to get the current directory which contains my jar file and the "test" file.

I have thought that I can get this kind of code in "java.io" or "runtime" classes, but
I cannot find any clue. So, how about get the location of the jar file since it’s the file that in this directory. After a while, I got the answer:

getClass().getProtectionDomain().getCodeSource().getLocation()

It will return the class code base’s location, and in my case, the jar file’s location. So I just need to get the parent path of this location. The problem solved.

BTW:

1) You’d better pack the file into the jar and use the classloader to read it;

2) Or you can use the home directory ( System.getProperty("user.home") )

3) In my case, for some special reason, I must do this.

More entries about : Java

These days, I have investigated the Netbeans RCP(Rich Client Platform), and developed some module on it. Netbeans is not only the Java IDE, Netbeans.org has provided netbeans platform as an application runtime for build rich desktop application, just like eclipse platform. The “plugin” here is called “Module”. Every module is a “nbm” file that could be loaded by their module class loader. The module’s information is stored in the manifest file in the Module file.

The netbeans platform has been developed since 1999 when NetBeans 3.0 was rewriten, and the latest version is 4.0. With it, developer could focus on the business logic and NetBeans platform will provide ways to handle module management, UI management, preference management and etc. and it provides rich APIs to help the developer to do customization. see more at http://www.netbeans.org/products/platform.

Like Eclipse, there’s also the extension concept in Netbeans Module Runtime, moreover it is based on a J2SE standard for extension registration - META-INF/services. You can checkout the detail information from here. And NetBeans Service registry is also based on J2SE standard extension mechanism (http://java.sun.com/j2se/1.4.2/docs/guide/jar/jar.html#Service%20Provider).

Netbeans’s Module runtime support dynamic module register/unregister/update feature (deploy the module on the fly), which are not supported in Eclipse 2.1(But have already been supported by Eclipse 3.0 using OSGi standard). And Netbeans RCP provide the module update center to help the developer to manage the modules.

After the release of Netbeans 4.0, most of the IDE related things have already been striped out from netbeans platform, and the core size of netbeans platform core has been downsized.

Netbeans has a long history, the story is very interesting, also, there’s many applications that already take the advantage of Netbean RCP, you can check out detail information here.

Currently, there’s no module development enviroment in netbeans, so the module development work is a little hard, and the beginning learn curve is a little higher. Hope we will get the “MDE”(so called ) in the later version. here’s the road map of Netbeans.

Then, how to develop a module using netbeans platform? From my experience, it’s not so hard.

I have ever developed a little tool called MP3 Renamer before. Because I have many music files in my laptop, but many of them are called “1.mp3″ , “music.mp3″. I build this little tool to parse the tag information from the mp3 files and rename the file name to “Author — Songname.mp3″.

I decide to change the stand alone application to a netbeans module to test the Netbeans RCP. Here I’d like to share my experience with you.

1) What we needed

• JDK 1.4.2 or above (http://java.sun.com)
• Netbeans RCP (http://www.netbeans.info/downloads/download.php?a=b&p=2), you can download the binary version or even the source to build one, all up to you.
• Apache Ant (http://ant.apache.org/)

2) Install the Netbeans RCP

After unzip the netbeans zip file to a directory (”/home/elan/netbeans” in my case), make a user preference directory such as “elan” in the netbeans directory. Then, type “/home/elan/netbeans/platform4/lib/nbexec –userdir /home/elan/elan to test if it works. If it works, congratulations, we have already installed the netbeans RCP and can build our own module base on it.

3) Create MP3 Renamer Module

First, we should build the module working enviroment. Here’s the structure of the Mp3 renamer dir:

Source files are all put into “src” and third party library files are put into “lib” directory.

After that, we need to edit the manifest file (”manifest.mf”). The content of mine is :

The layer file (”com/vvworkshop/shareware/mp3rename/resources/layer.xml“) describe the extension point and the Bundle file (”com/vvworkshop/shareware/mp3rename/Bundle.properties“) store the localized string of our module.

You can modify the file according to your case.

Ok, let’s take a look at the layer file:

It extends the netbeans system menu and will insert our own one into the “View” sub menu. The Action that the menu connected with is “com.vvworkshop.shareware.mp3rename.Mp3RenamerAction”. Let’s take a look at the source file of this action.

The most important functions are “performAction” and “getName“. Function “getName” will return the menu name, and function “performAction” will provide the real action when the user click the menu. And in the Bundle.properties file, there’s one line “SLC_title=MP3 Renamer” , so, the menu name will be called”Mp3 Renamer”. “performAction” provides the action, in my case, in this function the MP3 Renamer main panel will dock into the netbeans panel.

Another important file is “build.xml”, we can use Ant to compile, archive, and build “nbm” file. The file is a little long, I’d like to abstract some important slice from my ant script:

Some property

How to archive the jar file

besides the archive work, we also need to create the module xml file. And in order to build it, we also need a jar file named as “nbantext.jar”, it can be acquired from the NetBeans IDE binary.

How to create the “nbm” file

You can just copy this target to your build file and change the propertiy value.

4) Test the Module

So far, after build the nbm file, we can test our module. First, you should use the netbeans update center (”Tools”->”Update Center”->”Install Manually Downloaded Modules”) to install the new module.

After install the module, you could click the “View” menu, we can see a sub menu named “Mp3 renamer”, after click it, the Mp3 Renamer panel will popup. So, you can see, the netbeans module development is easy, and with the help of module development enviroment in the future version, the development work will be easier. Here, I cannot give you too much detail information because it will be too long, if you are interested in it, you can send email to me and ask for the demo source file.

Enjoy~

More entries about : Netbeans, RCP, Framework, Plugin

Today, my friend ask me to review some code of him, his code will encounter some unexpected error. He’s very confused and worried. After digging into the code, I found the problem.

Here’s the code slice :

private boolean done;
private Message[] messages;
... ...
synchronized(this) {
if(!done || messages ==null) {
	//	1
	try {
		wait();
		//    2
	} catch (InterruptedException e) {
		e.printStackTrace();
	}

	...

	dispatchMessage(messages);

	//    3

	...
}

dispatchMessage(Message[] messages) {
	int length = messages.length;

	//    4

	... ...

	messages = null;
}

When the program run, it will throw NullPointerException sometimes, though very infrequent. And just because of its infrequence, it’s hard to debug. But when go through this code slice, I think Java Expert can learn where’s the problem.
Try to imagine such scenario:

1) messages is null

2) Thread 1 check the condition in position 1 and waiting in position 2, and it will release the lock, So other thread can obtain it;

3) Thread 2 check the condition in position 1 and waiting in position 2 too;

4) When we get the message and notify all threads using notifyAll(), both thread 1 and thread 2 will be awaked but only one thread will obtain the lock.

5) Assume thread 1 will get the lock, and it will dispatch the message using dispatchMessage. after dispatching the message, it unreference the messages.

6) When thread 1 finished dispatching the message and release the lock. Thread 2 will obtain the lock, however, NOW, messages is null, so it will throw NPE.

Then, how to solve the problem? Yeah, it should use spin lock here. So, it will re-check the condition after being awaked and will avoid such problem.
That is, it should be

while(!done || message ==null)
... ...

And this trick is called spin lock(reference1) , you can see detail discussion in this book (practice 54).
BTW: You also can find this trick in “Effective Java”, in item 50 - “Never use wait out of loop”. And, this two book is really good and worth reading.

Reference:

1) “Pratical Java” - Peter Haggar

2) “Effective Java” - Joshua Bloch

More entries about : Java

These days, one of the Chinese Portal - Sina’s knowledge base search engine IAsk debut.

I am really interested in this new launched program. Their rules is very simple and straight forward. People can raise any kind of question here, and give some mark to that question to award the person who give the right(or appropriate) answers. Other people will try to solve the question and get the award. People who raised the question will give the mark according to the reply. Of course, the higher mark the people give, the more exposure the question will have. In China, there’s many website who provided such kind of service before, but none of them combined it with a powerful search engine.

Now, more and more people are interested in the “game”. And I often try to get what I wanna to know from it, when I encounter some problem, I even directly goto iAsk but not Google .

So, is it another search engine? Absolutely yes. Nowadays, there’s more and more search engines, but how to get the knowledge is the most important thing I think. Google will crawler billions of web pages, but are all of these pages useful? I don’t think so. I don’t think we must give user as many as result they searched, but should give them what they really want. I think user’s experience and knowledge is more valuable than these web pages. 80% people will care the same thing about one specfic question. For example, when talking about the word “mortagage”, you and I maybe will has the same puzzle and will raise the similar question. And my experience maybe is just what you wanna to know. Without question, if more and more users take part in his program and contribute their wisdom and experience, the knowledge base will be more and more rich and valuable and this search engine will be more and more clear and can will give the user what they wanna to know.

So I think, in this .search period (related to .com) , how to attract the user, collecting their data and experience is the most important. Contrast to the search technique, the knowledge base is more important.

To summarize, I think what we can learn from iAsk is:

1) Use award mark to attract user to take part in and contribute their knowledge;

2) Combine the user knowledge base with the powerful search engine.

Just my cents.

More entries about : IAsk, Search, Sina

These days, when I’m reading some other guy’s code, I encounter some problem. In these code, I can read following codes:

Look, it use “==” but not “equals” here. “Oh, it must be a bug!”, I told myself. But, wait, when I excuted the program, it worked quite well. And till this moment, I remembered, current powerful JVM will maintain a constant pool for String, so maybe two “OK” will reference the same place. So, such mechanism will work.

But, does Java Language Specification has such standard? and all JVM will follow this standard? I continue to dig into it.

First, I found such item in JLS 3.10.5 — String literals.

Abstract some points here:

Literal strings within the same class ($8) in the same package ($7) represent references to the same String object ($4.3.1).
Literal strings within different classes in the same package represent references to the same String object.
Literal strings within different classes in different packages likewise represent references to the same String object.
Strings computed by constant expressions ($15.28) are computed at compile time and then treated as if they were literals.
Strings computed at run time are newly created and therefore distinct.
The result of explicitly interning a computed string is the same string as any pre-existing literal string with the same contents.

So, this is the feature of String class, every JVM should follow. And, when I read the code of String.java, I found such comments in method “intern“.

public String intern()
Returns a canonical representation for the string object.
A pool of strings, initially empty, is maintained privately by the class String.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~So good:-)

When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
It follows that for any two strings s and t, s.intern() == t.intern() is true if and only if s.equals(t) is true.
All literal strings and string-valued constant expressions are interned. String literals are defined in $3.10.5 of the Java Language Specification.

It’s quite clear about the case I encountered. Then I understand, this is not a bug, but the trick . But, why he use “==” but not “equals“, I think that will be more clear and more easy to read, I think there must be other guys to be puzzled as me .

I think the author must care more about the performance than the code, the performance of “==” sure if better than “equals“, especially when the String is long~.

Ok, everything clear now, and sure, not only String has such pool. For example:

what will System.out.println(i==l) output? I think you can get the right answer.

Update (2005.11.09):

"String"’s method "equalsIgnoreCase" also take advantage of this string pool:

If the two string point the same one, simply return true.

So, if you need to compare Strings frequently, you should "Intern" them.

For example, in Lucene’s source code, you need to compare the Field name very often, so, they intern the field name.

More entries about : Java, Performance