貼代碼不說話:
/**
* <br>
* 標題: 關于Nested Sets and Materialized Path的java實現<br>
* 功能概要: <br>
* 版權: cityyouth.cn (c) 2005 <br>
* 公司:上海城市青年網 <br>
* 創建時間:2006-1-25 <br>
* 修改時間: <br>
* 修改原因：<br>
* <p>
* path x+y bin(numer)<br>
* <root> 1/1 1<br>
* 1 3/2 11<br>
* 1.1 7/4 111<br>
* 1.1.1 15/8 1111<br>
* 1.1.1.1 31/16 11111<br>
* 1.2 11/8 1011<br>
* 1.2.1 23/16 10111<br>
* 1.3 19/16 10011<br>
* 1.3.1 39/32 100111<br>
* 2 3/4 011<br>
* 2.1 7/8 0111<br>
* 2.1.1 15/16 01111<br>
* 2.1.2 27/32 011011<br>
* 2.2 11/16 01011<br>
* 2.2.1 19/32 010111<br>
* 3 3/8 0011<br>
* 3.1 7/16 00111<br>
* 4 3/16 00011
* </p>
*
* @author 張偉
* @version 1.0
*/
public class NestedSetsUtil {
public static double x_numer(double numer, double denom) {
double ret_num = numer + 1;
double ret_den = denom * 2;
while (Math.floor(ret_num / 2) == ret_num / 2) {
ret_num = ret_num / 2;
ret_den = ret_den / 2;
}
return ret_num;
}
public static double x_denom(double numer, double denom) {
double ret_num;
double ret_den;
ret_num = numer + 1;
ret_den = denom * 2;
while (Math.floor(ret_num / 2) == ret_num / 2) {
ret_num = ret_num / 2;
ret_den = ret_den / 2;
}
return ret_den;
}
public static double y_numer(double numer, double denom) {
double num;
double den;
num = x_numer(numer, denom);
den = x_denom(numer, denom);
while (den < denom) {
num = num * 2;
den = den * 2;
}
num = numer - num;
while (Math.floor(num / 2) == num / 2) {
num = num / 2;
den = den / 2;
}
return num;
}
public static double y_denom(double numer, double denom) {
double num;
double den;
num = x_numer(numer, denom);
den = x_denom(numer, denom);
while (den < denom) {
num = num * 2;
den = den * 2;
}
num = numer - num;
while (Math.floor(num / 2) == num / 2) {
num = num / 2;
den = den / 2;
}
return den;
}
public static double parent_numer(double numer, double denom) {
double ret_num;
double ret_den;
if (numer == 3) {
return Double.NaN;
}
ret_num = (numer - 1) / 2;
ret_den = denom / 2;
while (Math.floor((ret_num - 1) / 4) == (ret_num - 1) / 4) {
ret_num = (ret_num + 1) / 2;
ret_den = ret_den / 2;
}
return ret_num;
}
public static double parent_denom(double numer, double denom) {
double ret_num;
double ret_den;
if (numer == 3) {
return Double.NaN;
}
ret_num = (numer - 1) / 2;
ret_den = denom / 2;
while (Math.floor((ret_num - 1) / 4) == (ret_num - 1) / 4) {
ret_num = (ret_num + 1) / 2;
ret_den = ret_den / 2;
}
return ret_den;
}
public static double sibling_number(double numer, double denom) {
// 修正了驗證3/4,1/1等
/*
* if (numer == 3) { return Double.NaN; }
*/
double ret_num = (numer - 1) / 2;
double ret_den = denom / 2;
double ret = 1;
while (Math.floor((ret_num - 1) / 4) == (ret_num - 1) / 4) {
if (ret_num == 1 && ret_den == 1)
return ret;
ret_num = (ret_num + 1) / 2;
ret_den = ret_den / 2;
ret = ret + 1;
}
return ret;
}
private static String path_recur(double numer, double denom) {
if (Double.isNaN(numer))
return "";
return path_recur(parent_numer(numer, denom), parent_denom(numer, denom)) + "."
+ (int) sibling_number(numer, denom);
}
public static String path(double numer, double denom) {
String result = path_recur(numer, denom);
if (result.length() > 0)
return result.substring(1, result.length());
return result;
}
public static double distance(double num1, double den1, double num2, double den2) {
if (Double.isNaN(num1))
return -999999;
if (num1 == num2 && den1 == den2)
return 0;
return 1 + distance(parent_numer(num1, den1), parent_denom(num1, den1), num2, den2);
}
public static double child_numer(double num, double den, double child) {
return num * Math.pow(2d, child) + 3d - Math.pow(2d, child);
}
public static double child_denom(double num, double den, double child) {
return den * (double) Math.pow(2, child);
}
public static double path_numer(String path) {
double num = 1;
double den = 1;
String postfix = "." + path + ".";
String sibling;
while (postfix.length() > 1) {
sibling = postfix.substring(1, postfix.indexOf(".", 2));
postfix = postfix.substring(postfix.indexOf(".", 2), postfix.length()
- postfix.indexOf(".", 2) + 2);
num = child_numer(num, den, Integer.parseInt(sibling));
den = child_denom(num, den, Integer.parseInt(sibling));
}
return num;
}
public static double path_denom(String path) {
double num;
double den;
String postfix;
String sibling;
num = 1;
den = 1;
postfix = "." + path + ".";
while (postfix.length() > 1) {
sibling = postfix.substring(1, postfix.indexOf(".", 2));
postfix = postfix.substring(postfix.indexOf(".", 2), postfix.length()
- postfix.indexOf(".", 2) + 2);
num = child_numer(num, den, Double.parseDouble(sibling));
den = child_denom(num, den, Double.parseDouble(sibling));
}
return den;
}
public static void main(String[] args) {
// 說明5-8,19-32是39/32的x和y坐標,39/32 is the node 1.3.1
// System.out.println(x_numer(39d, 32d) + "/" + x_denom(39d, 32d));
// System.out.println(y_numer(39d, 32d) + "/" + y_denom(39d, 32d));
// System.out.println(5d / 8d + 19d / 32d);
// System.out.println(39d / 32d);
// 27/32 is the node 2.1.2, 那么 7/8 is 2.1,查找父節點成功
// System.out.println(parent_numer(27d, 32d) + "/" + parent_denom(27d,
// 32d));
// 開始查找那些是他的兄弟
// System.out.println(sibling_number(3d, 2d));
// System.out.println(sibling_number(3d, 4d));
// System.out.println(sibling_number(15d,16d));
// System.out.println(path_numer("1.1.7")+"/"+path_denom("1.1.7"));
// 計算節點的路徑
// System.out.println(path(15d, 16d));
/*
* System.out.println(distance(27d, 32d, 3d, 4d));
* System.out.println(child_numer(3d, 2d, 3d) + "/" + child_denom(3d,
* 2d, 3d));
* System.out.println(path_numer("2.1.1")+"/"+path_denom("2.1.1"));
*/
// System.out.println(".2.1.3.".substring(1,".2.1.3".indexOf(".",2)));
// System.out.println(".2.1.3.".substring(".2.1.3.".indexOf(".",2),".2.1.3.".length()-".2.1.3.".indexOf(".",2)+1));
String ss = "1.2";
System.out.println((int) path_numer(ss) + "/" + (int) path_denom(ss));
System.out.println(path(path_numer(ss), path_denom(ss)));
}
}
posted on 2006-01-26 11:52
老妖 閱讀(611)
評論(0) 編輯 收藏