perl tutorial

http://www.scs.leeds.ac.uk/Perl/start.html

difference between html and xhtml

http://raventools.com/blog/whats-the-difference-between-html-and-xhtml/

So, XHTML is a new version of HTML that is valid XML code. There’s not a huge difference between XHTML and HTML. The biggest thing is that all your tags must have a matching closing tag. For example, you know that when you create a link the opening has a matching . But what about the
tag? You don’t write
some text
do you? But according to the rules of XML, each tag has to have a matching closing tag. So, in XHTML you now have to write your
tags like
. That’s called a “self-closing” tag.

In addition to requiring every tag to have a closing tag (or be self-closing), they also got rid of some old tags and attributes that had been replaced by CSS. For example, the tag is no longer allowed. And the width attributes in tags, like , is gone, too. There are too many little changes like this to name here, but I think that should give you an idea.

XPath tutorial

http://www.w3schools.com/xpath/xpath_nodes.asp

terminology:

Nodes/Atomic values/parent/children/siblings/Ancestors/Descendants

http://www.w3schools.com/xpath/xpath_syntax.asp

examples:

http://www.w3schools.com/xpath/xpath_examples.asp

Using XMLHttpRequest to load XML documents is supported in all modern browsers.

var xmlhttp=new XMLHttpRequest()

IE: xmlDoc.selectNodes(xpath);

other browsers:xmlDoc.evaluate(xpath, xmlDoc, null, XPathResult.ANY_TYPE,null);

xpath = /bookstore/book/title Select all the titles

/bookstore/book[1]/title select the first book title

/bookstore/book[price>35]/title

Java and DOM

http://www.roseindia.net/xml/dom/

this link has great java examples.

SAX vs DOM

http://geekexplains.blogspot.com/2009/04/sax-dom-jaxp-jdom-evolution-of-java-xml.html

the difference
http://geekexplains.blogspot.com/2009/04/sax-vs-dom-differences-between-dom-and.html

--
SAX v/s DOM

Main differences between SAX and DOM, which are the two most popular APIs for processing XML documents in Java, are:-
Read v/s Read/Write: SAX can be used only for reading XML documents and not for the manipulation of the underlying XML data whereas DOM can be used for both read and write of the data in an XML document.
Sequential Access v/s Random Access: SAX can be used only for a sequential processing of an XML document whereas DOM can be used for a random processing of XML docs. So what to do if you want a random access to the underlying XML data while using SAX? You got to store and manage that information so that you can retrieve it when you need.
Call back v/s Tree: SAX uses call back mechanism and uses event-streams to read chunks of XML data into the memory in a sequential manner whereas DOM uses a tree representation of the underlying XML document and facilitates random access/manipulation of the underlying XML data.
XML-Dev mailing list v/s W3C: SAX was developed by the XML-Dev mailing list whereas DOM was developed by W3C (World Wide Web Consortium).
Information Set: SAX doesn't retain all the info of the underlying XML document such as comments whereas DOM retains almost all the info. New versions of SAX are trying to extend their coverage of information.

Shapes of CSS

http://css-tricks.com/examples/ShapesOfCSS/

Jquery for absolute beginners

http://net.tutsplus.com/articles/web-roundups/jquery-for-absolute-beginners-video-series/

great videos.

Doctype

http://www.w3schools.com/tags/tag_doctype.asp

JavaScript basics

http://www.w3schools.com/js/js_loop_for_in.asp

var person={fname:"John",lname:"Doe",age:25};

for (x in person)
{
document.write(person[x] + " ");
}

－－
JavaScript is Case Sensitive

－－
You can break up a code line within a text string with a backslash. The example below will be displayed properly:

document.write("Hello \
World!");

--
try--catch--throw

--

interview questions

1.draw architect design of the project you worked on.
2. SQL;
employee, dept
find departid which has duplicate employee name

SELECT name, departid  COUNT(name) AS NumOccurrences FROM employee GROUP BY name,departid HAVING ( COUNT(name) > 1 )

