vex_algoswitch/
lib.rs

1//! AlgoSwitch - Self-Optimizing Algorithm Runtime
2//!
3//! A runtime library that automatically selects the optimal algorithm for your data patterns.
4//!
5//! # Quick Start
6//!
7//! ```rust,ignore
8//! use algoswitch::{sort, select, Config};
9//!
10//! let mut data = vec![3, 1, 4, 1, 5, 9, 2, 6];
11//!
12//! let result = select(
13//!     vec![
14//!         ("quicksort", sort::quicksort),
15//!         ("mergesort", sort::mergesort),
16//!         ("heapsort", sort::heapsort),
17//!         ("insertionsort", sort::insertionsort),
18//!     ],
19//!     &mut data,
20//!     Config::default(),
21//! );
22//!
23//! println!("Winner: {} ({}ns)", result.winner, result.time_ns);
24//! ```
25
26use once_cell::sync::Lazy;
27use std::collections::HashMap;
28use std::fmt::Debug;
29use std::sync::Mutex;
30use std::time::Instant;
31
32pub mod prelude;
33
34// ============================================================================
35// Core Types
36// ============================================================================
37
38/// Selection configuration
39#[derive(Debug, Clone)]
40pub struct Config {
41    /// Number of warmup runs before selecting winner
42    pub warmup_runs: u32,
43    /// Enable caching of winning algorithms
44    pub cache_enabled: bool,
45    /// Enable debug logging
46    pub debug: bool,
47    /// Enable smart pattern detection
48    pub smart_detection: bool,
49}
50
51impl Default for Config {
52    fn default() -> Self {
53        Self {
54            warmup_runs: 3,
55            cache_enabled: true,
56            debug: false,
57            smart_detection: true,
58        }
59    }
60}
61
62impl Config {
63    pub fn new() -> Self {
64        Self::default()
65    }
66    pub fn with_warmup(mut self, runs: u32) -> Self {
67        self.warmup_runs = runs;
68        self
69    }
70    pub fn with_cache(mut self, enabled: bool) -> Self {
71        self.cache_enabled = enabled;
72        self
73    }
74    pub fn with_debug(mut self, enabled: bool) -> Self {
75        self.debug = enabled;
76        self
77    }
78    pub fn with_smart_detection(mut self, enabled: bool) -> Self {
79        self.smart_detection = enabled;
80        self
81    }
82}
83
84/// Selection result
85#[derive(Debug, Clone)]
86pub struct SelectResult<O> {
87    /// The output from the winning algorithm
88    pub output: O,
89    /// Name of the winning algorithm
90    pub winner: String,
91    /// Time taken by winner in nanoseconds
92    pub time_ns: u64,
93    /// All algorithm timings for comparison
94    pub timings: Vec<AlgoTiming>,
95    /// Detected data pattern (if smart detection enabled)
96    pub pattern: Option<DataPattern>,
97}
98
99/// Timing info for a single algorithm
100#[derive(Debug, Clone)]
101pub struct AlgoTiming {
102    pub name: String,
103    pub time_ns: u64,
104}
105
106// ============================================================================
107// Pattern Detection - PHASE 3 INTELLIGENCE
108// ============================================================================
109
110/// Data pattern types
111#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
112pub enum DataPattern {
113    /// Already sorted or nearly sorted
114    Sorted,
115    /// Reverse sorted
116    ReverseSorted,
117    /// Mostly sorted with few elements out of place
118    NearlySorted,
119    /// Random distribution
120    Random,
121    /// Many duplicate values
122    FewUnique,
123    /// Unknown pattern
124    Unknown,
125}
126
127impl DataPattern {
128    /// Get recommended algorithms for this pattern
129    pub fn recommended_sort(&self) -> Vec<&'static str> {
130        match self {
131            DataPattern::Sorted | DataPattern::NearlySorted => {
132                vec!["insertionsort", "quicksort"]
133            }
134            DataPattern::ReverseSorted => {
135                vec!["insertionsort"]
136            }
137            DataPattern::FewUnique => {
138                vec!["radixsort", "insertionsort"]
139            }
140            DataPattern::Random => {
141                vec!["quicksort", "mergesort", "heapsort"]
142            }
143            DataPattern::Unknown => {
144                vec!["quicksort", "mergesort", "heapsort", "insertionsort"]
145            }
146        }
147    }
148}
149
150/// Detect the pattern in data (optimized)
151pub fn detect_pattern(data: &[i64]) -> DataPattern {
152    if data.is_empty() {
153        return DataPattern::Unknown;
154    }
155
156    let n = data.len();
157
158    // For large data, use sampling for everything
159    let use_full_check = n <= 1000;
160    let sample_size = n.min(1000);
161    let step = if use_full_check { 1 } else { n / sample_size };
162
163    // Check for few unique values (sampled)
164    let mut unique_count = 0usize;
165    let mut seen = std::collections::HashSet::new();
166    for i in (0..n).step_by(step) {
167        if seen.insert(data[i]) {
168            unique_count += 1;
169            if unique_count > sample_size / 2 {
170                break; // Enough unique values
171            }
172        }
173    }
174
175    let checked = (n / step).max(1);
176    let unique_ratio = unique_count as f64 / checked as f64;
177
178    if unique_ratio < 0.30 {
179        return DataPattern::FewUnique;
180    }
181
182    // Check for sorted (sampled)
183    let mut sorted_count = 0usize;
184    let mut reverse_count = 0usize;
185    let mut sorted_checked = 0usize;
186
187    for i in (0..n.saturating_sub(1)).step_by(step) {
188        if data[i] <= data[i + 1] {
189            sorted_count += 1;
190        }
191        if data[i] >= data[i + 1] {
192            reverse_count += 1;
193        }
194        sorted_checked += 1;
195    }
196
197    if sorted_checked == 0 {
198        sorted_checked = 1;
199    }
200    let sorted_ratio = sorted_count as f64 / sorted_checked as f64;
201    let reverse_ratio = reverse_count as f64 / sorted_checked as f64;
202
203    if sorted_ratio > 0.99 {
204        return DataPattern::Sorted;
205    }
206
207    if reverse_ratio > 0.99 {
208        return DataPattern::ReverseSorted;
209    }
210
211    if sorted_ratio > 0.80 {
212        return DataPattern::NearlySorted;
213    }
214
215    DataPattern::Random
216}
217
218/// Get pattern as string
219pub fn pattern_name(pattern: &DataPattern) -> &'static str {
220    match pattern {
221        DataPattern::Sorted => "sorted",
222        DataPattern::ReverseSorted => "reverse sorted",
223        DataPattern::NearlySorted => "nearly sorted",
224        DataPattern::Random => "random",
225        DataPattern::FewUnique => "few unique",
226        DataPattern::Unknown => "unknown",
227    }
228}
229
230// ============================================================================
231// Global Cache - PHASE 3 INTELLIGENCE
232// ============================================================================
233
234/// Cache entry for a pattern
235#[derive(Debug, Clone)]
236struct CacheEntry {
237    winner: String,
238    count: u32,
239}
240
241/// Global algorithm cache (pattern -> winner)
242static ALGORITHM_CACHE: Lazy<Mutex<HashMap<String, CacheEntry>>> =
243    Lazy::new(|| Mutex::new(HashMap::new()));
244
245/// Get cached winner for pattern
246pub fn get_cached(pattern: &DataPattern) -> Option<String> {
247    let cache = ALGORITHM_CACHE.lock().ok()?;
248    let key = pattern_name(pattern);
249    cache.get(key).map(|e| e.winner.clone())
250}
251
252/// Cache a winner for pattern
253pub fn cache_winner(pattern: &DataPattern, winner: &str) {
254    if let Ok(mut cache) = ALGORITHM_CACHE.lock() {
255        let key = pattern_name(pattern);
256        cache.insert(
257            key.to_string(),
258            CacheEntry {
259                winner: winner.to_string(),
260                count: 1,
261            },
262        );
263    }
264}
265
266/// Clear the cache
267pub fn clear_cache() {
268    if let Ok(mut cache) = ALGORITHM_CACHE.lock() {
269        cache.clear();
270    }
271}
272
273/// Get cache statistics
274pub fn cache_stats() -> (usize, Vec<(String, String, u32)>) {
275    let cache = match ALGORITHM_CACHE.lock() {
276        Ok(c) => c,
277        Err(c) => c.into_inner(),
278    };
279    let entries: Vec<_> = cache
280        .iter()
281        .map(|(k, v)| (k.clone(), v.winner.clone(), v.count))
282        .collect();
283    (cache.len(), entries)
284}
285
286// ============================================================================
287// Sorting Algorithms
288// ============================================================================
289
290pub mod sort {
291    // Removed unused import
292
293    /// QuickSort algorithm
294    pub fn quicksort(data: &mut [i64]) {
295        if data.len() <= 1 {
296            return;
297        }
298        let pivot = data.len() / 2;
299        data.swap(pivot, data.len() - 1);
300        let mut i = 0;
301        for j in 0..data.len() - 1 {
302            if data[j] <= data[data.len() - 1] {
303                data.swap(i, j);
304                i += 1;
305            }
306        }
307        data.swap(i, data.len() - 1);
308        quicksort(&mut data[..i]);
309        quicksort(&mut data[i + 1..]);
310    }
311
312    /// MergeSort algorithm  
313    pub fn mergesort(data: &mut [i64]) {
314        if data.len() <= 1 {
315            return;
316        }
317        let mid = data.len() / 2;
318        let mut left = data[..mid].to_vec();
319        let mut right = data[mid..].to_vec();
320        mergesort(&mut left);
321        mergesort(&mut right);
322
323        let mut i = 0;
324        let mut j = 0;
325        let mut k = 0;
326        while i < left.len() && j < right.len() {
327            if left[i] <= right[j] {
328                data[k] = left[i];
329                i += 1;
330            } else {
331                data[k] = right[j];
332                j += 1;
333            }
334            k += 1;
335        }
336        while i < left.len() {
337            data[k] = left[i];
338            i += 1;
339            k += 1;
340        }
341        while j < right.len() {
342            data[k] = right[j];
343            j += 1;
344            k += 1;
345        }
346    }
347
348    /// HeapSort algorithm
349    pub fn heapsort(data: &mut [i64]) {
350        let n = data.len();
351        for i in (0..n / 2).rev() {
352            heapify(data, n, i);
353        }
354        for i in (1..n).rev() {
355            data.swap(0, i);
356            heapify(data, i, 0);
357        }
358    }
359
360    fn heapify(data: &mut [i64], heap_size: usize, root: usize) {
361        let mut largest = root;
362        let left = 2 * root + 1;
363        let right = 2 * root + 2;
364
365        if left < heap_size && data[left] > data[largest] {
366            largest = left;
367        }
368        if right < heap_size && data[right] > data[largest] {
369            largest = right;
370        }
371
372        if largest != root {
373            data.swap(root, largest);
374            heapify(data, heap_size, largest);
375        }
376    }
377
378    /// InsertionSort algorithm
379    pub fn insertionsort(data: &mut [i64]) {
380        for i in 1..data.len() {
381            let mut j = i;
382            while j > 0 && data[j - 1] > data[j] {
383                data.swap(j - 1, j);
384                j -= 1;
385            }
386        }
387    }
388
389    /// RadixSort algorithm (for positive integers)
390    pub fn radixsort(data: &mut [i64]) {
391        if data.is_empty() {
392            return;
393        }
394
395        let max = *data.iter().max().unwrap_or(&0);
396        if max < 0 {
397            return;
398        }
399
400        let mut exp = 1;
401        while max / exp > 0 {
402            counting_sort(data, exp);
403            exp *= 10;
404        }
405    }
406
407    fn counting_sort(data: &mut [i64], exp: i64) {
408        let n = data.len();
409        let mut output = vec![0i64; n];
410        let mut count = [0i64; 10];
411
412        for x in data.iter() {
413            let digit = ((x / exp) % 10) as usize;
414            count[digit] += 1;
415        }
416
417        for i in 1..10 {
418            count[i] += count[i - 1];
419        }
420
421        for i in (0..n).rev() {
422            let digit = ((data[i] / exp) % 10) as usize;
423            count[digit] -= 1;
424            output[count[digit] as usize] = data[i];
425        }
426
427        data.copy_from_slice(&output);
428    }
429}
430
431// ============================================================================
432// Search Algorithms
433// ============================================================================
434
435pub mod search {
436    // Removed unused import
437
438    /// Linear search - O(n)
439    pub fn linear(data: &[i64], target: i64) -> Option<usize> {
440        data.iter().position(|&x| x == target)
441    }
442
443    /// Binary search - O(log n) - requires sorted data
444    pub fn binary(data: &[i64], target: i64) -> Option<usize> {
445        if !is_sorted(data) {
446            return None;
447        }
448        binary_helper(data, target, 0, data.len())
449    }
450
451    fn binary_helper(data: &[i64], target: i64, left: usize, right: usize) -> Option<usize> {
452        if left >= right {
453            return None;
454        }
455        let mid = left + (right - left) / 2;
456        if data[mid] == target {
457            Some(mid)
458        } else if data[mid] < target {
459            binary_helper(data, target, mid + 1, right)
460        } else {
461            binary_helper(data, target, left, mid)
462        }
463    }
464
465    /// Interpolation search - O(log log n) for uniform data
466    pub fn interpolation(data: &[i64], target: i64) -> Option<usize> {
467        if data.is_empty() || !is_sorted(data) {
468            return None;
469        }
470        if data[0] == target {
471            return Some(0);
472        }
473        if target < data[0] || target > data[data.len() - 1] {
474            return None;
475        }
476
477        let low = 0;
478        let high = data.len() - 1;
479
480        let pos = low
481            + (((target - data[low]) * (high - low) as i64) / (data[high] - data[low])) as usize;
482
483        if data[pos] == target {
484            Some(pos)
485        } else if data[pos] < target {
486            interpolation(&data[pos + 1..], target).map(|i| pos + 1 + i)
487        } else {
488            interpolation(&data[low..pos], target)
489        }
490    }
491
492    fn is_sorted(data: &[i64]) -> bool {
493        data.windows(2).all(|w| w[0] <= w[1])
494    }
495}
496
497// ============================================================================
498// Hash Algorithms
499// ============================================================================
500
501pub mod hash {
502    // Removed unused import
503
504    /// FNV-1a hash
505    pub fn fnv(data: &[u8]) -> u64 {
506        let mut hash: u64 = 0xcbf29ce484222325;
507        for &byte in data {
508            hash ^= byte as u64;
509            hash = hash.wrapping_mul(0x100000001b3);
510        }
511        hash
512    }
513
514    /// DJB2 hash
515    pub fn djb2(data: &[u8]) -> u64 {
516        let mut hash: u64 = 5381;
517        for &byte in data {
518            hash = ((hash << 5).wrapping_add(hash)).wrapping_add(byte as u64);
519        }
520        hash
521    }
522
523    /// Simple hash (FNV variant)
524    pub fn simple(data: &[u8]) -> u64 {
525        let mut hash: u64 = 0;
526        for (i, &byte) in data.iter().enumerate() {
527            hash = hash.wrapping_add((byte as u64).wrapping_mul(31_u64.wrapping_pow(i as u32)));
528        }
529        hash
530    }
531}
532
533// ============================================================================
534// Algorithm Families - PHASE 3 INTELLIGENCE
535// ============================================================================
536
537/// A family of algorithms for a specific task
538pub struct SortFamily;
539
540impl SortFamily {
541    /// Get standard sorting algorithms
542    pub fn standard() -> Vec<(&'static str, AlgoFn)> {
543        vec![
544            ("quicksort", sort::quicksort),
545            ("mergesort", sort::mergesort),
546            ("heapsort", sort::heapsort),
547            ("insertionsort", sort::insertionsort),
548        ]
549    }
550
551    /// Get all available sorting algorithms
552    pub fn all() -> Vec<(&'static str, AlgoFn)> {
553        let mut all = Self::standard();
554        all.push(("radixsort", sort::radixsort));
555        all
556    }
557}
558
559/// Type alias for search functions
560pub type SearchFn = fn(&[i64], i64) -> Option<usize>;
561
562/// A family of algorithms for searching
563pub struct SearchFamily;
564
565impl SearchFamily {
566    /// Get standard search algorithms
567    pub fn standard() -> Vec<(&'static str, SearchFn)> {
568        vec![
569            ("linear", search::linear),
570            ("binary", search::binary),
571            ("interpolation", search::interpolation),
572        ]
573    }
574}
575
576/// Type alias for hash functions
577pub type HashFn = fn(&[u8]) -> u64;
578
579/// A family of algorithms for hashing
580pub struct HashFamily;
581
582impl HashFamily {
583    /// Get standard hash algorithms
584    pub fn standard() -> Vec<(&'static str, HashFn)> {
585        vec![
586            ("fnv", hash::fnv),
587            ("djb2", hash::djb2),
588            ("simple", hash::simple),
589        ]
590    }
591}
592
593/// A module to group the select function for cleaner API
594pub mod algo {
595    use super::*;
596    pub fn select(
597        algos: Vec<(&str, AlgoFn)>,
598        data: &mut [i64],
599        config: Config,
600    ) -> SelectResult<Vec<i64>> {
601        super::select(algos, data, config)
602    }
603}
604
605// ============================================================================
606// Main Selection Function with INTELLIGENCE
607// ============================================================================
608
609/// Type alias for algorithm functions to reduce type complexity
610pub type AlgoFn = fn(&mut [i64]);
611
612/// Select the best algorithm with smart pattern detection
613pub fn select(
614    algos: Vec<(&str, AlgoFn)>,
615    data: &mut [i64],
616    config: Config,
617) -> SelectResult<Vec<i64>> {
618    // Phase 3: Detect pattern
619    let pattern = if config.smart_detection {
620        Some(detect_pattern(data))
621    } else {
622        None
623    };
624
625    if config.debug {
626        if let Some(p) = &pattern {
627            println!("Detected pattern: {:?}", p);
628        }
629    }
630
631    // Check cache first
632    if config.cache_enabled {
633        if let Some(p) = &pattern {
634            if let Some(cached_winner) = get_cached(p) {
635                // Find the cached algorithm
636                for (name, algo_fn) in &algos {
637                    if name == &cached_winner {
638                        let mut d = data.to_vec();
639                        let start = Instant::now();
640                        algo_fn(&mut d);
641                        let elapsed = start.elapsed().as_nanos() as u64;
642
643                        if config.debug {
644                            println!("Using cached winner: {}", cached_winner);
645                        }
646
647                        return SelectResult {
648                            output: d,
649                            winner: cached_winner.to_string(),
650                            time_ns: elapsed,
651                            timings: vec![AlgoTiming {
652                                name: cached_winner.to_string(),
653                                time_ns: elapsed,
654                            }],
655                            pattern,
656                        };
657                    }
658                }
659            }
660        }
661    }
662
663    // Run all algorithms and find winner
664    let mut timings = Vec::new();
665    let mut best_time = u64::MAX;
666    let mut best_name = "";
667    let mut best_result = data.to_vec();
668
669    for (name, algo_fn) in &algos {
670        let mut d = data.to_vec();
671
672        // Warmup runs
673        for _ in 0..config.warmup_runs {
674            let mut warmup = data.to_vec();
675            algo_fn(&mut warmup);
676        }
677
678        // Timed run
679        let start = Instant::now();
680        algo_fn(&mut d);
681        let elapsed = start.elapsed().as_nanos() as u64;
682
683        timings.push(AlgoTiming {
684            name: name.to_string(),
685            time_ns: elapsed,
686        });
687
688        if config.debug {
689            println!("  {}: {}ns", name, elapsed);
690        }
691
692        if elapsed < best_time {
693            best_time = elapsed;
694            best_name = name;
695            best_result = d;
696        }
697    }
698
699    // Cache the winner
700    if config.cache_enabled {
701        if let Some(p) = &pattern {
702            cache_winner(p, best_name);
703        }
704    }
705
706    SelectResult {
707        output: best_result,
708        winner: best_name.to_string(),
709        time_ns: best_time,
710        timings,
711        pattern,
712    }
713}
714
715/// Select best search algorithm
716pub fn select_search(data: &[i64], target: i64) -> (Option<usize>, String, u64) {
717    let algos = [
718        ("linear", search::linear as fn(&[i64], i64) -> Option<usize>),
719        ("binary", search::binary),
720        ("interpolation", search::interpolation),
721    ];
722
723    let mut best_time = u64::MAX;
724    let mut best_result = None;
725    let mut best_name = "";
726
727    for (name, algo_fn) in &algos {
728        let start = Instant::now();
729        let result = algo_fn(data, target);
730        let elapsed = start.elapsed().as_nanos() as u64;
731
732        if elapsed < best_time {
733            best_time = elapsed;
734            best_result = result;
735            best_name = name;
736        }
737    }
738
739    (best_result, best_name.to_string(), best_time)
740}
741
742/// Select best hash algorithm
743pub fn select_hash(data: &[u8]) -> (u64, String, u64) {
744    let algos = [
745        ("fnv", hash::fnv as fn(&[u8]) -> u64),
746        ("djb2", hash::djb2),
747        ("simple", hash::simple),
748    ];
749
750    let mut best_time = u64::MAX;
751    let mut best_result = 0u64;
752    let mut best_name = "";
753
754    for (name, algo_fn) in &algos {
755        let start = Instant::now();
756        let result = algo_fn(data);
757        let elapsed = start.elapsed().as_nanos() as u64;
758
759        if elapsed < best_time {
760            best_time = elapsed;
761            best_result = result;
762            best_name = name;
763        }
764    }
765
766    (best_result, best_name.to_string(), best_time)
767}
vex_algoswitch/lib.rs

vex_algoswitch/
lib.rs
