add a lot of docs and a reference to them in the README
authorTim "S.D.Eagle" Zeitz <dev.tim.zeitz@gmail.com>
Wed, 17 Oct 2018 10:53:00 +0000 (12:53 +0200)
committerTim "S.D.Eagle" Zeitz <dev.tim.zeitz@gmail.com>
Wed, 17 Oct 2018 10:53:00 +0000 (12:53 +0200)
README.md
src/index_heap.rs
src/io.rs
src/lib.rs
src/time.rs
src/types.rs

index 3a06ffa..c8cfc59 100644 (file)
--- a/README.md
+++ b/README.md
@@ -66,6 +66,10 @@ Die Dateien in `src/bin/` sind einmal ein Beispielprogramm sowieso Hilfsprogramm
 Das Programm `compare_vector` vergleicht ob zwei Vektoren identisch sind und wenn sie es nicht sind gibt es eine Übersicht über die Unterschiede.
 Fügen sie Ihre Programme in `src/bin/` hinzu, diese werden dann von `cargo` automatisch gefunden.
 
+## Docs
+
+`cargo doc --open` öffnet die Dokumentation zu dem bereitgestelltem Code.
+
 ## Graphen
 
 Knoten und Kanten werden durch numerische IDs identifiziert, die von `0` bis `n-1` bzw. `m-1` gehen, wobei `n` die Anzahl an Knoten und `m` die Anzahl an gerichteten Kanten ist.
index c086dc3..a7af9ca 100644 (file)
@@ -1,14 +1,57 @@
+//! A priority queue implemented with a 4-ary heap.
+//!
+//! Insertion and popping the minimal element have `O(log n)` time complexity.
+//! Checking the minimal element is `O(1)`. Keys of elements in the heap can
+//! also be increased or decreased
+//!
+//! # Examples
+//!
+//! ```
+//! use stud_rust_base::index_heap::{Indexing, IndexdMinHeap};
+//!
+//! #[derive(Copy, Clone, Eq, PartialEq, Debug, Ord, PartialOrd)]
+//! pub struct State {
+//!     pub distance: usize,
+//!     pub node: usize,
+//! }
+//!
+//!
+//! // The `Indexing` traits needs to be implemented as well, so we can find elements to decrease their key.
+//! impl Indexing for State {
+//!     fn as_index(&self) -> usize {
+//!         self.node as usize
+//!     }
+//! }
+//!
+//! fn main() {
+//!     let mut heap = IndexdMinHeap::new(3);
+//!     heap.push(State { node: 0, distance: 42 });
+//!     heap.push(State { node: 1, distance: 23 });
+//!     heap.push(State { node: 2, distance: 50000 });
+//!     assert_eq!(heap.peek().cloned(), Some(State { node: 1, distance: 23 }));
+//!     heap.decrease_key(State { node: 0, distance: 1 });
+//!     assert_eq!(heap.pop(), Some(State { node: 0, distance: 1 }));
+//! }
+//!
+//! ```
+
 use std;
 use std::cmp::min;
 use std::mem::swap;
 use std::ptr;
 
+/// A trait to map elements in a heap to a unique index.
+/// The element type of the `IndexdMinHeap` has to implement this trait.
 pub trait Indexing {
+    /// This method has to map a heap element to a unique `usize` index.
     fn as_index(&self) -> usize;
 }
 