find the person who has the highest salary in one dept

select name

where salary = (select max(salary)

from employee

group by departid )

from employee
3. List
sort the list
(calling Collection.sort)
4.tapestry design
5.java jdbc calls what is the common mistakes
6. http protocol
7. WAR config
8. webservices structure

(ST)

create or update a view

http://www.w3schools.com/sql/sql_view.asp

CREATE OR REPLACE VIEW view_name AS
SELECT column_name(s)
FROM table_name
WHERE condition

java memory leak

what are Java memory leaks? If a program holds a reference to a heap chunk that is not used during the rest of its life, it is considered a memory leak because the memory could have been freed and reused.

http://www.ibm.com/developerworks/rational/library/05/0816_GuptaPalanki/

java 1.5 vs 1.4

1. autoboxing/unboxing
2.generics
3.annotations
4.java.util.concurrent
5.enum

http://docs.oracle.com/javase/1.5.0/docs/guide/language/enums.html
6.variable number of arguments

aMethod(T... args)

a T... is only a syntactic sugar for a T[].
7.for each
8. import static

http://www.deitel.com/articles/java_tutorials/20060211/index.html

the following syntax imports a particular static member:

import static packageName.ClassName.staticMemberName;

The following syntax imports all static members of a class:

import static packageName.ClassName.*;

9. printf

great examples

http://www.java2s.com/Tutorial/Java/0120__Development/0200__printf-Method.htm

Overflow and underflow

http://javapapers.com/core-java/java-overflow-and-underflow/

it has very good code example in the link:

In Java arithmetic operators don’t report overflow and underflow conditions. They simply swallow it! It is a very dangerous thing to do.

When the resultant value of an operation is larger than 32 bits (the maximum size an int variable can hold) then the low 32 bits only taken into consideration and the high order bits are discarded. When the MSB (most significant bit) is 1 then the value is treated as negative.

While using java floating point operators, overflow will result in Infinity and underflow will result 0.0 As a general rule here also Java doesn’t throw an error or exception for overflow and underflow.

Garbage Collection

1. reference counting
2. Mark and sweep: starting at root objects ( objects on the stack, global object etc), mark them live, and recursively marking any object referenced from them.

Interpreted language

http://en.wikipedia.org/wiki/Interpreted_language

Once was asked: is Java a interpreted language or compiled language.

Interpreted language is a programming language in which programs are 'indirectly' executed ("interpreted") by an interpreter program. This can be contrasted with a compiled language which is converted into machine code and then 'directly' executed by the host CPU.

query plan

http://www.sqlite.org/eqp.html

final array

void foo() {
final int[] number = {1,2,3};
numbers[1] = 50; // is this legal?
}

legal, the final is on the array, so you can not change the length of array, but you can change the element

Difference between Vector and List in Java

http://javapapers.com/core-java/java-collection/difference-between-vector-and-arraylist-in-java/

Vector and ArrayList are very similar. Both of them represent a 'growable array', where you access to the elements in it through an index.

ArrayList it's part of the Java Collection Framework, and has been added with version 1.2, while Vector it's an object that is present since the first version of the JDK. Vector, anyway, has been retrofitted to implement the List interface.

The main difference is that Vector it's a synchronized object, while ArrayList it's not.

While the iterator that are returned by both classes are fail-fast (they cleanly thrown a ConcurrentModificationException when the orignal object has been modified), the Enumeration returned by Vector are not.

Unless you have strong reason to use a Vector, the suggestion is to use the ArrayList.

--------

java.util.Vector came along with the first version of java development kit (JDK). java.util.ArrayList was introduced in java version1.2, as part of java collections framework. As per java API, in Java 2 platform v1.2,vector has been retrofitted to implement List and vector also became a part of java collection framework.

All the methods of Vector is synchronized. But, the methods of ArrayList is not synchronized. All the new implementations of java collection framework is not synchronized.

