[−][src]Trait outils::tree::bst::BinarySearchTree
This trait defines the fundamental operations of a binary search tree.
Required methods
fn insert_pos(&self, key: K) -> Option<(NodeIndex, Ordering)>
Returns the insertion point for a given key
. None
is returned, if the tree is empty,
otherwise an index to a node is returned together with the result of the comparison
against its key.
fn insert(&mut self, key: K, value: V) -> Option<V>
Inserts a key-value pair into the tree. If the tree did not have this key
present, None
is returned. If the tree did have this key
present, the value is updated, and the old
value is returned. Note that in this situation, the key is left unchanged.
fn remove(&mut self, key: K) -> Option<V>
Removes a key
from the tree if present, in this case returning the associated value.
fn contains_key(&self, key: K) -> bool
Returns true
if the map contains a value for the specified key
.
fn get(&self, key: K) -> Option<&V>
Returns an immutable reference to the associated value of the specified key
.
fn get_mut(&mut self, key: K) -> Option<&mut V>
Returns a mutable reference to the associated value of the specified key
.
fn index(&self, key: K) -> Option<NodeIndex<Ix>>
Returns the index of the tree node holding the specified key
.
fn key(&self, node: NodeIndex<Ix>) -> Option<&K>
Returns the key held by the tree node indexed by node
.
Implementors
impl<K, V> BinarySearchTree<K, V, usize> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
fn insert_pos(&self, key: K) -> Option<(NodeIndex, Ordering)>
[src]
fn insert(&mut self, key: K, value: V) -> Option<V>
[src]
Inserts a key-value pair into the AaTree
. If the tree did not have this key
present, None
is returned. If the tree did have this key
present, the value is updated, and the old
value is returned. Note that in this situation, the key is left unchanged.
use outils::prelude::*; let mut aatree = AaTree::new(10); assert_eq!(aatree.insert("KEY-1", "VALUE-1"), None); assert_eq!(aatree.insert("KEY-2", "VALUE-2"), None); assert_eq!(aatree.insert("KEY-1", "VALUE-3"), Some("VALUE-1")); assert_eq!(aatree.get(&"KEY-1"), Some(&"VALUE-3")); assert_eq!(aatree.get(&"KEY-2"), Some(&"VALUE-2"));
fn remove(&mut self, key: K) -> Option<V>
[src]
Removes a key
from the tree if present, in this case returning the associated value.
use outils::prelude::*; let mut aatree = AaTree::new(10); aatree.insert("KEY-1", "VALUE-1"); assert_eq!(aatree.remove(&"KEY-1"), Some("VALUE-1")); assert_eq!(aatree.remove(&"KEY-2"), None);
fn get(&self, key: K) -> Option<&V>
[src]
Returns an immutable reference to the associated value of the specified key
.
fn get_mut(&mut self, key: K) -> Option<&mut V>
[src]
Returns a mutable reference to the associated value of the specified key
.
fn index(&self, key: K) -> Option<NodeIndex>
[src]
Returns the index of the tree node holding the specified key
.
fn contains_key(&self, key: K) -> bool
[src]
Returns true
if the map contains a value for the specified key
.
fn key(&self, node: NodeIndex) -> Option<&K>
[src]
Returns the key held by the tree node indexed by node
.
use outils::prelude::*; let mut aatree = AaTree::new(10); aatree.insert("KEY-1", "VALUE-1"); let index = aatree.index(&"KEY-1").expect("KEY-1 should be present"); assert_eq!(aatree.key(index), Some(&"KEY-1"));
impl<K, V, W> BinarySearchTree<K, V, usize> for WeightedAaTree<K, V, W> where
K: KeyType,
V: ValueType,
W: WeightType,
[src]
K: KeyType,
V: ValueType,
W: WeightType,
fn insert_pos(&self, key: K) -> Option<(NodeIndex, Ordering)>
[src]
fn insert(&mut self, key: K, value: V) -> Option<V>
[src]
Inserts a key-value pair into the WeightedAaTree
and assign the node the weight W::default()
.
If the tree did not have this key
present, None
is returned. If the tree did have
this key
present, the value and the weight are updated, and the old value is returned.
Note that in this situation, the key is left unchanged.
use outils::prelude::*; let mut waatree = WeightedAaTree::new(10); assert_eq!(waatree.insert_weighted("KEY-1", "VALUE-1", 1), None); assert_eq!(waatree.insert_weighted("KEY-2", "VALUE-2", 1), None); assert_eq!(waatree.insert_weighted("KEY-1", "VALUE-3", 1), Some("VALUE-1")); assert_eq!(waatree.get(&"KEY-1"), Some(&"VALUE-3")); assert_eq!(waatree.get(&"KEY-2"), Some(&"VALUE-2"));
fn remove(&mut self, key: K) -> Option<V>
[src]
Removes a key
from the tree if present, in this case returning the associated value.
use outils::prelude::*; let mut waatree = WeightedAaTree::new(10); waatree.insert_weighted("KEY-1", "VALUE-1", 1); assert_eq!(waatree.remove(&"KEY-1"), Some("VALUE-1")); assert_eq!(waatree.remove(&"KEY-2"), None);
fn contains_key(&self, key: K) -> bool
[src]
Returns true
if the map contains a value for the specified key
.
fn get(&self, key: K) -> Option<&V>
[src]
Returns an immutable reference to the associated value of the specified key
.
fn get_mut(&mut self, key: K) -> Option<&mut V>
[src]
Returns a mutable reference to the associated value of the specified key
.
fn index(&self, key: K) -> Option<NodeIndex>
[src]
Returns the index of the tree node holding the specified key
.
fn key(&self, node: NodeIndex) -> Option<&K>
[src]
Returns the key held by the tree node indexed by node
.
use outils::prelude::*; let mut waatree = WeightedAaTree::new(10); waatree.insert_weighted("KEY-1", "VALUE-1", 1); let index = waatree.index(&"KEY-1").expect("KEY-1 should be present"); assert_eq!(waatree.key(index), Some(&"KEY-1"));