图形上下文导论（Introduction to SWT Graphics）

• 图形上下文
  • 在图像（Image）上绘画
  • 在控件（control）上绘画
• 切割（cliping）
• 画布（Canvas）
• 绘制线条和形状（Drawing lines and shapes）
• 绘制文本（Drawing text）
• 填充形状（Filling shapes）
• 异或（XOR）
• 绘制图像（Drawing images）

SWT图形系统使用了与控件（Control）相同的坐标习惯，即客户区最左上角开始的点为原点（0，0），x轴坐标向右增加，y轴坐标向下增加。Point 类被用于描述位置（坐标系统中的位置）以及偏移量（SWT中并没有Dimension类，矩形（rectangle）的大小是由Point类捕获的x、y坐标点偏移量到原点坐标来描述的）。

" src="/CuteSoft_Client/CuteEditor/Images/anchor.gif">图形上下文（Graphics Context）

图形能够被画在任何实现了org.eclipse.swt.graphics.Drawable接口的东西上，比如控件（Control）、图像（Image）、显示设备或者打印设备。 org.eclipse.swt.graphics.GC 就是封装了执行绘画操作的图形上下文（graphics context）。一般有两种使用GC的方法：一种是让Drawable 实例作为GC构造函数的参数获取的GC，另外一种是绘画事件（paintEvent）回调提供的GC。

在图像（Image）上绘画

    Image image = new Image(display,"C:/devEclipse_02/eclipse/plugins/org.eclipse.platform_2.0.2/eclipse_lg.gif");
    GC gc = new GC(image);
    Rectangle bounds = image.getBounds(); 
 gc.drawLine(0,0,bounds.width,bounds.height); 
 gc.drawLine(0,bounds.height,bounds.width,0); 
 gc.dispose();
    image.dispose(); 

原始图像	绘制线条后的图像

 由你创建的GC，就得由你负责销毁它。调用 dispose（）方法。关于怎样管理 SWT 资源的更多信息请参见 SWT: The Standard Widget Toolkit 。一个 GC 实例应该在使用完后就尽可能快的释放，这是因为每一个GC 都需要占用底层系统平台资源，而在某些操作系统平台中，这些资源是相当匮乏的，例如Windows 98仅仅提供了5个GC 对象。

在控件（Control）上绘画

以下代码 给Shell添加了一个绘画监听， 然后在paintControl（）方法中画一条连接原点到底部右下角的直线。

    Shell shell = new Shell(display); 
 shell.addPaintListener(new PaintListener(){
        public void paintControl(PaintEvent e){
            Rectangle clientArea = shell.getClientArea(); 
         e.gc.drawLine(0,0,clientArea.width,clientArea.height);
        }
    });
    shell.setSize(150,150)

虽然Shell的大小设置为（150,150）, 但实际上可绘画的区域比这还要再小一些，因为Shell还包括了边框、工具栏以及菜单栏，这也就是我们所要了解的客户区域。任何面板（Composite）都是使用getClientArea()方法获取客户区域的。

因为应用程序总是在底层OS绘制完控件后才得到绘画事件，所以绘画事件中的GC进行绘画后的效果就可以最终显示在控件上面了。当然也有例外，比如工具栏区域就不能在上面进行绘画。org.eclipse.swt.widgets.Canvas 能够用来进行多方面的图形绘画操作。

剪切（Clipping）

一个GC的剪切区域就是发生绘画的那部分，这里有个例子，如果你要填充出一个有缺口的三角形形状，一种方法是画出多个三角形和矩形组合出这么一个形状；当然也有另一种方法，就是利用GC的剪切操作。

    shell.addPaintListener(new PaintListener() {
        public void paintControl(PaintEvent e) {
            Rectangle clientArea = shell.getClientArea();
            int width = clientArea.width;
            int height = clientArea.height; 
         e.gc.setClipping(20,20,width - 40, height - 40);
            e.gc.setBackground(display.getSystemColor(SWT.COLOR_CYAN)); 
         e.gc.fillPolygon(new int[] {0,0,width,0,width/2,height});
        }
    });

这段代码在Shell上画了一个三角形。 左上角和右上角连接到底部边缘的中间。使用一个矩形CG对其进行剪切。 最后显示出被剪切的矩形区域。 

当控件发生绘画事件，GC总是剪切需要重绘的那部分区域。例如，另一个窗口移到了一个SWT shell的前面，随后又移走。那么需要重新显示的就是GUI被损坏的那部分（shell被覆盖的那部分），一个绘画事件就是事件队列。当绘画事件发生，paintControl(PaintEvent evt) 方法中的参数就包含了控件中需要的重绘区域的x、y坐标字段及宽和高字段。控件的受损部分能够包含若干个相分离的矩形区域，当绘画事件发生，控件的受损部 分不止一个时，那么它们就会被合并成一个单一的矩形。这一步是由底层平台来实现的，因为多个绘画事件在单独的一个回调过程中处理有利于执行。

