//! A fibonacci heap is a type of data structure optimized for use as a priority queue.

//! It is commonly useful in pathfinding algorithms like Dijkstra's and A*.

//! 

//! Below is a very in depth comparison and analysis of various types of heaps,

//! skip to [`FibHeap`] if you only want to know how to use this library.

//! Reading the tests is also a great way to find examples.  Building code as tests will

//! help debug fibheap code in particular because additional checks are performed under `cfg(test)`

//! that will `abort` if the heap breaks (ie because a duplicate node was added, a node was removed

//! that wasn't in the heap, or there is a bug in the library).

//! 

//! Depending on your needs, [`crate::mmheap::MmHeap`] may be more useful to you, or

//! Rust's builtin [`std::collections::BinaryHeap`].  Both of these are binary heaps,

//! but the former offers fast access to both the minimum and the maximum.

//! 

//! # Comparison of Heaps

//! ## Asymptotic Time

//!|            | Binary | Pairing | Fibonacci | Bucket |

//!|------------|--------|---------|-----------|--------|

//!|find-min    | O(1)   | O(1)    | O(1)      | O(1)   |

//!|extract-min | O(logn)| O(logn) | O(logn)   | O(1)   |

//!|insert      | O(logn)| O(1)    | O(1)      | O(1)   |

//!|decrease-key| O(logn)| O(logn) | O(1)      | O(1)   |

//!|increase-key| O(logn)| O(logn) | O(logn)   | O(1)   |

//!|meld        | O(n)   | O(1)    | O(1)      | O(n)   |

//! Not all of these operations are directly supported.  In Fibonacci heaps, `increase-key`

//! must be implemented by removing and re-inserting an element.  In binary heaps,

//! decrease/increase key can be difficult to implement because the elements exist in the heap's

//! internal buffer and there isn't a direct way to get a reference/index to them.

//! Also in binary heaps, meld is not directly supported and must be implemented by extending

//! the internal buffer of one heap by that of another and re-heapifying.

//! Bucket queues are extremely good when relevant, but they only support a fixed number of

//! priorities, literally having a bucket for each priority, so they are not always suitable.

//! 

//! ## Linked vs Unlinked Data Structures

//! Asymptotic time complexity is not the whole story.  Fibonacci heaps and pairing heaps are linked data

//! structures, so links to adjacent nodes are stored as pointers, whereas binary heaps

//! have such a simple, rigid structure that they can be stored directly in an array

//! (eg the children of a node at index i will be at indices 2i + 1 and 2i + 2).

//! Linked data structures can still be stored in an array, but the offsets between nodes

//! are not consistent and so generally pointers are used, which can introduce overhead in several

//! ways.  Linked data structures often underperform relative to "rigid" data structures

//! even though their asymptotic complexity is better.  And even among linked data structures,

//! Fibonacci heaps are considered complex and may perform worse than pairing heaps.

//! 

//! ## Amortized Running Time

//! The runtimes of Fibonacci heaps are amortized using potential, which means if the

//! number of other calls is much much greater than the number of extract-min calls,

//! the extract-min calls may take much longer because they are picking up more work.

//! This doesn't happen in most use cases since generally a large part of the heap will be

//! drained in algorithms like heapsort, A*, etc.  When it's not the case that a large part

//! of the heap will be drained, a minmax heap can often be a good choice since it allows

//! dropping entries that will never be used efficiently.  In particular, if the number of

//! entries that will be extracted from the heap is constant and small, a minmax heap will

//! probably be best.  If the number of entries that will be extracted is proportional to

//! the number inserted and/or large, a fibonacci heap may be the best.

//! 

//! ## Explanation of Algorithms

//! There are two operations (extract-min and decrease-key) that are central to Fibonacci heaps,

//! and all other operations are trivial.

//! A Fibonacci heap consists of a collection of subheaps, each of which is a tree where

//! nodes can have any number of children.  This is implemented by giving each node 4 pointers:

//! its parent, its first child, its next sibling, and its previous sibling.  For the subheap roots,

//! their parent is null and their next/previous siblings are instead other roots.

//! Each node also stores its degree (number of chilren) and whether or not it has had a child removed.

//! 

//! The heap itself stores a pointer to the minimal root, and the number of elements in the heap.

//! 

//! This structure is restricted by a few invariants.  First, each node is less than or equal to

//! all of its children according to the heap comparison function.  Second, the total size of a

//! subheap whose root has k children is at least F_(k+2), where F_k is the kth Fibonacci number,

//! with F_1 = F_2 = 1, F_3 = 2, F_4 = 3, etc.

//! 

//! When extract-min is called, first we remove the minimal root.

//! Then we iterate over the roots of all other subheaps, plus the children of the removed root,

//! placing them into an array with O(logn) elements.

//! Each such node goes into the index in the array corresponding to its degree.  If there is already a subheap there,

