关于Nested Sets and Materialized Path的java实现

zww80216

浏览: 47102 次
性别:
来自: 上海

最近访客更多访客>>

yesorno_510

gauss2008

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

Java

贴代码不说话:

/**
* 
* 标题: 关于Nested Sets and Materialized Path的java实现 
* 功能概要: 
* 版权: cityyouth.cn (c) 2005 
* 公司:上海城市青年网 
* 创建时间:2006-1-25 
* 修改时间: 
* 修改原因： 
* 
* path x+y bin(numer) 
* <root> 1/1 1 
* 1 3/2 11 
* 1.1 7/4 111 
* 1.1.1 15/8 1111 
* 1.1.1.1 31/16 11111 
* 1.2 11/8 1011 
* 1.2.1 23/16 10111 
* 1.3 19/16 10011 
* 1.3.1 39/32 100111 
* 2 3/4 011 
* 2.1 7/8 0111 
* 2.1.1 15/16 01111 
* 2.1.2 27/32 011011 
* 2.2 11/16 01011 
* 2.2.1 19/32 010111 
* 3 3/8 0011 
* 3.1 7/16 00111 
* 4 3/16 00011
* 
*
* @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)));

 }

}

分享到：