use std::{cmp::Ordering, collections::{HashMap, VecDeque}, fmt::Debug};
use ordermap::OrderSet;
use serde::{Deserialize, Serialize};
use crate::{builder::PakBuilder, error::{PakError, PakResult}, pointer::{PakPointer, PakUntypedPointer}};
use super::{value::PakValue, Pak};
pub struct PakTree<'p> {
pak : &'p Pak,
meta : PakTreeMeta,
}
impl <'p> PakTree<'p> {
pub fn new(pak: &'p Pak, key : &str) -> PakResult<PakTree<'p>> {
let indices = pak.fetch_indices()?;
let Some(pointer) = indices.get(key) else { return Err(PakError::InvalidIndex(key.to_string())) };
let meta : PakTreeMeta = pak.read_err::<PakTreeMeta>(&pointer.as_pointer())?;
Ok(PakTree {
pak,
meta,
})
}
pub fn get(&self, value : &PakValue) -> PakResult<OrderSet<PakPointer>> {
let pointer = self.meta.pages.get(&0).unwrap();
let mut set = OrderSet::new();
self.get_r(value, *pointer, &mut set)?;
Ok(set)
}
fn get_r(&self, value : &PakValue, current_page : PakUntypedPointer, set : &mut OrderSet<PakPointer>) -> PakResult<()> {
let page : PakTreePage = self.pak.read_err::<PakTreePage>(¤t_page.as_pointer())?;
for entry in page.values {
if &entry.key < value {
continue;
} else if &entry.key > value {
if let Some(index) = entry.previous {
let pointer = self.meta.pages.get(&index).unwrap();
self.get_r(value, *pointer, set)?;
return Ok(());
}
} else {
entry.values.clone().into_iter().for_each(|value| {set.insert(value);});
return Ok(());
}
}
if let Some(index) = page.next {
let pointer = self.meta.pages.get(&index).unwrap();
self.get_r(value, *pointer, set)?;
}
Ok(())
}
pub fn get_less(&self, value : &PakValue) -> PakResult<OrderSet<PakPointer>> {
let pointer = self.meta.pages.get(&0).unwrap();
let mut results = OrderSet::new();
self.get_less_r(value, *pointer, &mut results, false)?;
Ok(results)
}
pub fn get_less_eq(&self, value : &PakValue) -> PakResult<OrderSet<PakPointer>> {
let pointer = self.meta.pages.get(&0).unwrap();
let mut results = OrderSet::new();
self.get_less_r(value, *pointer, &mut results, true)?;
Ok(results)
}
fn get_less_r(&self, value : &PakValue, current_page : PakUntypedPointer, set : &mut OrderSet<PakPointer>, match_eq : bool) -> PakResult<()> {
let page = self.pak.read_err::<PakTreePage>(¤t_page.as_pointer())?;
for entry in page.values {
if &entry.key > value {
continue;
} else if &entry.key < value {
entry.values.clone().into_iter().for_each(|value| {set.insert(value);});
if let Some(index) = entry.previous {
let pointer = self.meta.pages.get(&index).unwrap();
self.get_less_r(value, *pointer, set, match_eq)?;
}
continue;
} else {
if match_eq {
entry.values.clone().into_iter().for_each(|value| {set.insert(value);});
}
continue;
}
}
if let Some(index) = page.next {
let pointer = self.meta.pages.get(&index).unwrap();
return self.get_less_r(value, *pointer, set, match_eq);
}
Ok(())
}
pub fn get_greater(&self, value : &PakValue) -> PakResult<OrderSet<PakPointer>> {
let pointer = self.meta.pages.get(&0).unwrap();
let mut results = OrderSet::new();
self.get_greater_r(value, *pointer, &mut results, false)?;
Ok(results)
}
pub fn get_greater_eq(&self, value : &PakValue) -> PakResult<OrderSet<PakPointer>> {
let pointer = self.meta.pages.get(&0).unwrap();
let mut results = OrderSet::new();
self.get_greater_r(value, *pointer, &mut results, true)?;
Ok(results)
}
fn get_greater_r(&self, value : &PakValue, current_page : PakUntypedPointer, set : &mut OrderSet<PakPointer>, match_eq : bool) -> PakResult<()> {
let page : PakTreePage = self.pak.read_err::<PakTreePage>(¤t_page.as_pointer())?;
for entry in page.values {
if &entry.key < value {
continue;
} else if &entry.key > value {
entry.values.clone().into_iter().for_each(|value| {set.insert(value);});
if let Some(index) = entry.previous {
let pointer = self.meta.pages.get(&index).unwrap();
self.get_greater_r(value, *pointer, set, match_eq)?;
}
continue;
} else {
if match_eq {
entry.values.clone().into_iter().for_each(|value| {set.insert(value);});
}
continue;
}
}
if let Some(index) = page.next {
let pointer = self.meta.pages.get(&index).unwrap();
return self.get_greater_r(value, *pointer, set, match_eq);
}
Ok(())
}
pub fn get_contains(&self, value : &PakValue) -> PakResult<OrderSet<PakPointer>> {
let pointer = self.meta.pages.get(&0).unwrap();
let mut results = OrderSet::new();
self.get_contains_r(value, *pointer, &mut results)?;
Ok(results)
}
fn get_contains_r(&self, value : &PakValue, current_page : PakUntypedPointer, set : &mut OrderSet<PakPointer>) -> PakResult<()> {
let page : PakTreePage = self.pak.read_err::<PakTreePage>(¤t_page.as_pointer())?;
for entry in page.values {
if entry.key.contains(value) {
entry.values.clone().into_iter().for_each(|value| {set.insert(value);});
}
if let Some(index) = entry.previous {
let pointer = self.meta.pages.get(&index).unwrap();
self.get_contains_r(value, *pointer, set)?;
}
}
Ok(())
}
}
#[derive(Deserialize, Serialize, Debug)]
pub struct PakTreeMeta {
pages: HashMap<usize, PakUntypedPointer>,
}
#[derive(Debug)]
pub struct PakTreeBuilder {
pages : Vec<PakTreePage>,
max_size: usize,
}
impl PakTreeBuilder {
pub fn new(power_of_two: u32) -> Self {
PakTreeBuilder {
pages: vec![PakTreePage::new()],
max_size : 2usize.pow(power_of_two),
}
}
pub fn access<'t>(&'t mut self) -> PakTreeBuilderAccess<'t> {
PakTreeBuilderAccess {
current: 0,
table: self,
trail : VecDeque::new()
}
}
pub fn into_pak(self, pak : &mut PakBuilder) -> PakResult<PakPointer> {
let mut page_map = HashMap::<usize, PakUntypedPointer>::new();
for (index, page) in self.pages.into_iter().enumerate() {
let pointer = pak.pak_no_search(&page)?;
page_map.insert(index as usize, pointer.as_untyped());
}
pak.pak_no_search(&PakTreeMeta{ pages : page_map})
}
}
pub struct PakTreeBuilderAccess<'t> {
table: &'t mut PakTreeBuilder,
current: usize,
trail : VecDeque<usize>
}
impl PakTreeBuilderAccess<'_> {
fn goto(&mut self, page: usize) -> &mut Self {
self.trail.push_front(self.current);
self.current = page;
self
}
fn back(&mut self) -> &mut Self {
let front = self.trail.pop_front();
if let Some(index) = front {
self.current = index;
}
self
}
fn current(&self) -> &PakTreePage {
&self.table.pages[self.current]
}
fn current_mut(&mut self) -> &mut PakTreePage {
&mut self.table.pages[self.current]
}
fn push(&mut self, entry : PakTreePageEntry) -> PakTreeStatus{
self.current_mut().push(entry)
}
fn insert_entry(&mut self, entry : PakTreePageEntry) -> usize {
let mut result = self.push(entry);
while let PakTreeStatus::Next(index, entry) = result {
self.goto(index);
result = self.push(entry);
}
let index = match result {
PakTreeStatus::Ok(index) => index,
PakTreeStatus::Next(_, _) => 0,
};
if self.current().values.len() > self.table.max_size {
self.split();
}
index
}
pub fn insert<K>(&mut self, key: K, value: PakPointer) -> &mut Self where K: Into<PakValue> {
self.insert_entry(PakTreePageEntry::new(key.into(), value));
self
}
fn split(&mut self) {
let mut leading_entries = VecDeque::new();
let mut trailing_entries = VecDeque::new();
let half_max = self.table.max_size / 2;
for _ in 0..half_max {
let current = self.current_mut();
leading_entries.push_back(current.values.pop_front().unwrap());
trailing_entries.push_front(current.values.pop_back().unwrap());
}
let mut middle_entry = self.current_mut().values.pop_front().unwrap();
self.current_mut().values = trailing_entries;
let leading_index = self.new_page(leading_entries);
middle_entry.previous = Some(leading_index);
self.back();
self.insert_entry(middle_entry);
}
fn new_page(&mut self, values : VecDeque<PakTreePageEntry>) -> usize {
let index = self.table.pages.len();
self.table.pages.push(PakTreePage::new_with_entries(values));
index
}
}
#[derive(Debug, Deserialize, Serialize)]
struct PakTreePage {
values: VecDeque<PakTreePageEntry>,
next: Option<usize>,
}
impl PakTreePage {
fn new() -> Self {
PakTreePage {
values: VecDeque::new(),
next: None,
}
}
fn new_with_entries(entries: VecDeque<PakTreePageEntry>) -> Self {
PakTreePage {
values: entries,
next: None,
}
}
fn push(&mut self, mut e : PakTreePageEntry) -> PakTreeStatus {
for (index, entry) in self.values.iter_mut().enumerate() {
match entry.key.cmp(&e.key) {
Ordering::Less => continue,
Ordering::Greater => match entry.previous {
Some(next) => return PakTreeStatus::Next(next, e),
None => {
self.values.insert(index, e);
return PakTreeStatus::Ok(index);
},
},
Ordering::Equal => {
entry.values.append(&mut e.values);
return PakTreeStatus::Ok(index);
},
}
}
match self.next {
Some(index) => PakTreeStatus::Next(index, e),
None => {
self.values.push_back(e);
return PakTreeStatus::Ok(self.values.len() - 1);
},
}
}
}
enum PakTreeStatus {
Ok(usize),
Next(usize, PakTreePageEntry),
}
#[derive(Serialize, Deserialize)]
pub struct PakTreePageEntry {
key: PakValue,
values: Vec<PakPointer>,
previous: Option<usize>,
}
impl Debug for PakTreePageEntry {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.key.fmt(f)?;
if let Some(previous) = self.previous {
f.write_str(" -> ")?;
write!(f, "{}", previous)?;
}
Ok(())
}
}
impl PakTreePageEntry {
pub fn new(key: PakValue, value: PakPointer) -> Self {
PakTreePageEntry {
key,
values : vec![value],
previous: None,
}
}
}
impl PartialEq for PakTreePageEntry {
fn eq(&self, other: &Self) -> bool {
self.key.eq(&other.key)
}
}
impl Eq for PakTreePageEntry {}
impl PartialOrd for PakTreePageEntry {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
self.key.partial_cmp(&other.key)
}
}
impl Ord for PakTreePageEntry {
fn cmp(&self, other: &Self) -> Ordering {
self.key.cmp(&other.key)
}
}