001/****************************************************************************** 002 Copyright 2011 See AUTHORS file. 003 004 Licensed under the Apache License, Version 2.0 (the "License"); 005 you may not use this file except in compliance with the License. 006 You may obtain a copy of the License at 007 008 http://www.apache.org/licenses/LICENSE-2.0 009 010 Unless required by applicable law or agreed to in writing, software 011 distributed under the License is distributed on an "AS IS" BASIS, 012 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 See the License for the specific language governing permissions and 014 limitations under the License. 015 */ 016 017package squidpony.squidmath; 018 019import java.util.Arrays; 020 021/** A binary heap that stores nodes which each have a double value and are sorted either lowest first or highest first. 022 * The {@link Node} class can be extended to store additional information. 023 * @author Nathan Sweet */ 024public class BinaryHeap<T extends BinaryHeap.Node> { 025 public int size; 026 027 private Node[] nodes; 028 private final boolean isMaxHeap; 029 030 public BinaryHeap () { 031 this(16, false); 032 } 033 034 public BinaryHeap (int capacity, boolean isMaxHeap) { 035 this.isMaxHeap = isMaxHeap; 036 nodes = new Node[capacity]; 037 } 038 039 /** Adds the node to the heap using its current value. The node should not already be in the heap. */ 040 public T add (T node) { 041 // Expand if necessary. 042 if (size == nodes.length) { 043 Node[] newNodes = new Node[size << 1]; 044 System.arraycopy(nodes, 0, newNodes, 0, size); 045 nodes = newNodes; 046 } 047 // Insert at end and bubble up. 048 node.index = size; 049 nodes[size] = node; 050 up(size++); 051 return node; 052 } 053 054 /** Sets the node's value and adds it to the heap. The node should not already be in the heap. */ 055 public T add (T node, double value) { 056 node.value = value; 057 return add(node); 058 } 059 060 /** Returns true if the heap contains the specified node. 061 * @param identity If true, == comparison will be used. If false, .equals() comparison will be used. */ 062 public boolean contains (T node, boolean identity) { 063 if (node == null) throw new IllegalArgumentException("node cannot be null."); 064 if (identity) { 065 for (Node n : nodes) 066 if (n == node) return true; 067 } else { 068 for (Node other : nodes) 069 if (other.equals(node)) return true; 070 } 071 return false; 072 } 073 074 /** Returns the first item in the heap. This is the item with the lowest value (or highest value if this heap is configured as 075 * a max heap). */ 076 public T peek () { 077 if (size == 0) throw new IllegalStateException("The heap is empty."); 078 return (T)nodes[0]; 079 } 080 081 /** Removes the first item in the heap and returns it. This is the item with the lowest value (or highest value if this heap is 082 * configured as a max heap). */ 083 public T pop () { 084 Node removed = nodes[0]; 085 if (--size > 0) { 086 nodes[0] = nodes[size]; 087 nodes[size] = null; 088 down(0); 089 } else 090 nodes[0] = null; 091 return (T)removed; 092 } 093 094 public T remove (T node) { 095 if (--size > 0) { 096 Node moved = nodes[size]; 097 nodes[size] = null; 098 nodes[node.index] = moved; 099 if (moved.value < node.value ^ isMaxHeap) 100 up(node.index); 101 else 102 down(node.index); 103 } else 104 nodes[0] = null; 105 return node; 106 } 107 108 /** Returns true if the heap has one or more items. */ 109 public boolean notEmpty () { 110 return size > 0; 111 } 112 113 /** Returns true if the heap is empty. */ 114 public boolean isEmpty () { 115 return size == 0; 116 } 117 118 public void clear () { 119 Arrays.fill(nodes, 0, size, null); 120 size = 0; 121 } 122 123 /** Changes the value of the node, which should already be in the heap. */ 124 public void setValue (T node, double value) { 125 double oldValue = node.value; 126 node.value = value; 127 if (value < oldValue ^ isMaxHeap) 128 up(node.index); 129 else 130 down(node.index); 131 } 132 133 private void up (int index) { 134 Node[] nodes = this.nodes; 135 Node node = nodes[index]; 136 double value = node.value; 137 while (index > 0) { 138 int parentIndex = (index - 1) >> 1; 139 Node parent = nodes[parentIndex]; 140 if (value < parent.value ^ isMaxHeap) { 141 nodes[index] = parent; 142 parent.index = index; 143 index = parentIndex; 144 } else 145 break; 146 } 147 nodes[index] = node; 148 node.index = index; 149 } 150 151 private void down (int index) { 152 Node[] nodes = this.nodes; 153 int size = this.size; 154 155 Node node = nodes[index]; 156 double value = node.value; 157 158 while (true) { 159 int leftIndex = 1 + (index << 1); 160 if (leftIndex >= size) break; 161 int rightIndex = leftIndex + 1; 162 163 // Always has a left child. 164 Node leftNode = nodes[leftIndex]; 165 double leftValue = leftNode.value; 166 167 // May have a right child. 168 Node rightNode; 169 double rightValue; 170 if (rightIndex >= size) { 171 rightNode = null; 172 rightValue = isMaxHeap ? -Double.MAX_VALUE : Double.MAX_VALUE; 173 } else { 174 rightNode = nodes[rightIndex]; 175 rightValue = rightNode.value; 176 } 177 178 // The smallest of the three values is the parent. 179 if (leftValue < rightValue ^ isMaxHeap) { 180 if (leftValue == value || (leftValue > value ^ isMaxHeap)) break; 181 nodes[index] = leftNode; 182 leftNode.index = index; 183 index = leftIndex; 184 } else { 185 if (rightValue == value || (rightValue > value ^ isMaxHeap)) break; 186 nodes[index] = rightNode; 187 if (rightNode != null) rightNode.index = index; 188 index = rightIndex; 189 } 190 } 191 192 while (index > 0) { 193 int parentIndex = (index - 1) >> 1; 194 Node parent = nodes[parentIndex]; 195 if (value < parent.value ^ isMaxHeap) { 196 nodes[index] = parent; 197 parent.index = index; 198 index = parentIndex; 199 } else 200 break; 201 } 202 203 nodes[index] = node; 204 node.index = index; 205 } 206 207 public boolean equals (Object obj) { 208 if (!(obj instanceof BinaryHeap)) return false; 209 BinaryHeap other = (BinaryHeap)obj; 210 if (other.size != size) return false; 211 Node[] nodes1 = this.nodes, nodes2 = other.nodes; 212 for (int i = 0, n = size; i < n; i++) 213 if (nodes1[i].value != nodes2[i].value) return false; 214 return true; 215 } 216 217 public int hashCode () { 218 int h = 1; 219 Node[] nodes = this.nodes; 220 for (int i = 0, n = size; i < n; i++) 221 h = h * 31 + NumberTools.doubleToMixedIntBits(nodes[i].value); 222 return h; 223 } 224 225 public String toString () { 226 if (size == 0) return "[]"; 227 Node[] nodes = this.nodes; 228 StringBuilder buffer = new StringBuilder(32); 229 buffer.append('['); 230 buffer.append(nodes[0].value); 231 for (int i = 1; i < size; i++) { 232 buffer.append(", "); 233 buffer.append(nodes[i].value); 234 } 235 buffer.append(']'); 236 return buffer.toString(); 237 } 238 239 /** A binary heap node. 240 * @author Nathan Sweet */ 241 static public class Node { 242 public double value; 243 public int index; 244 245 /** @param value The initial value for the node. To change the value, use {@link BinaryHeap#add(Node, double)} if the node is 246 * not in the heap, or {@link BinaryHeap#setValue(Node, double)} if the node is in the heap. */ 247 public Node (double value) { 248 this.value = value; 249 } 250 251 public double getValue () { 252 return value; 253 } 254 255 public String toString () { 256 return Double.toString(value); 257 } 258 } 259}