-// A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
-// The elements are sorted by integer keys.
+/// A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
+/// The elements are sorted ascending by the ordering defined by the `Ord` trait.
+/// The interface mirros the standard library BinaryHeap (except for the reversed order).
+/// Only the methods necessary for dijkstras algorithm are implemented.
+/// In addition, `increase_key` and `decrease_key` methods are available.
 #[derive(Debug)]
 pub struct IndexdMinHeap<T: Ord + Indexing> {
     positions: Vec<usize>,
@@ -19,25 +62,32 @@ const TREE_ARITY: usize = 4;
 const INVALID_POSITION: usize = std::usize::MAX;
 
 impl<T: Ord + Indexing> IndexdMinHeap<T> {
-    pub fn new(max_id: usize) -> IndexdMinHeap<T> {
+    /// Creates an empty `IndexdMinHeap` as a min-heap.
+    /// The indices (as defined by the `Indexing` trait) of all inserted elements
+    /// will have to be between in `[0, max_index)`
+    pub fn new(max_index: usize) -> IndexdMinHeap<T> {
         IndexdMinHeap {
-            positions: vec![INVALID_POSITION; max_id],
+            positions: vec![INVALID_POSITION; max_index],
             data: Vec::new()
         }
     }
 
+    /// Returns the length of the binary heap.
     pub fn len(&self) -> usize {
         self.data.len()
     }
 
+    /// Checks if the binary heap is empty.
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
 
+    /// Checks if the heap already contains an element mapped to the given index
     pub fn contains_index(&self, id: usize) -> bool {
         self.positions[id] != INVALID_POSITION
     }
 
+    /// Drops all items from the heap.
     pub fn clear(&mut self) {
         for element in &self.data {
             self.positions[element.as_index()] = INVALID_POSITION;
@@ -45,10 +95,12 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
         self.data.clear();
     }
 
+    /// Returns a reference to the smallest item in the heap, or None if it is empty.
     pub fn peek(&self) -> Option<&T> {
         self.data.first()
     }
 
+    /// Removes the greatest item from the binary heap and returns it, or None if it is empty.
     pub fn pop(&mut self) -> Option<T> {
         self.data.pop().map(|mut item| {
             self.positions[item.as_index()] = INVALID_POSITION;
@@ -62,6 +114,8 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
         })
     }
 
+    /// Pushes an item onto the binary heap.
+    /// Panics if an element with the same index already exists.
     pub fn push(&mut self, element: T) {
         assert!(!self.contains_index(element.as_index()));
         let insert_position = self.len();
@@ -70,18 +124,18 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
         self.move_up_in_tree(insert_position);
     }
 
-    // Updates the key of an element if the new key is smaller than the old key.
-    // Does nothing if the new key is larger.
-    // Undefined if the element is not part of the queue.
+    /// Updates the key of an element if the new key is smaller than the old key.
+    /// Does nothing if the new key is larger.
+    /// Panics if the element is not part of the queue.
     pub fn decrease_key(&mut self, element: T) {
         let position = self.positions[element.as_index()];
         self.data[position] = element;
         self.move_up_in_tree(position);
     }
 
-    // Updates the key of an element if the new key is larger than the old key.
-    // Does nothing if the new key is smaller.
-    // Undefined if the element is not part of the queue.
+    /// Updates the key of an element if the new key is larger than the old key.
+    /// Does nothing if the new key is smaller.
+    /// Panics if the element is not part of the queue.
     pub fn increase_key(&mut self, element: T) {
         let position = self.positions[element.as_index()];
         self.data[position] = element;
index 489d9e0..419fa45 100644 (file)
--- a/src/io.rs
+++ b/src/io.rs
@@ -1,3 +1,20 @@
+//! This module contains a few traits and blanket implementations
+//! for (de)serializing and writing/reading numeric data to/from the disc.
+//! To use it you should import the `Load` and `Store` traits and use the
+//! `load_from` and `write_to` methods.
+//!
+//! # Example
+//!
+//! ```
+//! use stud_rust_base::io::*;
+//!
+//! fn test() {
+//!     let head = Vec::<u32>::load_from("head_file_name").expect("could not read head");
+//!     let lat = Vec::<f32>::load_from("node_latitude_file_name").expect("could not read lat");
+//!     head.write_to("output_file").expect("could not write head");
+//! }
+//! ```
+
 use std::fs;
 use std::fs::File;
 use std::io::prelude::*;
@@ -5,11 +22,23 @@ use std::io::Result;
 use std::mem;
 use std::slice;
 
+/// A trait which allows accessing the data of an object as a slice of bytes.
+/// The bytes should represent a serialization of the object and allow
+/// recreating it when reading these bytes again from the disk.
+///
+/// Do not use this Trait but rather the `Store` trait.
 pub trait DataBytes {
+    /// Should return the serialized object as a slice of bytes
     fn data_bytes(&self) -> &[u8];
 }
 
+/// A trait which mutably exposes the internal data of an object so that
+/// a serialized object can be loaded from disk and written back into a precreated
+/// object of the right size.
+///
+/// Do not use this Trait but rather the `Load` trait.
 pub trait DataBytesMut {
+    /// Should return a mutable slice of the internal data of the object
     fn data_bytes_mut(&mut self) -> &mut [u8];
 }
 
@@ -34,7 +63,9 @@ impl<T: Copy> DataBytesMut for Vec<T> {
     }
 }
 
+/// A trait which extends the `DataBytes` trait and exposes a method to write objects to disk.
 pub trait Store : DataBytes {
+    /// Writes the serialized object to the file with the given filename
     fn write_to(&self, filename: &str) -> Result<()> {
         File::create(filename)?.write_all(self.data_bytes())
     }
@@ -43,9 +74,14 @@ pub trait Store : DataBytes {
 impl<T: DataBytes> Store for T {}
 impl<T> Store for [T] where [T]: DataBytes {}
 
+/// A trait to load serialized data back into objects.
 pub trait Load : DataBytesMut + Sized {
+    /// This method must create an object of the correct size for serialized data with the given number of bytes.
+    /// It should not be necessary to call this method directly.
     fn new_with_bytes(num_bytes: usize) -> Self;
 
+    /// This method will load serialized data from the disk, create an object of the appropriate size,
+    /// deserialize the bytes into the object and return the object.
     fn load_from(filename: &str) -> Result<Self> {
         let metadata = fs::metadata(filename)?;
         let mut file = File::open(filename)?;
index ffa1945..28f3f9b 100644 (file)
@@ -1,3 +1,5 @@
+//! A small base framework for route planning student projects.
+
 extern crate time as time_crate;
 
 pub mod index_heap;
index 30da0a2..8a3843c 100644 (file)
@@ -1,5 +1,10 @@
+//! This module contains a few utilities to measure how long executing algorithms takes.
+//! It utilizes the `time` crate.
+
 use time_crate as time;
 
+/// This function will measure how long it takes to execute the given lambda,
+/// print the time and return the result of the lambda.
 pub fn report_time<Out, F: FnOnce() -> Out>(name: &str, f: F) -> Out {
     let start = time::now();
     println!("starting {}", name);
@@ -8,12 +13,15 @@ pub fn report_time<Out, F: FnOnce() -> Out>(name: &str, f: F) -> Out {
     res
 }
 
+/// This function will measure how long it takes to execute the given lambda
+/// and return a tuple of the result of the lambda and a duration object.
 pub fn measure<Out, F: FnOnce() -> Out>(f: F) -> (Out, time::Duration) {
     let start = time::now();
     let res = f();
     (res, time::now() - start)
 }
 
+/// A struct to repeatedly measure the time passed since the timer was started
 #[derive(Debug)]
 pub struct Timer {
     start: time::Tm
@@ -26,18 +34,22 @@ impl Default for Timer {
 }
 
 impl Timer {
+    /// Create and start a new `Timer`
     pub fn new() -> Timer {
         Timer { start: time::now() }
     }
 
+    /// Reset the `Timer`
     pub fn restart(&mut self) {
         self.start = time::now();
     }
 
+    /// Print the passed time in ms since the timer was started
     pub fn report_passed_ms(&self) {
         println!("{}ms", (time::now() - self.start).num_milliseconds());
     }
 
+    /// Return the number of ms passed since the timer was started as a `i64`
     pub fn get_passed_ms(&self) -> i64 {
         (time::now() - self.start).num_milliseconds()
     }
index b10ba13..03d28f1 100644 (file)
@@ -1,6 +1,12 @@
+//! This module contains a few basic type and constant definitions
+
 use std;
 
+/// Node ids are unsigned 32 bit integers
 pub type NodeId = u32;
+/// Edge ids are unsigned 32 bit integers
 pub type EdgeId = u32;
+/// Edge weights are unsigned 32 bit integers
 pub type Weight = u32;
+/// The `INFINITY` weight is defined so that the check `INFINITY + INFINITY < INFINITY` does not cause any overflows
 pub const INFINITY: Weight = std::u32::MAX / 2;