hadean-std 0.1.6

/*

ByteList allows taking of address at iterator, start or end
submit takes two adjacent addresses, whether to position closure at start or end
	closure can iterate from either end, reading and writing (deleting/inserting) and all addresses remain constant

*/

//! A scalable distributed graph datastructure.

use std::{cmp,env,mem,ops,iter,marker,collections,hash};
use hadean::{Sender,Receiver,Connection,Process,ChannelType,Channel,pid,spawn,ProcessSendable};
use linked_hash_map;
// pub use pagerank::pagerank;


/// A scalable distributed graph datastructure.
/// `Graph<V,E>` is a graph datastructure using an adjacency list representation.
///
/// `Graph` is parameterized over:
///
/// - Associated data `V` for nodes and `E` for edges.
///   The associated data can be of arbitrary type.
///
/// The graph uses **O(|V| + |E|)** space, and allows fast node and edge insert, efficient graph search and graph algorithms.
///
/// Here's an example of building a graph with directed edges, and running 30 iterations of pagerank on it:
///
/// ```
/// use hadean_std::graph::{GraphConstructor,Graph,GraphInterpreter};
///
/// let mut graph_constructor: GraphConstructor<String,_,(),()> = GraphConstructor::new(|_|());
/// graph_constructor.push(String::from("http://google.com"), String::from("https://hadean.com"), ());
/// graph_constructor.push(String::from("http://bbc.co.uk"), String::from("https://hadean.com"), ());
/// graph_constructor.push(String::from("https://hadean.com"), String::from("http://alecmocatta.com"), ());
/// let (graph, graph_interpreter): (Graph<(),()>, GraphInterpreter<String>) = graph_constructor.construct();
/// let damping = 0.85f64;
/// let iterations = 30;
/// let graph: Graph<((),f64),()> = graph.pagerank(damping, iterations);
/// let graph: Graph<f64,()> = graph.map(move |vertex| vertex.1, move |edge| edge);
/// let rankmap: HashMap<String, f64> = graph_interpreter.interpret(graph);
/// for (name,score) in rankmap {
/// 	println!("{}: {}", name, score);
/// }
/// ```
///
pub struct Graph<V,E> where V: ProcessSendable, E: ProcessSendable {
	graph: Vec<(V,Vec<(E,usize)>)>,
	edges: usize
}
impl<V,E> Graph<V,E> where V: ProcessSendable, E: ProcessSendable {
	/// Constructs a new, empty `Graph<V,E>`.
	pub fn new() -> Graph<V,E> {
		Graph{graph:Vec::new(),edges:0}
	}
	/// Adds a vertex with associated data `v`.
	pub fn add_vertex(&mut self, v: V) {
		self.graph.push((v,Vec::new()));
	}
	/// Adds an edge between vertices `a` and `b`, with associated data `e`.
	/// Vertices `a` and `b` must have already been added.
	pub fn add_edge(&mut self, a: usize, b: usize, e: E) {
		assert!(b < self.graph.len());
		self.graph[a].1.push((e,b));
		self.edges += 1;
	}
	/// Returns the number of vertices added to the graph.
	pub fn num_vertices(&self) -> usize {
		self.graph.len()
	}
	/// Returns the number of edges added to the graph.
	pub fn num_edges(&self) -> usize {
		self.edges
	}
	/// Map the associated data of vertices and edges using `vertex_map` and `edge_map` respectively.
	pub fn map<VM,EM,V1,E1>(self, vertex_map: VM, edge_map: EM) -> Graph<V1,E1> where VM: Fn(V) -> V1 + ProcessSendable, EM: Fn(E) -> E1 + ProcessSendable, V1: ProcessSendable, E1: ProcessSendable {
		Graph{graph:self.graph.into_iter().map(|(vertex0,vertex1)| {
			(
				vertex_map(vertex0),
				vertex1.into_iter().map(|(edge0,edge1)| {
					(
						edge_map(edge0),
						edge1
					)
				}).collect()
			)
		}).collect(),edges:self.edges}
	}
	/// Run a pregel-like superstep
	pub fn step<F1,F2,M>(&mut self, send: F1, receive: F2) where F1: Fn(V, EdgeIter<E,M>) + ProcessSendable, F2: Fn(V, MessageIter<M>) -> V + ProcessSendable, M: ProcessSendable {
		// todo
	}
	/// Run a pregel-like superstep
	///
	/// # Examples
	/// ```
	/// let mut graph_constructor: GraphConstructor<String,_,(),()> = GraphConstructor::new(|_|());
	/// graph_constructor.push(String::from("http://google.com"), String::from("https://hadean.com"), ());
	/// graph_constructor.push(String::from("http://bbc.co.uk"), String::from("https://hadean.com"), ());
	/// graph_constructor.push(String::from("https://hadean.com"), String::from("http://alecmocatta.com"), ());
	/// let (graph, graph_interpreter): (Graph<(),()>, GraphInterpreter<String>) = graph_constructor.construct();
	/// let damping = 0.85f64;
	/// let iterations = 30;
	/// let num_vertices = self.num_vertices();
	/// let initial = 1.0/num_vertices as f64;
	/// let mut graph: Graph<(V,f64),E> = self.map(move |vertex| (vertex,initial), move |edge| edge);
	/// for _ in 0..iterations {
	/// 	graph.step(
	/// 		move |(_vertex,score), edges| {
	/// 			let out = score / edges.len() as f64;
	/// 			for mut edge in edges {
	/// 				edge.send(out);
	/// 			}
	/// 		}, move |(vertex,score), messages| {
	/// 			let mut sum = 0f64;
	/// 			for val in messages {
	/// 				sum += val;
	/// 			}
	/// 			(vertex,(1.0-damping) / num_vertices as f64 + damping * sum)
	/// 		}
	/// 	)
	/// }
	/// ```
	pub fn step_reduce<F1,F2,F3,M>(&mut self, send: F1, initial: M, reduce: F2, receive: F3) where F1: Fn(V, EdgeIter<E,M>) + ProcessSendable, F2: Fn(M, M) -> M + ProcessSendable, F3: Fn(V, M) -> V + ProcessSendable, M: ProcessSendable {
		// todo
	}
	// fn vertices(&self) -> VertexIter<V> {
	// 	VertexIter{a:&[]}
	// }
}
// struct ReduceFunction<F=core::ops::FnOnce<(),Output=M>>(F);

