# APMA (Adaptive Packed Memory Array)
[](https://crates.io/crates/apma)
[](https://docs.rs/apma)
[](https://github.com/krzysztofwos/apma#license)
[](https://github.com/krzysztofwos/apma/actions)
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
```rust
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](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license ([LICENSE-MIT](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.