Initial commit

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
index 0000000..53eaa21
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+/target
+**/*.rs.bk

diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644 (file)
index 0000000..bc66e43
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,53 @@
+[[package]]
+name = "libc"
+version = "0.2.43"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "redox_syscall"
+version = "0.1.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "stud-rust-base"
+version = "0.1.0"
+dependencies = [
+ "time 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "time"
+version = "0.1.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "libc 0.2.43 (registry+https://github.com/rust-lang/crates.io-index)",
+ "redox_syscall 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
+ "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "winapi"
+version = "0.3.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "winapi-i686-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "winapi-x86_64-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[metadata]
+"checksum libc 0.2.43 (registry+https://github.com/rust-lang/crates.io-index)" = "76e3a3ef172f1a0b9a9ff0dd1491ae5e6c948b94479a3021819ba7d860c8645d"
+"checksum redox_syscall 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)" = "c214e91d3ecf43e9a4e41e578973adeb14b474f2bee858742d127af75a0112b1"
+"checksum time 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)" = "d825be0eb33fda1a7e68012d51e9c7f451dc1a69391e7fdc197060bb8c56667b"
+"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0"
+"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
+"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"

diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644 (file)
index 0000000..efe5553
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "stud-rust-base"
+version = "0.1.0"
+authors = ["Tim Zeitz <tim.zeitz@kit.edu>"]
+
+[dependencies]
+time = "0.1.40"

diff --git a/src/index_heap.rs b/src/index_heap.rs
new file mode 100644 (file)
index 0000000..2f608d9
--- /dev/null
+++ b/src/index_heap.rs
@@ -0,0 +1,222 @@
+use std;
+use std::cmp::min;
+use std::mem::swap;
+use std::ptr;
+
+pub trait Indexing {
+    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.
+#[derive(Debug)]
+pub struct IndexdMinHeap<T: Ord + Indexing> {
+    positions: Vec<usize>,
+    data: Vec<T>
+}
+
+const TREE_ARITY: usize = 4;
+const INVALID_POSITION: usize = std::usize::MAX;
+
+impl<T: Ord + Indexing> IndexdMinHeap<T> {
+    #[allow(dead_code)]
+    pub fn new(max_id: usize) -> IndexdMinHeap<T> {
+        IndexdMinHeap {
+            positions: vec![INVALID_POSITION; max_id],
+            data: Vec::new()
+        }
+    }
+
+    pub fn len(&self) -> usize {
+        self.data.len()
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    #[allow(dead_code)]
+    pub fn contains_index(&self, id: usize) -> bool {
+        self.positions[id] != INVALID_POSITION
+    }
+
+    #[allow(dead_code)]
+    pub fn clear(&mut self) {
+        for element in &self.data {
+            self.positions[element.as_index()] = INVALID_POSITION;
+        }
+        self.data.clear();
+    }
+
+    #[allow(dead_code)]
+    pub fn peek(&self) -> Option<&T> {
+        self.data.first()
+    }
+
+    #[allow(dead_code)]
+    pub fn pop(&mut self) -> Option<T> {
+        self.data.pop().map(|mut item| {
+            self.positions[item.as_index()] = INVALID_POSITION;
+            if !self.is_empty() {
+                self.positions[item.as_index()] = 0;
+                self.positions[self.data[0].as_index()] = INVALID_POSITION;
+                swap(&mut item, &mut self.data[0]);
+                self.move_down_in_tree(0);
+            }
+            item
+        })
+    }
+
+    #[allow(dead_code)]
+    pub fn push(&mut self, element: T) {
+        assert!(!self.contains_index(element.as_index()));
+        let insert_position = self.len();
+        self.positions[element.as_index()] = insert_position;
+        self.data.push(element);
+        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.
+    #[allow(dead_code)]
+    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.
+    #[allow(dead_code)]
+    pub fn increase_key(&mut self, element: T) {
+        let position = self.positions[element.as_index()];
+        self.data[position] = element;
+        self.move_down_in_tree(position);
+    }
+
+    fn move_up_in_tree(&mut self, position: usize) {
+        unsafe {
+            let mut position = position;
+            let mut hole = Hole::new(&mut self.data, position);
+
+            while position > 0 {
+                let parent = (position - 1) / TREE_ARITY;
+
+                if hole.get(parent) < hole.element() {
+                    break;
+                }
+
+                self.positions[hole.get(parent).as_index()] = position;
+                hole.move_to(parent);
+                position = parent;
+            }
+
+            self.positions[hole.element().as_index()] = position;
+        }
+    }
+
+    fn move_down_in_tree(&mut self, position: usize) {
+        unsafe {
+            let mut position = position;
+            let heap_size = self.len();
+            let mut hole = Hole::new(&mut self.data, position);
+
+            loop {
+                if let Some(smallest_child) = IndexdMinHeap::<T>::children_index_range(position, heap_size).min_by_key(|&child_index| hole.get(child_index)) {
+                    if hole.get(smallest_child) >= hole.element() {
+                        self.positions[hole.element().as_index()] = position;
+                        return; // no child is smaller
+                    }
+
+                    self.positions[hole.get(smallest_child).as_index()] = position;
+                    hole.move_to(smallest_child);
+                    position = smallest_child;
+                } else {
+                    self.positions[hole.element().as_index()] = position;
+                    return; // no children at all
+                }
+            }
+        }
+    }
+
+    fn children_index_range(parent_index: usize, heap_size: usize) -> std::ops::Range<usize> {
+        let first_child = TREE_ARITY * parent_index + 1;
+        let last_child = min(TREE_ARITY * parent_index + TREE_ARITY + 1, heap_size);
+        first_child..last_child
+    }
+}
+
+
+// This is an optimization copied straight from the rust stdlib binary heap
+// it allows to avoid always swapping elements pairwise and rather
+// move each element only once.
+
+
+/// Hole represents a hole in a slice i.e. an index without valid value
+/// (because it was moved from or duplicated).
+/// In drop, `Hole` will restore the slice by filling the hole
+/// position with the value that was originally removed.
+struct Hole<'a, T: 'a> {
+    data: &'a mut [T],
+    /// `elt` is always `Some` from new until drop.
+    elt: Option<T>,
+    pos: usize,
+}
+
+impl<'a, T> Hole<'a, T> {
+    /// Create a new Hole at index `pos`.
+    ///
+    /// Unsafe because pos must be within the data slice.
+    #[inline]
+    unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
+        debug_assert!(pos < data.len());
+        let elt = ptr::read(&data[pos]);
+        Hole {
+            data,
+            elt: Some(elt),
+            pos,
+        }
+    }
+
+    /// Returns a reference to the element removed.
+    #[inline]
+    fn element(&self) -> &T {
+        self.elt.as_ref().unwrap()
+    }
+
+    /// Returns a reference to the element at `index`.
+    ///
+    /// Unsafe because index must be within the data slice and not equal to pos.
+    #[inline]
+    unsafe fn get(&self, index: usize) -> &T {
+        debug_assert!(index != self.pos);
+        debug_assert!(index < self.data.len());
+        self.data.get_unchecked(index)
+    }
+
+    /// Move hole to new location
+    ///
+    /// Unsafe because index must be within the data slice and not equal to pos.
+    #[inline]
+    unsafe fn move_to(&mut self, index: usize) {
+        debug_assert!(index != self.pos);
+        debug_assert!(index < self.data.len());
+        let index_ptr: *const _ = self.data.get_unchecked(index);
+        let hole_ptr = self.data.get_unchecked_mut(self.pos);
+        ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
+        self.pos = index;
+    }
+}
+
+impl<'a, T> Drop for Hole<'a, T> {
+    #[inline]
+    fn drop(&mut self) {
+        // fill the hole again
+        unsafe {
+            let pos = self.pos;
+            ptr::write(self.data.get_unchecked_mut(pos), self.elt.take().unwrap());
+        }
+    }
+}

diff --git a/src/io.rs b/src/io.rs
new file mode 100644 (file)
index 0000000..489d9e0
--- /dev/null
+++ b/src/io.rs
@@ -0,0 +1,67 @@
+use std::fs;
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::Result;
+use std::mem;
+use std::slice;
+
+pub trait DataBytes {
+    fn data_bytes(&self) -> &[u8];
+}
+
+pub trait DataBytesMut {
+    fn data_bytes_mut(&mut self) -> &mut [u8];
+}
+
+impl<T: Copy> DataBytes for [T] {
+    fn data_bytes(&self) -> &[u8] {
+        let num_bytes = self.len() * mem::size_of::<T>();
+        unsafe { slice::from_raw_parts(self.as_ptr() as *const u8, num_bytes) }
+    }
+}
+
+impl<T: Copy> DataBytesMut for [T] {
+    fn data_bytes_mut(&mut self) -> &mut [u8] {
+        let num_bytes = self.len() * mem::size_of::<T>();
+        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr() as *mut u8, num_bytes) }
+    }
+}
+
+impl<T: Copy> DataBytesMut for Vec<T> {
+    fn data_bytes_mut(&mut self) -> &mut [u8] {
+        let num_bytes = self.len() * mem::size_of::<T>();
+        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr() as *mut u8, num_bytes) }
+    }
+}
+
+pub trait Store : DataBytes {
+    fn write_to(&self, filename: &str) -> Result<()> {
+        File::create(filename)?.write_all(self.data_bytes())
+    }
+}
+
+impl<T: DataBytes> Store for T {}
+impl<T> Store for [T] where [T]: DataBytes {}
+
+pub trait Load : DataBytesMut + Sized {
+    fn new_with_bytes(num_bytes: usize) -> Self;
+
+    fn load_from(filename: &str) -> Result<Self> {
+        let metadata = fs::metadata(filename)?;
+        let mut file = File::open(filename)?;
+
+        let mut object = Self::new_with_bytes(metadata.len() as usize);
+        assert_eq!(metadata.len() as usize, object.data_bytes_mut().len());
+        file.read_exact(object.data_bytes_mut())?;
+
+        Ok(object)
+    }
+}
+
+impl<T: Default + Copy> Load for Vec<T> {
+    fn new_with_bytes(num_bytes: usize) -> Self {
+        assert_eq!(num_bytes % mem::size_of::<T>(), 0);
+        let num_elements = num_bytes / mem::size_of::<T>();
+        (0..num_elements).map(|_| T::default()).collect()
+    }
+}

diff --git a/src/main.rs b/src/main.rs
new file mode 100644 (file)
index 0000000..c920768
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,33 @@
+extern crate time as time_crate;
+
+mod index_heap;
+mod io;
+mod time;
+mod types;
+
+use types::*;
+use io::*;
+use time::*;
+
+use std::{env, path::Path};
+
+fn main() {
+    let mut args = env::args();
+    args.next();
+
+    let arg = &args.next().expect("No directory arg given");
+    let path = Path::new(arg);
+
+    let first_out: Vec<EdgeId> = Vec::load_from(path.join("first_out").to_str().unwrap()).expect("could not read first_out");
+    let head: Vec<NodeId> = Vec::load_from(path.join("head").to_str().unwrap()).expect("could not read head");
+    let travel_time: Vec<Weight> = Vec::load_from(path.join("travel_time").to_str().unwrap()).expect("could not read travel_time");
+
+    report_time("iterating over arcs of some node", || {
+        let node_id = 42;
+        for &edge_id in &head[first_out[node_id] as usize .. first_out[node_id + 1] as usize] {
+            println!("There is an arc from {} to {} with weight {}", node_id, head[edge_id as usize], travel_time[edge_id as usize]);
+        }
+    });
+
+    vec![42; 42].write_to(path.join("distances").to_str().unwrap()).expect("could not write distances");
+}

diff --git a/src/time.rs b/src/time.rs
new file mode 100644 (file)
index 0000000..2f6e9ac
--- /dev/null
+++ b/src/time.rs
@@ -0,0 +1,45 @@
+use time_crate as time;
+
+#[allow(dead_code)]
+pub fn report_time<Out, F: FnOnce() -> Out>(name: &str, f: F) -> Out {
+    let start = time::now();
+    println!("starting {}", name);
+    let res = f();
+    println!("done {} - took: {}", name, (time::now() - start));
+    res
+}
+
+#[allow(dead_code)]
+pub fn measure<Out, F: FnOnce() -> Out>(f: F) -> (Out, time::Duration) {
+    let start = time::now();
+    let res = f();
+    (res, time::now() - start)
+}
+
+#[allow(dead_code)]
+#[derive(Debug)]
+pub struct Timer {
+    start: time::Tm
+}
+
+impl Timer {
+    #[allow(dead_code)]
+    pub fn new() -> Timer {
+        Timer { start: time::now() }
+    }
+
+    #[allow(dead_code)]
+    pub fn restart(&mut self) {
+        self.start = time::now();
+    }
+
+    #[allow(dead_code)]
+    pub fn report_passed_ms(&self) {
+        println!("{}ms", (time::now() - self.start).num_milliseconds());
+    }
+
+    #[allow(dead_code)]
+    pub fn get_passed_ms(&self) -> i64 {
+        (time::now() - self.start).num_milliseconds()
+    }
+}

diff --git a/src/types.rs b/src/types.rs
new file mode 100644 (file)
index 0000000..bb11a00
--- /dev/null
+++ b/src/types.rs
@@ -0,0 +1,10 @@
+use std;
+
+#[allow(dead_code)]
+pub type NodeId = u32;
+#[allow(dead_code)]
+pub type EdgeId = u32;
+#[allow(dead_code)]
+pub type Weight = u32;
+#[allow(dead_code)]
+pub const INFINITY: Weight = std::u32::MAX / 2;