From 035233a25907af8206d254878e7e04048fcac95e Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Sat, 2 Mar 2013 13:27:29 -0500 Subject: treemap: reimplement using TotalOrd --- src/libstd/treemap.rs | 167 ++++++++++++++++++++++++++------------------------ 1 file changed, 86 insertions(+), 81 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs index 88e4ade4b82..a093351c4a7 100644 --- a/src/libstd/treemap.rs +++ b/src/libstd/treemap.rs @@ -10,12 +10,8 @@ //! An ordered map and set implemented as self-balancing binary search //! trees. The only requirement for the types is that the key implements -//! `Ord`, and that the `lt` method provides a total ordering. +//! `TotalOrd`. -use core::container::{Container, Mutable, Map, Set}; -use core::cmp::{Eq, Ord}; -use core::iter::{BaseIter, ReverseIter}; -use core::option::{Option, Some, None}; use core::prelude::*; // This is implemented as an AA tree, which is a simplified variation of @@ -39,7 +35,7 @@ pub struct TreeMap { priv length: uint } -impl Eq for TreeMap { +impl Eq for TreeMap { pure fn eq(&self, other: &TreeMap) -> bool { if self.len() != other.len() { false @@ -61,7 +57,8 @@ impl Eq for TreeMap { } // Lexicographical comparison -pure fn lt(a: &TreeMap, b: &TreeMap) -> bool { +pure fn lt(a: &TreeMap, + b: &TreeMap) -> bool { let mut x = a.iter(); let mut y = b.iter(); @@ -78,7 +75,7 @@ pure fn lt(a: &TreeMap, b: &TreeMap) -> bool { return a_len < b_len; } -impl Ord for TreeMap { +impl Ord for TreeMap { #[inline(always)] pure fn lt(&self, other: &TreeMap) -> bool { lt(self, other) @@ -97,7 +94,7 @@ impl Ord for TreeMap { } } -impl BaseIter<(&K, &V)> for TreeMap { +impl BaseIter<(&K, &V)> for TreeMap { /// Visit all key-value pairs in order pure fn each(&self, f: fn(&(&self/K, &self/V)) -> bool) { each(&self.root, f) @@ -105,14 +102,14 @@ impl BaseIter<(&K, &V)> for TreeMap { pure fn size_hint(&self) -> Option { Some(self.len()) } } -impl ReverseIter<(&K, &V)> for TreeMap { +impl ReverseIter<(&K, &V)> for TreeMap { /// Visit all key-value pairs in reverse order pure fn each_reverse(&self, f: fn(&(&self/K, &self/V)) -> bool) { each_reverse(&self.root, f); } } -impl Container for TreeMap { +impl Container for TreeMap { /// Return the number of elements in the map pure fn len(&self) -> uint { self.length } @@ -120,7 +117,7 @@ impl Container for TreeMap { pure fn is_empty(&self) -> bool { self.root.is_none() } } -impl Mutable for TreeMap { +impl Mutable for TreeMap { /// Clear the map, removing all key-value pairs. fn clear(&mut self) { self.root = None; @@ -128,7 +125,7 @@ impl Mutable for TreeMap { } } -impl Map for TreeMap { +impl Map for TreeMap { /// Return true if the map contains a value for the specified key pure fn contains_key(&self, key: &K) -> bool { self.find(key).is_some() @@ -146,12 +143,10 @@ impl Map for TreeMap { loop { match *current { Some(ref r) => { - if *key < r.key { - current = &r.left; - } else if r.key < *key { - current = &r.right; - } else { - return Some(&r.value); + match key.cmp(&r.key) { + Less => current = &r.left, + Greater => current = &r.right, + Equal => return Some(&r.value) } } None => return None @@ -177,7 +172,7 @@ impl Map for TreeMap { } } -pub impl TreeMap { +pub impl TreeMap { /// Create an empty TreeMap static pure fn new() -> TreeMap { TreeMap{root: None, length: 0} } @@ -207,7 +202,7 @@ pub struct TreeMapIterator { /// Advance the iterator to the next node (in order) and return a /// tuple with a reference to the key and value. If there are no /// more nodes, return `None`. -pub fn map_next(iter: &mut TreeMapIterator/&r) +pub fn map_next(iter: &mut TreeMapIterator/&r) -> Option<(&r/K, &r/V)> { while !iter.stack.is_empty() || iter.node.is_some() { match *iter.node { @@ -226,8 +221,8 @@ pub fn map_next(iter: &mut TreeMapIterator/&r) } /// Advance the iterator through the map -pub fn map_advance(iter: &mut TreeMapIterator/&r, - f: fn((&r/K, &r/V)) -> bool) { +pub fn map_advance(iter: &mut TreeMapIterator/&r, + f: fn((&r/K, &r/V)) -> bool) { loop { match map_next(iter) { Some(x) => { @@ -242,25 +237,25 @@ pub struct TreeSet { priv map: TreeMap } -impl BaseIter for TreeSet { +impl BaseIter for TreeSet { /// Visit all values in order pure fn each(&self, f: fn(&T) -> bool) { self.map.each_key(f) } pure fn size_hint(&self) -> Option { Some(self.len()) } } -impl ReverseIter for TreeSet { +impl ReverseIter for TreeSet { /// Visit all values in reverse order pure fn each_reverse(&self, f: fn(&T) -> bool) { self.map.each_key_reverse(f) } } -impl Eq for TreeSet { +impl Eq for TreeSet { pure fn eq(&self, other: &TreeSet) -> bool { self.map == other.map } pure fn ne(&self, other: &TreeSet) -> bool { self.map != other.map } } -impl Ord for TreeSet { +impl Ord for TreeSet { #[inline(always)] pure fn lt(&self, other: &TreeSet) -> bool { self.map < other.map } #[inline(always)] @@ -271,7 +266,7 @@ impl Ord for TreeSet { pure fn gt(&self, other: &TreeSet) -> bool { self.map > other.map } } -impl Container for TreeSet { +impl Container for TreeSet { /// Return the number of elements in the set pure fn len(&self) -> uint { self.map.len() } @@ -279,12 +274,12 @@ impl Container for TreeSet { pure fn is_empty(&self) -> bool { self.map.is_empty() } } -impl Mutable for TreeSet { +impl Mutable for TreeSet { /// Clear the set, removing all values. fn clear(&mut self) { self.map.clear() } } -impl Set for TreeSet { +impl Set for TreeSet { /// Return true if the set contains a value pure fn contains(&self, value: &T) -> bool { self.map.contains_key(value) @@ -309,12 +304,10 @@ impl Set for TreeSet { while a.is_some() && b.is_some() { let a1 = a.unwrap(); let b1 = b.unwrap(); - if a1 < b1 { - a = set_next(&mut x); - } else if b1 < a1 { - b = set_next(&mut y); - } else { - return false; + match a1.cmp(b1) { + Less => a = set_next(&mut x), + Greater => b = set_next(&mut y), + Equal => return false } } } @@ -341,13 +334,12 @@ impl Set for TreeSet { let a1 = a.unwrap(); let b1 = b.unwrap(); - if b1 < a1 { - return false + match a1.cmp(b1) { + Less => (), + Greater => return false, + Equal => b = set_next(&mut y), } - if !(a1 < b1) { - b = set_next(&mut y); - } a = set_next(&mut x); } } @@ -373,11 +365,13 @@ impl Set for TreeSet { let a1 = a.unwrap(); let b1 = b.unwrap(); - if a1 < b1 { + let cmp = a1.cmp(b1); + + if cmp == Less { if !f(a1) { return } a = set_next(&mut x); } else { - if !(b1 < a1) { a = set_next(&mut x) } + if cmp == Equal { a = set_next(&mut x) } b = set_next(&mut y); } } @@ -404,11 +398,13 @@ impl Set for TreeSet { let a1 = a.unwrap(); let b1 = b.unwrap(); - if a1 < b1 { + let cmp = a1.cmp(b1); + + if cmp == Less { if !f(a1) { return } a = set_next(&mut x); } else { - if b1 < a1 { + if cmp == Greater { if !f(b1) { return } } else { a = set_next(&mut x); @@ -434,10 +430,13 @@ impl Set for TreeSet { while a.is_some() && b.is_some() { let a1 = a.unwrap(); let b1 = b.unwrap(); - if a1 < b1 { + + let cmp = a1.cmp(b1); + + if cmp == Less { a = set_next(&mut x); } else { - if !(b1 < a1) { + if cmp == Equal { if !f(a1) { return } } b = set_next(&mut y); @@ -465,12 +464,14 @@ impl Set for TreeSet { let a1 = a.unwrap(); let b1 = b.unwrap(); - if b1 < a1 { + let cmp = a1.cmp(b1); + + if cmp == Greater { if !f(b1) { return } b = set_next(&mut y); } else { if !f(a1) { return } - if !(a1 < b1) { + if cmp == Equal { b = set_next(&mut y); } a = set_next(&mut x); @@ -480,7 +481,7 @@ impl Set for TreeSet { } } -pub impl TreeSet { +pub impl TreeSet { /// Create an empty TreeSet static pure fn new() -> TreeSet { TreeSet{map: TreeMap::new()} } @@ -498,12 +499,12 @@ pub struct TreeSetIterator { /// Advance the iterator to the next node (in order). If this iterator is /// finished, does nothing. -pub fn set_next(iter: &mut TreeSetIterator/&r) -> Option<&r/T> { +pub fn set_next(iter: &mut TreeSetIterator/&r) -> Option<&r/T> { do map_next(&mut iter.iter).map |&(value, _)| { value } } /// Advance the iterator through the set -fn set_advance(iter: &mut TreeSetIterator/&r, +fn set_advance(iter: &mut TreeSetIterator/&r, f: fn(&r/T) -> bool) { do map_advance(&mut iter.iter) |(k, _)| { f(k) } } @@ -518,14 +519,14 @@ struct TreeNode { level: uint } -pub impl TreeNode { +pub impl TreeNode { #[inline(always)] static pure fn new(key: K, value: V) -> TreeNode { TreeNode{key: key, value: value, left: None, right: None, level: 1} } } -pure fn each(node: &r/Option<~TreeNode>, +pure fn each(node: &r/Option<~TreeNode>, f: fn(&(&r/K, &r/V)) -> bool) { do node.iter |x| { each(&x.left, f); @@ -533,7 +534,7 @@ pure fn each(node: &r/Option<~TreeNode>, } } -pure fn each_reverse(node: &r/Option<~TreeNode>, +pure fn each_reverse(node: &r/Option<~TreeNode>, f: fn(&(&r/K, &r/V)) -> bool) { do node.iter |x| { each_reverse(&x.right, f); @@ -542,7 +543,7 @@ pure fn each_reverse(node: &r/Option<~TreeNode>, } // Remove left horizontal link by rotating right -fn skew(node: &mut ~TreeNode) { +fn skew(node: &mut ~TreeNode) { if node.left.map_default(false, |x| x.level == node.level) { let mut save = node.left.swap_unwrap(); node.left <-> save.right; // save.right now None @@ -553,7 +554,7 @@ fn skew(node: &mut ~TreeNode) { // Remove dual horizontal link by rotating left and increasing level of // the parent -fn split(node: &mut ~TreeNode) { +fn split(node: &mut ~TreeNode) { if node.right.map_default(false, |x| x.right.map_default(false, |y| y.level == node.level)) { let mut save = node.right.swap_unwrap(); @@ -564,24 +565,28 @@ fn split(node: &mut ~TreeNode) { } } -fn insert(node: &mut Option<~TreeNode>, key: K, - value: V) -> bool { +fn insert(node: &mut Option<~TreeNode>, key: K, + value: V) -> bool { match *node { Some(ref mut save) => { - if key < save.key { + match key.cmp(&save.key) { + Less => { let inserted = insert(&mut save.left, key, value); skew(save); split(save); inserted - } else if save.key < key { + } + Greater => { let inserted = insert(&mut save.right, key, value); skew(save); split(save); inserted - } else { + } + Equal => { save.key = key; save.value = value; false + } } } None => { @@ -591,8 +596,9 @@ fn insert(node: &mut Option<~TreeNode>, key: K, } } -fn remove(node: &mut Option<~TreeNode>, key: &K) -> bool { - fn heir_swap(node: &mut ~TreeNode, +fn remove(node: &mut Option<~TreeNode>, + key: &K) -> bool { + fn heir_swap(node: &mut ~TreeNode, child: &mut Option<~TreeNode>) { // *could* be done without recursion, but it won't borrow check do child.mutate |mut child| { @@ -611,11 +617,10 @@ fn remove(node: &mut Option<~TreeNode>, key: &K) -> bool { return false // bottom of tree } Some(ref mut save) => { - let (removed, this) = if save.key < *key { - (remove(&mut save.right, key), false) - } else if *key < save.key { - (remove(&mut save.left, key), false) - } else { + let (removed, this) = match key.cmp(&save.key) { + Less => (remove(&mut save.left, key), false), + Greater => (remove(&mut save.right, key), false), + Equal => { if save.left.is_some() { if save.right.is_some() { let mut left = save.left.swap_unwrap(); @@ -637,6 +642,7 @@ fn remove(node: &mut Option<~TreeNode>, key: &K) -> bool { } else { (true, true) } + } }; if !this { @@ -682,12 +688,9 @@ fn remove(node: &mut Option<~TreeNode>, key: &K) -> bool { #[cfg(test)] mod test_treemap { + use core::prelude::*; use super::*; - use core::cmp::{Ord, Eq}; - use core::option::{Some, Option, None}; use core::rand; - use core::str; - use core::vec; #[test] fn find_empty() { @@ -742,7 +745,8 @@ mod test_treemap { assert m.find(&k1) == Some(&v1); } - fn check_equal(ctrl: &[(K, V)], map: &TreeMap) { + fn check_equal(ctrl: &[(K, V)], + map: &TreeMap) { assert ctrl.is_empty() == map.is_empty(); for ctrl.each |x| { let &(k, v) = x; @@ -762,11 +766,11 @@ mod test_treemap { } } - fn check_left(node: &Option<~TreeNode>, - parent: &~TreeNode) { + fn check_left(node: &Option<~TreeNode>, + parent: &~TreeNode) { match *node { Some(ref r) => { - assert r.key < parent.key; + assert r.key.cmp(&parent.key) == Less; assert r.level == parent.level - 1; // left is black check_left(&r.left, r); check_right(&r.right, r, false); @@ -775,11 +779,12 @@ mod test_treemap { } } - fn check_right(node: &Option<~TreeNode>, - parent: &~TreeNode, parent_red: bool) { + fn check_right(node: &Option<~TreeNode>, + parent: &~TreeNode, + parent_red: bool) { match *node { Some(ref r) => { - assert r.key > parent.key; + assert r.key.cmp(&parent.key) == Greater; let red = r.level == parent.level; if parent_red { assert !red } // no dual horizontal links assert red || r.level == parent.level - 1; // right red or black @@ -790,7 +795,7 @@ mod test_treemap { } } - fn check_structure(map: &TreeMap) { + fn check_structure(map: &TreeMap) { match map.root { Some(ref r) => { check_left(&r.left, r); -- cgit 1.4.1-3-g733a5