pub fn new(num_of_elements: usize) -> Self {

        debug_assert!(num_of_elements > 0, "Cannot partition the empty set");

        let blocks = vec![Block::new(0, num_of_elements)];

        let elements = (0..num_of_elements).collect();

        Self { elements, blocks }

    }

    pub fn from_indexed_partition(partition: &IndexedPartition) -> Self {

        let mut blocks = vec![Block::new_empty(); partition.num_of_blocks()];

        for element in partition.iter() {

            blocks[element].end += 1;

        }

        let mut start = 0;

        for block in &mut blocks {

            let end = block.end;

            block.begin = start;

            block.end = start; // This will be updated when adding elements.

            start += end;

        }

        let mut elements = vec![0; partition.len()];

        for (element_index, block_index) in partition.iter().enumerate() {

            // Add the element to the block, and update the end index.

            let block = &mut blocks[block_index];

            let pos = block.end;

            elements[pos] = element_index;

            block.end = pos + 1;

        }

        blocks.retain(|block| !block.is_empty());

        Self { elements, blocks }

    }

    pub fn block(&self, block_index: BlockIndex) -> &Block<A> {

        &self.blocks[block_index]

    }

    pub fn block_annotation(&mut self, block_index: BlockIndex) -> &mut A {

        self.blocks[block_index].annotation_mut()

    }

    pub fn split_block<F>(&mut self, block_index: BlockIndex, predicate: F) -> Option<BlockIndex>

    where

        F: Fn(usize) -> bool,

        let mut size = 0usize;

        for state in self.blocks[block_index].begin..self.blocks[block_index].end {

            if predicate(self.elements[state]) {

                self.elements.swap(self.blocks[block_index].begin + size, state);

                size += 1;

            }

        if size == 0 || size == self.blocks[block_index].len() {

            return None;

        }

        let new_block = Block::new(self.blocks[block_index].begin + size, self.blocks[block_index].end);

        let last_block = self.blocks.len();

        self.blocks.push(new_block);

        let new_end = self.blocks[block_index].begin + size;

        self.blocks[block_index].end = new_end;

        trace!(

        Some(BlockIndex::new(last_block))

    }

    pub fn num_of_blocks(&self) -> usize {

        self.blocks.len()

    }

    pub fn iter_block(&self, block_index: BlockIndex) -> BlockIter<'_> {

        BlockIter {

            elements: &self.elements,

            index: self.blocks[block_index].begin,

            end: self.blocks[block_index].end,

        }

    }

    pub fn new(begin: usize, end: usize) -> Self {

        debug_assert!(begin < end, "The range of this block is incorrect {begin}..{end}");

        Block {

            begin,

            end,

            annotation: Default::default(),

        }

    }

    fn new_empty() -> Self {

        Block {

            begin: 0,

            end: 0,

            annotation: Default::default(),

        }

    }

    pub fn annotation(&self) -> &A {

        &self.annotation

    }

    pub fn annotation_mut(&mut self) -> &mut A {

        &mut self.annotation

    }

    pub fn len(&self) -> usize {

        self.assert_consistent();

        self.end - self.begin

    }

    pub fn is_empty(&self) -> bool {

        self.begin == self.end

    }

    fn assert_consistent(&self) {

        debug_assert!(self.begin < self.end, "The range of block {self:?} is incorrect");

    }

    fn next(&mut self) -> Option<Self::Item> {

        if self.index < self.end {

            let element = self.elements[self.index];

            self.index += 1;

            Some(element)

            None

    }

    fn test_simple_block_partition() {

        let mut partition: BlockPartition<()> = BlockPartition::new(10);

        assert_eq!(partition.num_of_blocks(), 1);

        let initial_block = BlockIndex::new(0);

        assert_eq!(partition.block(initial_block).len(), 10);

        let block_index = partition.split_block(BlockIndex::new(0), |state| state < 5).unwrap();

        assert_eq!(partition.num_of_blocks(), 2);

        assert_eq!(partition.block(initial_block).len(), 5);

        assert_eq!(partition.block(block_index).len(), 5);

    }

    fn test_random_from_indexed_partition() {

        random_test(100, |rng| {

            let mut partition = IndexedPartition::new(100);

            for element in 0..partition.len() {

                partition.set_block(element, BlockIndex::new(rng.random_range(0..10)));

            }

            trace!("Input partition {partition}");

            let block_partition: BlockPartition<()> = BlockPartition::from_indexed_partition(&partition);

            trace!("Output partition {block_partition}");

            for block in 0..block_partition.num_of_blocks() {

                let mut elements = block_partition.iter_block(BlockIndex::new(block));

                let first = elements.next().unwrap();

                let expected_block = partition.block(first);

                for element in elements {

                    assert_eq!(partition.block(element), expected_block, "Block {block} contains elements from different indexed-partition blocks");

        })

    }