在上面的例子中每当 paintControl(PaintEvent)被调用的时候， 就将在PaintEvent's area中寻找一个优化。绘画事件（paint event）很可能不交叉在绘画的形状（shape）中，在这种情况下，就不需要绘画（painting）或者指使需要一部分重画而已。依靠绘画的类型，就可以解决GC所选择的绘画部分，但事实上这要比GC剪切花费更多开销，而且在实践中常常忽视这些被损坏的区域让GC重新绘画全部，只有在刷新操作中才会依赖剪切。

如果程序需要手工损坏控件的某部分区域，可以使用Control.redraw(int x, int y, int width, int height)或者使用Control.redraw()损坏整个客户区域。此区域就被打上了标记然后包含在下一个绘画事件中，产生闪屏后，就会立即使用Control.update()方法强制处理控件的绘画请求。如果无绘画请求（也就是客户区域无损坏）, update()就什么不做。

（译者注：此处的Control并不单指Control类，而是指所有继承了Control类的控件类，比如button,canvas,shell等等）

画布（Canvas）

虽然任何控件都可以通过绘画事件（paintEvent）在其上进行绘制, 但是org.eclipse.swt.widgets.Canvas 是针对图形操作而特别设计的。可以直接使用Canvas，也可以通过添加绘画事件（paintEvent）使用，还可以创建Canvas的子类来自定义控件重复使用之。画布（Canvas）拥有大量的风格样式来影响绘画的产生。 

Canvas的默认行为是使用当前背景色填充自身的整个客户区域。这样会引起屏闪，因为绘画事件也是在GC上绘画，所以用户就会看到被填充的原始背 景色和产生绘画之间的闪烁。有一种方法可避免此类情况，在创建Canvas时使用SWT.NO_BACKGROUND样式。这样就防止了绘画背景，意思就 是程序要负责绘画客户区域的每一个像素。

当部件调整大小时，客户区域会重复绘画，这就会出现屏幕闪烁。使用SWT.NO_REDRAW_RESIZE 可减少这样的情况，控件会减少不必要的重绘。比如改变尺寸大小，绘画事件GC只会剪切需要重绘的部分即底部区域和右边区域，就像一个反方向的“L”。

在固定大小的GC上绘画NO-REDRAW_RESIZE样式能很好的减少屏闪。但是错误的使用NO_REDRAW_RESIZE 可以导致图形成扁圆形。扁圆形是个大概的说法，事实上是指部件没有随大小的调整而进行正确的更新。下面的例子就演示了这样的情况。 填充椭圆形。因为在窗口大小改变时没有产生绘画事件，因为GC只剪切受损的（发生改变的）区域，而上一个绘画又没有被抹去，这就产生了扁圆形状。( 即使用NO_REDRAW_RESIZE 绘画事件只处理扩大的那部分区域，原先部分它就不管了).

    shell.setLayout(new FillLayout()); 
 final Canvas canvas = new Canvas(shell,SWT.NO_REDRAW_RESIZE);

    canvas.addPaintListener(new PaintListener() {
        public void paintControl(PaintEvent e) {
            Rectangle clientArea = canvas.getClientArea();
            e.gc.setBackground(display.getSystemColor(SWT.COLOR_CYAN)); 
         e.gc.fillOval(0,0,clientArea.width,clientArea.height);
        }
    });

canvas的大小被增大，GC只剪切需要重绘的地方，扁圆形状就产生了。

问题出在 ，应该使用SWT.NONE 样式，这样GC就不会只剪切扩大的部分了。所以当Shell大小增大时整个椭圆形都会被重绘。

 final Canvas canvas = new Canvas(shell,SWT.NONE);

任何SWT部件，如果超过一个矩形区域被“损坏”，平台会把它们合并成一个，也就是说SWT程序只能处理一个绘画事件。在Canvas上使用NO_MERGE_PAINTS 样式可以覆盖这样的行为，可以为每一个被“损坏”的矩形区域调用绘画事件监听。

风格常量NO_BACKGROUND, NO_REDRAW_RESIZE 以及NO_MERGE_PAINTS 能够被使用在任何面板（Composite）以及子类中, 包括Canvas、Shell以及Group。 虽然这是被SWT允许的（不会由异常抛出），但在Composite 类的Javadoc中关于风格有这样的警告 "... 如果在其他的Composite子类中（除了Canvas）使用其行为是不明确的。"。所以实现图形绘画操作Canvas应该是首选。

