2007年5月28日随笔档案 - JobHu

实现一个栈,使其push,pop,min(取得栈中的最小元素)均为O(1)

实现一个栈,使其push,pop,min(取得栈中的最小元素)均为O(1)

我的解

interface IntStack

{

int pop();

void push(int i);

int get();

}

class MinStack

{

//store all the element

private IntStack elemStack = new IntStack();

//store current and historical smallest element

private IntStack minStack = new IntStack();

public void push(int i)

{

elemStack.push(i);

int currentMin = minStack.get();

if(i <= currentMin) minStack.push(i);

}

public int pop()

{

int result = elemStack.pop();

if(result == minStack.get()) minStack.pop();

return result;

}

public int getMinElem()

{

return minStack.get();

}

posted @ 2007-07-18 20:57 Job Hu 阅读(894) | 评论 (0) | 编辑收藏

二叉排序树变为双向链表

把一个二叉排序树(也许不叫这个)变为递增的双向链表,不能够生成额外的结点.
eg 6
       / \
      4   8
     / \ / \
    3 5 7 9

3=4=5=6=7=8=9

我的解:

class Node

{

public Node left;

public Node right;

private static Node getLinkListTail(Node head)

{

Node result = head;

if(result==null) return null;

while(result.right!=null)

{

result = result.right;

}

return result;

}

public static Node flatten(Node root)

{

if(root==null) return null;

Node result = root;

// A leaf node

if(root.left==null&&root.right==null) return root;

//divide-and-conquer

Node leftSubTreeLinkListHead = flatten(root.left);

Node rightSubTreeLinkListHead = flatten(root.right);

//merge

Node leftSubTreeLinkListTail = getLinkListTail(leftSubTreeLinkListHead);

root.left = leftSubTreeLinkListTail;

root.right = rightSubTreeLinkListHead;

if(leftSubTreeLinkListHead!=null)

{

result = leftSubTreeLinkListHead;

leftSubTreeLinkListTail.right = root;

}

if(rightSubTreeLinkListHead!=null) rightSubTreeLinkListHead.left = root;

return result;

}

posted @ 2007-07-18 20:37 Job Hu 阅读(641) | 评论 (0) | 编辑收藏

Byte in Java

public class ByteTest

{

public static void main(String[] args)

{

byte b;

byte c;

//b = 255; //Cannot convert from int to byte

//b = 0xFF; //Cannot convert from int to byte

b = 127;

c = 0x7F;

if(b == c) System.out.println("b == c");

if(127 == 0x7F) System.out.println("127 == 0x7F");

b = -128;

//c = 0x80; //Cannot convert from int to byte

c = (byte)0x80;

if(b == c) System.out.println("b == c");

if(-128 == 0x80) System.out.println("-128 == 0x80");

if(128 == 0x80) System.out.println("128 == 0x80");

c = (byte)0x80;

if(128 == c) System.out.println("128 == c");

if(-128 == c) System.out.println("-128 == c");

if(128 == (c&0xFF)) System.out.println("128 == (c&0xFF)");

}

输出:
b == c
127 == 0x7F
b == c
128 == 0x80
-128 == c
128 == (c&0xFF)

posted @ 2007-07-17 23:22 Job Hu 阅读(282) | 评论 (0) | 编辑收藏

Here's a list of keywords in the Java programming language. You cannot use any of the following as identifiers in your programs. The keywords const and goto are reserved, even though they are not currently used. true, false, and null might seem like keywords, but they are actually literals; you cannot use them as identifiers in your programs.

`abstract`	`continue`	`for`	`new`	`switch`
`assert`^***	`default`	`goto`^*	`package`	`synchronized`
`boolean`	`do`	`if`	`private`	`this`
`break`	`double`	`implements`	`protected`	`throw`
`byte`	`else`	`import`	`public`	`throws`
`case`	`enum`^****	`instanceof`	`return`	`transient`
`catch`	`extends`	`int`	`short`	`try`
`char`	`final`	`interface`	`static`	`void`
`class`	`finally`	`long`	`strictfp`^**	`volatile`
`const`^*	`float`	`native`	`super`	`while`

posted @ 2007-07-09 22:38 Job Hu 阅读(194) | 评论 (1) | 编辑收藏

Tomcat笔记（三）

来看看ContainerBase的start方法：

1

public synchronized void start() throws LifecycleException {
2

3

//如果Container已经处于start状态，直接返回
4

if (started) {
5

if(log.isInfoEnabled())
6

log.info(sm.getString("containerBase.alreadyStarted", logName()));
7

return;
8

}
9

10

// Notify our interested LifecycleListeners
11

lifecycle.fireLifecycleEvent(BEFORE_START_EVENT, null);
12

13

started = true;
14

15

// Start our subordinate components, if any
16

if ((loader != null) && (loader instanceof Lifecycle))
17

((Lifecycle) loader).start();
18

logger = null;
19

getLogger();
20

if ((logger != null) && (logger instanceof Lifecycle))
21

((Lifecycle) logger).start();
22

//用来管理session
23

if ((manager != null) && (manager instanceof Lifecycle))
24

((Lifecycle) manager).start();
25

//看名字就知道是干什么的，不过研究集群的优先级很低
26

if ((cluster != null) && (cluster instanceof Lifecycle))
27

((Lifecycle) cluster).start();
28

//用来进行访问控制，或者权限控制的
29

if ((realm != null) && (realm instanceof Lifecycle))
30

((Lifecycle) realm).start();
31

//和JNDI相关
32

if ((resources != null) && (resources instanceof Lifecycle))
33

((Lifecycle) resources).start();
34

35

//启动所有子container
36

Container children[] = findChildren();
37

for (int i = 0; i < children.length; i++) {
38

if (children[i] instanceof Lifecycle)
39

((Lifecycle) children[i]).start();
40

}
41

42

// 启动Container内部持有的pipeline对象，Container对Pipeline接口的实现就是通过调用这个内部持有的Pipeline对象
43

if (pipeline instanceof Lifecycle)
44

((Lifecycle) pipeline).start();
45

46

// Notify our interested LifecycleListeners
47

lifecycle.fireLifecycleEvent(START_EVENT, null);
48

49

// 注释说这个函数用来check session是否过期，但看的不是太懂
50

threadStart();
51

52

// Notify our interested LifecycleListeners
53

lifecycle.fireLifecycleEvent(AFTER_START_EVENT, null);
54

55

}
56

所有和cluster、realm相关都放在最后来研究了，不管怎么样先把tomcat如何处理request的整个过程串起来对现在的我来说是最重要的。另外还有Tomcat中的很多部件都用到了JMX API，即SNMP的Java实现来进行性能检测和管理，这个也会放在最后研究。

ContainerBase就看这么多了，下面来看看StandardEngine这个类。除去和cluster、realm、JMX相关的方法后，StanderdEngine剩下的方法就很很少了。

StandardEngine有一个Service类型的成员。Java doc中指出Service就是由很多共享同一个Container的Connector组成。一个Service对应于一个Container，来自这个Service的任何一个Connector的request都会由其对应的Container进行处理。看到现在的感觉就是Connector对Container提供request对象，并接受Container返回的response对象。在Tomcat中有很多类别都被用来体现现request或者response，例如org.apache.catalina.connector .Request就是Coyote request的一个wrapper类，Coyote这个framework帮助封装了底层的网络复杂性，向上提供一个统一的接口。我想tomcat既能够成为一个standalone的http、jsp/Servlet服务器，也能够同apache http server集成，很可能就是依赖于Coyote提供的统一接口。

在构造函数中会将StandardEngine这个Pipeline的最后一个Valve，即Basic设置为StandardEngineValve。来看看StandardEnginValue的invoke方法

1

public final void invoke(Request request, Response response)
2

throws IOException, ServletException {
3

4

// Select the Host to be used for this Request
5

Host host = request.getHost();
6

if (host == null) {
7

response.sendError
8

(HttpServletResponse.SC_BAD_REQUEST,
9

sm.getString("standardEngine.noHost",
10

request.getServerName()));
11

return;
12

}
13

14

// Ask this Host to process this request
15

host.getPipeline().getFirst().invoke(request, response);
16

17

}
18

可以看出在处理到StandardEngine这个Pipeline的最后一个Valve时，会根据当前request所指定的Host，将当前的request和response传递给该Host这个Pipeline的第一个Valve进行处理。

我想Tomcat中的Engine、Host、Context、Wrapper处理request生成response的过程大概是这样的：

Engine在收到request后在其Pipeline中的每一个Valve对request进行处理，也可能会生成response的某些部分，在最后一个Valve中将request和response传给下一级Container即Host的第一个Valve。Host重复同样过程，继续传递给Context，Context再传递给Wrapper。由于Wrapper代表的是Servlet对象，因此在Wrapper处所有的处理都结束了，response对象生成完毕。当然了，如果在某一级中无法找到request要求的下一级对象，则整个处理过程也会立即结束。

posted @ 2007-05-30 22:58 Job Hu 阅读(353) | 评论 (1) | 编辑收藏

Tomcat笔记（二）

ContainerBase对Pipeline接口的实现完全依赖于其内部的一个Pipeline类型的成员pipeline（实现类为StandardPipeline）。
在Tomcat的doc中这样介绍Pipeline接口：该接口的invoke（）方法被调用时，将会引发一系列Value对象的序列调用。要求一个Pipeline中的存在一个Value对象（多为最后一个Value对象）完成对request的处理，并生成相应的response，而不能试图将Request继续传递给其它Value对象（这个Value对象被称为Basic）。通常，每个Container对象都持有一个Pipline类型(实际上为StandardPipeline)的成员。在Pipeline的doc中，方法getBasic，getFirst两个方法的Method Summary完全一样，Apache的牛人们也不能免俗啊。

StandardPipeline除实现Pipeline接口外，也实现了Lifecycle接口。这个类的start和stop方法，首先检查是否已经被start或stop，如果是则会抛出一个LifecycleException的异常，否则便fire和生命期改变的相关事件，并调用其内部valve对象（如果该valve对象也实现了Lifecycle接口）的start和stop方法。addValve方法用来向StandardPipeline中加入Valve对象，新加入的Value对象被放在一个叫做Basic的特殊Valve（就是一个Pipeline的最后一个Valve）的前面，如果在添加Valve的时候该StandardPipeline已经处于start状态，则会进行一些注册（调用apache commons库的一个类，完全没有看懂这个地方是什么作用>_<）

posted @ 2007-05-28 07:39 Job Hu 阅读(300) | 评论 (0) | 编辑收藏

JobHu

实现一个栈,使其push,pop,min(取得栈中的最小元素)均为O(1)

二叉排序树变为双向链表

Byte in Java

Java Language Keywords

Tomcat笔记（三）

Tomcat笔记（二）

导航

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