Vector and ArrayList both uses Array internally as data structure. They are dynamically resizable. Difference is in the way they are internally resized. By default, Vector doubles the size of its array when its size is increased. But, ArrayList increases by half of its size when its size is increased.

Therefore as per Java API the only main difference is, Vector’s methods are synchronized and ArrayList’s methods are not synchronized.

Vector or ArrayList? Which is better to use in java?

In general, executing a ‘synchronized’ method results in costlier performance than a unsynchronized method. Keeping the difference in mind, using Vector will incur a performance hit than the ArrayList. But, when there is a certain need for thread-safe operation Vector needs to be used.

Is there an alternate available in java for Vector?
ArrayList can be synchronized using the java collections framework utility class and then ArrayList itself can be used in place of Vector.

When there is no need for synchronized operation and you still look for better performance ‘Array’ can be used instead of ArrayList. But the development is tedious, since it doesn’t provide user friendly methods.

When you use Vector or ArrayList, always initialize to the largest capacity that the java program will need. Since incrementing the size is a costlier operation.

LDAP

LDAP, Lightweight Directory Access Protocol, is an Internet protocol that email and other programs use to look up information from a server.

dn: cn=John Doe,dc=example,dc=com
cn: John Doe
givenName: John
sn: Doe
telephoneNumber: +1 888 555 6789
telephoneNumber: +1 888 555 1232
mail: john@example.com
manager: cn=Barbara Doe,dc=example,dc=com
objectClass: inetOrgPerson
objectClass: organizationalPerson
objectClass: person
objectClass: top

Spring tutorial

http://www.developersbook.com/spring/spring-tutorials/spring-tutorials.php

iBatis tutorial

http://www.developersbook.com/ibatis/iBatis-tutorials/iBatis-tutorials.php

Getting Started with Enterprise JavaBeans

http://www.conceptgo.com/gsejb/index.html

use of jboss-web.xml

http://www.huihoo.org/jboss/online_manual/3.0/ch07s22.html

A beginners guide to Ant

http://www.comscigate.com/ant/A_beginners_guide_to_Ant.htm

Developing a Spring Framework MVC application step-by-step

http://static.springsource.org/docs/Spring-MVC-step-by-step/

SOAP

http://www.w3schools.com/soap/default.asp

SOAP provides a way to communicate between applications running on different operating systems, with different technologies and programming languages.

A SOAP message is an ordinary XML document containing the following elements:

An Envelope element that identifies the XML document as a SOAP message
A Header element that contains header information
A Body element that contains call and response information
A Fault element containing errors and status information

The optional SOAP Header element contains application-specific information (like authentication, payment, etc) about the SOAP message.

If the Header element is present, it must be the first child element of the Envelope element.The attributes defined in the SOAP Header defines how a recipient should process the SOAP message.

If a Fault element is present, it must appear as a child element of the Body element. A Fault element can only appear once in a SOAP message.

median of a billion numbers

http://stackoverflow.com/questions/2571358/median-of-a-billion-numbers

Simple LRU Caching with Expiration

http://www.codeproject.com/KB/java/lru.aspx

http://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java-6

recursion to iterative

f(){

if( condition = false)

return;

f();

g()

}

change to iterative

f(){

while(condition = true){

g();

}

}

powerSet -- binary approach

http://forums.devshed.com/java-help-9/generating-power-set-of-a-set-563361.html

The binary approach just means you're considering each element of the original set(e) as a bit value of a binary number. So if you have an original set of four elements(A, B, C, D) you would consider each one a bit value.

A - 00000001
B - 00000010
C - 00000100
D - 00001000

The size of a power set is calculated by 2^N of the original set. So in this case the size of the power set will be 2^4 or 16. This means that you must create sixteen elements for your power set with binary values starting at 0 and ending at 15 in binary. For each binary value you would add the elements of the original set which have similar bits.

Example:

00000000 - (O) - {Empty Set}
00000001 - (1) - {A}
00000010 - (2) - {B}
00000011 - (3) - {A, B}
00000100 - (4) - {C}
00000101 - (5) - {A,C}
00000111 - (6) - {A,B,C}

collection of technical interview questions

http://www.scribd.com/doc/7691861/A-collection-of-technical-interview-questions

How do you test a large amount of data

1. check if there is specification of the data to see if you can narrow down the format/definition of the data so you can run your program with no/little error.
2. write your code to write in the log when running into exception of the specification.
3. run your test over PART of the data until there is no exception thrown.
4. estimate based on 2 number of errors/exception you might see in production.
5. later on, you will be finding rare exceptions that might only occur a couple of times in the input. Just solve these by hand

if there is no spec, try to see if you can normalize the data

Java performance Tuning

http://www.javaperformancetuning.com/

Best practices to improve performance using Patterns in J2EE

http://www.precisejava.com/javaperf/j2ee/Patterns.htm

String/StringBuffer/StringBuilder

http://www.java-tips.org/java-se-tips/java.lang/difference-between-string-stringbuffer-and-stringbu.html

String is immutable whereas StringBuffer and StringBuilder can change their values.

The only difference between StringBuffer and StringBuilder is that StringBuilder is unsynchronized whereas StringBuffer is synchronized. So when the application needs to be run only in a single thread then it is better to use StringBuilder. StringBuilder is more efficient than StringBuffer.

Criteria to choose among String, StringBuffer and StringBuilder

1. If your text is not going to change use a string Class because a String object is immutable.
2. If your text can change and will only be accessed from a single thread, use a StringBuilder because StringBuilder is unsynchronized.
3. If your text can changes, and will be accessed from multiple threads, use a StringBuffer because StringBuffer is synchronous.

can a class be declared static

http://www.javaworld.com/javaqa/1999-08/01-qa-static2.html

There are 2 types of classes.
Top-level class, and Inner class.

there are 4 types Inner classes:
1. Anonymous
2. local class--it is like local variables. local classes aren't allowed to be declared public, protected, private, or static.
3. Member class : this is the only one you can declare static
class TopLevelClass{

class MemberClass
}
4. Nested top-level

class TopLevelClass{

static class MemberClass
}

new TopLevelClass.MemberClass

Basic Algorithm Code

http://algs4.cs.princeton.edu/code/

Why use Singleton over Static classes?

http://my.opera.com/zomg/blog/2007/09/17/singleton-pattern-vs-static-classes

If you want a simple class that's accessible from everywhere in your code, you could easily use a static class to achieve this.

The singleton does have some advantages though...


With Singleton, you can keep track of who's using it easily. This is because you need to call the getInstance() or whatever method which returns an instance of the class.

Also, because of the above, you can control the amount of actual instances. In some special cases, it might be useful to have multiple instances of the singleton class, for example for load balancing.


You can also give a singleton some parameters. When working with static classes, you may need to pass a lot of parameters to the methods of the class because you aren't "constructing" it. This can, however, be avoided by using a method in the static class that saves the parameters and calling the method you want after that which is pretty much equal to first calling the singleton's getInstance with your parameters and then calling its method.


Singleton also gives a reference/pointer to the class instance. You can then pass this reference as a parameter for some other function for example. If you were using static classes, the other function would have to use the class statically too and if you ever needed to change the behavior, you would need to rewrite parts of that function too instead of just having the first one pass a different class as the parameter.

There's also an another side to the reference thing. If you use the reference in your class and decide that you won't need a singleton anymore, but a normal class, you will just need to change the behavior of the class itself and perhaps replace the line which gets an instance of it to constructing a new one or such. If you were using a static class, you would have to rewrite a lot of the code to use the new reference to the class instead of the static class name. A singleton class should also work almost out of the box as a normal class too. If you had a static class and wanted to convert it to a normal one, you would have to rewrite many parts of it.


You can't extend static classes, but singletons you can. Except it doesn't work very well in PHP due to some issues with static method inheritance, but it's not the only language in the world and it can be done but slightly hackily.

Deep Copy and Shallow copy

http://javapapers.com/core-java/java-clone-shallow-copy-and-deep-copy/

