使用HashMap實現類似SQL的RIGHT OUTER JOIN的迭代器適配器

Question

我試圖用類似SQL的連接迭代器擴展bluss的rust-itertools。我使用散列連接策略遇到了RIGHT OUTER JOIN的特定問題（策略本身實際上非常簡單）。

迭代器適配器結構需要2個輸入迭代器，其中第二個（右側）被加載到HashMap中。迭代的工作原理如下：

1. 從左側迭代器的項目是對地圖匹配 - 在匹配的情況下，返回這兩個項目
2. 當左迭代器耗盡時，從返回非匹配的值地圖

問題是，我試圖在地圖的價值迭代器存儲與地圖存儲它的迭代狀態沿着第二部分。但正如我在answer中所瞭解的那樣，生鏽是不可能的。 不幸的是，我不知道如何做到這一點。

下面是完整的代碼，INNER JOIN適配器，它做的第一部分：

use std::collections::HashMap; 
use std::hash::Hash; 

pub struct HashJoinInner<I, K, V0, V1> where 
    I: Iterator<Item=(K, V0)>, 
    K: Hash + Eq, 
    V1: Clone, 
{ 
    left: I, 
    right: HashMap<K, V1>, 
} 

impl<I, K, V0, V1> HashJoinInner<I, K, V0, V1> where 
    I: Iterator<Item=(K, V0)>, 
    K: Hash + Eq, 
    V1: Clone, 
{ 
    /// Create a `HashJoinInner` iterator. 
    pub fn new<J>(l: I, r: J) -> Self 
     where J: Iterator<Item=(K, V1)> 
    { 
     let mut hm: HashMap<K, V1> = HashMap::new(); 
     for (k, v) in r { 
      hm.insert(k, v); 
     } 
     HashJoinInner { 
      left: l, 
      right: hm, 
     } 
    } 
} 

impl<I, K, V0, V1> Iterator for HashJoinInner<I, K, V0, V1> where 
    I: Iterator<Item=(K, V0)>, 
    K: Hash + Eq, 
    V1: Clone, 
{ 
    type Item = (V0, V1); 

    fn next(&mut self) -> Option<Self::Item> { 
     loop { 
      match self.left.next() { 
       Some((k0, v0)) => match self.right.get(&k0) { 
        Some(v1) => return Some((v0, Clone::clone(v1))), 
        None => continue, 
       }, 
       None => return None, 
      } 
     } 
    } 
} 

我將是任何想法感謝。

Answer 1

您不能存儲Values迭代器，因爲它包含對HashMap的引用。如果您移動地圖，這些引用可能會失效。但是，您可以使用into_iter方法消耗HashMap。它擁有HashMap的所有值，並可以移動到新的結構中。

下面是您的代碼從早期的問題調整。這還不是左連接或右連接。從一個迭代器完成切換到另一個迭代器的切換是複雜的。

use std::collections::hash_map::{HashMap, IntoIter}; 
use std::hash::Hash; 

struct Foo<K, V> 
    where K: Hash + Eq, 
      V: Clone, 
{ 
    iter: IntoIter<K, (V, bool)>, 
} 

impl<K, V> Foo<K, V> 
    where K: Hash + Eq, 
      V: Clone, 
{ 
    fn new<I>(it: I) -> Self 
     where I: Iterator<Item=(K, V)> 
    { 
     let mut map = HashMap::new(); 
     for (k, v) in it { 
      map.insert(k, (v, false)); 
     } 
     Foo { iter: map.into_iter() } 
    } 
} 

impl<K, V> Iterator for Foo<K, V> 
    where K: Hash + Eq, 
      V: Clone, 
{ 
    type Item = V; 
    fn next(&mut self) -> Option<Self::Item> { 
     loop { 
      match self.iter.next() { 
       Some((_, (v, false))) => return Some(v.clone()), 
       Some(_) => continue, 
       None => return None, 
      } 
     } 
    } 
} 

fn main() { 
    let it = (0..).zip("AB".chars()); 
    let foo = Foo::new(it); 
    for v in foo { 
     println!("{}", v); 
    } 
} 

但是你不需要做任何的是得到你想要的東西。您可以簡單地創建一個hashmap，並在迭代另一個項目時檢查它。我意外地創建了一個左外連接，但只是將參數翻轉來獲得正確的外連接。^_^

use std::collections::hash_map::HashMap; 
use std::hash::Hash; 

struct LeftOuterJoin<L, K, RV> { 
    left: L, 
    right: HashMap<K, RV>, 
} 

impl<L, K, RV> LeftOuterJoin<L, K, RV> 
    where K: Hash + Eq 
{ 
    fn new<LI, RI>(left: LI, right: RI) -> Self 
     where L: Iterator<Item=LI::Item>, 
       LI: IntoIterator<IntoIter=L>, 
       RI: IntoIterator<Item=(K, RV)> 
    { 
     LeftOuterJoin { 
      left: left.into_iter(), 
      right: right.into_iter().collect() 
     } 
    } 
} 

