2013年5月2日 星期四

[ Java 代碼範本 ] JExcel - Writing Spreadsheets

Preface: 
This section describes how to write out simple spreadsheet data without any formatting information via open source library JExcelApi, such as fonts or decimal places. Similarly to reading a spreadsheet, the first step is to create a writable workbook using the factory method on the Workbook class. 
  1. import java.io.File;   
  2. import java.util.Date;   
  3. import jxl.*;   
  4. import jxl.write.*;   
  5.   
  6. ...   
  7.   
  8. WritableWorkbook workbook = Workbook.createWorkbook(new File("output.xls"));  
This creates the workbook object. The generated file will be located in the current working directory and will be called "output.xls". The API can also be used to send the workbook directly to an output stream eg. from a web server to the user's browser. If the HTTP header is set correctly, then this will launch Excel and display the generated spreadsheet. 

The next stage is to create sheets for the workbook. Again, this is a factory method, which takes the name of the sheet and the position it will occupy in the workbook. The code fragment below creates a sheet called "First Sheet" at the first position: 
  1. WritableSheet sheet = workbook.createSheet("First Sheet", 0);  
Now all that remains is to add the cells into the worksheet. This is simply a matter of instantiating cell objects and adding them to the sheet. The following code fragment puts a label in cell A3, and the number 3.14159 in cell D5. 
  1. Label label = new Label(0, 2, "A label record");   
  2. sheet.addCell(label);   
  3.   
  4. Number number = new Number(3, 4, 3.1459);   
  5. sheet.addCell(number);  
There are a couple of points to note here. Firstly, the cell's location in the sheet is specified as part of the constructor information. Once created, it is not possible to change a cell's location, although the cell's contents may be altered. The other point to note is that the cell's location is specified as (column, row). Both are zero indexed integer values - A1 being represented by (0,0), B1 by (1,0), A2 by (0,1) and so on. 

Once you have finished adding sheets and cells to the workbook, you call write() on the workbook, and then close the file. This final step generates the output file (output.xls in this case) which may be read by Excel. If you call close() without calling write() first, a completely empty file will be generated. 
  1. ...   
  2. // All sheets and cells added. Now write out the workbook   
  3. workbook.write();   
  4. workbook.close();  
 

Adding Format Information: 
The previous section illustrates the fundamentals of generating an Excel compatible spreadsheet using the JExcelApi. However, as it stands Excel will render the data in the default font, and will display the numbers to 3 decimal places. In order to supply formatting information to Excel, we must make use of the overloaded constructor, which takes an additional object containing the cell's formatting information (both the font and the style). 

The code fragment below illustrates creating a label cell for an arial 10 point font. 
  1. // Create a cell format for Arial 10 point font   
  2. WritableFont arial10font = new WritableFont(WritableFont.ARIAL, 10);   
  3. WritableCellFormat arial10format = new WritableCellFormat (arial10font);   
  4.   
  5. // Create the label, specifying content and format   
  6. Label label2 = new Label(1,0, "Arial 10 point label", arial10format);   
  7. sheet.addCell(label2);  
Cell formats objects are shared, so many cells may use the same format object, eg. 
  1. Label label3 = new Label(2, 0, "Another Arial 10 point label", arial10format);   
  2. sheet.addCell(label3);  
This creates another label, with the same format, in cell C1. 

Because cell formats are shared, it is not possible to change the contents of a cell format object. (If this were permitted, then changing the contents of the object could have unforeseen repurcussions on the look of the rest of the workbook). In order to change the way a particular cell is displayed, the API does allow you to assign a new format to an individual cell. 

The constructors for the WritableFont object have many overloads. By way of example, the code fragment below creates a label in 16 point Times, bold italic and assigns it to position D1. 
  1. // Create a cell format for Times 16, bold and italic   
  2. WritableFont times16font = new WritableFont(WritableFont.TIMES, 16, WritableFont.BOLD, true);   
  3. WritableCellFormat times16format = new WritableCellFormat (times16font);   
  4.   
  5. // Create the label, specifying content and format   
  6. Label label4 = new Label(3,0, "Times 16 bold italic label", times16format);   
  7. sheet.addCell(label4);  
 