另一种减少屏幕闪烁的方法，就是使用双缓冲技术。你可以先根据Canvas客户区域大小创建Image对象，然后使用GC(Image)将其绘画到Canvas上;  在绘画事件GC中调用drawImage(Image image, int x, int y)。 在一些平台上已经为你实现了双缓冲，所以你可以根据情况考虑使用三缓冲。" src="/CuteSoft_Client/CuteEditor/Images/anchor.gif">

绘制线条和形状（Drawing lines and shapes）

GC.drawLine(int x1, int y1, int x2, int y2);

GC.drawPolyline(int[] pointArray);

画一条连接多个坐标点的直线，int[] 存放着要连接的x、y坐标值。代码如下:

gc.drawPolyline(new int[] { 25,5,45,45,5,45 });

先是从坐标点25,5到45,45，然后从45,45到5,45。

GC.drawPolygon(int[] pointArray);

drawPolyline(int[])的使用与gc.drawPolyline很相似，不同的是最后一个点（5,45）连接了第一个点（25,5）。

gc.drawPolygon(new int[] { 25,5,45,45,5,45 });

相当于用三条线段链接三角形的单个端点，从而形成了一个三角形区域。

GC.drawRectangle(int x, int y, int width, int height);

画一个矩形区域，int x,int y是矩形左上角的坐标点，int width,int heighy分别是矩形的宽和高。

gc.drawRectangle(5,5,90,45);

左上角坐标点为（5,5），对角坐标点为（95，50）。

你可以将Rectangle作为一个单独的参数传送给绘画方法。GC.drawRectangle(Rectangle);

GC.drawRoundedRectangle(int x, int y, int width, int height, int arcWidth, int arcHeight);

圆角矩形不同于标准矩形，它的四角呈圆形。每一个圆角实际上就是一个1/4的椭圆形，其弧宽和弧高就是完整椭圆形的宽和高。

gc.drawRoundedRectangle(5,5,90,45,25,15)

画了一个圆角矩形，左顶角坐标值（5,5）。下面是圆角矩形的右下角放大图，其宽和高分别是25、15。 

虽然调用4次drawArc()和4次drawLine()完全可以实现一个圆角矩形。但在一些平台下，例如Windows或者Photon，SWT就可以使用非常优秀的平台API。

GC.drawOval(int x, int y, int width, int height);

一个椭圆形是画在矩形里的，所以由矩形的左顶点坐标以及宽和高来定义。定义一个正圆形同样使用这个方法。

gc.drawOval(5,5,90,45);

GC.drawArc(int x, int y, int width, int height, int startAngle, int endAngle);

一个弧形是被画在一个指明了高和宽以及左顶角x,y坐标的矩形区域内。int startAngle是个角度，是开始画弧形的位置，开始点就是此角度与X轴坐标线相交的那个点。int endAngle同样是角度，它是弧形结束的位置，道理和int startAngle相同。

gc.drawArc(5,5,90,45,90,200);

这里画了一个弧形，从90度垂线和X轴坐标相交处开始，然后持续画200度。

GC.setLineStyle(int style);

SWT.LINE_SOLID
SWT.LINE_DOT
SWT.LINE_DASH
SWT.LINE_DASHDOT
SWT.LINE_DASHDOTDOT

GC.setLineWidth(int width);

gc.setLineWidth(2);
gc.setLineWidth(4);

因为线条风格影响着所有的绘画操作，所以这也就使你可以画出不同边线风格的矩形或椭圆等图形。

gc.setLineWidth(3);
gc.drawOval(5,5,40,40);
gc.setLineWidth(1);
gc.setLineStyle(SWT.LINE_DOT);
gc.setForeground(display.getSystemColor(SWT.COLOR_BLUE));
gc.drawRectangle(60,5,60,40);

当GC的属性被改变，比如像线条的宽度、线条的风格或者是颜色，这些变化都会影响到后续的绘画操作。以上代码片段中，首先设置线条的宽度为3画了一个椭圆，随后重新设置线条属性画了一个边线是虚线的矩形。在SWT图形编程中，忘记重新设置这些字段属性的值是经常会犯的错误。

绘制文本（Drawing text）

GC之上同样可以绘制文本，文字的轮廓可通过GC的foreground color和font确定。你需要定义它的左上角坐标（就是字体的位置）以及字体的高和宽。绘制文本有两种设置方法：第一种是在drawText（）绘制 方法里直接输入文本它将处理行分隔符和tabs制表符，常用来模仿一个Label。第二种是在drawString（）绘制方法中输入字符串，没有tab 以及回车处理，常用于更加复杂的控件，就像StyledText常用于Eclipse Java editor那样。

GC.drawText(String text, int x, int y);

