Ordered

A sorted collection library for Zig

---

Ordered is a Zig library that provides fast and efficient implementations of various data structures that keep elements sorted (AKA sorted collections). It is written in pure Zig and has no external dependencies. Ordered is inspired by Java collections and sorted containers in the C++ standard library, and aims to provide a similar experience in Zig.

Features

• Simple and uniform API for all data structures
• Pure Zig implementations with no external dependencies
• Fast, cache-friendly, and memory-efficient implementations (see benches)

Data Structures

Ordered provides two main interfaces for working with sorted collections: sorted maps and sorted sets. At the moment, Ordered supports the following implementations of these interfaces:

Maps (key-value)

Type	Data Structure	Insert	Search	Delete	Space
BTreeMap	B-tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
SkipListMap	Skip list	$O(\log n)$†	$O(\log n)$†	$O(\log n)$†	$O(n)$
TrieMap	Trie	$O(m)$	$O(m)$	$O(m)$	$O(n \cdot m)$
CartesianTreeMap	Treap	$O(\log n)$†	$O(\log n)$†	$O(\log n)$†	$O(n)$

Sets (value-only)

Type	Data Structure	Insert	Search	Delete	Space
SortedSet	Sorted array	$O(n)$	$O(\log n)$	$O(n)$	$O(n)$
RedBlackTreeSet	Red-black tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$

• $n$ = number of elements stored
• $m$ = length of the key (for string-based keys)
• † = average case complexity (the worst case is $O(n)$)

Important

Ordered is in early development, so bugs and breaking API changes are expected. Please use the issues page to report bugs or request features.

---

Getting Started

You can add Ordered to your project and start using it by following the steps below.

Installation

Run the following command in the root directory of your project to download Ordered:

zig fetch --save=ordered "https://github.com/CogitatorTech/ordered/archive/<branch_or_tag>.tar.gz"

Replace <branch_or_tag> with the desired branch or release tag, like main (for the development version) or v0.1.0. This command will download Ordered and add it to Zig's global cache and update your project's build.zig.zon file.

Adding to Build Script

Next, modify your build.zig file to make Ordered available to your build target as a module.

const std = @import("std");

pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});

    // 1. Get the dependency object from the builder
    const ordered_dep = b.dependency("ordered", .{});

    // 2. Create a module for the dependency
    const ordered_module = ordered_dep.module("ordered");

    // 3. Create your executable module and add ordered as import
    const exe_module = b.createModule(.{
        .root_source_file = b.path("src/main.zig"),
        .target = target,
        .optimize = optimize,
    });
    exe_module.addImport("ordered", ordered_module);

    // 4. Create executable with the module
    const exe = b.addExecutable(.{
        .name = "your-application",
        .root_module = exe_module,
    });

    b.installArtifact(exe);
}

Using Ordered in Your Project

Finally, you can @import("ordered") and start using it in your Zig code.

const std = @import("std");
const ordered = @import("ordered");

// Define a comparison function for the keys.
// The function must return a `std.math.Order` value based on the comparison of the two keys
fn strCompare(lhs: []const u8, rhs: []const u8) std.math.Order {
    return std.mem.order(u8, lhs, rhs);
}

pub fn main() !void {
    const allocator = std.heap.page_allocator;

    std.debug.print("## BTreeMap Example ##\n", .{});
    const B = 4; // Branching Factor for B-tree
    var map = ordered.BTreeMap([]const u8, u32, strCompare, B).init(allocator);
    defer map.deinit();

    try map.put("banana", 150);
    try map.put("apple", 100);
    try map.put("cherry", 200);

    const key_to_find = "apple";
    if (map.get(key_to_find)) |value_ptr| {
        std.debug.print("Found key '{s}': value is {d}\n", .{ key_to_find, value_ptr.* });
    }

    const removed = map.remove("banana");
    std.debug.print("Removed 'banana' with value: {?d}\n", .{if (removed) |v| v else null});
    std.debug.print("Contains 'banana' after remove? {any}\n", .{map.contains("banana")});
    std.debug.print("Map count: {d}\n\n", .{map.count()});
}

---

Documentation

You can find the API documentation for the latest release of Ordered here.

Alternatively, you can use the make docs command to generate the documentation for the current version of Ordered. This will generate HTML documentation in the docs/api directory, which you can serve locally with make serve-docs and view in a web browser.

Examples

Check out the examples directory for example usages of Ordered.

Benchmarks

Check out the benchmarks directory for local benchmarks.

---

Contributing

See CONTRIBUTING.md for details on how to make a contribution.

License

Ordered is licensed under the MIT License (see LICENSE).

Acknowledgements

• The logo is from SVG Repo with some modifications.