Formatting Numbers: 
Number formatting information may be passed to the cell format object by a similar mechanism to that described for fonts. A variety of predefined number formats are defined statically. These may be used to format numerical values as follows: 
  1. WritableCellFormat integerFormat = new WritableCellFormat (NumberFormats.INTEGER);   
  2. Number number2 = new Number(0, 4, 3.141519, integerFormat);   
  3. sheet.addCell(number2);   
  4.   
  5. WritableCellFormat floatFormat = new WritableCellFormat (NumberFormats.FLOAT);   
  6. Number number3 = new Number(1, 4, 3.141519, floatFormat);   
  7. sheet.addCell(number3);  
The above code inserts the value 3.14159 into cells A5 and B5, using the preset integer and floating points format respectively. When Excel renders these cells, A5 will display as "3" and B5 will display as "3.14", even though both cells contain the same floating point value. 

It's possible for a user to define their own number formats, by passing in a number format string. The string passed in should be in the same format as that used by thejava.text.DecimalFormat class. To format a number to display up to five decimal places in cell C5, the following code fragment may be used: 
  1. NumberFormat fivedps = new NumberFormat("#.#####");   
  2. WritableCellFormat fivedpsFormat = new WritableCellFormat(fivedps);   
  3. Number number4 = new Number(2, 4, 3.141519, fivedpsFormat);   
  4. sheet.addCell(number4);  
It is, of course, also possible to specify font information as well eg. to display the same value in the 16 point times bold font defined earlier we can write: 
  1. WritableCellFormat fivedpsFontFormat = new WritableCellFormat (times16font, fivedps);   
  2. Number number5 = new Number(3, 4, 3.141519, fivedpsFontFormat);   
  3. sheet.addCell(number5);  
 

Formatting Dates: 
Dates are handled similarly to numbers, taking in a format compatible with that used by the java.text.SimpleDateFormat class. In addition, several predefined date formats are specified in the jxl.write.DateFormat class. 

As a brief example, the below code fragment illustrates placing the current date and time in cell A7 using a custom format: 
  1. // Get the current date and time from the Calendar object   
  2. Date now = Calendar.getInstance().getTime();   
  3. DateFormat customDateFormat = new DateFormat ("dd MMM yyyy hh:mm:ss");   
  4. WritableCellFormat dateFormat = new WritableCellFormat (customDateFormat);   
  5. DateTime dateCell = new DateTime(0, 6, now, dateFormat);   
  6. sheet.addCell(dateCell);   
 

As with numbers, font information may be used to display the date text by using the overloaded constructors on WritableCellFormat. 


For a more extensive example of writing spreadsheets, the demonstration program Write.java should be studied. In addition to the functionality described above, this program tests out a variety of cell, formatting and font options, as well as displaying cells with different background and foreground colours, shading and boundaries.

[ Alg info ] Dijkstra’s algorithm (shortest path problem)

Preface: 
最短路徑問題是圖論研究中的一個經典演算法問題, 旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。 演算法具體的形式包括: 
* 確定起點的最短路徑問題 - 即已知起始結點,求最短路徑的問題。適合使用 Dijkstra演算法。
* 確定終點的最短路徑問題 - 與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
* 確定起點終點的最短路徑問題 - 即已知起點和終點,求兩結點之間的最短路徑。
* 全局最短路徑問題 - 求圖中所有的最短路徑。適合使用 Floyd-Warshall演算法。

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」, 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有: 
* Dijkstra演算法
* A*演算法
* Bellman-Ford演算法
* SPFA演算法 (Bellman-Ford演算法的改進版本)
* Floyd-Warshall演算法
* Johnson演算法
* Bi-Direction BFS演算法

