iddqd

Struct IdOrdMap

Source 
pub struct IdOrdMap<T: IdOrdItem> { /* private fields */ }
Expand description

An ordered map where the keys are part of the values, based on a B-Tree.

The storage mechanism is a fast hash table of integer indexes to items, with the indexes stored in a B-Tree map.

§Examples

use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

// Define a struct with a key.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct MyItem {
    id: String,
    value: u32,
}

// Implement IdOrdItem for the struct.
impl IdOrdItem for MyItem {
    // Keys can borrow from the item.
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

// Create an IdOrdMap and insert items.
let mut map = IdOrdMap::new();
map.insert_unique(MyItem { id: "foo".to_string(), value: 42 }).unwrap();
map.insert_unique(MyItem { id: "bar".to_string(), value: 20 }).unwrap();

// Look up items by their keys.
assert_eq!(map.get("foo").unwrap().value, 42);
assert_eq!(map.get("bar").unwrap().value, 20);
assert!(map.get("baz").is_none());

Implementations§

Source§

impl<T: IdOrdItem> IdOrdMap<T>

Source

pub fn new() -> Self

Creates a new, empty IdOrdMap.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let map: IdOrdMap<Item> = IdOrdMap::new();
assert!(map.is_empty());
assert_eq!(map.len(), 0);
Source

pub fn with_capacity(capacity: usize) -> Self

Creates a new IdOrdMap with the given capacity.

The capacity will be used to initialize the underlying hash table.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let map: IdOrdMap<Item> = IdOrdMap::with_capacity(10);
assert!(map.capacity() >= 10);
assert!(map.is_empty());
Source

pub fn capacity(&self) -> usize

Returns the currently allocated capacity of the map.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let map: IdOrdMap<Item> = IdOrdMap::with_capacity(10);
assert!(map.capacity() >= 10);
Source

pub fn from_iter_unique<I: IntoIterator<Item = T>>( iter: I, ) -> Result<Self, DuplicateItem<T>>

Constructs a new IdOrdMap from an iterator of values, rejecting duplicates.

To overwrite duplicates instead, use IdOrdMap::from_iter.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let items = vec![
    Item { id: "foo".to_string(), value: 42 },
    Item { id: "bar".to_string(), value: 99 },
];

// Successful creation with unique keys
let map = IdOrdMap::from_iter_unique(items).unwrap();
assert_eq!(map.len(), 2);
assert_eq!(map.get("foo").unwrap().value, 42);

// Error with duplicate keys
let duplicate_items = vec![
    Item { id: "foo".to_string(), value: 42 },
    Item { id: "foo".to_string(), value: 99 },
];
assert!(IdOrdMap::from_iter_unique(duplicate_items).is_err());
Source

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
assert!(map.is_empty());

map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
assert!(!map.is_empty());
Source

pub fn len(&self) -> usize

Returns the number of items in the map.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
assert_eq!(map.len(), 0);

map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
map.insert_unique(Item { id: "bar".to_string(), value: 99 }).unwrap();
assert_eq!(map.len(), 2);
Source

pub fn iter(&self) -> Iter<'_, T> ⓘ

Iterates over the items in the map.

Similar to BTreeMap, the iteration is ordered by T::Key.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
map.insert_unique(Item { id: "charlie".to_string(), value: 30 }).unwrap();
map.insert_unique(Item { id: "alice".to_string(), value: 42 }).unwrap();
map.insert_unique(Item { id: "bob".to_string(), value: 99 }).unwrap();

// Iteration is ordered by key
let mut iter = map.iter();
let item = iter.next().unwrap();
assert_eq!(item.id, "alice");
let item = iter.next().unwrap();
assert_eq!(item.id, "bob");
let item = iter.next().unwrap();
assert_eq!(item.id, "charlie");
assert!(iter.next().is_none());
Source

pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> ⓘ
where T::Key<'a>: Hash,

Iterates over the items in the map, allowing for mutation.

Similar to BTreeMap, the iteration is ordered by T::Key.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
map.insert_unique(Item { id: "bar".to_string(), value: 99 }).unwrap();

// Modify values through the mutable iterator
for mut item in map.iter_mut() {
    item.value *= 2;
}

assert_eq!(map.get("foo").unwrap().value, 84);
assert_eq!(map.get("bar").unwrap().value, 198);
Source

pub fn insert_unique(&mut self, value: T) -> Result<(), DuplicateItem<T, &T>>

Inserts a value into the set, returning an error if any duplicates were added.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();

// Successful insertion
assert!(
    map.insert_unique(Item { id: "foo".to_string(), value: 42 }).is_ok()
);
assert!(
    map.insert_unique(Item { id: "bar".to_string(), value: 99 }).is_ok()
);

// Duplicate key
assert!(
    map.insert_unique(Item { id: "foo".to_string(), value: 100 }).is_err()
);
Source

pub fn insert_overwrite(&mut self, value: T) -> Option<T>

Inserts a value into the map, removing and returning the conflicting item, if any.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();

// First insertion - no conflict
let old = map.insert_overwrite(Item { id: "foo".to_string(), value: 42 });
assert!(old.is_none());

// Overwrite existing key - returns old value
let old = map.insert_overwrite(Item { id: "foo".to_string(), value: 99 });
assert!(old.is_some());
assert_eq!(old.unwrap().value, 42);

// Verify new value is in the map
assert_eq!(map.get("foo").unwrap().value, 99);
Source

pub fn contains_key<'a, Q>(&'a self, key: &Q) -> bool
where Q: ?Sized + Comparable<T::Key<'a>>,