Font font = new Font(display,"Arial",14,SWT.BOLD | SWT.ITALIC);
// ...
gc.drawText("Hello World",5,5);
gc.setForeground(display.getSystemColor(SWT.COLOR_BLUE));
gc.setFont(font);
gc.drawText("Hello\tThere\nWide\tWorld",5,25);
// ...
font.dispose();

drawText API 支持控制转义字符，\t 就是tab，\n就是回车换行。  

GC.drawString(String text, int x, int y);

使用drawString时，tab 和回车换行转义字符没有被处理。在GC绘制时字符串所占的大小基于它的内容和GC所设置的字体。获取字符串所占宽度可以分别使用GC.stringExtent(String text)和GC.textExtent(String text)这两个方法。 它们所返回的Point的x,y坐标值分别就是宽和高。

GC.drawText(String text, int x, int y, boolean isTransparent);

drawText(String text, int x, int y)绘制的文本使用的是GC的当前foreground color。当你希望文本透过背景色在最顶层显示的画，你可设置它的isTransparent这个布尔型的参数为true。此方法在图像（image） 上绘制时特别有用。

Font font = new Font(display,"Arial",12,SWT.BOLD | SWT.ITALIC);
Image image = new Image(display,"C:/devEclipse_02/eclipse/plugins/org.eclipse.platform_2.0.2/eclipse_lg.gif");
GC gc = new GC(image);
gc.drawText("Hello World",5,5);
gc.setFont(font);
gc.setForeground(display.getSystemColor(SWT.COLOR_WHITE));
gc.drawText("Hello World",5,25,true);
gc.dispose();
image.dispose();
font.dispose();

GC.drawText(String text, int x, int y, int flags);

gc.drawImage(image,0,0);
gc.drawText("Hello\t&There\nWide\tWorld",5,5,SWT.DRAW_TRANSPARENT);
gc.drawText("Hello\t&There\nWide\tWorld",5,25,SWT.DRAW_DELIMITER | SWT.DRAW_TAB | SWT.DRAW_MNEMONIC );

" src="/CuteSoft_Client/CuteEditor/Images/anchor.gif">填充形状（Filling shapes）

GC.fillPolygon(int[]);

GC.fillRectangle(int x, int y, int width, int height);

填充矩形的时候，底部边线和右边线是不包含在内的。虽然点（5,5）被包含在填充矩形的代码中，但右下角点 95,50 (5+90 , 45+5) 不在填充区域的范围里，右下角的填充点是94,49。这不同于drawRectangle(5,5,90,45)，drawRectangle指的是整个形状，所以其右下角点是95,50。

举例说明一下，下面的代码填充了一个矩形，但是填充的颜色并没有覆盖边线。填充区域的右上角点坐标以及宽和高都减小了1像素。

gc.drawRectangle(5,5,90,45);
gc.setBackground(display.getSystemColor(SWT.COLOR_CYAN));
gc.fillRectangle(6,6,89,44);

GC.fillRoundedRectangle(int x, int y, int width, int height, int arcWidth, int arcHeight);

有点像 GC.fillRectangle(...)方法。底部边框和右边框都被排除在填充范围之内，所以底部右下角坐标变成了（94，49）而不是（95，50）

GC.fillOval(int x, int y, int width, int height);

gc.fillOval(5,5,90,45);

与其他的填充APIs相似

GC.fillArc(int x, int y, int widt4h., int height, int startAngle, int endAngle);

gc.fillArc(5,5,90,45,90,200);

fillArc(...) 方法中的参数和drawArc(...)中的参数很相似。fillArc(...)遵守着和其他填充方法一样的模式，底部边框和右边框不在填充范围之内。 

GC.fillGradientRectangle(int x, int y, int width. int height, vertical boolean);

对矩形进行由前景色到背景色的渐变填充。Vertical为true表示垂直渐变，反之则表示水平渐变。

gc.setBackgrouind(display,getSystemColor(SWT.COLOR_BLUE));
gc.fillGradientRectangle(5,5,90,45,false);

水平渐变从左边的黑色前景色开始向右边蓝色背景色变化。正如其他的填充方法，底部和右边框是被排除在外的，所以底部右下角会由1像素插入。 

gc.setBackground(display.getSystemColor(SWT.COLOR_BLUE));
gc.setForeground(display.getSystemColor(SWT.COLOR_CYAN));
gc.fillGradientRectangle(5,5,90,45,true);

垂直渐变从上而下，由前景色向背景色变化。 

异或（XOR）

shell.setBackground(display.getSystemColor(SWT.COLOR_WHITE));
// ...
gc.setBackground(display.getSystemColor(SWT.COLOR_BLUE));
gc.fillRectangle(5,5,90,45);
gc.setXORMode(true);
gc.setBackground(display.getSystemColor(SWT.COLOR_WHITE));
gc.fillRectangle(20,20,50,50);
gc.setBackground(display.getSystemColor(SWT.COLOR_RED));
gc.fillOval(80,20,50,50);

