Struct IndexedGraph

Source

pub struct IndexedGraph<K, V> { /* private fields */ }

Expand description

A node in the graph is identified by the key. Keys are stored in the order they were inserted, a redundant copy is stored in the index. Values don’t have this redundancy. There could be more than one values for a key.

Implementations§

Source §

impl<K: Ord + Clone, V> IndexedGraph<K, V>

Source

pub fn new() -> IndexedGraph<K, V>

Makes a new, empty IndexedGraph.

§Examples

use std::collections::BTreeMap;
let mut map = BTreeMap::<u8,u8>::new();
assert_eq!(core::mem::size_of::<BTreeMap<u8,u8>>(), 24);
assert_eq!(core::mem::size_of_val(&map), 24);

use igraph::IndexedGraph;
let mut graph = IndexedGraph::new();

assert_eq!(core::mem::size_of::<IndexedGraph<u8,u8>>(), 96);
assert_eq!(core::mem::size_of_val(&graph), 96);

// entries can now be inserted into the empty graph
graph.insert(1, "a");

Source

pub fn clear(&mut self)

Clears the graph, removing all elements.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "a");
graph.clear();
// assert!(graph.is_empty());

Source

pub fn get(&self, key: &K) -> Vec<&V>

Returns a reference to the values corresponding to the key.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "a");
assert_eq!(graph.get(&1), vec![&"a"]);
assert_eq!(graph.get(&2), Vec::<&&str>::new());

Source

pub fn get_key_values(&self, key: &K) -> Vec<(&K, &V)>

Returns the key-value pairs corresponding to the supplied key.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "a");
assert_eq!(graph.get_key_values(&1), vec![(&1, &"a")]);
assert_eq!(graph.get_key_values(&2), vec![]);

Source

pub fn first_key_value(&self) -> Option<(&K, &V)>

Returns the first key-value pair in the graph. The key in this pair is the minimum key in the graph.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
assert_eq!(graph.first_key_value(), None);
graph.insert(1, "b");
graph.insert(2, "a");
assert_eq!(graph.first_key_value(), Some((&1, &"b")));

Source

pub fn pop_first(&mut self) -> Option<(K, V)>

Removes and returns the first element in the graph. The key of this element is the key first inserted into the graph.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "a");
graph.insert(2, "b");
while let Some((key, _val)) = graph.pop_first() {
    assert!(graph.iter().all(|(k, _v)| *k > key));
}
for item in graph.iter() {
    assert!(*item.0 < 3);
    assert!(*item.1 == "a" || *item.1 == "b");
}
assert!(graph.is_empty());

Source

pub fn last_key_value(&self) -> Option<(&K, &V)>

Returns the last key-value pair in the graph. The key in this pair is last inserted in the graph.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "b");
graph.insert(2, "a");
assert_eq!(graph.last_key_value(), Some((&2, &"a")));

Source

pub fn pop_last(&mut self) -> Option<(K, V)>

Removes and returns the last element in the graph. The key of this element is the last inserted in the graph.

§Examples

Draining elements in descending order, while keeping a usable graph each iteration.

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "a");
graph.insert(2, "b");
while let Some((key, _val)) = graph.pop_last() {
    assert!(graph.iter().all(|(k, _v)| *k < key));
}
assert!(graph.is_empty());

Source

pub fn contains_key(&self, key: &K) -> bool

Returns true if the graph contains a value for the specified key using the internal index.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(1, "a");
assert_eq!(graph.contains_key(&1), true);
assert_eq!(graph.contains_key(&2), false);

Source

pub fn insert(&mut self, key: K, value: V) -> Option<&V>

Inserts a key-value pair into the graph.

If the graph did not have this key present, None is returned.

If the graph did have this key present, the value is inserted after the existing one. Then the new value is returned. The key is not updated, only inserted the first time.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
assert_eq!(graph.insert(37, "a"), Some(&"a"));
assert_eq!(graph.is_empty(), false);

graph.insert(37, "b");
assert_eq!(graph.insert(37, "c"), Some(&"c"));
//assert_eq!(graph[&37], "c");

Source

pub fn insert_edge(&mut self, from: K, to: K) -> Option<(&K, &K)>

Inserts a key-value pair into the graph.

If the graph did not have this key present, None is returned.

If the graph did have this key present, the value is inserted after the existing one. Then the new value is returned. The key is not updated, only inserted the first time.

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
assert_eq!(graph.insert(37, "a"), Some(&"a"));
assert_eq!(graph.insert(12, "b"), Some(&"b"));
assert_eq!(graph.is_empty(), false);

graph.insert_edge(12, 37);
assert_eq!(graph.insert(37, "c"), Some(&"c"));
//assert_eq!(graph[&37], "c");

Source

pub fn len(&self) -> usize

Returns the number of elements in the graph.

§Examples

use igraph::IndexedGraph;

let mut a = IndexedGraph::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

Source

pub fn is_empty(&self) -> bool

Returns true if the graph contains no elements.

§Examples

use igraph::IndexedGraph;

let mut a = IndexedGraph::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

Source

pub fn index_copy(&self) -> BTreeMap<K, Vec<usize>>

Source

pub fn index(&self, key: K) -> Vec<&V>

Returns a Vec of references to the values corresponding to the supplied key.

§Examples

use igraph::IndexedGraph;

let mut a = IndexedGraph::new();
a.insert(1, "a");
assert_eq!(*a.index(1), [&"a"]);

Source

pub fn iter(&self) -> Iter<'_, K, V> ⓘ

Gets an iterator over the entries of the graph, sorted by key. IndexedGraph preserves the order of insertion for iter().

§Examples

use igraph::IndexedGraph;

let mut graph = IndexedGraph::new();
graph.insert(3, "c");
graph.insert(2, "b");
graph.insert(1, "a");

for (key, value) in graph.iter() {
    println!("{}: {}", key, value);
}

let (first_key, first_value) = graph.iter().next().unwrap();
assert_eq!((*first_key, *first_value), (3, "c"));