alexandria_searching

Fully qualified path: alexandria_searching

Modules

Modules

Modules

binary_search

Fully qualified path: alexandria_searching::binary_search

Free functions

Free functions

Free functions

binary_search

Performs binary search on a sorted span to find the exact position of a target value.

Time complexity: O(log n) Space complexity: O(log n) due to recursion

Arguments

• span - A sorted span of elements to search in
• val - The target value to search for

Returns

• Option<u32> - Some(index) if value is found, None if not found

Requirements

• The input span must be sorted in ascending order
• Type T must implement Copy, Drop, PartialEq, and PartialOrd traits

Fully qualified path: alexandria_searching::binary_search::binary_search

pub fn binary_search<T, +Copy<T>, +Drop<T>, +PartialEq<T>, +PartialOrd<T>>(
    span: Span<T>, val: T,
) -> Option<u32>

binary_search_closest

Performs binary search to find the position where a value would be inserted to maintain sorted order, or the closest position to the target value.

Time complexity: O(log n) Space complexity: O(log n) due to recursion

Arguments

• span - A sorted span of elements to search in
• val - The target value to find the closest position for

Returns

• Option<u32> - Some(index) of the closest position, None if span is empty or no valid position

Requirements

• The input span must be sorted in ascending order
• Type T must implement Copy, Drop, and PartialOrd traits

Behavior

• Returns the index where val would fit in the sorted order
• Useful for insertion points and range queries

Fully qualified path: alexandria_searching::binary_search::binary_search_closest

pub fn binary_search_closest<T, +Copy<T>, +Drop<T>, +PartialOrd<T>>(
    span: Span<T>, val: T,
) -> Option<u32>

bm_search

Fully qualified path: alexandria_searching::bm_search

Free functions

Free functions

Free functions

bm_search

Find pattern in text and return the index of every match.

• text - The text to search in.
• pattern - The pattern to search for.

Returns

• Array<usize> - The index of every match.

Fully qualified path: alexandria_searching::bm_search::bm_search

pub fn bm_search(text: @ByteArray, pattern: @ByteArray) -> Array<u32>

dijkstra

Fully qualified path: alexandria_searching::dijkstra

Free functions

Structs

Traits

Impls

Free functions

Free functions

dijkstra

Implements Dijkstra’s shortest path algorithm to find shortest distances from a source node to all other nodes in a weighted graph with non-negative edge weights.

Time complexity: O((V + E) log V) where V is vertices and E is edges Space complexity: O(V) for distance tracking and priority queue

Arguments

• self - The graph containing nodes and adjacency information
• source - The starting node to calculate shortest paths from

Returns

• Felt252Dict<u128> - Dictionary mapping node IDs to their shortest distances from source

Algorithm Overview

1. Initialize all distances to infinity except source (distance 0)
2. Use priority queue to always process the closest unvisited node
3. For each node, update distances to its neighbors if a shorter path is found
4. Mark nodes as visited to avoid reprocessing
5. Continue until all reachable nodes are processed

Fully qualified path: alexandria_searching::dijkstra::dijkstra

pub fn dijkstra(ref self: Graph<Nullable<Span<Node>>>, source: u32) -> Felt252Dict<u128>

Structs

Structs

Node

Fully qualified path: alexandria_searching::dijkstra::Node

[derive(Copy, Drop)]
pub struct Node { /* private fields */ }

Graph

Graph representation.

Fully qualified path: alexandria_searching::dijkstra::Graph

pub struct Graph<T> {
    pub nodes: Array<Node>,
    /* private fields */
}

Members

nodes

Fully qualified path: alexandria_searching::dijkstra::Graph::nodes

pub nodes: Array<Node>

Traits

Traits

GraphTrait

Graph trait defining operations for working with weighted directed graphs.

Fully qualified path: alexandria_searching::dijkstra::GraphTrait

pub trait GraphTrait

Trait functions

new

Create a new empty graph instance.

Returns

• Graph<Nullable<Span<Node>>> - A new empty graph

Fully qualified path: alexandria_searching::dijkstra::GraphTrait::new

fn new() -> Graph<Nullable<Span<Node>>>

add_edge

Add a weighted directed edge to the graph.

Arguments

• self - The graph instance to modify
• source - The source node ID
• dest - The destination node ID
• weight - The weight/cost of the edge

Fully qualified path: alexandria_searching::dijkstra::GraphTrait::add_edge

fn add_edge(ref self: Graph<Nullable<Span<Node>>>, source: u32, dest: u32, weight: u128)

shortest_path

Calculate shortest paths from a source node to all other nodes using Dijkstra’s algorithm.

Arguments

• self - The graph instance
• source - The starting node ID to calculate paths from

Returns

• Felt252Dict<u128> - Dictionary mapping node IDs to shortest distances

Fully qualified path: alexandria_searching::dijkstra::GraphTrait::shortest_path

fn shortest_path(ref self: Graph<Nullable<Span<Node>>>, source: u32) -> Felt252Dict<u128>

adj_nodes

Get adjacent nodes for a given source node.

Arguments

• self - The graph instance
• source - The node ID to get adjacencies for

Returns

• Nullable<Span<Node>> - Span of adjacent nodes or null if none exist

Fully qualified path: alexandria_searching::dijkstra::GraphTrait::adj_nodes

fn adj_nodes(ref self: Graph<Nullable<Span<Node>>>, source: felt252) -> Nullable<Span<Node>>

NodeGettersTrait

Fully qualified path: alexandria_searching::dijkstra::NodeGettersTrait

pub trait NodeGettersTrait

Trait functions

weight

Fully qualified path: alexandria_searching::dijkstra::NodeGettersTrait::weight

fn weight(self: @Node) -> @u128

dest

Fully qualified path: alexandria_searching::dijkstra::NodeGettersTrait::dest

fn dest(self: @Node) -> @u32

source

Fully qualified path: alexandria_searching::dijkstra::NodeGettersTrait::source

fn source(self: @Node) -> @u32

Impls

Impls

NodeGetters

Fully qualified path: alexandria_searching::dijkstra::NodeGetters

pub impl NodeGetters of NodeGettersTrait;

Impl functions

weight

Fully qualified path: alexandria_searching::dijkstra::NodeGetters::weight

fn weight(self: @Node) -> @u128

dest

Fully qualified path: alexandria_searching::dijkstra::NodeGetters::dest

fn dest(self: @Node) -> @u32

source

Fully qualified path: alexandria_searching::dijkstra::NodeGetters::source

fn source(self: @Node) -> @u32

levenshtein_distance

Fully qualified path: alexandria_searching::levenshtein_distance

Free functions

Free functions

Free functions

levenshtein_distance

Compute the edit distance between two byte arrays

Arguments

• arr1 - The first byte array.
• arr2 - The second byte array.

Returns

• usize - The edit distance between the two byte arrays.

Fully qualified path: alexandria_searching::levenshtein_distance::levenshtein_distance

pub fn levenshtein_distance(arr1: @ByteArray, arr2: @ByteArray) -> u32