BinaryTree


1   package com.icl.saxon.sort;
2   import java.text.*;
3   import java.util.*;
4   
5   // Copyright � International Computers Limited 1998
6   // See conditions of use
7   
8   /**
9    * A Binary Tree used for sorting.
10   *
11   * Similar to the java.util.Dictionary interface except (a) that the
12   * keys must be Strings rather than general Objects (b) the results
13   * are returned as a Vector, not an Enumeration. <P>
14   * 
15   * The methods getKeys() and getValues() return values in ascending order
16   * of key. The keys are compared using a default Collator which sorts
17   * in alphabetical order with intelligent handling of case and accents.<P>
18   *
19   * Note that duplicate keys are not
20   * allowed: a new entry silently overwrites any previous entry with
21   * the same key. If you want to use dulicate keys, append a unique
22   * value (for example, a random number) to each one.<P>
23   *
24   * @author Michael H. Kay (mhkay@iclway.co.uk)
25   * @version 9 July 1999: now returns a Vector rather than an Enumeration
26   *
27   */
28  
29  public class BinaryTree {
30  
31      private BinaryTreeNode root;       // the root node of the tree; null if tree is empty
32      private Comparer comparer;         // object used for comparing key values
33      private BinaryTreeNode prev;       // temporary variable used while making new chain
34      private boolean ascending;         // indicates a sort in ascending order of key value
35      private boolean allowDuplicates;   // indicates duplicates are allowed (their order is retained)
36  
37      // The implementation of the binary tree uses a classic structure with
38      // nodes containing a left pointer, a right pointer, and a key/value pair.
39  
40      // Removal of entries is handled by setting the value to null: the node
41      // itself remains in the tree.
42  
43      /*
44       * Constructor: creates an empty tree
45       */
46      
47      public BinaryTree ()
48      {
49          root = null;
50          ascending = true;
51          allowDuplicates = false;
52      }
53  
54      /**
55      * Set order. This must be called before any nodes are added to the tree.
56      * Default is ascending order
57      * @param ascending true indicates ascending order; false indicates descending
58      */
59  
60      public void setAscending(boolean ascending) {
61          this.ascending = ascending;
62      }
63  
64      /**
65      * Define whether duplicate keys are allowed or not. If duplicates are allowed, objects
66      * with the same key value will be sequenced in order of arrival. If duplicates are not
67      * allowed, a new value will overwrite an existing value with the same key.
68      */
69  
70      public void setDuplicatesAllowed(boolean allow) {
71          allowDuplicates = allow;
72      }
73  
74      /**
75      * Set the Comparer to be used for the keys in this tree.
76      * At the time this is called, the tree must be empty
77      */
78  
79      public void setComparer(Comparer c) {
80          if (isEmpty()) comparer = c;
81      }
82  
83      /** 
84      * getValues() returns the values in the tree in sorted order.
85      * @return an Vector containing the values in this BinaryTree (in key order).
86      */
87   
88      public Vector getValues() {
89          BinaryTreeNode node = root;
90          Vector v = new Vector();
91          getValues(root, v);
92          return v;
93      }
94  
95      /**
96       * getValues() supporting method:
97       * Walk through the nodes recursively in key order adding each value to a supplied vector
98       */
99  
100     private void getValues (BinaryTreeNode here, Vector v) {
101         if (here!=null) {
102            getValues(here.left, v);
103            if (!here.isDeleted()) {
104                v.addElement(here.value);
105            }
106            getValues(here.right, v);
107         } 
108     }
109 
110     /** 
111     * getKeys() returns the keys in the tree in sorted order.
112     * @return an Vector containing the keys in this BinaryTree (in key order).
113     */
114  
115     public Vector getKeys() {
116         BinaryTreeNode node = root;
117         Vector v = new Vector();
118         getKeys(root, v);
119         return v;
120     }
121 
122     /**
123      * getKeys() supporting method
124      * walk through the nodes recursively in key order adding each value to a supplied vector
125      */
126 
127     private void getKeys (BinaryTreeNode here, Vector v) {
128         if (here!=null) {
129            getKeys(here.left, v);
130            if (!here.isDeleted()) {
131                v.addElement(here.key);
132            }
133            getKeys(here.right, v);
134         } 
135     }
136 
137     /**
138     * get(String) returns the value corresponding to a given key, if any
139     * @param key The key value being sought
140     * @return the value to which the key is mapped in this binary tree, or null
141     * if there is no entry with this key
142     */
143 
144     public Object   get(Object   key)
145     {
146         BinaryTreeNode n = find(key);
147         return (n==null ? null : n.value);
148     };
149 
150     /**
151     * isEmpty() 
152     * Tests if this binary tree contains no keys.
153     * @return true if there are no entries in the tree
154     */
155 
156     public boolean isEmpty() {
157        return (size()==0);
158     }
159 
160     /** 
161     * put(Object, Object) puts a new entry in the tree, overwriting any previous entry with
162     * the same key.
163     * @param key The value of the key. Note this must be a String, and must not be null.
164     * @param value The value to be associated with this key. Must not be null.
165     * @return the value previously associated with this key, if there was one. Otherwise null.
166     */
167 
168     public Object   put(Object   key, Object   value)
169     {
170         if (key==null || value==null) throw new NullPointerException  ();
171 
172         BinaryTreeNode node = root;
173 
174         if (comparer==null) {
175             comparer = new StringComparer();
176         }
177         
178         if (root==null) {
179             root = new BinaryTreeNode(key, value);
180             return null;
181         }
182         while (true) {
183             int w = comparer.compare(node.key, key);
184             if (!ascending) w = 0 - w;
185             if (w == 0 && allowDuplicates) w = -1;
186             if ( w > 0 ) {
187                 if (node.left==null) {
188                     node.left = new BinaryTreeNode(key, value);
189                     return null;
190                 }                
191                 node = node.left;               
192             }
193             if ( w == 0 ) {
194                 Object   old = node.value; 
195                 node.value = value;
196                 return old;
197             }
198             if ( w < 0 ) {
199                 if (node.right==null) {
200                    node.right = new BinaryTreeNode(key, value);
201                    return null;
202                 }
203                 node = node.right;
204             }
205         }
206     }
207         
208 
209     /**
210     * remove(Object) 
211     * removes the key (and its corresponding value) from this Binary Tree.
212     * If duplicates are allowed it removes at most one entry with this key
213     * @param key identifies the entry to be removed
214     * @return the value that was associated with this key, if there was one.
215     * Otherwise null.
216     */
217     
218     public Object   remove(Object   key)
219     {
220          // implemented by setting a logical delete marker in the node
221          BinaryTreeNode n = find(key);
222  
223          if (n==null) return null;
224          Object   val = n.value;
225          n.delete();
226          return(val);
227     }
228 
229 
230     /**
231      * size() 
232      * @return the number of entries in this binary tree. 
233      */
234      
235     public int size() {
236         return count(root);
237     }
238 
239     /*
240      * private method to count the nodes subordinate to a given node
241      */
242 
243     private int count ( BinaryTreeNode here )
244     {
245         if (here==null) return 0;
246         return count(here.left) + (here.isDeleted() ? 0 : 1) + count(here.right);
247     }
248 
249     /*
250      * Private method to find a node given a key value. If duplicates are allowed it finds the first.
251      */
252 
253     private BinaryTreeNode find(Object   s)
254     {
255         BinaryTreeNode node = root;
256         
257         if (node==null) return null;
258         while (node!=null) {
259             int w = comparer.compare(s, node.key);
260             if ( w < 0 ) node= node.left;
261             if ( w == 0 ) return (node.isDeleted() ? null : node);
262             if ( w > 0 ) node= node.right;
263         }
264         return null;
265     }
266     
267 
268 // inner classes
269 
270 private class BinaryTreeNode {
271     BinaryTreeNode left;
272     BinaryTreeNode right;
273     Object   key;
274     Object   value;
275 
276     public BinaryTreeNode ( Object   k, Object   v ) {
277         left = null;
278         right = null;
279         key = k;
280         value = v;
281     }
282     
283     public boolean isDeleted() {
284         return (value==null);
285     }
286     public void delete() {
287         value = null;
288     }        
289         
290 }
291 
292 // end of inner classes
293 
294 // main program, for testing
295 
296 public static void main(String   args[]) throws Exception   {
297 
298     BinaryTree tree = new BinaryTree();
299     tree.setComparer(new UppercaseFirstComparer());
300     tree.setAscending(true);
301     tree.setDuplicatesAllowed(true);
302     tree.put("a", "1");
303     tree.put("b", "2");
304     tree.put("c", "3");
305     tree.put("aa", "4");
306     tree.put("ab", "5");
307     tree.put("A", "6");
308     tree.put("A", "6a");
309     tree.put("B", "7");
310     tree.put("AA", "8");
311     tree.put("XYZ", "9");
312     tree.put("", "10");
313     System.out.println(tree.getKeys());
314     System.out.println(tree.getValues());
315 
316     tree = new BinaryTree();
317     tree.setComparer(new DoubleComparer());
318     tree.setAscending(false);
319     tree.put(new Double  (1.43), "1");
320     tree.put(new Double  (84.2), "2");
321     tree.put(new Double  (-100), "3");
322     tree.put(new Double  (0.0), "4");
323     System.out.println(tree.getKeys());
324     System.out.println(tree.getValues());
325     
326 }
327 
328 }
329
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags