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

Overview

identified_vec

Code Coverage Crates.io Documentation Rust

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)

You might also like...
Like wee_alloc, but smaller since I used skinnier letters in the name.

lol_alloc A laughably simple wasm global_allocator. Like wee_alloc, but smaller since I used skinnier letters in the name. lol_alloc is a experimental

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

0x - like xxd but colorful! Note: for technical reasons, this library is listed as ohx on crates.io. 0x is a simple utility similar to xxd with a few

It's like monkeytype but from your terminal

DoggyType It's like monkeytype but from ur terminal (ik very unoriginal lmao) Preview doggytype-preview.mp4 Requirements: Rust Build: git clone https:

It's like pixelfix, but quix.
It's like pixelfix, but quix.

pixelquix It's like pixelfix, but quix. Written in Rust for low-level speed Uses rayon for work-stealing parallelism Based on Jump Flood for impressiv

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

Poisson intensity of limit order execution, calibration of parameters A and k using level 1 tick data Description A limit order placed at a price St ±

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

Higher-order Finite Elements for Embedded Simulation This repository contains the source code used to produce the results for our paper: Longva, A., L

A Rust library for evaluating log4j substitution queries in order to determine whether or not malicious queries may exist.

log4j_interpreter A Rust library for evaluating log4j substitution queries in order to determine whether or not malicious queries may exist. Limitatio

Abuse the node.js inspector mechanism in order to force any node.js/electron/v8 based process to execute arbitrary javascript code.
Abuse the node.js inspector mechanism in order to force any node.js/electron/v8 based process to execute arbitrary javascript code.

jscythe abuses the node.js inspector mechanism in order to force any node.js/electron/v8 based process to execute arbitrary javascript code, even if t

Adapt the screen's color spectrum according to the hour of the day in order to improve your sleep

circadianlight What It Is Circadian Light is a program, currently only working on Linux with X, that controls the color spectrum of your screen accord

Comments
  • Add try_append and try_update to return Result-types

    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

    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
Releases(0.1.11)
Owner
Alexander Cyon
Author of free Open Source Software, mostly crypto. Swift | Rust | HoMM3 | Chess
Alexander Cyon
A bit like tee, a bit like script, but all with a fake tty. Lets you remote control and watch a process

teetty teetty is a wrapper binary to execute a command in a pty while providing remote control facilities. This allows logging the stdout of a process

Armin Ronacher 259 Jan 3, 2023
Parallel iteration of FASTA/FASTQ files, for when sequence order doesn't matter but speed does

Rust-parallelfastx A truly parallel parser for FASTA/FASTQ files. Principle The input file is memory-mapped then virtually split into N chunks. Each c

Rayan Chikhi 8 Oct 24, 2022
A crate that allows you to mostly-safely cast one type into another type.

A crate that allows you to mostly-safely cast one type into another type. This is mostly useful for generic functions, e.g. pub fn foo<S>(s: S) {

Bincode 3 Sep 23, 2023
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.

sero Lightning-fast, static web publishing with zero configuration and full control ?? Table Of Contents ?? Table Of Contents ?? Tools ❓ About The Pro

Dmitry Miasnenko 6 Nov 13, 2023
Zenith - sort of like top or htop but with zoom-able charts, CPU, GPU, network, and disk usage

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

Benjamin Vaisvil 1.6k Jan 4, 2023
Like Lua, but in Rust, and different

AirScript It's like Lua, but in Rust, and different. Introduction AirScript is a dynamically typed, interpreted language inspired by Lua and written i

David Delassus 5 Jun 28, 2022
du + rust = dust. Like du but more intuitive.

Dust du + rust = dust. Like du but more intuitive. Why Because I want an easy way to see where my disk is being used. Demo Install Cargo cargo install

andy.boot 5.4k Jan 4, 2023
Like grep, but uses tree-sitter grammars to search

tree-grepper Works like grep, but uses tree-sitter to search for structure instead of strings. Installing This isn't available packaged anywhere. That

Brian Hicks 219 Dec 25, 2022
A command-line shell like fish, but POSIX compatible.

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

Seiya Nuta 813 Dec 29, 2022
Like a cell, but make lifetimes dynamic instead of ownership

LendingCell is a mutable container that allows you to get an owned reference to the same object. When the owned reference is dropped, ownership return

Kalle Samuels 19 Dec 15, 2022