Returns true if the map contains the given key.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();

assert!(map.contains_key("foo"));
assert!(!map.contains_key("bar"));
Source

pub fn get<'a, Q>(&'a self, key: &Q) -> Option<&'a T>
where Q: ?Sized + Comparable<T::Key<'a>>,

Gets a reference to the value associated with the given key.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();

assert_eq!(map.get("foo").unwrap().value, 42);
assert!(map.get("bar").is_none());
Source

pub fn get_mut<'a, Q>(&'a mut self, key: &Q) -> Option<RefMut<'a, T>>
where Q: ?Sized + Comparable<T::Key<'a>>, T::Key<'a>: Hash,

Gets a mutable reference to the item associated with the given key.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();

if let Some(mut item) = map.get_mut("foo") {
    item.value = 99;
}

assert_eq!(map.get("foo").unwrap().value, 99);
Source

pub fn remove<'a, Q>(&'a mut self, key: &Q) -> Option<T>
where Q: ?Sized + Comparable<T::Key<'a>>,

Removes an item from the map by its key.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();
map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();

let removed = map.remove("foo");
assert!(removed.is_some());
assert_eq!(removed.unwrap().value, 42);
assert!(map.is_empty());

// Removing a non-existent key returns None
assert!(map.remove("bar").is_none());
Source

pub fn entry<'a>(&'a mut self, key: T::Key<'_>) -> Entry<'a, T>

Retrieves an entry by its key.

Due to borrow checker limitations, this always accepts an owned key rather than a borrowed form.

§Examples
use iddqd::{IdOrdItem, IdOrdMap, id_ord_map, id_upcast};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    id: String,
    value: u32,
}

impl IdOrdItem for Item {
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.id
    }

    id_upcast!();
}

let mut map = IdOrdMap::new();

// Insert via vacant entry
match map.entry("foo") {
    id_ord_map::Entry::Vacant(entry) => {
        entry.insert(Item { id: "foo".to_string(), value: 42 });
    }
    id_ord_map::Entry::Occupied(_) => {}
}

// Update via occupied entry
match map.entry("foo") {
    id_ord_map::Entry::Occupied(mut entry) => {
        entry.get_mut().value = 99;
    }
    id_ord_map::Entry::Vacant(_) => {}
}

assert_eq!(map.get("foo").unwrap().value, 99);

Trait Implementations§

Source§

impl<T: Clone + IdOrdItem> Clone for IdOrdMap<T>

Source§

fn clone(&self) -> IdOrdMap<T>

Returns a copy of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<'a, T> Debug for IdOrdMap<T>
where T: Debug + 'a + IdOrdItem, T::Key<'a>: Debug,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T: IdOrdItem> Default for IdOrdMap<T>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T: IdOrdItem> Extend<T> for IdOrdMap<T>

The Extend implementation overwrites duplicates. In the future, there will also be an extend_unique method that will return an error.

Source§

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)
Reserves capacity in a collection for the given number of additional elements. Read more
Source§

impl<T: IdOrdItem> FromIterator<T> for IdOrdMap<T>

The FromIterator implementation for IdOrdMap overwrites duplicate items.

To reject duplicates, use IdOrdMap::from_iter_unique.

Source§

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator. Read more
Source§

impl<'a, T: IdOrdItem> IntoIterator for &'a IdOrdMap<T>

Source§

type Item = &'a T

The type of the elements being iterated over.
Source§

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

impl<'a, T: IdOrdItem> IntoIterator for &'a mut IdOrdMap<T>
where T::Key<'a>: Hash,

Source§

type Item = RefMut<'a, T>

The type of the elements being iterated over.
Source§

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

impl<T: IdOrdItem> IntoIterator for IdOrdMap<T>

Source§

type Item = T

The type of the elements being iterated over.
Source§

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

impl<T: IdOrdItem + PartialEq> PartialEq for IdOrdMap<T>

Source§

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl<T: IdOrdItem + Eq> Eq for IdOrdMap<T>

Auto Trait Implementations§

§

impl<T> Freeze for IdOrdMap<T>

§

impl<T> RefUnwindSafe for IdOrdMap<T>
where T: RefUnwindSafe,

§

impl<T> Send for IdOrdMap<T>
where T: Send,

§

impl<T> Sync for IdOrdMap<T>
where T: Sync,

§

impl<T> Unpin for IdOrdMap<T>
where T: Unpin,

§

impl<T> UnwindSafe for IdOrdMap<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.