被填充的背景色是白色的（255,255,255）矩形，当在上面覆盖一层蓝色（0,0,255），或（XOR）后的颜色就是黄色（25,255,0）。白背景的部分和黄色异或后就成了黑色（0,0,0）。一个红色背景的圆，它覆盖在蓝色上面异或（XOR）后就成了紫色（255,0,255）。盖在白色上面异或（XOR）后就成了青色（0,255,255）。

（译者注： SWT API帮助文档中对setXORMode（）方法是这样描述的“此方法在某些平台下是不被支持的，显著表现的有Mac OS X，如果你希望你的代码可运行在所有平台，应该尽量避免使用此方法。”）

" src="/CuteSoft_Client/CuteEditor/Images/anchor.gif">绘制图像（Drawing Images）

Image image = new Image(display,"C:/eclipse/eclipse/plugins/org.eclipse.platform_2.0.2/eclipse_lg.gif");

GC.drawImage(Image image, int x, int y);

gc.drawImage(image,5,5);

GC.drawImage(Image image, int srcX, int srcY, int srcWidth, int srcHeight, int dstX, int dstY, int dstWidth, int dstHeight);

根据原始图像的宽度和高度，不但可以绘画出不同大小的图像还可以只绘画原始图像的局部。

src 参数联系图像本身，要画完整的图像，srcX、srcY 使用0,0，宽高就使用图像的宽高。dst 参数表示图像被画在哪里以及画成多大。原始图像的大小是115,164，若要把图像宽度增加2倍，高度减低一半，可以使用下面的语句：

gc.drawImage(image,0,0,115,164,5,5,230,82);

使用src坐标可以使你只画出图像的局部。例如，如果你只想画出图像的右上角部分，你可以设定src坐标为20,0，宽度和高度为95，82。下面的代码中dst 宽度和高度同样使用95,82。通过指定不同大小就可以对图像进行拉长或收缩操作。

gc.drawImage(image,20,0,95,82,5,5,95,82);

还能完成一些其他的图像效果，比如图像透明度、animation以及alpha通道。但这些不属于本篇的讨论范围，我希望在以后的文章中能够涉及到这些东西。

总结（Conclusion）

    恐怕现在用过电脑的人，一定都知道大部分带文本编辑功能的软件都有一个快捷键ctrl+f 吧（比如word）。这个功能主要来完成“查找”，“替换”和“全部替换”功能的，其实这就是典型的模式匹配的应用，即在文本文件中查找串。

1.模式匹配

    模式匹配的模型大概是这样的：给定两个字符串变量S和P，其中S成为目标串，其中包含n个字符，P称为模式串，包含m个字符，其中m<=n。从S的 给定位置（通常是S的第一个位置）开始搜索模式P。如果找到，则返回模式P在目标串中的位置（即：P的第一个字符在S中的下标）。如果在目标串S中没有找 到模式串P，则返回-1.这就是模式匹配的定义啦，下面来看看怎么实现模式匹配算法吧。

2.朴素的模式匹配

    朴素的模式匹配算法非常简单，容易理解，大概思路是这样的：从S的第一个字符S0开始，将P中的字符依次和S中字符比较，若S0=P0 && …… && Sm-1 = Pm-1，则证明匹配成功，剩下的匹配无需进行了，返回下标0。若在某一步Si != Pi 则P中剩下的字符也不用比较了，不可能匹配成功了，然后从S中第二个字符开始与P中第一个字符进行比较，同理，也是知道Sm = Pm-1或者找到某个i使得Si != S-1为止。依次类推若知道以S中第n-m个开始字符为止，还没有匹配成功则证明S中不存模式P。（想想为什么这里强调是n-m）这个代码实现应该是非常 简单的，具体开始参考strstr函数的内部实现。可以看看百度百科，给个链接http://baike.baidu.com/view/745156.htm，这里不写出来了，还得赶紧进入正题KMP呢。

3.快速模式匹配算法（KMP）

    朴素的模式匹配效率不高的主要原因是进行了重复的字符比较。下一次比较和上一次比较没有任何的联系，是朴素模式匹配的缺点，其实上一次比较的比较结果是可 以利用的，这就产生了快速模式匹配。在朴素的模式匹配中，目标串S的下标移动是一步一步的，这其实并不好，移动步数没有必要为1。