Generally clone method of an object, creates a new instance of the same class and copies all the fields to the new instance and returns it. This is nothing but shallow copy

clone() method in Object is protected.

to overwrite clone(), you must implement Cloneable marker interface or else you will get CloneNotSupportedException.

deep copy the copied object contains some other object its references are copied recursively . be careful with cyclic.
If you don’t want to implement deep copy yourselves then you can go for serialization. It does implements deep copy implicitly and gracefully handling cyclic dependencies.

Thread Safety

1 .All threads inside a Java virtual machine (JVM) share the same heap and method area
2. Because multithreading is built into Java, it is possible that any class you design eventually may be used concurrently by multiple threads.

Given the architecture of the JVM, you need only be concerned with instance and class variables when you worry about thread safety. Because all threads share the same heap, and the heap is where all instance variables are stored,

You needn't worry about multithreaded access to local variables, method parameters, and return values, because these variables reside on the Java stack. In the JVM, each thread is awarded its own Java stack. No thread can see or use any local variables, return values, or parameters belonging to another thread.

Given the structure of the JVM, local variables, method parameters, and return values are inherently "thread-safe." But instance variables and class variables will only be thread-safe if you design your class appropriately.

Three ways to make an object thread-
Synchronize critical sections
public void setColor(int r, int g, int b) {
checkRGBVals(r, g, b);
synchronized (this) {
this.a = r
this.b = g
}
}

public synchronized void invert() {
r = 255 - r;
g = 255 - g;
b = 255 - b;
}

Make it immutable

public RGBColor invert() {
RGBColor retVal = new RGBColor(255 - r,
255 - g, 255 - b);
return retVal;
}

Use a thread-safe wrapper

http://www.artima.com/designtechniques/threadsafety7.html

