KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jboss > util > Heap


1 /*
2   * JBoss, Home of Professional Open Source
3   * Copyright 2005, JBoss Inc., and individual contributors as indicated
4   * by the @authors tag. See the copyright.txt in the distribution for a
5   * full listing of individual contributors.
6   *
7   * This is free software; you can redistribute it and/or modify it
8   * under the terms of the GNU Lesser General Public License as
9   * published by the Free Software Foundation; either version 2.1 of
10   * the License, or (at your option) any later version.
11   *
12   * This software is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15   * Lesser General Public License for more details.
16   *
17   * You should have received a copy of the GNU Lesser General Public
18   * License along with this software; if not, write to the Free
19   * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20   * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
21   */
22 package org.jboss.util;
23  
24 import java.util.Comparator JavaDoc;
25
26 /**
27  * Data structure that mantains data in a ordered binary tree; each node is
28  * greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy. <p>
29  * Elements of this data structure should either implement Comparable, or a
30  * Comparator should be given as argument to the constructor.
31  *
32  * @author <a HREF="mailto:simone.bordet@compaq.com">Simone Bordet</a>
33  * @version $Revision: 1958 $
34  */
35 public class Heap
36 {
37    private Comparator JavaDoc m_comparator;
38    private int m_count;
39    private Object JavaDoc[] m_nodes;
40
41    /**
42     * Creates a new Heap whose elements inserted implement the
43     * {@link Comparable} interface.
44     */
45    public Heap()
46    {
47       this(null);
48    }
49    
50    /**
51     * Creates a new Heap whose elements are compared using the given
52     * {@link Comparator}.
53     */
54    public Heap(Comparator JavaDoc comparator)
55    {
56       m_comparator = comparator;
57       clear();
58    }
59
60    /**
61     * Inserts the given element in this heap.
62     *
63     * @see #extract
64     */
65    public void insert(Object JavaDoc obj)
66    {
67       int length = m_nodes.length;
68       // Expand if necessary
69 if (m_count == length)
70       {
71          Object JavaDoc[] newNodes = new Object JavaDoc[length + length];
72          System.arraycopy(m_nodes, 0, newNodes, 0, length);
73          m_nodes = newNodes;
74       }
75       // Be cur_slot the first unused slot index; be par_slot its parent index.
76 // Start from cur_slot and walk up the tree comparing the object to
77 // insert with the object at par_slot; if it's smaller move down the object at par_slot,
78 // otherwise cur_slot is the index where insert the object. If not done,
79 // shift up the tree so that now cur_slot is the old par_slot and
80 // par_slot is the parent index of the new cur_slot (so the grand-parent
81 // index of the old cur_slot) and compare again.
82 int k = m_count;
83       while (k > 0)
84       {
85          int par = parent(k);
86          if (compare(obj, m_nodes[par]) < 0)
87          {
88             m_nodes[k] = m_nodes[par];
89             k = par;
90          }
91          else break;
92       }
93       m_nodes[k] = obj;
94       ++m_count;
95    }
96    
97    /**
98     * Removes and returns the least element of this heap.
99     *
100     * @see #insert
101     * @see #peek
102     */
103    public Object JavaDoc extract()
104    {
105       if (m_count < 1) {return null;}
106       else
107       {
108          int length = m_nodes.length >> 1;
109          // Shrink if necessary
110 if (length > 5 && m_count < (length >> 1))
111          {
112             Object JavaDoc[] newNodes = new Object JavaDoc[length];
113             System.arraycopy(m_nodes, 0, newNodes, 0, length);
114             m_nodes = newNodes;
115          }
116          //
117 int k = 0;
118          Object JavaDoc ret = m_nodes[k];
119          --m_count;
120          Object JavaDoc last = m_nodes[m_count];
121          for (;;)
122          {
123             int l = left(k);
124             if (l >= m_count) {break;}
125             else
126             {
127                int r = right(k);
128                int child = (r >= m_count || compare(m_nodes[l], m_nodes[r]) < 0) ? l : r;
129                if (compare(last, m_nodes[child]) > 0)
130                {
131                   m_nodes[k] = m_nodes[child];
132                   k = child;
133                }
134                else {break;}
135             }
136          }
137          m_nodes[k] = last;
138          m_nodes[m_count] = null;
139          return ret;
140       }
141    }
142    
143    /**
144     * Returns, without removing it, the least element of this heap.
145     *
146     * @see #extract
147     */
148    public Object JavaDoc peek()
149    {
150       if (m_count < 1) {return null;}
151       else {return m_nodes[0];}
152    }
153    
154    /**
155     * Empties this heap
156     */
157    public void clear()
158    {
159       m_count = 0;
160       m_nodes = new Object JavaDoc[10];
161    }
162
163    /**
164     * Compares the given objects using the comparator, if available,
165     * or considering them Comparable objects.
166     *
167     * @throws ClassCastException if nor the comparator is given
168     * and nor both objects implements the Comparable interface
169     */
170    protected int compare(Object JavaDoc o1, Object JavaDoc o2)
171    {
172       if (m_comparator != null)
173       {
174          return m_comparator.compare(o1, o2);
175       }
176       else
177       {
178          if (o1 == null)
179          {
180             if (o2 == null) {return 0;}
181             else {return -((Comparable JavaDoc)o2).compareTo(o1);}
182          }
183          else {return ((Comparable JavaDoc)o1).compareTo(o2);}
184       }
185    }
186    
187    /**
188     * Returns the parent index of <code>index</code>.
189     */
190    protected int parent(int index)
191    {
192       return (index - 1) >> 1;
193    }
194    
195    /**
196     * Returns the left child index of <code>index</code>.
197     */
198    protected int left(int index)
199    {
200       return index + index + 1;
201    }
202    
203    /**
204     * Returns the right child index of <code>index</code>.
205     */
206    protected int right(int index)
207    {
208       return index + index + 2;
209    }
210 }
211
Popular Tags