并发遍历二叉树 (四)

public class ConcurTravBTree {
class BTreeNode {

public BTreeNode left;
public BTreeNode right;
public T value;

public BTreeNode(BTreeNode left, BTreeNode right, T value) {
this.left = left;
this.right = right;
this.value = value;
}

public BTreeNode(T value) {
this(null, null, value);
}
}

public class BTree {
String dumpStr;

public BTreeNode root;

public BTree() {
}

public BTree(BTreeNode root) {
this.root = root;
}

public void orderAdd(T v) {
if (root == null)
root = new BTreeNode(v);
else
orderAdd(root, v);
}

public void orderAdd(BTreeNode node, T v) {
if (node.value.compareTo(v) > 0) {
if (node.left == null)
node.left = new BTreeNode(v);
else
orderAdd(node.left, v);
} else {
if (node.right == null)
node.right = new BTreeNode(v);
else
orderAdd(node.right, v);
}
}

public void preOrderTraverse() {
preOrderTraverse(root);
}

public void preOrderTraverse( BTreeNode node) {
if (node != null) {
//System.out.println(node.value);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
preOrderTraverse(node.left);
preOrderTraverse(node.right);
}
}
}

static int global_id = 0;
public static final int POOLSIZE = 4;

ThreadPoolExecutor threadPool;
BTree tree;
HashSet tasks = new HashSet();

public void init() {
tree = new BTree();

/*
int[] data = new int[] { 1, 3, 5 };
for (int i = 0; i < data.length; i++)
tree.orderAdd(data[i]);
*/

Random r = new Random();
for( int i=0; i< 500; i++) {
tree.orderAdd( r.nextInt(500));
}

threadPool = new ThreadPoolExecutor(POOLSIZE, // corePoolSize
POOLSIZE + 2, // maximumPoolSize
60, // keepAliveTime
TimeUnit.SECONDS, // keepAliveTime unit
new ArrayBlockingQueue(POOLSIZE + 2), // workQueue
new ThreadPoolExecutor.CallerRunsPolicy()); // handler
}

public void start() {
threadPool.execute(new Visitor(tree.root));
}

class Visitor implements Runnable {
private int id;
private BTreeNode node;

public Visitor(BTreeNode node) {
this.id = ++global_id;
this.node = node;
}

public boolean handleNode(BTreeNode node) {
if (node == null)
return true;

if (ConcurTravBTree.this.threadPool.getActiveCount() <= ConcurTravBTree.this.threadPool
.getCorePoolSize()) {
System.out.println("--- ActiveCount "
+ ConcurTravBTree.this.threadPool.getActiveCount());
ConcurTravBTree.this.threadPool.execute(new Visitor(node));
return true;
}
return false;
}

public void run() {
System.out.println("[ job" + id + " ] ---start ");
tasks.add(id);
if (handleNode(node.right)) // assign Node to a task
node.right = null; //

// pre-order traverse
Stack> stack = new Stack>();
while (node != null || !stack.isEmpty()) {
long start = System.currentTimeMillis();
while (node != null) {
//System.out.println("[ job" + id + " ]" + node.value);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}

stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;

long cur = System.currentTimeMillis();
if (cur - start > 1000) {
if (handleNode(node)) {
node = null;
}