Description: 
在一個有向圖形 G=(V,E), G 中的每一個邊都有一個比例常數 W(Weight) 與之對應, 如果想求 G 圖形中某一點V0 到其他頂點的最少 W 總和之值, 這類問題就稱為最短路徑問題 (The shortest path problem). 這裡首先討論單點對全部頂點的最短距離, 而一個頂點到多個頂點通常使用 Dijkstra 演算法求得. 接著會在 Dijkstra's algorithm 用到下面的變數: 
* S: 用來存放處理過的 vertex
* V: Graph 的 vertex 集合
* Q: 存放待處理的 vertex. Q = V - S
* u,v: 過程中代表 edge 的變數
* v.d: 用來記錄從 source vertex 到該 vertex 的最短距離
* v.π: 用來記錄從 source vertex 走到該 vertex 的路徑, 離 vertex 最近的 vertex.

Dijkstra’s algorithm: 
首先來看看這個演算法的 pseudo code: 
  1. DIJKSTRA(G, w, s)  
  2. 1 INITIALIZE-SINGLE-SOURCE(G, s)  
  3. 2 S = ∅  
  4. 3 Q = G.V  
  5. 4 while Q != ∅  
  6. 5     u = EXTRACT-MIN(Q)  
  7. 6     S = S ∪ {u}  
  8. 7     for each vertex v ∈ G.Adj[u ]  
  9. 8         RELAX(u,v, w)  
接著簡單說明該 pseudo code: 
1. INITIALIZE-SINGLE-SOURCE(G, s) 是將 G 中的 vertex 進行初始化 v.d=∞, v.π=nil, s.d=0 (v 代表 graph 中的所有 vertex, s 則是 source vertex)
2. 初始集合 S 為空集合
3. 將 G 中的所有 vertex 加到集合 Q
4. while Q != ∅ - 接著每次處理一個 Q 中的 vertex 直到 Q 為空集合.
5. u = EXTRACT-MIN(Q) - 從 Q 中取出一個 v.d 為最小的 vertex.
6. S = S ∪ {u} - 將取出的 vertex u 加到集合 S
7. for each vertex v ∈ G.Adj[u ] - 將取出的 vertex 重新計算它走得到的 vertex 的最短距離(不在 S 集合中)
8. RELAX(u, v, w) - 將新的計算結果更新到 vertex 並將目前 vertex 加到 S 集合

Example: 
1. 接著我們來看一個範例, 假設有下面 Graph, 我們要計算從 vertex 0 到每一個 vertex 的最短距離. 所以一開始處理 vertex 0 後 S={"0"} ; Q={"1","2","3","4","5"}. 因為 vertex 3 距離最短 (v.d=10), 故取它當作下一個處理的 vertex 
 

2. 在處理 vertex 3 時, 發現原本 vertex 4 的最短路徑為 ∞ > (到 vertex 3 最短路徑 = 10) + (vertex 3 到 vertex 4 的 cost = 15)=25, 故更新 vertex 4 的最短距離 (v.d=25). 此時 S={"0", "3"} ; Q={"1","2","4","5"}, 因為 vertex 4 距離最短, 故取它當作下一個處理的 vertex: 
 

3. 在處理 vertex 4 時, 發現原本 vertex 1 的最短路徑為 50 > (到 vertex 4 最短路徑 = 25) + (vertex 4 到 vertex 1 的 cost = 20)=45, 故更新 vertex 1 的最短距離 (v.d=45). 此時 S={"0", "3", "4"} ; Q={"1","2","5"}, 因為 vertex 1 與 vertex 2 距離最短, 而我們取 vertex 1 作下一個處理: 
 

4. 在處理 vertex 1 時, 唯一會碰到不屬於集合 S 的 vertex 2 並不會使原先 vertex 2 最短路徑變短 ((45+10=55)>45). 此時 S={"0", "1", "3", "4"} ; Q={"2","5"}, 因為 vertex 2 距離最短, 故取它當作下一個處理的 vertex: 
 

5. 在處理 vertex 2 時並部會碰到任何不屬於集合 S 的 vertex. 故不做任何處理; 同樣的剩下的 vertex5 也是如此. 故此時集合 Q 已經成為空集合並結束整個演算法. 
 

Supplement: 
* [ Data Structures with Java ] Section 25.5 : Dijkstra's Minimum-Path Algorithm 
* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (單點對全部頂點) 
* NTU 2013 course - DSA : 4/30 Graph3

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...