use serde::de::Error;
use serde::{Serialize, Serializer, Deserialize, Deserializer};
use std::marker::PhantomData;
use prelude::*;
use EdgeType;
use graph::Node;
use graph::{IndexType, Edge};
use stable_graph::StableGraph;
use util::rev;
use serde_utils::MappedSequenceVisitor;
use serde_utils::CollectSeqWithLength;
use serde_utils::{IntoSerializable, FromDeserialized};
use visit::NodeIndexable;
use super::super::serialization::{EdgeProperty, invalid_length_err, invalid_node_err};
#[derive(Serialize)]
#[serde(rename = "Graph")]
#[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))]
pub struct SerStableGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> {
nodes: Somes<&'a [Node<Option<N>, Ix>]>,
node_holes: Holes<&'a [Node<Option<N>, Ix>]>,
edge_property: EdgeProperty,
#[serde(serialize_with="ser_stable_graph_edges")]
edges: &'a [Edge<Option<E>, Ix>],
}
#[derive(Deserialize)]
#[serde(rename = "Graph")]
#[serde(bound(deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>"))]
pub struct DeserStableGraph<N, E, Ix> {
#[serde(deserialize_with="deser_stable_graph_nodes")]
nodes: Vec<Node<Option<N>, Ix>>,
#[serde(default="Vec::new")]
node_holes: Vec<NodeIndex<Ix>>,
edge_property: EdgeProperty,
#[serde(deserialize_with="deser_stable_graph_edges")]
edges: Vec<Edge<Option<E>, Ix>>,
}
struct Somes<T>(usize, T);
impl<'a, N, Ix> Serialize for Somes<&'a [Node<Option<N>, Ix>]>
where N: Serialize,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer,
{
serializer.collect_seq_with_length(self.0,
self.1.iter().filter_map(|node| node.weight.as_ref()))
}
}
struct Holes<T>(usize, T);
impl<'a, N, Ix> Serialize for Holes<&'a [Node<Option<N>, Ix>]>
where Ix: Serialize + IndexType,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer,
{
serializer.collect_seq_with_length(self.0,
self.1.iter()
.enumerate()
.filter_map(|(i, node)| if node.weight.is_none() {
Some(NodeIndex::<Ix>::new(i))
} else {
None
}))
}
}
fn ser_stable_graph_edges<S, E, Ix>(edges: &&[Edge<Option<E>, Ix>], serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer,
E: Serialize,
Ix: Serialize + IndexType,
{
serializer.collect_seq_exact(
edges.iter()
.map(|edge| edge.weight.as_ref().map(|w| (
edge.source(),
edge.target(),
w
))))
}
fn deser_stable_graph_nodes<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Node<Option<N>, Ix>>, D::Error>
where D: Deserializer<'de>,
N: Deserialize<'de>,
Ix: IndexType + Deserialize<'de>,
{
deserializer.deserialize_seq(MappedSequenceVisitor::new(|n|
Ok(Node {
weight: Some(n),
next: [EdgeIndex::end(); 2],
})
))
}
fn deser_stable_graph_edges<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Edge<Option<N>, Ix>>, D::Error>
where D: Deserializer<'de>,
N: Deserialize<'de>,
Ix: IndexType + Deserialize<'de>,
{
deserializer.deserialize_seq(MappedSequenceVisitor::<Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>, _, _>::new(|x|
if let Some((i, j, w)) = x {
Ok(Edge {
weight: Some(w),
node: [i, j],
next: [EdgeIndex::end(); 2],
})
} else {
Ok(Edge {
weight: None,
node: [NodeIndex::end(); 2],
next: [EdgeIndex::end(); 2],
})
}
))
}
impl<'a, N, E, Ty, Ix> IntoSerializable for &'a StableGraph<N, E, Ty, Ix>
where Ix: IndexType,
Ty: EdgeType,
{
type Output = SerStableGraph<'a, N, E, Ix>;
fn into_serializable(self) -> Self::Output {
let nodes = &self.raw_nodes()[..self.node_bound()];
let node_count = self.node_count();
let hole_count = nodes.len() - node_count;
let edges = &self.raw_edges()[..self.edge_bound()];
SerStableGraph {
nodes: Somes(node_count, nodes),
node_holes: Holes(hole_count, nodes),
edges: edges,
edge_property: EdgeProperty::from(PhantomData::<Ty>),
}
}
}
impl<N, E, Ty, Ix> Serialize for StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType + Serialize,
N: Serialize,
E: Serialize,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer
{
self.into_serializable().serialize(serializer)
}
}
impl<'a, N, E, Ty, Ix> FromDeserialized for StableGraph<N, E, Ty, Ix>
where Ix: IndexType,
Ty: EdgeType,
{
type Input = DeserStableGraph<N, E, Ix>;
fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
where E2: Error
{
let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?;
let mut nodes = input.nodes;
let node_holes = input.node_holes;
let edges = input.edges;
if edges.len() >= <Ix as IndexType>::max().index() {
Err(invalid_length_err::<Ix, _>("edge", edges.len()))?
}
let mut offset = node_holes.len();
let node_bound = node_holes.len() + nodes.len();
for hole_pos in rev(node_holes) {
offset -= 1;
if hole_pos.index() >= node_bound {
Err(invalid_node_err(hole_pos.index(), node_bound))?;
}
let insert_pos = hole_pos.index() - offset;
nodes.insert(insert_pos, Node {
weight: None,
next: [EdgeIndex::end(); 2],
});
}
if nodes.len() >= <Ix as IndexType>::max().index() {
Err(invalid_length_err::<Ix, _>("node", nodes.len()))?
}
let node_bound = nodes.len();
let mut sgr = StableGraph {
g: Graph {
nodes: nodes,
edges: edges,
ty: ty,
},
node_count: 0,
edge_count: 0,
free_edge: EdgeIndex::end(),
free_node: NodeIndex::end(),
};
sgr.link_edges().map_err(|i| invalid_node_err(i.index(), node_bound))?;
Ok(sgr)
}
}
impl<'de, N, E, Ty, Ix> Deserialize<'de> for StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType + Deserialize<'de>,
N: Deserialize<'de>,
E: Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where D: Deserializer<'de>
{
Self::from_deserialized(DeserStableGraph::deserialize(deserializer)?)
}
}
#[test]
fn test_from_deserialized_with_holes() {
use graph::node_index;
use stable_graph::StableUnGraph;
use serde::de::value::Error as SerdeError;
use itertools::assert_equal;
let input = DeserStableGraph::<_, (), u32> {
nodes: vec![
Node {
weight: Some(1),
next: [EdgeIndex::end(); 2],
},
Node {
weight: Some(4),
next: [EdgeIndex::end(); 2],
},
Node {
weight: Some(5),
next: [EdgeIndex::end(); 2],
},
],
node_holes: vec![
node_index(0),
node_index(2),
node_index(3),
node_index(6),
],
edges: vec![],
edge_property: EdgeProperty::Undirected,
};
let graph = StableUnGraph::from_deserialized::<SerdeError>(input).unwrap();
assert_eq!(graph.node_count(), 3);
assert_equal(
graph.raw_nodes().iter().map(|n| n.weight.as_ref().cloned()),
vec![None, Some(1), None, None, Some(4), Some(5), None]);
}