// struct VertexIter<'a, V> where V: 'a {
// 	a: &'a[V]
// }
// impl<'a,V> VertexIter<'a,V> {
// 	fn len(&self) -> usize {
// 		self.a.len()
// 	}
// }
// impl<'a,V> iter::Iterator for VertexIter<'a,V> {
// 	type Item = V;
// 	fn next(&mut self) -> Option<Self::Item> {
// 		None
// 	}
// }

pub struct Edge<E,M> where E: ProcessSendable, M: ProcessSendable {
	attr: E,
	offset: usize,
	// graph: &mut Graph<V,E>,
	phantom: marker::PhantomData<M>
}
impl<E,M> Edge<E,M> where E: ProcessSendable, M: ProcessSendable {
	pub fn send(&mut self, message: M) {
		// todo
	}
}

pub struct EdgeIter<'a,E,M> where E: 'a + ProcessSendable, M: ProcessSendable {
	a: &'a[E],
	phantom: marker::PhantomData<M>
}
impl<'a,E,M> EdgeIter<'a,E,M> where E: 'a + ProcessSendable, M: ProcessSendable {
	pub fn len(&self) -> usize {
		self.a.len()
	}
}
impl<'a,E,M> iter::Iterator for EdgeIter<'a,E,M> where E: 'a + ProcessSendable, M: ProcessSendable {
	type Item = Edge<E,M>;
	fn next(&mut self) -> Option<Self::Item> {
		None
		// todo
	}
}
pub struct MessageIter<'a,E> where E: 'a + ProcessSendable {
	a: &'a[E]
}
impl<'a,E> iter::Iterator for MessageIter<'a,E> where E: ProcessSendable {
	type Item = E;
	fn next(&mut self) -> Option<Self::Item> {
		None
		// todo
	}
}