//! we instead remove that subheap, merge it with the current one, and keep going.  When we merge the subheaps,

//! the one with the larger root is added as a child of the one with the smaller root, so the degree of the latter goes

//! up and then we try to put it in the next corresponding index in the array, repeating until we reach a degree that

//! isn't in the array yet.

//! 

//! At the end, this gives us an array of subheaps with distinct degrees.

//! We re-link these into a double circularly linked list, and update the minimal root pointer to point to the minimal one.

//! 

//! If all subheaps obey the `size >= F_(degree + 2)` invariant before `extract-min`, they will also obey it after.

//! 

//! If there are two or fewer nodes in the heap before we extract-min, we can optimize by not merging subheaps and just

//! setting the new minimal root to either the one remaining node or null.

//! 

//! When decrease-key is called, if the key is still greater than or equal to the parent's key, or the node is

//! a root node and the key is still greater than or equal to the minimal root, or the root node is the minimal root,

//! there is nothing to be done.  If the node is a root node but not the minimal root and the key becomes

//! less than the minimal heap, update the minimal heap.

//! 

//! Finally, if the key is now less than the parent's key, remove the node from its sibling list and as a child of its parent.

//! Add it as a new subeap.  If the parent was not marked as already having a child removed, mark it as such

//! and then remove it as well, repeating for any remaining parents.  However, root nodes need not be marked as such.

//! 

//! This marking is needed to ensure that the `size >= F_(degree + 2)` invariant does not break

//! 

//! Insert and meld just require adding a new subheap with one element, and stitching together the subheap root linked lists,

//! respectively.

//! 

//! Find-min just requires inspecting the min_root pointer.

//! 

//! ## Further Reading

//! [Wikipedia](https://en.wikipedia.org/wiki/Fibonacci_heap)

//! [3b1b style video by SithDev](https://youtu.be/6JxvKfSV9Ns)

//! 

//! A very popular priority queue crate.  This crate implements priority queues using a hash table to allow key-indexed node

//! access, and builds the priority queue on top of its internal hash table.  It has a good api and is a good choice most of

//! the time.  Crater has some advantages over this crate: our fib heap allows building priority queues with any backing

//! store, eg KD trees, vectors, just putting each node in `Box`, etc; and references to nodes have generous lifetimes,

//! so storing references instead of keys is possible and makes lookup as fast as possible.  However, unless you need these

//! features, this crate is a better choice than Crater.

//! [priority-queue](https://crates.io/crates/priority-queue)

use std::{cell::UnsafeCell, cmp::Ordering, marker::PhantomData, ptr};

/// The intrusive struct itself that should be embedded in any types that

/// implement [`Node`].  See [`FibHeap`] for more information.

#[derive(Debug)]

pub struct RawNode<'a, T: Node<'a> + ?Sized> {

	prev: UnsafeCell<Option<&'a T>>,

	next: UnsafeCell<Option<&'a T>>,

	first_child: UnsafeCell<Option<&'a T>>,

	parent: UnsafeCell<Option<&'a T>>,

	has_split: UnsafeCell<bool>,

	degree: UnsafeCell<u8>

}

/// Any struct can be used as the fib heap element simply by embedding a [`RawNode`]

/// in it (or wrapping it in a struct containing a raw node) and implementing this trait.

pub trait Node<'a> {

	/// Comparison function for nodes, can just wrap Ord impl if present

	fn cmp(&'a self, other: &'a Self) -> Ordering;

	/// Get a reference to the embedded raw node.  This is used internally to traverse and bookkeep the heap.

	/// Accessing this is not thread safe as-is.  Implementors can place the raw node under a lock,

	/// but it's better to lock the entire [`FibHeap`] to avoid race conditions.

	fn get_raw(&'a self) -> &RawNode<'a, Self>;

}

struct SiblingIter<'a, T: Node<'a> + ?Sized> {

	start: Option<&'a T>,

	iter: &'a T

}

impl<'a, T: Node<'a> + ?Sized> Iterator for SiblingIter<'a, T> {

	type Item = &'a T;

}

struct UnlinkingSiblingIter<'a, T: Node<'a> + ?Sized> {

	start: Option<&'a T>,

	iter: &'a T

}

impl<'a, T: Node<'a> + ?Sized> Iterator for UnlinkingSiblingIter<'a, T> {

	type Item = &'a T;

}

#[cfg(test)]

enum FibHeapError<'a, T: Node<'a> + ?Sized> {

	BrokenPrevLink(&'a T),

	LessThanParent(&'a T),

	BrokenParentLink(&'a T),

	WrongDegree(&'a T),

	TooSmall(&'a T),

	WrongCount

}

#[cfg(test)]

impl<'a, T: Node<'a> + ?Sized> PartialEq for FibHeapError<'a, T> {

		}

}

#[cfg(test)]

impl<'a, T: Node<'a> + ?Sized> std::fmt::Debug for FibHeapError<'a, T> {

		}

}

impl<'a, T: Node<'a> + ?Sized> Default for RawNode<'a, T> {

}

