圖形上下文導論（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對象手工回收即可，代碼如下：