/// Construct a `Graph<V,E>` from arbitrary vertex identifiers.
/// Here's an example of building a graph from Strings:
///
/// ```
/// use hadean_std::graph::{GraphConstructor,Graph,GraphInterpreter};
///
/// let mut graph_constructor: GraphConstructor<String,_,(),()> = GraphConstructor::new(|_|());
/// graph_constructor.push(String::from("http://google.com"), String::from("https://hadean.com"), ());
/// graph_constructor.push(String::from("http://bbc.co.uk"), String::from("https://hadean.com"), ());
/// graph_constructor.push(String::from("https://hadean.com"), String::from("http://alecmocatta.com"), ());
/// let (graph, graph_interpreter): (Graph<(),()>, GraphInterpreter<String>) = graph_constructor.construct();
/// ```
///
pub struct GraphConstructor<T,F,V,E> where T: cmp::Eq + hash::Hash + ProcessSendable, F: Fn(&T) -> V + ProcessSendable, V: ProcessSendable, E: ProcessSendable {
	v: F,
	map: linked_hash_map::LinkedHashMap<T,usize>,
	links: Vec<Vec<(E,usize)>>
}
impl<T,F,V,E> GraphConstructor<T,F,V,E> where T: cmp::Eq + hash::Hash + ProcessSendable, F: Fn(&T) -> V + ProcessSendable, V: ProcessSendable, E: ProcessSendable {
	/// Constructs a new, empty `GraphConstructor<T,F,V,E>`. `v` generates initial vertex associated data.
	pub fn new(v: F) -> GraphConstructor<T,F,V,E> {
		GraphConstructor{v:v, map:linked_hash_map::LinkedHashMap::new(), links:Vec::new()}
	}
	/// Add an edge between two vertex identifiers `a` and `b`, where `e` is the edge associated data.
	pub fn push(&mut self, a: T, b: T, e: E) {
		let count = self.map.len();
		let a = if self.map.contains_key(&a) {
			*self.map.get(&a).unwrap()
		} else {
			self.map.insert(a, count);
			self.links.push(Vec::new());
			count
		};
		let count = self.map.len();
		let b = if self.map.contains_key(&b) {
			*self.map.get(&b).unwrap()
		} else {
			self.map.insert(b, count);
			self.links.push(Vec::new());
			count
		};
		self.links[a].push((e,b));
	}
	/// Constructs a `Graph<V,E>` upon which algorithms can be run, and a `GraphInterpreter<T>` which can be used to interpret the graph with the vertex identifiers.
	pub fn construct(self) -> (Graph<V,E>,GraphInterpreter<T>) {
		let mut graph = Graph::new();
		let mut keys = Vec::new();
		for (key,_) in self.map {
			graph.add_vertex((self.v)(&key));
			keys.push(key);
		}
		for (i,vertex_links) in self.links.into_iter().enumerate() {
			for (e,link) in vertex_links {
				graph.add_edge(i, link, e);
			}
		}
		(graph, GraphInterpreter(keys))
	}
}
/// Interpret a `Graph<V,E>` using arbitrary vertex identifiers supplied to `GraphConstructor`.
/// Here's an example of building a graph from Strings and interpreting it:
///
/// ```
/// use hadean_std::graph::{GraphConstructor,Graph,GraphInterpreter};
///
/// let mut graph_constructor: GraphConstructor<String,_,f64,()> = GraphConstructor::new(|_|0.0);
/// graph_constructor.push(String::from("http://google.com"), String::from("https://hadean.com"), ());
/// graph_constructor.push(String::from("http://bbc.co.uk"), String::from("https://hadean.com"), ());
/// graph_constructor.push(String::from("https://hadean.com"), String::from("http://alecmocatta.com"), ());
/// let (graph, graph_interpreter): (Graph<f64,()>, GraphInterpreter<String>) = graph_constructor.construct();
/// let rankmap: HashMap<String, f64> = graph_interpreter.interpret(graph);
/// for (name,score) in rankmap {
/// 	println!("{}: {}", name, score);
/// }
/// ```
///
pub struct GraphInterpreter<T>(Vec<T>) where T: cmp::Eq + hash::Hash + ProcessSendable;
impl<T> GraphInterpreter<T> where T: cmp::Eq + hash::Hash + ProcessSendable {
	/// Interprets a `Graph<V,E>` and returns a `HashMap` mapping vertex identifiers to vertex associated data.
	pub fn interpret<V,E>(self, graph: Graph<V,E>) -> collections::HashMap<T,V> where V: ProcessSendable, E: ProcessSendable {
		let mut ret: collections::HashMap<T,V> = collections::HashMap::new();
		assert!(self.0.len() == graph.graph.len());
		for (key,v) in self.0.into_iter().zip(graph.graph.into_iter()) {
			ret.insert(key, v.0);
		}
		ret
	}
}