Like HashSet but retaining INSERTION order and without `Hash` requirement on the Element type.

Alexander Cyon

Last update: Dec 11, 2023

Related tags

Command-line rust crate unique vec insertion-order btreeset identified-vec

Overview

`identified_vec`

A collection of unique identifiable elements which retains insertion order, inspired by Pointfree's Swift Identified Collections.

Similar to the standard Vec, the IdentifiedVec maintain their elements in a particular user-specified order. However, unlike Vec, the IdentifiedVec introduce the ability to uniquely identify elements, using a hash table to ensure that no two elements have the same identity, and to efficiently look up elements corresponding to specific identifiers.

IdentifiedVec is a useful alternative to Vec when you need to be able to efficiently access unique elements by a stable identifier. It is also a useful alternative to BTreeSet, where the Ord trait requirement may be too strict, an a useful alternative to HashSet where Hash trait requirement may be too strict.

You can create an identified vec with any element type that implements the Identifiable trait.

Example

extern crate identified_vec;
use identified_vec::{IsIdentifiedVec, IdentifiedVec, Identifiable, IdentifiedVecOf};
use std::cell::RefCell;

#[derive(Eq, PartialEq, Clone, Debug)]
struct User {
    id: &'static str,
    name: RefCell<&'static str>,
}

impl User {
    fn new(id: &'static str, name: &'static str) -> Self {
        Self {
            id,
            name: RefCell::new(name),
        }
    }
    fn name(&self) -> &'static str {
        *self.name.borrow()
    }
}

Identifiable

impl Identifiable for User {
    type ID = &'static str;
    fn id(&self) -> Self::ID {
        self.id
    }
}

`from_iter`

let mut users = IdentifiedVecOf::<User>::from_iter([
    User::new("u_42", "Satoshi Nakamoto"),
    User::new("u_1337", "Leia Skywalker"),
]);

assert_eq!(
    users.get(&"u_42").map(|u| u.name()),
    Some("Satoshi Nakamoto")
);

assert_eq!(
    users.get_at_index(1).map(|u| u.name()),
    Some("Leia Skywalker")
);

`append` & `elements()`

users.append(User::new("u_237", "Alan Turing"));
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Satoshi Nakamoto"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Alan Turing"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

// Element with same ID is not appended:
users.append(User::new("u_42", "Tom Mervolo Dolder"));
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Satoshi Nakamoto"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Alan Turing"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

`update_or_insert`

// Element with same ID replaces existing if an `update_*` method is used:
// e.g. `update_or_insert`:
users.update_or_insert(User::new("u_42", "Tom Mervolo Dolder"), 0);
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Tom Mervolo Dolder"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Alan Turing"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

`update_or_append`

// or `update_or_append`
users.update_or_append(User::new("u_237", "Marie Curie"));
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Tom Mervolo Dolder"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Marie Curie"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

Or you can provide a closure that describes an element's identity:

let numbers = IdentifiedVec::<u32, u32>::new_identifying_element(|e| *e);

Motivation

None of the std collections BTreeSet and HashSet retain insertion order, Vec retains insertion order, however, it allows for duplicates. So if you want a collection of unique elements (Set-like) that does retain insertion order, IdentifiedVec suits your needs. Even better, the elements does not need to be to impl Hash nor Ord.

Flags

This crate has the following Cargo features:

serde: Enables serde serialization support on IdentifiedVecOf type (which Element impl Identifiable trait).
id_prim: Get impl of trait Identifiable for primitives: i8,.., i128, u8, ..., u128 and bool (not so useful, allows for only two elements in IdentifiedVecOf, but who am I to discriminate.)

Implementation Details

An identified vec consists of a Vec of IDs keeping insertion order and a HashMap of id-element pairs, for constant time lookup of element given an ID.

License

Licensed under MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)

Comments

Add try_append and try_update to return Result-types

Implementation of methods try_append and try_update_or_append adding the function signatures:

pub fn try_append(&mut self, element: Element) -> Result<(bool, usize), InsertionFailure> {

and

pub fn try_update_or_append( &mut self, element: Element, ) -> Result<Option<Element>, InsertionFailure> {

This is to add certainties of element value and ID not existing in the collection at call-site.

opened by Vinnstah 1
Add `IsIdentifiableVecOfVia` trait and `newtype_identified_vec` macro
Big PR adding powerful features, that allows you to create a new type using the newtype_identified_vec macro.

You use it like so:

newtype_identified_vec!(of: User, named: Users);

It creates this:

#[derive(Debug, Clone, Eq, PartialEq)] pub struct Users(IdentifiedVecOf<User>) impl IsIdentifiableVecOfVia<User> for Users { ... }

The trait IsIdentifiableVecOfVia is also new, which inherits from IsIdentifiableVec - also a new trait to where all previous methods (well almost all, except a few... might do them later) and functions are moved - the IsIdentifiableVecOfVia trait allows a type to act as if it is IsIdentifiableVec via a field it has.
opened by Sajjon 0

Like HashSet but retaining INSERTION order and without `Hash` requirement on the Element type.

Related tags

Overview

identified_vec

Example

Identifiable

from_iter

append & elements()

update_or_insert

update_or_append

Motivation

Flags

Implementation Details

License

You might also like...

Like grep, but uses tree-sitter grammars to search

A command-line shell like fish, but POSIX compatible.

Like a cell, but make lifetimes dynamic instead of ownership

Like wee_alloc, but smaller since I used skinnier letters in the name.

`0x` - like `xxd` but colorful!

It's like monkeytype but from your terminal

It's like pixelfix, but quix.

Poisson intensity of limit order execution, calibration of parameters A and k using level 1 tick data

Source code for our paper "Higher-order finite elements for embedded simulation"

Comments

Add try_append and try_update to return Result-types

Add `IsIdentifiableVecOfVia` trait and `newtype_identified_vec` macro

Releases(0.1.11)

0.1.11(Dec 22, 2023)

0.1.4(Dec 10, 2023)

0.1.2(Dec 9, 2023)

0.1.1(Dec 9, 2023)

Owner

Alexander Cyon

A bit like tee, a bit like script, but all with a fake tty. Lets you remote control and watch a process

Parallel iteration of FASTA/FASTQ files, for when sequence order doesn't matter but speed does

A 2D Rust-Based Finite Element Simulator

A crate that allows you to mostly-safely cast one type into another type.

Keybinder to type diacrytical characters without needing to hack the layout itself. Supports bindings to the left Alt + letter

Sero is a web server that allows you to easily host your static sites without pain. The idea was inspired by surge.sh but gives you full control.

A lightweight and high-performance order-book designed to process level 2 and trades data. Available in Rust and Python

Zenith - sort of like top or htop but with zoom-able charts, CPU, GPU, network, and disk usage

Like Lua, but in Rust, and different

du + rust = dust. Like du but more intuitive.

`identified_vec`

`from_iter`

`append` & `elements()`

`update_or_insert`

`update_or_append`