IntoIterator for Custom Bidirectional HashMap

help
1

Hello Rust community! I am trying to create a bidirectional HashMap which translates between cartesian and Hilbert space.

Previously, my Hilbert logic was highly coupled to my image processing and I've been learning about modules, and I'm trying to create a re-usable map.

I would like the ability to enumerate over this map as you can see in my main function. I have gotten to the point where the "for h in hmap" loop iterates as many times as I expect for an order 1 Hilbert curve (4 distinct points).

Unfortunately, the value that comes back in the loop is always my defaulted "None" zeros. I am not accustomed to unwrapping optionals and I am finding debugging this very... stressful.

In addition to understanding why I'm not getting back the values I want, I am open to suggestions about how I can improve this implementation and how I can debug situations like this in the future.

Thanks!

use std::collections::HashMap;
use std::rc::Rc;
use std::hash::Hash;
use std::ops::Deref;
use std::iter::Iterator;

#[derive(PartialEq, Eq, Hash, Debug, Copy, Clone)]
struct HilbertNumber(u32);

#[derive(PartialEq, Eq, Hash, Debug, Copy, Clone)]
struct Point2 { x: u32, y: u32, }

struct HilbertMapping {
    number: HilbertNumber,
    point: Point2
}

impl IntoIterator for BidirectionalMap<HilbertNumber, Point2> {
    type Item = HilbertMapping;
    type IntoIter = BidirectionalMapIntoIterator;
    fn into_iter(self) -> Self::IntoIter {
        BidirectionalMapIntoIterator {
            map: self.left_to_right.into_iter()
        }
    }
}

struct BidirectionalMapIntoIterator {
    map: std::collections::hash_map::IntoIter<Rc<HilbertNumber>, Rc<Point2>>
}

impl Iterator for BidirectionalMapIntoIterator {
    type Item = HilbertMapping;

    fn next(&mut self) -> Option<HilbertMapping> {
        let next_hilbert = self.map.next();
        let result = match next_hilbert {
            Some(x) => Some(HilbertMapping { 
                number: Rc::try_unwrap(x.0.to_owned()).ok().unwrap_or(HilbertNumber(0)),
                point: Rc::try_unwrap(x.1.to_owned()).ok().unwrap_or(Point2 {x:0,y:0})
            }),
            None => None    // reached the end of left_to_right map
        };
        result
    }
}

struct BidirectionalMap<A, B> {
    left_to_right: HashMap<Rc<A>, Rc<B>>,
    right_to_left: HashMap<Rc<B>, Rc<A>>,
}

impl<A, B> BidirectionalMap<A, B>
    where A: Eq + Hash,
          B: Eq + Hash
{
    fn new() -> Self {
        BidirectionalMap {
            left_to_right: HashMap::new(),
            right_to_left: HashMap::new(),
        }
    }

    fn put(&mut self, a: A, b: B) {
        let a = Rc::new(a);
        let b = Rc::new(b);
        self.left_to_right.insert(a.clone(), b.clone());
        self.right_to_left.insert(b, a);
    }

    fn get(&self, a: &A) -> Option<&B> {
        self.left_to_right.get(a).map(Deref::deref)
    }

    fn get_reverse(&self, b: &B) -> Option<&A> {
        self.right_to_left.get(b).map(Deref::deref)
    }
}

// http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
static HILBERT_KEY: [(char, [((u8, u8), (u8, char)); 4]); 4] = (
    [
        ('a', [((0,0), (0,'d')), ((0,1), (1,'a')), ((1,0), (3,'b')), ((1,1), (2,'a')),]),
        ('b', [((0,0), (2,'b')), ((0,1), (1,'b')), ((1,0), (3,'a')), ((1,1), (0,'c')),]),
        ('c', [((0,0), (2,'c')), ((0,1), (3,'d')), ((1,0), (1,'c')), ((1,1), (0,'b')),]),
        ('d', [((0,0), (0,'a')), ((0,1), (3,'c')), ((1,0), (1,'d')), ((1,1), (2,'d')),]),
    ]
);

// map a 2-D coordinate to its corresponding order Hilbert curve position
fn point_to_hilbert(p: &Point2, order: u8) -> HilbertNumber {
    let mut current_square: char = 'a';
    let mut position: u32 = 0;
    for i in (0..order).rev() {
        position = position << 2;
        let quad_x: u8 = if (p.x & ((1 << i) as u32)) == 0 {0} else {1};
        let quad_y: u8 = if (p.y & ((1 << i) as u32)) == 0 {0} else {1};
        let square = HILBERT_KEY.into_iter().find(|&&k| k.0 == current_square).unwrap().1;
        let quad = square.into_iter().find(|&&k| k.0 == (quad_x, quad_y)).unwrap().1;
        let quad_position: u8 = quad.0;
        current_square = quad.1;
        position = position | (quad_position as u32);
    }
    return HilbertNumber(position);
}

// generate a bi-directional hilbert map with provided properties
fn hilbert_map2(order: u8) -> BidirectionalMap<HilbertNumber,Point2> {
    // let hilbert_max: usize = 1 << 2 * order;
    let side: u32 = 1 << 1 * order;
    let mut map = BidirectionalMap::new();
    for i in 0..side {
        for j in 0..side {
            let p: Point2 = Point2 {x: i, y: j};
            let h: HilbertNumber = point_to_hilbert(&p, order);
            map.put(h, p); 
        }
    }
    return map
}

fn main() {
    let hmap = hilbert_map2(1);
    //println!("hmap.get_point({:?}) = {:?}", &HilbertNumber(1), hmap.get(&HilbertNumber(1)));
    //println!("hmap.get_point({:?}) = {:?}", &Point2 {x:1,y:0}, hmap.get_reverse(&Point2{x:1,y:0}));

    for h in hmap {
        println!("h.number = {:?}, h.point = {:?}", h.number, h.point);
    }

}
2

Looks like I was able to answer my own question this time. I was just getting a little out of hand with my unwrapping, it seems...

I still feel like I'm not fully grasping the different unwrapping methods. If someone can please explain a little more in detail if there is any other handling I should be doing here, I would appreciate it :slight_smile:

What I ended up doing in the next function:

fn next(&mut self) -> Option<HilbertMapping> {
    let next_hilbert = self.map.next();
    let result = match next_hilbert {
        Some(x) => Some(HilbertMapping { 
            number: Rc::try_unwrap(x.0).unwrap(),
            point: Rc::try_unwrap(x.1).unwrap()
        }),
        None => None    // reached the end of left_to_right map
    };
    result
}