　　现在不妨假设，当前匹配情况是这样的：S0 …… St St+1 …… St+j  与 P0 P1…… Pj ，现在正在尝试匹配的字符是St+j+1和Pj+1，并且St+j+1 != Pj+1，言外之意就是说S St+1……St+j和P0 P1……Pj是完全匹配的。那么这个时候，S中下一次匹配开始位置应该是什么呢？？按照朴素的模式匹配，下次比较应该从St+1开始，并且令St+1和 P0比较，但是在快速模式匹配中并不是这样，快速模式匹配选择St+j+1和Pk比较，K是什么呢？K是这样的一个值，使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配，不妨设k=next[j]，因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要进行匹配的两个字符应为St+j+1和Pk+1。S和P都没有回溯到下标0在进行比较，这就是KMP之所以快的原因 啦。

    现在关键问题来了，这个K怎么能得到呢？如果得到这个K值复杂度高，那这个思路就不好了，其实这个K呢，只和模式串P有关系，并且要求m个k，k = next[j]，因此只要算一次存储到next数组中就可以了，并且时间复杂度和m有关系（线性关系）。看看具体怎么求next数组的值，即求k。

用归纳法求next[]：设next(0) = -1，若已知next(j) = k，欲求得next[j+1]。

（1）如果Pk+1 = Pj+1，显然next[j+1] = k+1.如果Pk+1 != Pj+1，则next[j+1] < next[j]，于是寻找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。也就是说h = next(k);看出来了吧，这是个迭代的过程。（也就是以前的结果对求以后的值有用）

（2）如果不存这样的h，说明P0 P1……Pj+1中没有前后相等的子串，因此next[j+1] =-1.

（3）如果存在这样的h，继续检验Ph和Pj是否相等。知道找到这中相等的情况，或者确定为-1求next[j+1]的过程结束。

看看实现的代码：

View Code

 1 int next[20] ={0};
 2 //注意返回结果是一个数组next，保存m个k值得地方，即若next[j]=k
 3 //则str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j]
 4 //这样当des[t+j+1]和pat[j+1]匹配失败时，下一个匹配位置为des[t+j+1]和next[j]+1
 5 void Next(char str[],int len)
 6 {
 7     next[0] = -1;
 8     for(int j = 1 ; j < len ; j++)
 9     {
10         int i = next[j-1];
11         while(str[j] != str[i+1] && i >= 0)//迭代的过程
12         {
13             i = next[i];
14         }
15         if(str[j] == str[i+1])
16         {
17             next[j] = i+1;
18         }
19         else
20         {
21             next[j] = -1;
22         }
23     }
24 }

现在有了next数组保存的k值，就可以实现KMP算法了：

View Code

 1 View Code 
 2 
 3 //des是目标串，pat是模式串，len1和len2是串的长度
 4 int kmp(char des[],int len1,char pat[],int len2)
 5 {
 6     Next(str2,len2);
 7     int p=0,s=0;
 8     while(p < len2  && s < len1)
 9     {
10         if(pat[p] == des[s])
11         {
12             p++;s++;
13         }
14         else
15         {
16             if(p==0) 
17             {
18                 s++;//若第一个字符就匹配失败，则从des的下一个字符开始
19             }
20             else
21             {
22                 p = next[p-1]+1;//用失败函数确定pat应回溯到的字符
23             }
24         }
25     }
26     if(p < len2)//整个过程匹配失败
27     {
28         return -1;
29     }
30     return s-len2;
31 }

时间复杂度：
　　对于Next函数近似接近O（m），KMP算法的时间复杂度为O(n)，所以整个算法的时间复杂度为O(n+m)

空间复杂度：

　　多引入了O（m）的空间复杂度。

4.应用KMP的一道面试题 

　　给定两个字符串是s1和s2，要判定s2是否能够被s1做循环移位得到的字符串包含。例如s1=AABCD，s2 =CDAA，返回true，因为s1循环移位可以变成CDAAB。给定s1=ACBD和s2=ACBD则返回false。

      分析：不难发现对s2移位得到的字符串都将是字符串s1s1的子串，如果s2可以有s1循环移位得到，那么s2一定是s1s1的子串，这时KMP算法是不是就很管用了呢。

思考：有没有比KMP更好的思路呢？？

OpenEjb使用笔记--让Tomcat可以部署EJB

1  OpenEJB概述

      Tomcat本不支持部署EJB，通过向其安装OpenEjb，可使其支持。

2  安装

2.1 下载

http://www.apache.org/dyn/closer.cgi/openejb/3.1.3/openejb.war

2.2  安装

1、将下载的openejb.war 放在Tomcat的安装目录 webapps下。

2、启动Tomcat。

3、在IE中输入：http://localhost:8080/openejb 回车后显示如下信息：

OK！安装成功，就这么简单！

4、测试一下：http://localhost:8080/openejb/viewjndi.jsp

3  部署

像往常一样，开发一个Ejb工程。

接口:

实现类：

      将此EJB工程打成jar包，比如放在D:\Tomcat\ejb下。注：“D:\Tomcat\ejb”是我自己建的。

     然后打开：Tomcat\conf\openejb.xml,将</openejb>前的内容改为：

重启Tomcat，在浏览器输入：http://127.0.0.1:8089/openejb/invokeobj.jsp

点击其中的”Browse for an EJB”，转到如下界面：

如果在其中能看到自己的EJB Bean，那就成功了。

4  客户端调用

按照官方给出的说明：http://openejb.apache.org/3.0/clients.html，此处使用“Remote Client with HTTP (in tomcat)”方式。对上面部署的EJB调用的客户端代码如下：

简介

Eclipse 平台允许使用可插入组件 —— 插件 —— 帮助创建丰富的图形用户界面（graphical user interface，GUI）应用程序。例如，插件可以向 GUI 提供视图。但是，在现实的应用程序中，UI 视图不能是孤立的。它们需要根据其他视图的状态进行交互和对本身进行更新。

一个简单的例子是描述世界各地的主要旅游目的地的 GUI 应用程序。这个 GUI 可能有一个 Select City 视图，用于显示旅游景点和公共交通信息。

本文介绍在 Eclipse 中结合视图的方式以及如何对其他视图的状态做出响应。还讨论链接视图方式在哪些情况下可能比其他方式合适。

Eclipse 开发人员可以依赖以下方法对视图进行链接：

1. 选择提供器 - 选择监听器（selection provider-selection listener）模式，从而让视图对其他视图中的选择做出反应
2. IAdaptable 接口，与某些事件结合使用
3. 属性改变监听器，它允许视图将属性改变事件告之已注册的监听器

选择提供器 - 选择监听器范型

选择提供器 - 选择监听器模式能够方便地创建对其他视图中的改变做出响应的视图。例如，当用户点击代表城市名的 UI 项时，另一个视图可能需要显示这个城市的景点详情。这样的视图可以使用 UI 选择对象（可能是代表城市名的字符串对象）中包含的信息，并使用它从模型中获取和显示其他信息。

视图应该能够识别并利用 UI 选择事件。org.eclipse.ui.ISelectionListener 是接收 UI 选择事件的监听器接口。选择监听器必须注册到工作台页面。工作台页面实现 org.eclipse.ui.ISelectionService 接口定义的服务，从而将 UI 选择事件告之监听器。选择监听器必须注册到选择服务。

用于显示可选择的 UI 项的视图还应该能够公布 UI 选择。视图通过将 “选择提供器” 注册到它们各自的工作台站点来实现这一点。Eclipse 中的每个 UI 部分通过 org.eclipse.ui.IWorkbenchPartSite 引用与工作台站点联络。选择提供器注册到工作台站点。

在使用选择提供器 - 选择监听器模式链接视图时，视图可以将本身作为监听器添加到工作台页面，而希望公布选择的其他视图必须将选择提供器添加到它们各自的工作台站点。org.eclipse.ui.ISelectionListener 接口如下所示。

要使视图能够监听选择改变，视图必须实现 ISelectionListener 接口并必须将自己注册到工作台页面。清单 1 显示一个例子。

使用 UI 选择的更好的方法是，将消费者视图作为监听器注册到特定的视图部分。正如在下面的例子中可以看到的，源视图部分的视图 ID 在注册选择监听器期间被作为一个参数。

这种方式可以避免对消费者视图进行多余的回调，如果视图被注册为非特定的监听器，就会出现这种情况。

清单 2 中的代码片段显示一个视图的 createPartControl() 方法，这个方法创建一个 JFace TableViewer 并将它作为选择提供器添加到工作台站点。这些代码使 TableViewer 中的任何 UI 选择改变能够传播到页面，并最终传播到对这种事件感兴趣的消费者视图。

这个视图将它创建的 JFace TableViewer 注册为选择提供器有两个原因：

1. 这个视图打算使用这个 TableViewer 显示信息，而且用户将与 TableViewer 进行交互。
2. TableViewer 实现了选择提供器接口并能够向工作台部分站点传播选择事件。

因为 JFace 查看器是选择提供器，所以在大多数情况下就不必创建选择提供器了。视图只需使用众多的 JFace 查看器之一来显示信息，并将 JFace 查看器注册为选择提供器。

另一种链接方式

某些情况需要另一种视图链接方式：

1. 信息量可能太大，由于内存使用量增加，UI 选择对象无法有效地容纳它。
2. 视图可能希望公布其他信息，而不只是公布可视化选择信息。公布的信息可能是根据选择进行某些后期处理的结果。
3. 视图可能希望使用来自另一个插件的信息，而这个插件可能根本没有提供视图（使用包含的 JFace 查看器）。在这种情况下，使用基于 UI 选择的链接是不可能的。