#[cfg(test)]

		} else {

		}

	} else {

	}

	// first, find which of node / other has the minimal key, breaking ties with node

	}

#[cfg(test)]

	}

		// we don't need to check "prev".next because that's the termination condition of `iter_siblings`

/// A fibonacci heap is a type of data structure optimized for use as a priority queue.

/// It is commonly useful in pathfinding algorithms like Dijkstra's and A*.

/// Fib heaps have the following amortized time complexities:

/// - find-min: O(1)

/// - extract-min: O(logn)

/// - insert: O(1), compare to O(logn) in a binary heap

/// - decrease-key: O(1), compare to O(logn) in a binary heap / pairing heap

/// - meld: O(1), compare to O(n) in a binary heap

/// Extracting (or deleting) an arbitrary element is also O(logn).

/// Increase-key is not directly supported, but can be done by removing and reinserting.

/// Fib heaps will generally be a better choice than other heaps when:

/// - The number of elements extracted from the heap is proportional to the number inserted and/or large, not fixed and small

/// - The keys/priorities of elements need to be decreased frequently

/// - The keys/priorities of elements don't need to be increased frequently (also the comparison function doesn't need to be changed)

pub struct FibHeap<'a, T: Node<'a> + ?Sized, U> {

	min_root: Option<&'a T>,

	count: usize,

	container: PhantomData<&'a mut U>

}

impl<'a, T: Node<'a> + ?Sized + 'a, U> FibHeap<'a, T, U> {

	/// Create a new fibonacci heap whose backing storage will live at least as long as `_container`.

	/// Typically, if the nodes are stored in a `Vec` or a [`crate::kdtree::KdTree`] or so on,

	/// this backing container will have to remain effectively pinned for as long as the fibonacci

	/// heap exists, so that references to nodes remain valid.

	/// 

	/// Conceptually, only the lifespan of `_container` matters: by passing it in here and holding a `PhantomData`

	/// reference with the same lifespan, we force the shared reference to the container to outlive the

	/// fibonacci heap and prevent any mutable references to it from existing for that time.

	/// 

	/// Internally, [`RawNode`] uses [`UnsafeCell`] so that nodes can be mutated through shared reference.

	/// Otherwise, correctly mutating nodes is excessively complicated (requires using raw pointers throughout,

	/// and requires the backing storage to have some way to get a mutable subreference that doesn't overlap with

	/// any node so we can assume it is effectively pinned, most of the time this would be a mutable reference to

	/// an empty slice).

	/// Get the minimal element if it exists, returning a reference to it without removing it.

	/// It is safe to decrease the key of the result, but not to increase it

	/// if doing so could cause it to no longer be minimal (the key probably lives behind an [`UnsafeCell`])

	/// Get and remove the minimal element if it exists, returning a reference to it.

	/// The key of the result may be freely modified

			}

					None => {

					},

				}

			}

		}

		}

		}

	/// Add a node to the heap.  This is unsafe because the node must not already be in

	/// the heap, nor in a different heap.  It is not strictly required for all nodes

	/// to have the same backing store as long as the borrow checker confirms they outlive

	/// the heap, but most of the time all references will be to elements of the backing store.

		}

	/// Called immediately AFTER a node's key is decreased, to ensure that the heap invariants

	/// are maintained.  This is unsafe because the node must be an element of the heap.

	/// Remove a node from the heap by reference.  Since the heap is intrusive and does not own its

	/// nodes, nothing is returned because the caller already has a reference to the removed node.

	/// This is unsafe because the node must be an element of the heap.

	pub unsafe fn remove(&mut self, node: &'a T) {

		self.separate_node(node);

		self.min_root = Some(node);

		self.pop_min();

	}

			1 => {

			},

			_ => {

			}

		}

		loop {

		}

		#[cfg(test)]{

		}

	#[cfg(test)]

		}

			// we don't need to check "prev".next because that's the termination condition of `iter_siblings`

}

#[cfg(test)]

mod tests {

    use std::{cell::UnsafeCell, cmp::Ordering, fs, ops::Deref};

    use num_traits::Euclid;

    use super::{FibHeap, Node, RawNode};

	struct GenNode<'a> {

		multiple: UnsafeCell<u64>,

		prime: UnsafeCell<u64>,

		_node: RawNode<'a, Self>

	}

	impl<'a> Node<'a> for GenNode<'a> {

	}

	#[test]

				}

			}

					}

		}

	struct GridNode<'a> {

		cost: u64,

		h: u64,

		min_dist: UnsafeCell<u64>,

		visited: UnsafeCell<bool>,

		_node: RawNode<'a, Self>

	}

	impl<'a> Node<'a> for GridNode<'a> {

	}

	#[test]

		}

				}

			}

		}

}