📄 ternarytree.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"><!--NewPage--><HTML><HEAD><!-- Generated by javadoc (build 1.6.0_04) on Sat May 17 11:57:55 CEST 2008 --><TITLE>TernaryTree</TITLE><META NAME="date" CONTENT="2008-05-17"><LINK REL ="stylesheet" TYPE="text/css" HREF="../../../../../stylesheet.css" TITLE="Style"><SCRIPT type="text/javascript">function windowTitle(){ if (location.href.indexOf('is-external=true') == -1) { parent.document.title="TernaryTree"; }}</SCRIPT><NOSCRIPT></NOSCRIPT></HEAD><BODY BGCOLOR="white" onload="windowTitle();"><HR><!-- ========= START OF TOP NAVBAR ======= --><A NAME="navbar_top"><!-- --></A><A HREF="#skip-navbar_top" title="Skip navigation links"></A><TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY=""><TR><TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1"><A NAME="navbar_top_firstrow"><!-- --></A><TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY=""> <TR ALIGN="center" VALIGN="top"> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A> </TD> <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> <FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A> </TD> </TR></TABLE></TD><TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM><a href="http://www.1t3xt.com/docs/book.php" target="_blank"><img src="http://www.1t3xt.com/img/book/lowagie_3d.jpg" border="0" /></a></EM></TD></TR><TR><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../../../com/lowagie/text/pdf/hyphenation/SimplePatternParser.html" title="class in com.lowagie.text.pdf.hyphenation"><B>PREV CLASS</B></A> <A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.Iterator.html" title="class in com.lowagie.text.pdf.hyphenation"><B>NEXT CLASS</B></A></FONT></TD><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../../../index.html?com/lowagie/text/pdf/hyphenation/TernaryTree.html" target="_top"><B>FRAMES</B></A> <A HREF="TernaryTree.html" target="_top"><B>NO FRAMES</B></A> <SCRIPT type="text/javascript"> <!-- if(window==top) { document.writeln('<A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A>'); } //--></SCRIPT><NOSCRIPT> <A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A></NOSCRIPT></FONT></TD></TR><TR><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2"> SUMMARY: <A HREF="#nested_class_summary">NESTED</A> | <A HREF="#field_summary">FIELD</A> | <A HREF="#constructor_summary">CONSTR</A> | <A HREF="#method_summary">METHOD</A></FONT></TD><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">DETAIL: <A HREF="#field_detail">FIELD</A> | <A HREF="#constructor_detail">CONSTR</A> | <A HREF="#method_detail">METHOD</A></FONT></TD></TR></TABLE><A NAME="skip-navbar_top"></A><!-- ========= END OF TOP NAVBAR ========= --><HR><!-- ======== START OF CLASS DATA ======== --><H2><FONT SIZE="-1">com.lowagie.text.pdf.hyphenation</FONT><BR>Class TernaryTree</H2><PRE><A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">java.lang.Object</A> <IMG SRC="../../../../../resources/inherit.gif" ALT="extended by "><B>com.lowagie.text.pdf.hyphenation.TernaryTree</B></PRE><DL><DT><B>All Implemented Interfaces:</B> <DD><A HREF="http://java.sun.com/j2se/1.4/docs/api/java/io/Serializable.html?is-external=true" title="class or interface in java.io">Serializable</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Cloneable.html?is-external=true" title="class or interface in java.lang">Cloneable</A></DD></DL><DL><DT><B>Direct Known Subclasses:</B> <DD><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/HyphenationTree.html" title="class in com.lowagie.text.pdf.hyphenation">HyphenationTree</A></DD></DL><HR><DL><DT><PRE>public class <B>TernaryTree</B><DT>extends <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</A><DT>implements <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Cloneable.html?is-external=true" title="class or interface in java.lang">Cloneable</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/io/Serializable.html?is-external=true" title="class or interface in java.io">Serializable</A></DL></PRE><P><h2>Ternary Search Tree.</h2> <p>A ternary search tree is a hybrid between a binary tree and a digital search tree (trie). Keys are limited to strings. A data value of type char is stored in each leaf node. It can be used as an index (or pointer) to the data. Branches that only contain one key are compressed to one node by storing a pointer to the trailer substring of the key. This class is intended to serve as base class or helper class to implement Dictionary collections or the like. Ternary trees have some nice properties as the following: the tree can be traversed in sorted order, partial matches (wildcard) can be implemented, retrieval of all keys within a given distance from the target, etc. The storage requirements are higher than a binary tree but a lot less than a trie. Performance is comparable with a hash table, sometimes it outperforms a hash function (most of the time can determine a miss faster than a hash).</p> <p>The main purpose of this java port is to serve as a base for implementing TeX's hyphenation algorithm (see The TeXBook, appendix H). Each language requires from 5000 to 15000 hyphenation patterns which will be keys in this tree. The strings patterns are usually small (from 2 to 5 characters), but each char in the tree is stored in a node. Thus memory usage is the main concern. We will sacrifice 'elegance' to keep memory requirements to the minimum. Using java's char type as pointer (yes, I know pointer it is a forbidden word in java) we can keep the size of the node to be just 8 bytes (3 pointers and the data char). This gives room for about 65000 nodes. In my tests the English patterns took 7694 nodes and the German patterns 10055 nodes, so I think we are safe.</p> <p>All said, this is a map with strings as keys and char as value. Pretty limited!. It can be extended to a general map by using the string representation of an object and using the char value as an index to an array that contains the object values.</p><P><P><DL><DT><B>Author:</B></DT> <DD>cav@uniscope.co.jp</DD><DT><B>See Also:</B><DD><A HREF="../../../../../serialized-form.html#com.lowagie.text.pdf.hyphenation.TernaryTree">Serialized Form</A></DL><HR><P><!-- ======== NESTED CLASS SUMMARY ======== --><A NAME="nested_class_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Nested Class Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> class</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.Iterator.html" title="class in com.lowagie.text.pdf.hyphenation">TernaryTree.Iterator</A></B></CODE><BR> </TD></TR></TABLE> <!-- =========== FIELD SUMMARY =========== --><A NAME="field_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Field Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected static int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#BLOCK_SIZE">BLOCK_SIZE</A></B></CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected char[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#eq">eq</A></B></CODE><BR> Pointer to equal branch and to data when this node is a string terminator.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected char</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#freenode">freenode</A></B></CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected char[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#hi">hi</A></B></CODE><BR> Pointer to high branch.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected <A HREF="../../../../../com/lowagie/text/pdf/hyphenation/CharVector.html" title="class in com.lowagie.text.pdf.hyphenation">CharVector</A></CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#kv">kv</A></B></CODE><BR> This vector holds the trailing of the keys when the branch is compressed.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#length">length</A></B></CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected char[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#lo">lo</A></B></CODE><BR> Pointer to low branch and to rest of the key when it is stored directly in this node, we don't have unions in java!</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected char</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#root">root</A></B></CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected char[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#sc">sc</A></B></CODE><BR> The character stored in this node: splitchar.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>private static long</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#serialVersionUID">serialVersionUID</A></B></CODE><BR> We use 4 arrays to represent a node.</TD></TR></TABLE> <!-- ======== CONSTRUCTOR SUMMARY ======== --><A NAME="constructor_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Constructor Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#TernaryTree()">TernaryTree</A></B>()</CODE><BR> </TD></TR></TABLE> <!-- ========== METHOD SUMMARY =========== --><A NAME="method_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Method Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> void</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#balance()">balance</A></B>()</CODE><BR> Balance the tree for best search performance</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</A></CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#clone()">clone</A></B>()</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>private void</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#compact(com.lowagie.text.pdf.hyphenation.CharVector, com.lowagie.text.pdf.hyphenation.TernaryTree, char)">compact</A></B>(<A HREF="../../../../../com/lowagie/text/pdf/hyphenation/CharVector.html" title="class in com.lowagie.text.pdf.hyphenation">CharVector</A> kx, <A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html" title="class in com.lowagie.text.pdf.hyphenation">TernaryTree</A> map, char p)</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#find(char[], int)">find</A></B>(char[] key, int start)</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#find(java.lang.String)">find</A></B>(<A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html?is-external=true" title="class or interface in java.lang">String</A> key)</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected void</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#init()">init</A></B>()</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> void</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#insert(char[], int, char)">insert</A></B>(char[] key, int start, char val)</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>private char</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../com/lowagie/text/pdf/hyphenation/TernaryTree.html#insert(char, char[], int, char)">insert</A></B>(char p, char[] key, int start,⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -