competitive/data_structure/
mod.rs

1//! data structures
2
3use crate::algebra::{
4    AbelianGroup, AbelianMonoid, AdditiveOperation, Associative, EmptyAct, Group, LazyMapMonoid,
5    Magma, MaxOperation, MinOperation, Monoid, MonoidAct, SemiGroup, Unital,
6};
7use crate::algorithm::{BitDpExt, RadixSortKey, SliceSortExt};
8use crate::num::{Bounded, IntBase, RangeBoundsExt, Zero};
9#[cfg(target_arch = "x86_64")]
10use crate::tools::avx512_enabled;
11use crate::tools::{Comparator, SimdBackend, Xorshift, comparator, simd_backend};
12
13#[codesnip::entry("Accumulate")]
14pub use self::accumulate::{Accumulate, Accumulate2d, AccumulateKd};
15#[codesnip::entry("Allocator")]
16pub use self::allocator::{Allocator, BoxAllocator, MemoryPool};
17#[codesnip::entry("BinaryIndexedTree")]
18pub use self::binary_indexed_tree::BinaryIndexedTree;
19#[codesnip::entry("BinaryIndexedTree2D")]
20pub use self::binary_indexed_tree_2d::BinaryIndexedTree2D;
21#[codesnip::entry("BinaryTrie")]
22pub use self::binary_trie::BinaryTrie;
23#[codesnip::entry("BitVector")]
24pub use self::bit_vector::{BitVector, BitVectorBlock, RankSelectDictionaries};
25#[codesnip::entry("BitSet")]
26pub use self::bitset::BitSet;
27#[codesnip::entry("BucketQueue")]
28pub use self::bucket_queue::{BucketQueueI8, BucketQueueI16, BucketQueueU8, BucketQueueU16};
29#[codesnip::entry("compress")]
30pub use self::compress::{Compressor, HashCompress, OrderedCompressor, VecCompress};
31#[codesnip::entry("CompressedBinaryIndexedTree")]
32pub use self::compressed_binary_indexed_tree::{
33    CompressedBinaryIndexedTree, CompressedBinaryIndexedTree1d, CompressedBinaryIndexedTree2d,
34    CompressedBinaryIndexedTree3d, CompressedBinaryIndexedTree4d,
35};
36#[codesnip::entry("CompressedSegmentTree")]
37pub use self::compressed_segment_tree::{
38    CompressedSegmentTree, CompressedSegmentTree1d, CompressedSegmentTree2d,
39    CompressedSegmentTree3d, CompressedSegmentTree4d,
40};
41#[codesnip::entry("container")]
42pub use self::container::{
43    BTreeMapFactory, Container, ContainerEntry, ContainerFactory, HashMapFactory,
44    HashMapFactoryWithCapacity,
45};
46#[codesnip::entry("Counter")]
47pub use self::counter::{BTreeCounter, HashCounter};
48#[codesnip::entry("DaryHeap")]
49pub use self::dary_heap::{
50    DaryHeapI32, DaryHeapI64, DaryHeapI128, DaryHeapU32, DaryHeapU64, DaryHeapU128,
51};
52#[codesnip::entry("DaryPrefixSumTree")]
53pub use self::dary_prefix_sum_tree::{DaryPrefixSumTreeU32, DaryPrefixSumTreeU64};
54#[codesnip::entry("DarySegmentTree")]
55pub use self::dary_segment_tree::{
56    DarySegmentTreeAddI32, DarySegmentTreeAddI64, DarySegmentTreeMaxI32, DarySegmentTreeMaxI64,
57    DarySegmentTreeMinI32, DarySegmentTreeMinI64,
58};
59#[codesnip::entry("DisjointSparseTable")]
60pub use self::disjoint_sparse_table::DisjointSparseTable;
61#[codesnip::entry("DoublyLinkedList")]
62pub use self::doubly_linked_list::DoublyLinkedList;
63#[codesnip::entry("DualSegmentTree")]
64pub use self::dual_segment_tree::DualSegmentTree;
65#[codesnip::entry("FibonacciHash")]
66pub use self::fibonacci_hash::{
67    FibHashMap, FibHashSet, FibonacciHasher, FibonacciHasheru32, FibonacciHasheru64,
68};
69#[codesnip::entry("ImplicitSplayTree")]
70pub use self::implicit_splay_tree::ImplicitSplayTree;
71#[codesnip::entry("ImplicitTreap")]
72pub use self::implicit_treap::ImplicitTreap;
73#[codesnip::entry("Static2DTree")]
74pub use self::kdtree::Static2DTree;
75#[codesnip::entry("LazySegmentTree")]
76pub use self::lazy_segment_tree::LazySegmentTree;
77#[codesnip::entry("LazySegmentTreeMap")]
78pub use self::lazy_segment_tree_map::LazySegmentTreeMap;
79#[codesnip::entry("LiChaoTree")]
80pub use self::li_chao_tree::{LiChaoLine, LiChaoTree, OfflineLiChaoTree};
81#[codesnip::entry("LineSet")]
82pub use self::line_set::LineSet;
83#[codesnip::entry("PairingHeap")]
84pub use self::pairing_heap::PairingHeap;
85#[codesnip::entry("PartiallyRetroactivePriorityQueue")]
86pub use self::partially_retroactive_priority_queue::PartiallyRetroactivePriorityQueue;
87#[codesnip::entry("PersistentSegmentTree")]
88pub use self::persistent_segment_tree::PersistentSegmentTree;
89#[codesnip::entry("RadixHeap")]
90pub use self::radix_heap::{RadixHeapU32, RadixHeapU64};
91#[codesnip::entry("RangeArithmeticProgressionAdd")]
92pub use self::range_ap_add::RangeArithmeticProgressionAdd;
93#[codesnip::entry("RangeFoldWithUpperBound")]
94pub use self::range_fold_with_upper_bound::RangeFoldWithUpperBound;
95#[codesnip::entry("RangeFrequency")]
96pub use self::range_frequency::RangeFrequency;
97#[codesnip::entry("RangeMap")]
98pub use self::range_map::{RangeMap, RangeSet};
99#[codesnip::entry("RangeMinimumQuery")]
100pub use self::range_minimum_query::RangeMinimumQuery;
101#[codesnip::entry("SegmentTree")]
102pub use self::segment_tree::SegmentTree;
103#[codesnip::entry("SegmentTreeMap")]
104pub use self::segment_tree_map::SegmentTreeMap;
105#[codesnip::entry("sliding_window_aggregation")]
106pub use self::sliding_window_aggregation::{DequeAggregation, QueueAggregation};
107#[codesnip::entry("slope_trick")]
108pub use self::slope_trick::SlopeTrick;
109#[codesnip::entry("SparseSet")]
110pub use self::sparse_set::SparseSet;
111#[codesnip::entry("SplayTree")]
112pub use self::splay_tree::SplayTree;
113#[codesnip::entry("StaticRangeProduct")]
114pub use self::static_range_product::StaticRangeProduct;
115#[codesnip::entry("StaticSearch")]
116pub use self::static_search::{SimdKey, StaticSearch};
117#[codesnip::entry("SubmaskRangeQuery")]
118pub use self::submask_range_query::SubmaskRangeQuery;
119#[codesnip::entry("transducer")]
120pub use self::transducer::*;
121#[codesnip::entry("Treap")]
122pub use self::treap::{Treap, TreapData};
123#[codesnip::entry("Trie")]
124pub use self::trie::Trie;
125#[codesnip::entry("UnionFind")]
126pub use self::union_find::{
127    MergingUnionFind, PotentializedUnionFind, UndoableUnionFind, UnionFind, UnionFindBase,
128};
129#[codesnip::entry("VecMap")]
130pub use self::vec_map::{FixedVecMapFactory, VecMap, VecMapFactory, VecMapFactoryWithCapacity};
131#[codesnip::entry("WaveletMatrix")]
132pub use self::wavelet_matrix::{WaveletMatrix, WaveletMatrixPointAdd};
133
134#[cfg_attr(
135    nightly,
136    codesnip::entry("Accumulate", include("algebra", "discrete_steps"))
137)]
138mod accumulate;
139#[cfg_attr(nightly, codesnip::entry("Allocator"))]
140mod allocator;
141#[cfg_attr(nightly, codesnip::entry("BinaryIndexedTree", include("algebra")))]
142mod binary_indexed_tree;
143#[cfg_attr(nightly, codesnip::entry("BinaryIndexedTree2D", include("algebra")))]
144mod binary_indexed_tree_2d;
145#[cfg_attr(
146    nightly,
147    codesnip::entry("binary_search_tree", include("Allocator", "LazyMapMonoid"))
148)]
149pub mod binary_search_tree;
150#[cfg_attr(
151    nightly,
152    codesnip::entry("BinaryTrie", include("algebra", "LazyMapMonoid"))
153)]
154mod binary_trie;
155#[cfg_attr(nightly, codesnip::entry("BitVector"))]
156mod bit_vector;
157#[cfg_attr(nightly, codesnip::entry("BitSet", include("avx_helper")))]
158mod bitset;
159#[cfg_attr(nightly, codesnip::entry("BucketQueue"))]
160mod bucket_queue;
161#[cfg_attr(nightly, codesnip::entry("compress"))]
162mod compress;
163#[cfg_attr(
164    nightly,
165    codesnip::entry("CompressedBinaryIndexedTree", include("algebra"))
166)]
167mod compressed_binary_indexed_tree;
168#[cfg_attr(nightly, codesnip::entry("CompressedSegmentTree", include("algebra")))]
169mod compressed_segment_tree;
170#[cfg_attr(nightly, codesnip::entry("container"))]
171mod container;
172#[cfg_attr(nightly, codesnip::entry("Counter"))]
173mod counter;
174#[cfg_attr(nightly, codesnip::entry("DaryHeap", include("_simd")))]
175mod dary_heap;
176#[cfg_attr(nightly, codesnip::entry("DaryPrefixSumTree", include("_simd")))]
177mod dary_prefix_sum_tree;
178#[cfg_attr(
179    nightly,
180    codesnip::entry("DarySegmentTree", include("_simd", "discrete_steps"))
181)]
182mod dary_segment_tree;
183#[cfg_attr(nightly, codesnip::entry("DisjointSparseTable", include("algebra")))]
184mod disjoint_sparse_table;
185#[cfg_attr(nightly, codesnip::entry("DoublyLinkedList"))]
186mod doubly_linked_list;
187#[cfg_attr(
188    nightly,
189    codesnip::entry("DualSegmentTree", include("MonoidAct", "discrete_steps"))
190)]
191mod dual_segment_tree;
192#[cfg_attr(nightly, codesnip::entry("FibonacciHash"))]
193mod fibonacci_hash;
194#[cfg_attr(
195    nightly,
196    codesnip::entry("ImplicitSplayTree", include("_splay_operations"))
197)]
198mod implicit_splay_tree;
199#[cfg_attr(
200    nightly,
201    codesnip::entry("ImplicitTreap", include("binary_search_tree", "Xorshift"))
202)]
203mod implicit_treap;
204#[cfg_attr(nightly, codesnip::entry("Static2DTree"))]
205mod kdtree;
206#[cfg_attr(
207    nightly,
208    codesnip::entry("LazySegmentTree", include("LazyMapMonoid", "discrete_steps"))
209)]
210mod lazy_segment_tree;
211#[cfg_attr(
212    nightly,
213    codesnip::entry(
214        "LazySegmentTreeMap",
215        include("FibonacciHash", "LazyMapMonoid", "discrete_steps")
216    )
217)]
218mod lazy_segment_tree_map;
219#[cfg_attr(
220    nightly,
221    codesnip::entry("LiChaoTree", include("bounded", "integer", "sort", "zero_one"))
222)]
223mod li_chao_tree;
224#[cfg_attr(nightly, codesnip::entry("LineSet", include("bounded")))]
225mod line_set;
226#[cfg_attr(
227    nightly,
228    codesnip::entry("PairingHeap", include("Comparator", "MonoidAct"))
229)]
230mod pairing_heap;
231#[cfg_attr(
232    nightly,
233    codesnip::entry(
234        "PartiallyRetroactivePriorityQueue",
235        include("bounded", "SegmentTree", "MaxOperation", "MinOperation")
236    )
237)]
238pub mod partially_retroactive_priority_queue;
239#[cfg_attr(
240    nightly,
241    codesnip::entry(
242        "PersistentSegmentTree",
243        include("Allocator", "algebra", "discrete_steps")
244    )
245)]
246mod persistent_segment_tree;
247#[cfg_attr(nightly, codesnip::entry("RadixHeap"))]
248mod radix_heap;
249#[cfg_attr(nightly, codesnip::entry("RangeArithmeticProgressionAdd"))]
250mod range_ap_add;
251#[cfg_attr(
252    nightly,
253    codesnip::entry("RangeFoldWithUpperBound", include("BinaryIndexedTree", "sort"))
254)]
255mod range_fold_with_upper_bound;
256#[cfg_attr(
257    nightly,
258    codesnip::entry(
259        "RangeFrequency",
260        include("BinaryIndexedTree", "AdditiveOperation", "FibonacciHash")
261    )
262)]
263mod range_frequency;
264#[cfg_attr(nightly, codesnip::entry("RangeMap"))]
265mod range_map;
266#[cfg_attr(nightly, codesnip::entry("RangeMinimumQuery"))]
267mod range_minimum_query;
268#[cfg_attr(
269    nightly,
270    codesnip::entry("SegmentTree", include("algebra", "discrete_steps"))
271)]
272mod segment_tree;
273#[cfg_attr(
274    nightly,
275    codesnip::entry(
276        "SegmentTreeMap",
277        include("FibonacciHash", "algebra", "discrete_steps")
278    )
279)]
280mod segment_tree_map;
281#[cfg_attr(nightly, codesnip::entry("_simd", include("avx_helper")))]
282pub mod simd;
283#[cfg_attr(
284    nightly,
285    codesnip::entry("sliding_window_aggregation", include("algebra"))
286)]
287mod sliding_window_aggregation;
288#[cfg_attr(nightly, codesnip::entry("slope_trick"))]
289mod slope_trick;
290#[cfg_attr(nightly, codesnip::entry("SparseSet"))]
291mod sparse_set;
292#[cfg_attr(
293    nightly,
294    codesnip::entry("_splay_operations", include("binary_search_tree"))
295)]
296pub mod splay_operations;
297#[cfg_attr(nightly, codesnip::entry("SplayTree", include("_splay_operations")))]
298mod splay_tree;
299#[cfg_attr(
300    nightly,
301    codesnip::entry("StaticRangeProduct", include("DisjointSparseTable"))
302)]
303mod static_range_product;
304#[cfg_attr(nightly, codesnip::entry("StaticSearch", include("_simd")))]
305mod static_search;
306#[cfg_attr(
307    nightly,
308    codesnip::entry("SubmaskRangeQuery", include("algebra", "BitDp", "Xorshift"))
309)]
310pub mod submask_range_query;
311#[cfg_attr(
312    nightly,
313    codesnip::entry(
314        "transducer",
315        include("algebra", "container", "VecMap", "digit_sequence")
316    )
317)]
318mod transducer;
319#[cfg_attr(
320    nightly,
321    codesnip::entry("Treap", include("binary_search_tree", "Xorshift"))
322)]
323pub mod treap;
324#[cfg_attr(nightly, codesnip::entry("Trie", include("algebra")))]
325mod trie;
326#[cfg_attr(
327    nightly,
328    codesnip::entry("UnionFind", include("algebra", "TupleOperation"))
329)]
330pub mod union_find;
331#[cfg_attr(nightly, codesnip::entry("VecMap", include("container")))]
332mod vec_map;
333#[cfg_attr(
334    nightly,
335    codesnip::entry(
336        "WaveletMatrix",
337        include("BinaryIndexedTree", "BitVector", "compress", "algebra", "avx_helper")
338    )
339)]
340mod wavelet_matrix;
competitive/data_structure/mod.rs

competitive/data_structure/
mod.rs
