APMA (Adaptive Packed Memory Array)

A Rust implementation of the Adaptive Packed Memory Array (APMA) data structure, providing an efficient sorted associative container.

Overview

The Adaptive Packed Memory Array is a cache-efficient data structure that maintains elements in a sorted order while providing the following benefits:

• Cache-friendly: Elements are stored in a packed array, improving cache locality
• Efficient operations: O(log n) search, insert, and delete operations
• Adaptive density: Self-adjusts to maintain efficient space utilization
• Memory-efficient: Automatically rebalances to manage space usage

Features

• Fast lookup by key with binary search
• Efficient insertion and deletion with automatic rebalancing
• Double-ended iteration over all elements in sorted order
• Customizable density thresholds for fine-tuning performance

Usage

use apma::Apma;

// Create a new empty APMA
let mut map = Apma::new();

// Insert key-value pairs
map.insert("apple", 5);
map.insert("banana", 3);
map.insert("cherry", 7);

// Lookup values
if let Some(count) = map.get(&"banana") {
    println!("Banana count: {}", count);
}

// Remove entries
let removed_value = map.remove(&"apple");

// Iterate through all entries in sorted order
for (key, value) in &map {
    println!("{}: {}", key, value);
}

Implementation Details

The APMA maintains elements in a packed array with intentional gaps to facilitate efficient insertions and deletions. The key features include:

• Adaptive rebalancing: Maintains density thresholds that vary by level in a conceptual tree structure
• Efficient element distribution: Uses specialized algorithms to pack and spread elements
• Binary search: Modified to handle gaps in the array efficiently
• Automatic resizing: Grows or shrinks as needed based on element count

API Reference

Constructor Methods

• new(): Creates a new, empty APMA with default density thresholds
• with_thresholds(up_h, up_0, low_h, low_0): Creates an APMA with custom density thresholds
• from_sorted_slice(items): Creates an APMA from a pre-sorted slice of key-value pairs

Core Operations

• insert(key, value): Inserts a key-value pair, returning whether it was a new insertion
• remove(key): Removes a key, returning the associated value if found
• get(key): Retrieves a reference to the value for a given key
• contains_key(key): Checks if a key exists in the APMA

Utility Methods

• len(): Returns the number of elements
• is_empty(): Checks if the APMA contains no elements
• capacity(): Returns the total capacity (used and unused slots)
• clear(): Removes all elements

Iteration

• iter(): Returns an iterator over all key-value pairs in sorted order

Performance Characteristics

• Search: O(log n)
• Insert: O(log n) amortized
• Delete: O(log n) amortized
• Space usage: O(n)

The data structure is optimized for scenarios requiring sorted key access with frequent modifications, providing better cache performance than traditional tree structures in many cases.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at the option of the user.

Contribution

Unless explicitly stated otherwise, any contribution intentionally submitted for inclusion in the work, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.