rlucene 0.1.0-alpha.3

A Rust port of Apache Lucene, a full-text search engine library
Documentation
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
use crate::core::util::error::lucene_error::Result;
use crate::core::util::intro_sorter::IntroSorter;
use crate::core::util::{Comparator, NaturalOrder, Sorter, TimSorter, TimSorterBase};
use std::collections::HashMap;

///  Methods for manipulating (sorting) and creating collections. Sort methods work directly on the supplied lists and don't copy to/from arrays before/after. For medium size collections as used in the Lucene indexer that is much more efficient.
pub struct CollectionUtil;

impl CollectionUtil {
  #[allow(dead_code)]
  pub fn new_hashmap<K, V>(size: usize) -> HashMap<K, V> {
    let capacity = ((size as f32) / 0.75f32 + 1f32) as usize;
    HashMap::with_capacity(capacity)
  }
  /// Sorts the given mutable slice using the supplied [`Comparator`].
  pub fn intro_sort_with_comparator<T, C>(list: &mut [T], comp: C) -> Result<()>
  where
    C: Comparator<T>,
  {
    let size = list.len();
    if size <= 1 {
      return Ok(());
    }
    ListIntroSorter::new(list, comp).sort(0, size)?;
    Ok(())
  }
  pub fn intro_sort<T>(list: &mut [T]) -> Result<()>
  where
    T: Ord,
  {
    let size = list.len();
    if size <= 1 {
      return Ok(());
    }
    Self::intro_sort_with_comparator(list, NaturalOrder::new())
  }

  pub fn tim_sort_with_comparator<T, C>(list: &mut [T], comp: C) -> Result<()>
  where
    C: Comparator<T>,
    T: Copy,
  {
    let size = list.len();
    if size <= 1 {
      return Ok(());
    }
    ListTimSorter::new(list, comp, size / 64).sort(0, size)?;
    Ok(())
  }
  pub fn tim_sort<T>(list: &mut [T]) -> Result<()>
  where
    T: Copy + Ord,
  {
    let size = list.len();
    if size <= 1 {
      return Ok(());
    }
    Self::tim_sort_with_comparator(list, NaturalOrder::new())
  }
}
// ListTimSorter
struct ListTimSorter<'a, T, C> {
  arr: &'a mut [T],
  tmp: Vec<T>,
  max_temp_slots: usize,
  comp: C,
  pivot: usize,
}
impl<'a, T, C: Comparator<T>> ListTimSorter<'a, T, C>
where
  T: Copy,
{
  pub fn new(
    arr: &'a mut [T],
    comp: C,
    max_temp_slots: usize,
  ) -> TimSorter<ListTimSorter<'a, T, C>> {
    let sub = ListTimSorter {
      arr,
      tmp: Vec::new(),
      max_temp_slots,
      comp,
      pivot: 0,
    };
    TimSorter::new(max_temp_slots, sub)
  }
}
impl<T, C: Comparator<T>> Sorter for ListTimSorter<'_, T, C>
where
  T: Copy,
{
  fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
    self.comp.compare(&self.arr[i], &self.arr[j])
  }

  fn swap(&mut self, i: usize, j: usize) -> Result<()> {
    self.arr.swap(i, j);
    Ok(())
  }

  fn set_pivot(&mut self, i: usize) -> Result<()> {
    self.pivot = i;
    Ok(())
  }

  fn compare_pivot(&mut self, j: usize) -> Result<i32> {
    self.compare(self.pivot, j)
  }
}
impl<T, C: Comparator<T>> TimSorterBase for ListTimSorter<'_, T, C>
where
  T: Copy,
{
  fn copy(&mut self, src: usize, dest: usize) -> Result<()> {
    self.arr[dest] = self.arr[src];
    Ok(())
  }

  fn save(&mut self, start: usize, len: usize) -> Result<()> {
    self.tmp.clear();
    if self.tmp.capacity() == 0 {
      self.tmp.reserve_exact(self.max_temp_slots);
    }
    self.tmp.extend_from_slice(&self.arr[start..start + len]);
    Ok(())
  }

  fn restore(&mut self, src: usize, dest: usize) {
    self.arr[dest] = self.tmp[src];
  }

  fn compare_saved(&self, i: usize, j: usize) -> Result<i32> {
    self.comp.compare(&self.tmp[i], &self.arr[j])
  }
}

// ListIntroSorter
struct ListIntroSorter<'a, T, C> {
  pub list: &'a mut [T],
  comp: C,
  pivot: usize,
}
impl<'a, T, C> ListIntroSorter<'a, T, C> {
  pub fn new(list: &'a mut [T], comp: C) -> ListIntroSorter<'a, T, C> {
    ListIntroSorter {
      list,
      comp,
      pivot: 0,
    }
  }
}

impl<T, C: Comparator<T>> Sorter for ListIntroSorter<'_, T, C> {
  fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
    self.comp.compare(&self.list[i], &self.list[j])
  }

  fn swap(&mut self, i: usize, j: usize) -> Result<()> {
    // The data pointed to by the pivot has been swapped.
    // We need to adjust the pivot value to ensure that
    // the value corresponding to the pivot remains unchanged.
    // To avoid Copying the value, we just swap the pivot index.
    if self.pivot == i || self.pivot == j {
      self.pivot = if self.pivot == i { j } else { i };
    }
    self.list.swap(i, j);
    Ok(())
  }

  fn set_pivot(&mut self, i: usize) -> Result<()> {
    self.pivot = i;
    Ok(())
  }

  fn compare_pivot(&mut self, i: usize) -> Result<i32> {
    self.comp.compare(&self.list[self.pivot], &self.list[i])
  }

  fn sort(&mut self, from: usize, to: usize) -> Result<()> {
    IntroSorter::sort_range(self, from, to)?;
    Ok(())
  }
}

impl<T, C: Comparator<T>> IntroSorter for ListIntroSorter<'_, T, C> {}