<commit_before>//! Directed Graphs.
#![crate_type = "lib"]
#![feature(macro_rules, default_type_params)]
#![deny(warnings, missing_doc)]

use std::collections::Deque;
use std::collections::hashmap;
use std::collections::hashmap::{HashMap, HashSet};
use std::collections::ringbuf::RingBuf;
use std::iter;
use std::option;
use std::rc::Rc;

/// All the edges in a graph, tagged with parameter `E`.
pub type EdgeMap<E> = HashMap<uint, HashMap<uint, Rc<E>>>;

/// A graph is parameterized by data of your choice, so you can tag nodes and
/// edges with custom data.
///
/// This library was created to scratch my own itches. If you want to see more
/// methods implemented, I will be very responsive in merging patches.
#[deriving(Clone, PartialEq, Eq, Show)]
pub struct Graph<V, E> {
  nodes: HashMap<uint, V>,
  edges: EdgeMap<E>,

  // A reverse mapping of every edge. Useful for several algorithms (such as
  // cycle detection) and does not increase the asymptotic complexity.
  rev_edges: EdgeMap<E>,
}

pub type Verticies<'a, V> = hashmap::Entries<'a, uint, V>;

// An iterator through all the nodes connected to a node.
pub type Connections<'a, E> =
  iter::Map<'a,
    (uint, (&'a uint, &'a Rc<E>)),
    (uint, uint, Rc<E>),
    iter::Zip<
      iter::Repeat<uint>,
      iter::FlatMap<'a,
        &'a HashMap<uint, Rc<E>>,
        option::Item<&'a HashMap<uint, Rc<E>>>,
        hashmap::Entries<'a, uint, Rc<E>>>>>;

impl<V, E> Graph<V, E> {
  /// Construct a new, empty graph.
  pub fn new() -> Graph<V, E> {
    let g =
      Graph {
        nodes:     HashMap::new(),
        edges:     HashMap::new(),
        rev_edges: HashMap::new(),
      };

    g.invariant();

    g
  }

  /// Empty out the graph for reuse.
  pub fn clear(&mut self) {
    self.nodes = HashMap::new();
    self.clear_edges();
  }

  /// Remove all edges from the graph.
  pub fn clear_edges(&mut self) {
    self.edges     = HashMap::new();
    self.rev_edges = HashMap::new();
  }

  /// Returns an iterator over every node in the graph.
  pub fn verticies<'a>(&'a self) -> Verticies<'a, V> {
    self.nodes.iter()
  }

  /// Returns the number of verticies in the graph.
  pub fn number_of_verticies(&self) -> uint {
    self.nodes.len()
  }

  /// Returns the number of nodes in the graph.
  pub fn number_of_edges(&self) -> uint {
    self.edges.iter().flat_map(|(_, es)| es.iter()).count()
  }

  #[cfg(test)]
  fn create_directly(vs: Vec<(uint, V)>, es: Vec<(uint, uint, E)>) -> Graph<V, E> {
    let mut g = Graph::new();

    g.nodes = vs.move_iter().map(|(i, v)| (i, v)).collect();
    
    for (from, to, e) in es.move_iter() {
      let rce = Rc::new(e);

      let emap = g.edges.find_or_insert_with(from, |_| HashMap::new());
      emap.insert(to, rce.clone());

      let rmap = g.rev_edges.find_or_insert_with(to, |_| HashMap::new());
      rmap.insert(from, rce);
    }

    g.invariant();

    g
  }

  #[cfg(test)]
  fn invariant(&self) {
    for (from, tos) in self.edges.iter() {
      assert!(self.nodes.contains_key(from));
      for to in tos.keys() {
        assert!(self.nodes.contains_key(to));
        match self.rev_edges.find(to) {
          None => fail!("{} was not found in the rev map.", &to),
          Some(r_map) => {
            assert!(r_map.contains_key(from));
          }
        }
      }
    }

    let num_edges = self.edges.iter().flat_map(|(_, es)| es.iter()).count();
    let num_rev_edges = self.rev_edges.iter().flat_map(|(_, es)| es.iter()).count();
    assert_eq!(num_edges, num_rev_edges);
  }

  #[cfg(not(test))]
  fn invariant(&self) {}

  /// Inserts a vertex into the graph. If such a vertex already exists
  /// (possibly with another tag), the new vertex will silently overwrite it.<commit_msg>slightly more efficient edge counting<commit_after>//! Directed Graphs.
#![crate_type = "lib"]
#![feature(macro_rules, default_type_params)]
#![deny(warnings, missing_doc)]

