Struct nekolib::ds::BicrementalMedian

pub struct BicrementalMedian<T: Ord + Clone> { /* private fields */ }

中央値の管理。

多重集合への要素の追加と削除を行いつつ、中央値を管理する。

Naming

incremental と decremental の双方向の処理を行うので、bidirectional の気持ちで bicremental とした。記憶が正しければえびちゃんの造語なので、 もっとよい名前があれば変えたい。dynamic は意味が曖昧なのできらい。

Notes

集合に $k$ 個追加・削除する操作をサポートできないか？と思ったが、 これだと計算量の保証ができない。$\{\{1, 2, \dots, n\}\}$ に対して $0$ を $n$ 個追加する操作と、$0$ を $n$ 個削除する操作を繰り返すことで、 簡単に worst $\Omega(n)$ 時間になってしまう。

Implementations

impl<T: Ord + Clone> BicrementalMedian<T>

pub fn new() -> Self

pub fn insert(&mut self, x: T)

pub fn remove(&mut self, x: &T) -> bool

pub fn median(&self) -> Option<&T>

Trait Implementations

impl<T: Clone + Ord + Clone> Clone for BicrementalMedian<T>

fn clone(&self) -> BicrementalMedian<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Ord + Clone> Debug for BicrementalMedian<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialEq + Ord + Clone> PartialEq<BicrementalMedian<T>> for BicrementalMedian<T>

fn eq(&self, other: &BicrementalMedian<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq + Ord + Clone> Eq for BicrementalMedian<T>

impl<T: Ord + Clone> StructuralEq for BicrementalMedian<T>

impl<T: Ord + Clone> StructuralPartialEq for BicrementalMedian<T>