impl<L, K, LV, RV> Iterator for LeftOuterJoin<L, K, RV> 
    where L: Iterator<Item=(K, LV)>, 
      K: Hash + Eq, 
      RV: Clone 
{ 
    type Item = (K, LV, Option<RV>); 

    fn next(&mut self) -> Option<Self::Item> { 
     match self.left.next() { 
      Some((k, lv)) => { 
       let rv = self.right.get(&k); 
       Some((k, lv, rv.cloned())) 
      }, 
      None => None, 
     } 
    } 
} 

fn main() { 
    let mut left = HashMap::new(); 
    left.insert(1, "Alice"); 
    left.insert(2, "Bob"); 

    let mut right = HashMap::new(); 
    right.insert(1, "Programmer"); 

    for (id, name, job) in LeftOuterJoin::new(left.into_iter(), right) { 
     println!("{} ({}) is a {:?}", name, id, job); 
    } 
} 

Answer 2

由於使用std::collections::hash_map::IntoIter我已經設法解決這個問題的Shepmaster的想法。

這裏是右外的完整解決方案JOIN使用散列連接策略：

use std::collections::hash_map::{HashMap, IntoIter,}; 
use std::mem; 
use std::hash::Hash; 

#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] 
pub struct HashJoinRightOuter<L, K, RV> { 
    left: L, 
    map: HashMap<K, (RV, bool)>, 
    /// exclusion iterator - yields the unmatched values from the map. It is created once the left 
    /// iterator is exhausted 
    excl_iter: Option<IntoIter<K, (RV, bool)>>, 
} 

impl<L, K, RV> HashJoinRightOuter<L, K, RV> 
    where K: Hash + Eq, 
{ 
    /// Create a `HashJoinRightOuter` iterator. 
    pub fn new<LI, RI>(left: LI, right: RI) -> Self 
     where L: Iterator<Item=LI::Item>, 
       LI: IntoIterator<IntoIter=L>, 
       RI: IntoIterator<Item=(K, RV)> 
    { 
     let mut map: HashMap<K, (RV, bool)> = HashMap::new(); 
     for (k, v) in right.into_iter() { 
      map.insert(k, (v, false)); 
     } 
     HashJoinRightOuter { 
      left: left.into_iter(), 
      map: map, 
      excl_iter: None, 
     } 
    } 

    /// Moves the map to `self.excl_iter` 
    /// 
    /// Once the left iterator is exhausted, the info about which keys were matched is complete. 
    /// To be able to iterate over map's values we need to move it into its `IntoIter`. 
    fn set_excl_iter(&mut self) { 
     let map = mem::replace(&mut self.map, HashMap::<K, (RV, bool)>::new()); 
     self.excl_iter = Some(map.into_iter()); 
    } 
} 

impl<L, K, LV, RV> Iterator for HashJoinRightOuter<L, K, RV> 
    where L: Iterator<Item=(K, LV)>, 
      K: Hash + Eq, 
      RV: Clone, 
{ 
    type Item = (Option<LV>, RV); 

    fn next(&mut self) -> Option<Self::Item> { 
     loop { 
      match self.excl_iter { 
       // the left iterator is not yet exhausted 
       None => match self.left.next() { 
        Some((lk, lv)) => match self.map.get_mut(&lk) { 
         Some(rt) => { 
          rt.1 = true; // flag as matched 
          return Some((Some(lv), Clone::clone(&rt.0))) 
         }, 
         None => continue, // not interested in unmatched left value 
        }, 
        // the left iterator is exhausted so move the map into `self.excl_iter`. 
        None => self.set_excl_iter(), 
       }, 
       // iterate over unmatched values 
       Some(ref mut r) => match r.next() { 
        Some((_, (rv, matched))) => { 
         if !matched { 
          return Some((None, rv)); 
         } else { 
          continue; 
         } 
        }, 
        None => return None, 
       } 
      } 
     } 
    } 
} 

fn main() { 
    let a = (0..).zip("AB".chars()); 
    let b = (1..).zip("XY".chars()); 
    let mut it = HashJoinRightOuter::new(a, b); 
    assert_eq!(it.next(), Some((Some('B'), 'X'))); 
    assert_eq!(it.next(), Some((None, 'Y'))); 
    assert_eq!(it.next(), None); 
} 

在我失敗了，因爲我試圖同時存儲數據的開始和它在同一個結構，它沒有引用無論如何。我想真的想要存儲的數據第一，做一些神奇的事情，一旦完成，將移動到另一個領域與其轉型工作。

這也可以用來解決其他自引用結構問題。