use std::collections::Deque;
use std::collections::hashmap;
use std::collections::hashmap::{HashMap, HashSet};
use std::collections::ringbuf::RingBuf;
use std::iter;
use std::option;
use std::rc::Rc;

/// All the edges in a graph, tagged with parameter `E`.
pub type EdgeMap<E> = HashMap<uint, HashMap<uint, Rc<E>>>;

/// A graph is parameterized by data of your choice, so you can tag nodes and
/// edges with custom data.
///
/// This library was created to scratch my own itches. If you want to see more
/// methods implemented, I will be very responsive in merging patches.
#[deriving(Clone, PartialEq, Eq, Show)]
pub struct Graph<V, E> {
  nodes: HashMap<uint, V>,
  edges: EdgeMap<E>,

  // A reverse mapping of every edge. Useful for several algorithms (such as
  // cycle detection) and does not increase the asymptotic complexity.
  rev_edges: EdgeMap<E>,
}

pub type Verticies<'a, V> = hashmap::Entries<'a, uint, V>;

// An iterator through all the nodes connected to a node.
pub type Connections<'a, E> =
  iter::Map<'a,
    (uint, (&'a uint, &'a Rc<E>)),
    (uint, uint, Rc<E>),
    iter::Zip<
      iter::Repeat<uint>,
      iter::FlatMap<'a,
        &'a HashMap<uint, Rc<E>>,
        option::Item<&'a HashMap<uint, Rc<E>>>,
        hashmap::Entries<'a, uint, Rc<E>>>>>;

impl<V, E> Graph<V, E> {
  /// Construct a new, empty graph.
  pub fn new() -> Graph<V, E> {
    let g =
      Graph {
        nodes:     HashMap::new(),
        edges:     HashMap::new(),
        rev_edges: HashMap::new(),
      };

    g.invariant();

    g
  }

  /// Empty out the graph for reuse.
  pub fn clear(&mut self) {
    self.nodes = HashMap::new();
    self.clear_edges();
  }

  /// Remove all edges from the graph.
  pub fn clear_edges(&mut self) {
    self.edges     = HashMap::new();
    self.rev_edges = HashMap::new();
  }

  /// Returns an iterator over every node in the graph.
  pub fn verticies<'a>(&'a self) -> Verticies<'a, V> {
    self.nodes.iter()
  }

  /// Returns the number of verticies in the graph.
  pub fn number_of_verticies(&self) -> uint {
    self.nodes.len()
  }

  /// Returns the number of nodes in the graph.
  pub fn number_of_edges(&self) -> uint {
    self.edges.iter().map(|(_, es)| es.len()).fold(0, |x, y| x + y)
  }

  #[cfg(test)]
  fn create_directly(vs: Vec<(uint, V)>, es: Vec<(uint, uint, E)>) -> Graph<V, E> {
    let mut g = Graph::new();

    g.nodes = vs.move_iter().map(|(i, v)| (i, v)).collect();
    
    for (from, to, e) in es.move_iter() {
      let rce = Rc::new(e);

      let emap = g.edges.find_or_insert_with(from, |_| HashMap::new());
      emap.insert(to, rce.clone());

      let rmap = g.rev_edges.find_or_insert_with(to, |_| HashMap::new());
      rmap.insert(from, rce);
    }

    g.invariant();

    g
  }

  #[cfg(test)]
  fn invariant(&self) {
    for (from, tos) in self.edges.iter() {
      assert!(self.nodes.contains_key(from));
      for to in tos.keys() {
        assert!(self.nodes.contains_key(to));
        match self.rev_edges.find(to) {
          None => fail!("{} was not found in the rev map.", &to),
          Some(r_map) => {
            assert!(r_map.contains_key(from));
          }
        }
      }
    }

    let num_edges = self.edges.iter().map(|(_, es)| es.len()).fold(0, |x, y| x + y);
    let num_rev_edges = self.rev_edges.iter().map(|(_, es)| es.len()).fold(0, |x, y| x + y);
    assert_eq!(num_edges, num_rev_edges);
  }

  #[cfg(not(test))]
  fn invariant(&self) {}

  /// Inserts a vertex into the graph. If such a vertex already exists
  /// (possibly with another tag), the new vertex will silently overwrite it.
{'fraction_non_alphanumeric': 0.17211589580010633, 'fraction_numerical': 0.00039872408293460925, 'mean_word_length': 2.923357664233577, 'pattern_counts': {'":': 0, '<': 67, '<?xml version=': 0, '>': 81, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5951896', 'n_tokens_mistral': 2647, 'n_tokens_neox': 2627, 'n_words': 749}