我有一个二叉树,其中每个节点代表一个电子门(AND,OR,...)。我的任务是计算树的总价值(像这样的画面,二叉树):如何正确使用共享的BlockingQueue?
这是到目前为止我的代码(没有线程执行):
gate_node:
public class gate_node {
gate_node right_c, left_c;
Oprtator op;
int value;
int right_v, left_v;
public gate_node(gate_node right, gate_node left, Oprtator op) {
this.left_c = left;
this.right_c = right;
this.op = op;
right_v = left_v = 0;
}
void add_input(int right_v, int left_v){
this.right_v=right_v;
this.left_v=left_v;
}
int compute(int array_index, int arr_size) {
/*
* The following use of a static sInputCounter assumes that the
* static/global input array is ordered from left to right, irrespective
* of "depth".
*/
final int left, right;
System.out.print(this.op+"(");
if (null != this.left_c) {
left = this.left_c.compute(array_index,arr_size/2);
System.out.print(",");
} else {
left = main_class.arr[array_index];
System.out.print(left + ",");
}
if (null != this.right_c) {
right = this.right_c.compute(array_index + arr_size/2,arr_size/2);
System.out.print(")");
} else {
right = main_class.arr[array_index + 1];
System.out.print(right + ")");
}
return op.calc(left, right);
}
}
Oprtator:
public abstract class Oprtator {
abstract int calc(int x, int y);
}
和
public class and extends Oprtator {
public int calc(int x, int y){
return (x&y);
}
}
或者
public class or extends Oprtator {
public int calc(int x, int y){
return (x|y);
}
}
树:
public class tree implements Runnable {
gate_node head;
tree(gate_node head) {
this.head = head;
}
void go_right() {
head = head.right_c;
}
void go_left() {
head = head.left_c;
}
@Override
public void run() {
// TODO Auto-generated method stub
}
}
主类
public class main_class {
public static int arr[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
public static void main(String[] args) {
tree t = new tree(new gate_node(null, null, new and()));
t.head.right_c = new gate_node(null, null, new or());
t.head.right_c.right_c = new gate_node(null, null, new and());
t.head.right_c.left_c = new gate_node(null, null, new and());
t.head.left_c = new gate_node(null, null, new or());
t.head.left_c.right_c = new gate_node(null, null, new and());
t.head.left_c.left_c = new gate_node(null, null, new and());
int res = t.head.compute(0, arr.length);
System.out.println();
System.out.println("The result is: " + res);
}
}
我要计算使用它的线程池,这样的算法:
制备:
实现每个门作为类/对象。它必须有2个属性:输入A,输入B和计算结果的方法;
实现一棵树。每个节点是一对(gate,next_node)。 Root是next_node为空的节点。叶子是没有其他节点指向它的节点。
使用共享(线程安全)节点队列。它最初是空的。
从队列中持续等待一个元素的线程有一个固定的数字(选择一个,不依赖于门的数量)(除非在这种情况下他们刚刚退出)。
循环:
每当输入把节点队列中的节点上发生(在开始输入到叶)。这可以通过在门上定义add_input方法来实现。
线程从队列拾取节点:
-
如果输入中的一个被丢失丢弃它(第二输入出现时它会在那里再一次)。另一个想法是仅当两个输入都存在时才将节点放入队列中。
如果两个输入都存在,则计算结果并将其传递给next_node(如果它不为空)(并将next_node放入队列中)。如果next_node为null,那么这就是你的结果 - 打破循环并最终确定。
唯一的问题是,我不知道如何创建一个共享的BlockingQueue树中的每个节点对象可以将自己变成它,以及如何创建的固定大小的线程的数组不断等待队列中的新元素可用(然后执行它们).....直到头从列表中移除(这意味着我们正在计算)。
我在网上搜索了BlockingQueue的例子,但我只找到生产者和消费者的例子,我很难将这些例子移动到适合我的问题。如果有人能够帮助我,我会很感激。