CO_Tree_defs.hh

Go to the documentation of this file.

/* CO_Tree class declaration.
   Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
   Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)

This file is part of the Parma Polyhedra Library (PPL).

The PPL is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version.

The PPL is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software Foundation,
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.

For the most up-to-date information see the Parma Polyhedra Library
site: http://bugseng.com/products/ppl/ . */

#ifndef PPL_CO_Tree_defs_hh
#define PPL_CO_Tree_defs_hh 1

#include "CO_Tree_types.hh"

#include "Coefficient_defs.hh"
#include <memory>
#include <cstddef>

#ifndef PPL_CO_TREE_EXTRA_DEBUG
#ifdef PPL_ABI_BREAKING_EXTRA_DEBUG
#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
#define PPL_CO_TREE_EXTRA_DEBUG 1
#else // !defined(PPL_ABI_BREAKING_EXTRA_DEBUG)
#define PPL_CO_TREE_EXTRA_DEBUG 0
#endif // !defined(PPL_ABI_BREAKING_EXTRA_DEBUG)
#endif // !defined(PPL_CO_TREE_EXTRA_DEBUG)


namespace Parma_Polyhedra_Library {

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
class CO_Tree {

public:
  class const_iterator;
  class iterator;

private:
  typedef unsigned height_t;

  PPL_COMPILE_TIME_CHECK(C_Integer<height_t>::max
                         >= sizeof_to_bits(sizeof(dimension_type)),
                         "height_t is too small to store depths.");

  class tree_iterator;

  // This must be declared here, because it is a friend of const_iterator.

  dimension_type dfs_index(const_iterator itr) const;

  // This must be declared here, because it is a friend of iterator.

  dimension_type dfs_index(iterator itr) const;

public:


  typedef Coefficient data_type;
  typedef Coefficient_traits::const_reference data_type_const_reference;


  class const_iterator {
  private:
  public:

    typedef std::bidirectional_iterator_tag iterator_category;
    typedef const data_type value_type;
    typedef std::ptrdiff_t difference_type;
    typedef value_type* pointer;
    typedef data_type_const_reference reference;


    explicit const_iterator();


    explicit const_iterator(const CO_Tree& tree);


    const_iterator(const CO_Tree& tree, dimension_type i);


    const_iterator(const const_iterator& itr);


    const_iterator(const iterator& itr);


    void m_swap(const_iterator& itr);


    const_iterator& operator=(const const_iterator& itr);


    const_iterator& operator=(const iterator& itr);


    const_iterator& operator++();


    const_iterator& operator--();


    const_iterator operator++(int);


    const_iterator operator--(int);

    data_type_const_reference operator*() const;


    dimension_type index() const;


    bool operator==(const const_iterator& x) const;


    bool operator!=(const const_iterator& x) const;

  private:
    bool OK() const;

    const dimension_type* current_index;

    const data_type* current_data;

#if PPL_CO_TREE_EXTRA_DEBUG
    const CO_Tree* tree;
#endif

    friend dimension_type CO_Tree::dfs_index(const_iterator itr) const;
  };


  class iterator {
  public:

    typedef std::bidirectional_iterator_tag iterator_category;
    typedef data_type value_type;
    typedef std::ptrdiff_t difference_type;
    typedef value_type* pointer;
    typedef value_type& reference;


    iterator();


    explicit iterator(CO_Tree& tree);


    iterator(CO_Tree& tree, dimension_type i);


    explicit iterator(const tree_iterator& itr);


    iterator(const iterator& itr);


    void m_swap(iterator& itr);


    iterator& operator=(const iterator& itr);


    iterator& operator=(const tree_iterator& itr);


    iterator& operator++();


    iterator& operator--();


    iterator operator++(int);


    iterator operator--(int);

    data_type& operator*();

    data_type_const_reference operator*() const;


    dimension_type index() const;


    bool operator==(const iterator& x) const;


    bool operator!=(const iterator& x) const;

  private:
    bool OK() const;

    const dimension_type* current_index;

    data_type* current_data;

#if PPL_CO_TREE_EXTRA_DEBUG
    CO_Tree* tree;
#endif

    friend const_iterator& const_iterator::operator=(const iterator&);
    friend dimension_type CO_Tree::dfs_index(iterator itr) const;
  };


  CO_Tree();


  CO_Tree(const CO_Tree& y);


  template <typename Iterator>
  CO_Tree(Iterator i, dimension_type n);


  CO_Tree& operator=(const CO_Tree& y);


  void clear();


  ~CO_Tree();


  bool empty() const;


  dimension_type size() const;

  static dimension_type max_size();

  void dump_tree() const;


  dimension_type external_memory_in_bytes() const;


  iterator insert(dimension_type key);


  iterator insert(dimension_type key, data_type_const_reference data);


  iterator insert(iterator itr, dimension_type key);


