csc_7b_fc/
eytzinger.rs

1// Eytzinger layout AVL trees (immutable once constructed, for now)
2#![allow(dead_code)]
3#![allow(non_snake_case)]
4#![allow(unused_variables)]
5use std::mem;
6use crate::avltree::Bst::*;
7use crate::avltree::*;
8use std::collections::VecDeque;
9
10fn left(i:usize) -> usize {2*i+1}
11fn right(i:usize) -> usize {2*i+2}
12fn parent(i:usize) -> usize { (i-1)/2 }  // no underflow check!
13
14//2**n
15const fn power2(mut n:usize) -> usize {
16  let mut ax = 1;
17  let mut fct = 2;
18  while n>0 {
19    if n%2==1 {ax*= fct;}
20    fct = fct*fct;
21    n = n/2;
22  }
23  ax
24}
25
26fn cmp<T:Ord>(x:&T, y:&T) -> i8 {
27  if x==y { 0}
28  else if x<y {-1}
29  else {1}
30}
31
32#[derive(Clone, Debug)]
33pub struct Eytzinger<T> {
34  nodes: Vec<Option<T>>,
35  size: usize,
36}
37impl<T:Ord> Eytzinger<T> {
38  pub fn len(&self) -> usize { self.size }
39  pub fn new() -> Self {
40    Eytzinger {
41      nodes: Vec::new(),
42      size: 0,
43    }
44  }
45
46  pub fn with_capacity(cap:usize) -> Self {
47    let mut n = Vec::with_capacity(cap);
48    n.resize_with(cap,||None);
49    Eytzinger {
50      nodes: n,
51      size: 0,
52    }
53  }
54
55  pub fn search(&self, x:&T) -> bool {
56    let mut current = 0; // root index
57    while (current<self.nodes.len()) {
58       let c = self.nodes[current].as_ref()
59         .map(|item|cmp(item,x))
60	 .unwrap_or(-2);
61       if (c == -2) { return false; }
62       else if (c == 0) { return true; }
63       else if (c == 1) { current = left(current); }
64       else { current = right(current);}
65    }
66    false
67  }
68
69  fn from_bstr(&mut self, tree: Bst<T>, index:usize) {
70    if index>=self.nodes.len() { return; }
71    match tree {
72      Empty => { /* self.nodes[index] = None; */},  // stays None
73      Node(cell) => {
74       self.nodes[index] = Some(cell.item);
75       self.size += 1;
76       self.from_bstr(cell.left, left(index));
77       self.from_bstr(cell.right, right(index));       
78      }
79    }//match
80  }//from_bst
81
82  pub fn from_bst(tree:Bst<T>) -> Self {
83    let cap = power2(tree.height() as usize);
84    let mut newself = Eytzinger::with_capacity(cap);
85    newself.from_bstr(tree, 0);
86    newself
87  }
88  
89}//main impl
csc_7b_fc/eytzinger.rs

csc_7b_fc/
eytzinger.rs
