KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > util > FibonacciHeapNode


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (barak_naveh@users.sourceforge.net)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* --------------------------
26  * FibonnaciHeapNode.java
27  * --------------------------
28  * (C) Copyright 1999-2006, by Nathan Fiedler and Contributors.
29  *
30  * Original Author: Nathan Fiedler
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: FibonacciHeapNode.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 03-Sept-2003 : Adapted from Nathan Fiedler (JVS);
38  *
39  * Name Date Description
40  * ---- ---- -----------
41  * nf 08/31/97 Initial version
42  * nf 09/07/97 Removed FibHeapData interface
43  * nf 01/20/01 Added synchronization
44  * nf 01/21/01 Made Node an inner class
45  * nf 01/05/02 Added clear(), renamed empty() to
46  * isEmpty(), and renamed printHeap()
47  * to toString()
48  * nf 01/06/02 Removed all synchronization
49  * JVS 06/24/06 Generics
50  *
51  */
52 package org.jgrapht.util;
53
54 /**
55  * Implements a node of the Fibonacci heap. It holds the information necessary
56  * for maintaining the structure of the heap. It also holds the reference to the
57  * key value (which is used to determine the heap structure).
58  *
59  * @author Nathan Fiedler
60  */
61 public class FibonacciHeapNode<T>
62 {
63
64     //~ Instance fields -------------------------------------------------------
65
66     /**
67      * Node data.
68      */
69     T data;
70
71     /**
72      * first child node
73      */
74     FibonacciHeapNode<T> child;
75
76     /**
77      * left sibling node
78      */
79     FibonacciHeapNode<T> left;
80
81     /**
82      * parent node
83      */
84     FibonacciHeapNode<T> parent;
85
86     /**
87      * right sibling node
88      */
89     FibonacciHeapNode<T> right;
90
91     /**
92      * true if this node has had a child removed since this node was added to
93      * its parent
94      */
95     boolean mark;
96
97     /**
98      * key value for this node
99      */
100     double key;
101
102     /**
103      * number of children of this node (does not count grandchildren)
104      */
105     int degree;
106
107     //~ Constructors ----------------------------------------------------------
108
109     /**
110      * Default constructor. Initializes the right and left pointers, making
111      * this a circular doubly-linked list.
112      *
113      * @param data data for this node
114      * @param key initial key for node
115      */
116     public FibonacciHeapNode(T data, double key)
117     {
118         right = this;
119         left = this;
120         this.data = data;
121         this.key = key;
122     }
123
124     //~ Methods ---------------------------------------------------------------
125
126     /**
127      * Obtain the key for this node.
128      *
129      * @return the key
130      */
131     public final double getKey()
132     {
133         return key;
134     }
135
136     /**
137      * Obtain the data for this node.
138      */
139     public final T getData()
140     {
141         return data;
142     }
143
144     /**
145      * Return the string representation of this object.
146      *
147      * @return string representing this object
148      */
149     public String JavaDoc toString()
150     {
151         if (true) {
152             return Double.toString(key);
153         } else {
154             StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
155             buf.append("Node=[parent = ");
156
157             if (parent != null) {
158                 buf.append(Double.toString(parent.key));
159             } else {
160                 buf.append("---");
161             }
162
163             buf.append(", key = ");
164             buf.append(Double.toString(key));
165             buf.append(", degree = ");
166             buf.append(Integer.toString(degree));
167             buf.append(", right = ");
168
169             if (right != null) {
170                 buf.append(Double.toString(right.key));
171             } else {
172                 buf.append("---");
173             }
174
175             buf.append(", left = ");
176
177             if (left != null) {
178                 buf.append(Double.toString(left.key));
179             } else {
180                 buf.append("---");
181             }
182
183             buf.append(", child = ");
184
185             if (child != null) {
186                 buf.append(Double.toString(child.key));
187             } else {
188                 buf.append("---");
189             }
190
191             buf.append(']');
192
193             return buf.toString();
194         }
195     }
196
197     // toString
198 }
199
200 // End FibonacciHeapNode.java
201
Popular Tags