order_set.rs

Overview

This file defines the OrderSet struct, which encapsulates an ordered set of unique AccountAddress elements. It leverages an underlying balanced tree-based set (indexset::BTreeSet) wrapped in an atomic reference-counted pointer (Arc) to enable efficient cloning and shared ownership. The primary purpose of OrderSet is to provide a lightweight, cloneable, and mutable ordered set abstraction with set operations and serialization support.

Key functionalities include insertion, removal, containment checks, indexed access, and conversion back to the underlying set type. The file also implements serialization and deserialization for interoperability with external data formats and debugging support through the Debug trait.

Struct: OrderSet

pub struct OrderSet(Arc<indexset::BTreeSet<AccountAddress>>);

• Wraps an Arc pointer to an indexset::BTreeSet<AccountAddress>.

• Provides shared ownership with copy-on-write semantics when mutating.

• The inner set maintains unique AccountAddress items in a sorted order.

Traits Implemented

• Clone: Clones the Arc pointer, allowing cheap cloning of the set.

• Default: Creates an empty OrderSet.

• Debug: Formats the set contents for debugging.

• Serialize / Deserialize (from serde): Enables conversion to/from serialized representations (e.g., JSON).

Methods

new() -> Self

Constructs a new, empty OrderSet.

Usage:

let os = OrderSet::new();

len(&self) -> usize

Returns the number of elements in the set.

Usage:

let count = os.len();

get_index(&self, index: usize) -> Option<&AccountAddress>

Returns a reference to the element at the given index, if it exists. Indexing respects the sorted order of the set.

Parameters:

• index: Zero-based position in the ordered set.

Returns:

• Some(&AccountAddress) if index is valid.

• None otherwise.

Usage:

if let Some(addr) = os.get_index(0) {
    // Use addr
}

contains(&self, account_address: &AccountAddress) -> bool

Checks whether the set contains the specified AccountAddress.

Parameters:

• account_address: Reference to the account address to check.

Returns:

• true if the address is present.

• false otherwise.

Usage:

if os.contains(&addr) {
    // Address exists in the set
}

insert(&mut self, account_address: AccountAddress)

Inserts an AccountAddress into the set. If the value is already present, the set remains unchanged.

Because the inner set is wrapped in an Arc, this method performs a clone-on-write (Arc::make_mut) to ensure safe mutation without affecting other clones.

Parameters:

• account_address: The account address to insert.

Usage:

os.insert(new_addr);

remove(&mut self, account_address: &AccountAddress)

Removes the specified AccountAddress from the set if it exists.

Like insert, this method uses clone-on-write to mutate safely.

Parameters:

• account_address: Reference to the account address to remove.

Usage:

os.remove(&addr_to_remove);

to_set(&self) -> indexset::BTreeSet<AccountAddress>

Returns a cloned instance of the underlying BTreeSet.

This can be useful for operations that require the original data structure or for interfacing with other parts of the system expecting BTreeSet.

Returns:

• A cloned indexset::BTreeSet<AccountAddress> containing the same elements.

Usage:

let original_set = os.to_set();

Trait Implementations

serde::Serialize

Serializes the OrderSet as a vector of AccountAddress items, preserving order.

During serialization, the internal set is iterated and collected into a Vec<AccountAddress>, which is then serialized.

serde::Deserialize

Deserializes from a sequence of AccountAddress elements into an OrderSet.

The deserialized vector is converted into an indexset::BTreeSet via from_iter and wrapped in an Arc.

Debug

Provides debug formatting for the OrderSet by displaying its internal BTreeSet contents as a tuple struct named "OrderSet".

Implementation Details

• Clone-on-Write Mutation:
  The use of Arc<indexset::BTreeSet> together with Arc::make_mut allows multiple clones of OrderSet to share the same underlying data without unnecessary copying. When a mutation occurs, the data is cloned only if more than one owner exists, ensuring efficient memory usage.

• Ordered Set with Indexing:
  The indexset::BTreeSet provides ordered set semantics with the ability to access elements by index. This facilitates use cases where order matters and random access is needed.

• Serialization Strategy:
  By serializing as a vector and deserializing back into a BTreeSet, the serialized data captures order and uniqueness without exposing internal implementation details.

Interaction with Other Parts of the System

• Dependency on AccountAddress:
  The OrderSet is tightly coupled with AccountAddress, a type presumably representing unique account identifiers. This struct is imported from the crate::types module.

• Integration with indexset::BTreeSet:
  The core data structure is indexset::BTreeSet, used for ordered unique storage with indexing capabilities.

• Serialization via serde:
  Implements standard serialization traits for interoperability with formats such as JSON, MessagePack, or others supported by serde.

• Potential Usage:
  Likely used wherever an ordered collection of unique accounts is required, such as managing permissions, ordered execution sets, or maintaining lists of participants in a protocol.

Visual Diagram: Class Diagram of OrderSet

classDiagram
class OrderSet {
- Arc<BTreeSet<AccountAddress>> 0..1
+ new()
+ len() : usize
+ get_index() : Option<&AccountAddress>
+ contains() : bool
+ insert()
+ remove()
+ to_set() : BTreeSet<AccountAddress>
}
OrderSet ..> "Arc" : uses
OrderSet ..> "BTreeSet<AccountAddress>" : wraps

This diagram summarizes the OrderSet struct, its encapsulated data, and its exposed methods. The arrows indicate composition and usage relationships.