  iterator insert(iterator itr, dimension_type key,
                  data_type_const_reference data);


  iterator erase(dimension_type key);


  iterator erase(iterator itr);

  void erase_element_and_shift_left(dimension_type key);


  void increase_keys_from(dimension_type key, dimension_type n);


  void fast_shift(dimension_type i, iterator itr);


  void m_swap(CO_Tree& x);


  iterator begin();


  const iterator& end();

  const_iterator begin() const;

  const const_iterator& end() const;


  const_iterator cbegin() const;


  const const_iterator& cend() const;


  iterator bisect(dimension_type key);


  const_iterator bisect(dimension_type key) const;


  iterator bisect_in(iterator first, iterator last, dimension_type key);


  const_iterator bisect_in(const_iterator first, const_iterator last,
                           dimension_type key) const;


  iterator bisect_near(iterator hint, dimension_type key);


  const_iterator bisect_near(const_iterator hint, dimension_type key) const;

private:


  dimension_type bisect_in(dimension_type first, dimension_type last,
                           dimension_type key) const;


  dimension_type bisect_near(dimension_type hint, dimension_type key) const;


  tree_iterator insert_precise(dimension_type key,
                               data_type_const_reference data,
                               tree_iterator itr);


  tree_iterator insert_precise_aux(dimension_type key,
                                   data_type_const_reference data,
                                   tree_iterator itr);


  void insert_in_empty_tree(dimension_type key,
                            data_type_const_reference data);


  iterator erase(tree_iterator itr);


  void init(dimension_type n);


  void destroy();

  bool structure_OK() const;

  bool OK() const;


  static unsigned integer_log2(dimension_type n);


  static bool is_less_than_ratio(dimension_type numer, dimension_type denom,
                                 dimension_type ratio);


  static bool is_greater_than_ratio(dimension_type numer, dimension_type denom,
                                    dimension_type ratio);


  static void dump_subtree(tree_iterator itr);


  void rebuild_bigger_tree();


  void rebuild_smaller_tree();


  void refresh_cached_iterators();


  tree_iterator rebalance(tree_iterator itr, dimension_type key,
                          data_type_const_reference value);


  dimension_type compact_elements_in_the_rightmost_end(
    dimension_type last_in_subtree, dimension_type subtree_size,
    dimension_type key, data_type_const_reference value,
    bool add_element);


  void redistribute_elements_in_subtree(dimension_type root_index,
                                        dimension_type subtree_size,
                                        dimension_type last_used,
                                        dimension_type key,
                                        data_type_const_reference value,
                                        bool add_element);


  void move_data_from(CO_Tree& tree);


  void copy_data_from(const CO_Tree& tree);


  static dimension_type count_used_in_subtree(tree_iterator itr);


  static void move_data_element(data_type& to, data_type& from);


  static const dimension_type max_density_percent = 91;


  static const dimension_type min_density_percent = 38;


  static const dimension_type min_leaf_density_percent = 1;


  static const dimension_type unused_index = C_Integer<dimension_type>::max;


  iterator cached_end;


  const_iterator cached_const_end;

  height_t max_depth;


  dimension_type* indexes;

  std::allocator<data_type> data_allocator;


  data_type* data;


  dimension_type reserved_size;

  dimension_type size_;
};

class CO_Tree::tree_iterator {

public:

  explicit tree_iterator(CO_Tree& tree);


  tree_iterator(CO_Tree& tree, dimension_type i);


  tree_iterator(const iterator& itr, CO_Tree& tree);


  tree_iterator& operator=(const tree_iterator& itr);


  tree_iterator& operator=(const iterator& itr);


  bool operator==(const tree_iterator& itr) const;


  bool operator!=(const tree_iterator& itr) const;


  void get_root();


  void get_left_child();


  void get_right_child();


  void get_parent();

  void go_down_searching_key(dimension_type key);

  void follow_left_children_with_value();

  void follow_right_children_with_value();


  bool is_root() const;


  bool is_right_child() const;


  bool is_leaf() const;

  data_type& operator*();

  Coefficient_traits::const_reference operator*() const;


  dimension_type& index();


  dimension_type index() const;


  dimension_type key() const;

  CO_Tree& tree;

  dimension_type dfs_index() const;

  dimension_type get_offset() const;


  height_t depth() const;

private:
  bool OK() const;

  dimension_type i;

  dimension_type offset;
};

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
void swap(CO_Tree& x, CO_Tree& y);

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
void swap(CO_Tree::const_iterator& x, CO_Tree::const_iterator& y);

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
void swap(CO_Tree::iterator& x, CO_Tree::iterator& y);

} // namespace Parma_Polyhedra_Library

#include "CO_Tree_inlines.hh"
#include "CO_Tree_templates.hh"

#endif // !defined(PPL_CO_Tree_defs_hh)