可以使用 org.eclipse.core.runtime.IAdaptable 接口来缓解第一个问题，这个接口使选择对象能够在需要时传播更多信息。第二个和第三个问题需要用手工方式解决，属性改变监听器模式是合适的解决方案。

使用 IAdaptable 接口

实现 IAdaptable 接口的类能够动态地返回某些类型的适配器，然后可以使用这些适配器获取更多信息。如果查看器中的选择对象实现了 IAdaptable 接口，那么根据它们可以返回的适配器类型，可以有效地获取更多信息或相关信息。org.eclipse.core.runtime.IAdaptable 接口如下所示。

显然，调用者应该知道它期望选择返回的适配器接口类型。考虑一个 JFace TreeViewer，它在一个单层的树中显示城市。代表城市的对象是 CityClass 类型的。CityClass 对象应该包含关于此城市的基本信息，并只在需要时返回详细信息。在清单 3 中要注意，CityClass 支持的适配器类型使调用者能够在需要时获得更多信息。

熟悉 Eclipse IDE 工作台的开发人员都了解 Outline 视图，这个视图提供了编辑器中打开的文件的结构化视图。这个 Outline 视图展示了 IAdaptable 接口如何与某些事件类型结合使用，从而有效地根据其他视图的内容对视图进行初始化。编辑器必须为用户打开的文件创建一个 Content Outline 页面。Content Outline 页面符合 IContentOutlinePage 接口。编辑器还必须实现 IAdaptable 接口，这样就能够向编辑器查询 IContentOutlinePage 类型的适配器。使用这个适配器来获取和显示文件的大纲信息。

IAdaptable 接口的另一个例子是 Properties 视图。Properties 视图跟踪对活动部分的选择，并调用当前选择对象上的 getAdapter 方法。查询的适配器类型是 IPropertySource。然后，Properties 视图使用 IPropertySource 适配器来获取要显示的信息。

在这些视图链接例子中，应用程序在接到 Selection Changed 或 Part Activation 通知时，通过 IAdaptable 获取信息。因此，如果选择对象实现了 IAdaptable，那么与从选择对象本身获取的信息量相比，用户可以通过适配器获得多得多的信息。

属性改变监听器范型

可以使用属性改变监听器类型的交互来解决前面提到的另外两个问题：视图如何使用来自未提供视图的插件的信息，以及视图如何公布在可视化选择之后某些处理所生成的信息？

可以建立一个插件来接受属性改变监听器的注册，并在需要时通知注册的监听器。应用程序可以将定制的事件告之监听器，事件中还可以包含要共享的信息。

与选择提供器的情况不同，属性改变提供器不需要实现特定的接口。您必须决定将监听器注册到提供器的语义。清单 4 中的代码片段是一些方法，它们允许在属性提供器视图或插件类中添加或删除属性改变监听器。

属性提供器应该使用 org.eclipse.jface.util.PropertyChangeEvent 来创建一个可以有效填充和传播的事件。另外，属性提供器要负责维护监听器列表并对它们进行回调。

作为一个例子，请考虑一个每小时调用 World Weather Web Service 来查询主要城市的气象的插件，它要使这些信息可供其他插件和视图使用。CityWeatherPlugin 可以公开一个称为 CitiesWeatherXML 的属性，消费者可以将本身作为 PropertyChange 监听器注册到 CityWeatherPlugin。为此，监听器必须了解 CityWeatherPlugin 中的注册方法，这样才能将本身注册为气象数据事件的监听器。CityWeatherPlugin 应该跟踪并通知监听器。它使用 PropertyChangeEvent 向监听器提供数据。

属性改变监听器必须实现 org.eclipse.jface.util.IPropertyChangeListener 接口，以便允许属性改变提供器对它进行回调。这个接口有一个方法


这种方式的灵活性在于，应用程序可以在需要时通知监听器，并根据各种场景向它们传递信息。传递的信息不必直接与 UI 选择相关；这些信息可以是某些后期处理的结果。另外，它可以与其他后台作业的状态相关，或者是定期从模型中获取的最新信息。例如，City Selector View 可能不只是传播选择的城市，还使用 PropertyChange 范型将当前选择的城市的气象信息异步地传播给其他消费者。

结束语

本文讨论了使视图相互协作和响应的各种方式。如果 UI 选择本身不够，可以使用 IAdaptable 接口加强它们。属性改变监听器也为满足非 UI 场景提供了更大的灵活性。

通过查看jquery API，发现jquery还有一个 complete对象，是请求完成后回调函数 (请求成功或失败之后均调用)。 同时有两个参数XMLHttpRequest, textStatus。所以，我们只需要在请求完成后，将传回的XMLHttprequest对象手工回收即可，代码如下：