The third approach to making an object thread-safe is to embed that object in a thread-safe wrapper object. In this approach you leave the original class (which isn't thread-safe) unchanged and create a separate class that is thread-safe.

-------------
thread safety may involve a performance penalty
Synchronized method invocations generally are going to be slower than non-synchronized method invocations.

Synchronized method invocations generally are going to be slower than non-synchronized method invocations.

Unnecessary synchronized method invocations (and synchronized blocks) can cause unnecessary blocking and unblocking of threads, which can hurt performance.

Immutable objects tend to be instantiated more often, leading to greater numbers of often short-lived objects that can increase the work of the garbage collector.

Synchronization gives rise to the possibility of deadlock, a severe performance problem in which your program appears to hang.

How to reduce the number of bugs when coding?

Junit , run code coverage, find bugs tool.

Avoid fancy coding. The more complicated the code, the more likely there's bugs. Usually on modern systems, clearly written code will be fast and small enough.

Use available libraries. The easiest way to not have bugs writing a utility routine is to not write it.

Learn a few formal techniques for the more complicated stuff. If there's complicated conditions, nail them down with pen and paper. Ideally, know some proof techniques. If I can prove code correct, it's almost always good except for big, dumb, obvious bugs that are easy to fix. Obviously, this only goes so far, but sometimes you can formally reason about small but complicated things.

Beyond that, set the highest warning level your compiler offers, and make sure warnings are treated as errors. Bugs often hide in those "erroneous" errors.

• Don't ignore error codes - e.g. don't assume that you got a valid result, that a file has been successfully created, etc... Because some day, something will happen.
• Don't assume that your code will never enter some condition and that therefore "it's safe to ignore that condition".
• Test your code, then have it tested by someone else. I find I'm the worst person to test my own code.
• Take a break, then re-read your code and see if you "missed the obvious". Often happens to me.

if you're so sure that condition X will never happen... use an assert to make sure that when condition X happens, you'll know about it (through an exception, or logging, or whatever). –

I found that if I pass all of the context to a function (or method) that that function needs to do its job, and return the meaningful data that I'm looking for, that my code has become much more robust.

Implicit state is the enemy and in my experience is the #1 source of bugs. This state can be global variables or member variables, but if results are dependent on something that's not passed to the function you're asking for trouble. Clearly it is not feasible to eliminate state, but minimizing it has huge positive effects on program reliability.

Involve your testers as early as you can

http://programmers.stackexchange.com/questions/7927/how-to-reduce-the-number-of-bugs-when-coding

ArrayQueue Implementation

https://docs.google.com/document/d/1OW2FOK8YuPs2egY04DSNsvd13FGmeASbjRdj4kg0KSI/edit?pli=1&hl=en&authkey=COKZqoMB#

Java interview questions

what is disadvantage of using Java Generic?

http://www.javabeat.net/articles/33-generics-in-java-50-1.html

what is the common practice you do to reduce bugs?

what do you do to write thread safe code?

WildCard

REST

http://www.infoq.com/articles/rest-introduction

http://tomayko.com/writings/rest-to-my-wife

PHP for beginners

http://www.phptutorial.info/

transient variable

what is a transient variable

A transient variable is a variable that may not be serialized.

A variable that won't be allowed for object serialisation. so that the state of the value will always be defaulted after the deserialisation.

serialization

serialization is the process of converting a data structure or object into a format that can be stored
When the resulting series of bits is reread according to the serialization format, it can be used to create a semantically identical clone of the original object

Serialization provides:

• a method of persisting objects which is more convenient than writing their properties to a text file on disk, and re-assembling them by reading this back in.
• a method of issuing remote procedure calls, e.g., as in SOAP
• a method for distributing objects, especially in software componentry such as COM, CORBA, etc.
• a method for detecting changes in time-varying data.

O/R mapping

http://www.agiledata.org/essays/mappingObjects.html

mapping Object to Relational databases
The easiest mapping you will ever have is a property mapping of a single attribute to a single column.

Shadow information is any data that objects need to maintain, above and beyond their normal domain data, to persist themselves. This typically includes primary key information

One type of shadow information that I have not discussed yet is a boolean flag to indicate whether an object currently exists in the database.
A common practice is for each class to implement an isPersistent boolean fla that is set to true when the data is read in from the database and set to false when the object is newly created. ( or isLocal() )

--
Shadow information doesn’t necessarily need to be implemented by the business objects, although your application will need to take care of it somehow. For example, with Enterprise JavaBeans (EJBs) you store primary key information outside of EJBs in primary key classes, the individual object references a corresponding primary key object. The Java Data Object (JDO) approach goes one step further and implement shadow information in the JDOs and not the business objects. (Do, DoImpl)

nts at an important part of the O/R impedance mismatch between object technology and relational technology. Classes implement both behavior and data whereas relational database tables just implement data.

interview questions : distributed sorting

if you have a large log which contains urls and queries, design a algorithm finding top 100 most frequent searched queries

1. extract the queries from the log first, then put in the hashmap, get the top 100

2. what is limitation of hashmap?

might be too limited if the queries are too many. in memory operation

3. what would you do instead?

add more CPUs, distributed into multiple computers

4. what if the file is still too large?

divide the file in chunks, say each file only get queries starting with A.

Memory in Java

http://www.vogella.de/articles/JavaPerformance/article.html

In the heap the Java Virtual Machine (JVM) stores all objects created by the Java application, e.g. by using the "new" operator. The Java garbage collector (gc) can logically separate the heap into different areas, so that the gc can faster identify objects which can get removed

The memory for new objects is allocated on the heap at run time. Instance variables live inside the object in which they are declared.

--

Stack is where the method invocations and the the local variables are stored. If a method is called then its stack frame is put onto the top of the call stack. The stack frame holds the state of the method including which line of code is executing and the values of all local variables. The method at the top of the stack is always the current running method for that stack. Threads have their own call stack.

Runtime runtime = Runtime.getRuntime();
  // Run the garbage collector
  runtime.gc();
  // Calculate the used memory
  long memory = runtime.totalMemory() - runtime.freeMemory();

great website for tutorial

http://www.vogella.de/java.html

Java Concurrency & Threads

http://www.vogella.de/articles/JavaConcurrency/article.html

To make a class immutable make

• all its fields final

• the class declared as final

• the this reference is not allowed to escape during construction

• Any fields which refer to mutable data objects are

  • private

  • have no setter method

  • they are never directly returned of otherwise exposed to a caller

  • if they are changed internally in the class this change is not visible and has no effect outside of the class

An immutable class may have some mutable data which is uses to manages its state but from the outside this class nor any attribute of this classes can get changed.

The base means for concurrency are "java.lang.Threads". Each thread will execute an object of type "java.lang.Runnable". Runnable is an interface with defines only the one method "run()". This method is called by "Thread" and contains the work which should be done. Therefore the "Runnable" is the task to perform. The Thread is the worker who is doing this task.

Runnable task = new MyRunnable(10000000L + i);
  Thread worker = new Thread(task);
  // We can set the name of the thread
  worker.setName(String.valueOf(i));
  // Start the thread, never call method run() direct
worker.start();

Using Threads directly has the following disadvantages.

• Creating a new thread causes some performance overhead

• Too many threads can lead to reduced performance, as the CPU needs to switch between these threads.

• You cannot easily control the number of threads, therefore you may run into out of memory errors due to too many threads.

The "java.util.concurrent" package offers improved support for concurrency compared to threads. The java.util.concurrent package helps solving several of the issues with threads.

The Executor framework provides example implementation of the
 java.util.concurrent.Executor interface, e.g.
 Executors.newFixedThreadPool(int n) which will create n worker
 threads. The ExecutorService adds lifecycle methods to the Executor,
 which allows to shutdown the Executor and to wait for termination.
  

ExecutorService executor = Executors.newFixedThreadPool(NTHREDS);
 for (int i = 0; i < 500; i++) {    Runnable worker = new MyRunnable(10000000L + i);    executor.execute(worker);   }   // This will make the executor accept no new threads   // and finish all existing threads in the queue   executor.shutdown();   // Wait until all threads are finish   while (!executor.isTerminated()) {  


import java.util.concurrent.atomic.AtomicInteger;
Non Blocking Algorithms
. The fork-join framework allows you to
  distribute a certain task on several workers and when wait for the
  result.

Binary search Tree in Java

http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// void removeMin( ) --> Remove minimum item
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Exceptions are thrown by insert, remove, and removeMin if warranted

/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinarySearchTree {
/**
* Construct the tree.
*/
public BinarySearchTree( ) {
root = null;
}

/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( Comparable x ) {
root = insert( x, root );
}

/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( Comparable x ) {
root = remove( x, root );
}

/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) {
root = removeMin( root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( ) {
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public Comparable findMax( ) {
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return root == null;
}

/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
throw new DuplicateItemException( x.toString( ) ); // Duplicate
return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}

/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;

return t;
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;

return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match
}

return null; // Not found
}

/** The tree root. */
protected BinaryNode root;


// Test program
public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );

for( int i = 1; i <>2 )
t.remove( new Integer( i ) );

if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 2; i <>2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );

for( int i = 1; i <>2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( "Find error2!" );
}
}
}


// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of this package.

class BinaryNode {
// Constructors
BinaryNode( Comparable theElement ) {
element = theElement;
left = right = null;
}

// Friendly data; accessible by other package routines
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}


/**
* Exception class for duplicate item errors
* in search tree insertions.
* @author Mark Allen Weiss
*/
public class DuplicateItemException extends RuntimeException {
/**
* Construct this exception object.
*/
public DuplicateItemException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message ) {
super( message );
}
}


/**
* Exception class for failed finds/removes in search
* trees, hash tables, and list and tree iterators.
* @author Mark Allen Weiss
*/
public class ItemNotFoundException extends RuntimeException {
/**
* Construct this exception object.
*/
public ItemNotFoundException( ) {
super( );
}

/**
* Construct this exception object.
* @param message the error message.
*/
public ItemNotFoundException( String message ) {
super( message );
}
}