From: Tim "S.D.Eagle" Zeitz Date: Wed, 17 Oct 2018 10:53:00 +0000 (+0200) Subject: add a lot of docs and a reference to them in the README X-Git-Url: https://i11git.iti.kit.edu/anon-gitweb/?p=Mitarbeiter%2FTim-Zeitz%2Fstud-rust-base.git;a=commitdiff_plain;h=b52fc015957bcfa65d2e8fbb8d4ea44f4923e3a8;hp=56149781fe0423d57676003b7c42698d295bb279 add a lot of docs and a reference to them in the README --- diff --git a/README.md b/README.md index 3a06ffa..c8cfc59 100644 --- 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. diff --git a/src/index_heap.rs b/src/index_heap.rs index c086dc3..a7af9ca 100644 --- a/src/index_heap.rs +++ b/src/index_heap.rs @@ -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 { positions: Vec, @@ -19,25 +62,32 @@ const TREE_ARITY: usize = 4; const INVALID_POSITION: usize = std::usize::MAX; impl IndexdMinHeap { - pub fn new(max_id: usize) -> IndexdMinHeap { + /// 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 { 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 IndexdMinHeap { 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 { self.data.pop().map(|mut item| { self.positions[item.as_index()] = INVALID_POSITION; @@ -62,6 +114,8 @@ impl IndexdMinHeap { }) } + /// 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 IndexdMinHeap { 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; diff --git a/src/io.rs b/src/io.rs index 489d9e0..419fa45 100644 --- 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::::load_from("head_file_name").expect("could not read head"); +//! let lat = Vec::::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 DataBytesMut for Vec { } } +/// 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 Store for T {} impl 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 { let metadata = fs::metadata(filename)?; let mut file = File::open(filename)?; diff --git a/src/lib.rs b/src/lib.rs index ffa1945..28f3f9b 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,3 +1,5 @@ +//! A small base framework for route planning student projects. + extern crate time as time_crate; pub mod index_heap; diff --git a/src/time.rs b/src/time.rs index 30da0a2..8a3843c 100644 --- a/src/time.rs +++ b/src/time.rs @@ -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>(name: &str, f: F) -> Out { let start = time::now(); println!("starting {}", name); @@ -8,12 +13,15 @@ pub fn report_time 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: 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() } diff --git a/src/types.rs b/src/types.rs index b10ba13..03d28f1 100644 --- a/src/types.rs +++ b/src/types.rs @@ -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;