added iOS source code

[wl-app.git] / iOS / Pods / Realm / include / core / realm / column.hpp

/*************************************************************************
 *
 * Copyright 2016 Realm Inc.
 *
 * Licensed 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.
 *
 **************************************************************************/

#ifndef REALM_COLUMN_HPP
#define REALM_COLUMN_HPP

#include <cstdint> // unint8_t etc
#include <cstdlib> // size_t
#include <vector>
#include <memory>

#include <realm/array_integer.hpp>
#include <realm/column_type.hpp>
#include <realm/column_fwd.hpp>
#include <realm/spec.hpp>
#include <realm/impl/output_stream.hpp>
#include <realm/query_conditions.hpp>
#include <realm/bptree.hpp>
#include <realm/index_string.hpp>
#include <realm/impl/destroy_guard.hpp>
#include <realm/exceptions.hpp>
#include <realm/table_ref.hpp>

namespace realm {


// Pre-definitions
struct CascadeState;
class StringIndex;

template <class T>
struct ImplicitNull;

template <class T>
struct ImplicitNull<util::Optional<T>> {
    static constexpr bool value = true;
};

template <>
struct ImplicitNull<int64_t> {
    static constexpr bool value = false;
};

template <>
struct ImplicitNull<float> {
    static constexpr bool value = true;
};

template <>
struct ImplicitNull<double> {
    static constexpr bool value = true;
};

// FIXME: Add specialization for ImplicitNull for float, double, StringData, BinaryData.

template <class T, class R, Action action, class Condition, class ColType>
R aggregate(const ColType& column, T target, size_t start, size_t end, size_t limit, size_t* return_ndx);


// Iterator with random access for Columns
template <typename ColumnDataType>
class ColumnRandIterator : public std::iterator<std::random_access_iterator_tag, ColumnDataType, ptrdiff_t, size_t> {
public:
    ColumnRandIterator(const Column<ColumnDataType>* src_col, size_t ndx = 0);
    bool operator==(const ColumnRandIterator<ColumnDataType>& rhs) const;
    bool operator!=(const ColumnRandIterator<ColumnDataType>& rhs) const;
    bool operator<(const ColumnRandIterator<ColumnDataType>& rhs) const;
    bool operator>(const ColumnRandIterator<ColumnDataType>& rhs) const;
    bool operator<=(const ColumnRandIterator<ColumnDataType>& rhs) const;
    bool operator>=(const ColumnRandIterator<ColumnDataType>& rhs) const;
    ColumnRandIterator<ColumnDataType>& operator+=(ptrdiff_t movement);
    ColumnRandIterator<ColumnDataType>& operator-=(ptrdiff_t movement);
    ColumnRandIterator<ColumnDataType>& operator++();
    ColumnRandIterator<ColumnDataType>& operator--();
    ColumnRandIterator<ColumnDataType> operator++(int);
    ColumnRandIterator<ColumnDataType> operator--(int);
    ColumnRandIterator<ColumnDataType> operator+(ptrdiff_t movement);
    ColumnRandIterator<ColumnDataType> operator-(ptrdiff_t movement);
    ptrdiff_t operator-(const ColumnRandIterator<ColumnDataType>& right) const;
    const ColumnDataType operator*() const;
    const ColumnDataType operator->() const;
    const ColumnDataType operator[](ptrdiff_t offset) const;
    size_t get_col_ndx() const;

protected:
    size_t m_col_ndx;
    const Column<ColumnDataType>* m_col;
};

/// Base class for all column types.
class ColumnBase {
public:
    /// Get the number of entries in this column. This operation is relatively
    /// slow.
    virtual size_t size() const noexcept = 0;

    /// \throw LogicError Thrown if this column is not string valued.
    virtual void set_string(size_t row_ndx, StringData value);

    /// Whether or not this column is nullable.
    virtual bool is_nullable() const noexcept;

    /// Whether or not the value at \a row_ndx is NULL. If the column is not
    /// nullable, always returns false.
    virtual bool is_null(size_t row_ndx) const noexcept;

    /// Sets the value at \a row_ndx to be NULL.
    /// \throw LogicError Thrown if this column is not nullable.
    virtual void set_null(size_t row_ndx);

    /// Inserts the specified number of elements into this column
    /// starting at the specified row index. The new elements will have the
    /// default value for the column type.
    ///
    /// \param row_ndx The row to start insertion at. If the row_ndx is less
    /// than prior_num_rows then previous rows from row_ndx onwards will be
    /// moved ahead by num_rows_to_insert.
    ///
    /// \param num_rows_to_insert The number of rows to insert. There is no
    /// restriction on this value.
    ///
    /// \param prior_num_rows The number of elements in this column prior to the
    /// modification.
    ///
    /// \param nullable Specifies whether or not this column is nullable. This
    /// function may assert if nullable does not agree with \a is_nullable()
    virtual void insert_rows(size_t row_ndx, size_t num_rows_to_insert, size_t prior_num_rows, bool nullable) = 0;

    /// Removes the specified number of consecutive elements from
    /// this column, starting at the specified row index.
    ///
    /// \param row_ndx The row to start removal at (inclusive). This must be
    /// less than prior_num_rows.
    ///
    /// \param num_rows_to_erase The number of rows to erase.
    /// The row_ndx + num_rows_to_erase must be less than prior_num_rows.
    ///
    /// \param prior_num_rows The number of elements in this column prior to the
    /// modification.
    ///
    /// \param broken_reciprocal_backlinks If true, link columns must assume
    /// that reciprocal backlinks have already been removed. Non-link columns
    /// should ignore this argument.
    virtual void erase_rows(size_t row_ndx, size_t num_rows_to_erase, size_t prior_num_rows,
                            bool broken_reciprocal_backlinks) = 0;

    /// Removes the element at the specified row index by
    /// moving the element at the last row index over it. This reduces the
    /// number of elements by one.
    ///
    /// \param row_ndx The row to erase. Must be less than prior_num_rows.
    ///
    /// \param prior_num_rows The number of elements in this column prior to the
    /// modification.
    ///
    /// \param broken_reciprocal_backlinks If true, link columns must assume
    /// that reciprocal backlinks have already been removed. Non-link columns
    /// should ignore this argument.
    virtual void move_last_row_over(size_t row_ndx, size_t prior_num_rows, bool broken_reciprocal_backlinks) = 0;

    /// Remove all elements from this column.
    ///
    /// \param num_rows The total number of rows in this column.
    ///
    /// \param broken_reciprocal_backlinks If true, link columns must assume
    /// that reciprocal backlinks have already been removed. Non-link columns
    /// should ignore this argument.
    virtual void clear(size_t num_rows, bool broken_reciprocal_backlinks) = 0;

    /// \brief Swap the elements at the specified indices.
    ///
    /// Behaviour is undefined if:
    /// - \a row_ndx_1 or \a row_ndx_2 point to an invalid element (out-of
    /// bounds)
    /// - \a row_ndx_1 and \a row_ndx_2 point to the same value
    virtual void swap_rows(size_t row_ndx_1, size_t row_ndx_2) = 0;

    virtual void destroy() noexcept = 0;
    void move_assign(ColumnBase& col) noexcept;

    virtual ~ColumnBase() noexcept
    {
    }

    // Disable copying, this is not supported.
    ColumnBase& operator=(const ColumnBase&) = delete;
    ColumnBase(const ColumnBase&) = delete;

    // Getter function for index. For integer index, the caller must supply a
    // buffer that we can store the extracted value in (it may be bitpacked, so
    // we cannot return a pointer in to the Array as we do with String index).
    virtual StringData get_index_data(size_t, StringIndex::StringConversionBuffer& buffer) const noexcept = 0;

    // Search index
    virtual bool supports_search_index() const noexcept;
    virtual bool has_search_index() const noexcept;
    virtual StringIndex* create_search_index();
    virtual void destroy_search_index() noexcept;
    virtual const StringIndex* get_search_index() const noexcept;
    virtual StringIndex* get_search_index() noexcept;
    virtual void set_search_index_ref(ref_type, ArrayParent*, size_t ndx_in_parent);

    virtual Allocator& get_alloc() const noexcept = 0;

    /// Returns the 'ref' of the root array.
    virtual ref_type get_ref() const noexcept = 0;
    virtual MemRef get_mem() const noexcept = 0;

    virtual void replace_root_array(std::unique_ptr<Array> leaf) = 0;
    virtual MemRef clone_deep(Allocator& alloc) const = 0;
    virtual void detach(void) = 0;
    virtual bool is_attached(void) const noexcept = 0;

    static size_t get_size_from_type_and_ref(ColumnType, ref_type, Allocator&, bool) noexcept;

    // These assume that the right column compile-time type has been
    // figured out.
    static size_t get_size_from_ref(ref_type root_ref, Allocator&);
    static size_t get_size_from_ref(ref_type spec_ref, ref_type columns_ref, Allocator&);

    /// Write a slice of this column to the specified output stream.
    virtual ref_type write(size_t slice_offset, size_t slice_size, size_t table_size, _impl::OutputStream&) const = 0;

    /// Get this column's logical index within the containing table, or npos
    /// for free-standing or non-top-level columns.
    size_t get_column_index() const noexcept
    {
        return m_column_ndx;
    }

    virtual void set_parent(ArrayParent*, size_t ndx_in_parent) noexcept = 0;
    virtual size_t get_ndx_in_parent() const noexcept = 0;
    virtual void set_ndx_in_parent(size_t ndx_in_parent) noexcept = 0;

    /// Called to update refs and memory pointers of this column accessor and
    /// all its nested accessors, but only in cases where the logical contents
    /// in strictly unchanged. Group::commit(), and
    /// SharedGroup::commit_and_continue_as_read()() are examples of such
    /// cases. In both those cases, the purpose is to keep user visible
    /// accessors in a valid state across a commit.
    virtual void update_from_parent(size_t old_baseline) noexcept = 0;

    //@{

    /// cascade_break_backlinks_to() is called iteratively for each column by
    /// Table::cascade_break_backlinks_to() with the same arguments as are
    /// passed to Table::cascade_break_backlinks_to(). Link columns must
    /// override it. The same is true for cascade_break_backlinks_to_all_rows(),
    /// except that it is called from
    /// Table::cascade_break_backlinks_to_all_rows(), and that it expects
    /// Table::cascade_break_backlinks_to_all_rows() to pass the number of rows
    /// in the table as \a num_rows.

    virtual void cascade_break_backlinks_to(size_t row_ndx, CascadeState&);
    virtual void cascade_break_backlinks_to_all_rows(size_t num_rows, CascadeState&);

    //@}

    void discard_child_accessors() noexcept;

    /// For columns that are able to contain subtables, this function returns
    /// the pointer to the subtable accessor at the specified row index if it
    /// exists, otherwise it returns null. For other column types, this function
    /// returns null.
    virtual TableRef get_subtable_accessor(size_t row_ndx) const noexcept;

    /// Detach and remove the subtable accessor at the specified row if it
    /// exists. For column types that are unable to contain subtable, this
    /// function does nothing.
    virtual void discard_subtable_accessor(size_t row_ndx) noexcept;

    virtual void adj_acc_insert_rows(size_t row_ndx, size_t num_rows) noexcept;
    virtual void adj_acc_erase_row(size_t row_ndx) noexcept;
    /// See Table::adj_acc_move_over()
    virtual void adj_acc_move_over(size_t from_row_ndx, size_t to_row_ndx) noexcept;
    virtual void adj_acc_swap_rows(size_t row_ndx_1, size_t row_ndx_2) noexcept;
    virtual void adj_acc_move_row(size_t from_ndx, size_t to_ndx) noexcept;
    virtual void adj_acc_merge_rows(size_t old_row_ndx, size_t new_row_ndx) noexcept;
    virtual void adj_acc_clear_root_table() noexcept;

    enum {
        mark_Recursive = 0x01,
        mark_LinkTargets = 0x02,
        mark_LinkOrigins = 0x04,
    };

    virtual void mark(int type) noexcept;

    virtual void bump_link_origin_table_version() noexcept;

    virtual int compare_values(size_t row1, size_t row2) const noexcept = 0;

    /// Refresh the dirty part of the accessor subtree rooted at this column
    /// accessor.
    ///
    /// The following conditions are necessary and sufficient for the proper
    /// operation of this function:
    ///
    ///  - The parent table accessor (excluding its column accessors) is in a
    ///    valid state (already refreshed).
    ///
    ///  - Every subtable accessor in the subtree is marked dirty if it needs to
    ///    be refreshed, or if it has a descendant accessor that needs to be
    ///    refreshed.
    ///
    ///  - This column accessor, as well as all its descendant accessors, are in
    ///    structural correspondence with the underlying node hierarchy whose
    ///    root ref is stored in the parent (`Table::m_columns`) (see
    ///    AccessorConsistencyLevels).
    ///
    ///  - The 'index in parent' property of the cached root array
    ///    (`root->m_ndx_in_parent`) is valid.
    virtual void refresh_accessor_tree(size_t new_col_ndx, const Spec&);

    virtual void verify() const = 0;
    virtual void verify(const Table&, size_t col_ndx) const;
    virtual void to_dot(std::ostream&, StringData title = StringData()) const = 0;
    virtual void do_dump_node_structure(std::ostream&, int level) const = 0;

#ifdef REALM_DEBUG
    void dump_node_structure() const; // To std::cerr (for GDB)
    void bptree_to_dot(const Array* root, std::ostream& out) const;
#endif

protected:
    using SliceHandler = BpTreeBase::SliceHandler;

    ColumnBase(size_t column_ndx = npos)
        : m_column_ndx(column_ndx)
    {
    }
    ColumnBase(ColumnBase&&) = default;

    // Must not assume more than minimal consistency (see
    // AccessorConsistencyLevels).
    virtual void do_discard_child_accessors() noexcept
    {
    }

    //@{
    /// \tparam L Any type with an appropriate `value_type`, %size(),
    /// and %get() members.
    template <class L, class T>
    size_t lower_bound(const L& list, T value) const noexcept;

    template <class L, class T>
    size_t upper_bound(const L& list, T value) const noexcept;
    //@}

    // Node functions

    class CreateHandler {
    public:
        virtual ref_type create_leaf(size_t size) = 0;
        ~CreateHandler() noexcept
        {
        }
    };

    static ref_type create(Allocator&, size_t size, CreateHandler&);

    class LeafToDot;
    virtual void leaf_to_dot(MemRef, ArrayParent*, size_t ndx_in_parent, std::ostream&) const = 0;

    template <class Column>
    static int compare_values(const Column* column, size_t row1, size_t row2) noexcept;

private:
    size_t m_column_ndx = npos;

    static ref_type build(size_t* rest_size_ptr, size_t fixed_height, Allocator&, CreateHandler&);
};


// FIXME: Temporary class until all column types have been migrated to use BpTree interface
class ColumnBaseSimple : public ColumnBase {
public:
    //@{
    /// Returns the array node at the root of this column, but note
    /// that there is no guarantee that this node is an inner B+-tree
    /// node or a leaf. This is the case for a MixedColumn in
    /// particular.
    Array* get_root_array() noexcept
    {
        return m_array.get();
    }
    const Array* get_root_array() const noexcept
    {
        return m_array.get();
    }
    //@}

    Allocator& get_alloc() const noexcept final
    {
        return m_array->get_alloc();
    }
    void destroy() noexcept override
    {
        if (m_array)
            m_array->destroy_deep();
    }
    ref_type get_ref() const noexcept final
    {
        return m_array->get_ref();
    }
    MemRef get_mem() const noexcept final
    {
        return m_array->get_mem();
    }
    void detach() noexcept final
    {
        m_array->detach();
    }
    bool is_attached() const noexcept final
    {
        return m_array->is_attached();
    }
    void set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept final
    {
        m_array->set_parent(parent, ndx_in_parent);
    }
    size_t get_ndx_in_parent() const noexcept final
    {
        return m_array->get_ndx_in_parent();
    }
    void set_ndx_in_parent(size_t ndx_in_parent) noexcept override
    {
        m_array->set_ndx_in_parent(ndx_in_parent);
    }
    void update_from_parent(size_t old_baseline) noexcept override
    {
        m_array->update_from_parent(old_baseline);
    }
    MemRef clone_deep(Allocator& alloc) const override
    {
        return m_array->clone_deep(alloc);
    }

protected:
    ColumnBaseSimple(size_t column_ndx)
        : ColumnBase(column_ndx)
    {
    }
    ColumnBaseSimple(Array* root)
        : m_array(root)
    {
    }
    std::unique_ptr<Array> m_array;

    void replace_root_array(std::unique_ptr<Array> new_root) final;
    bool root_is_leaf() const noexcept
    {
        return !m_array->is_inner_bptree_node();
    }

    /// Introduce a new root node which increments the height of the
    /// tree by one.
    void introduce_new_root(ref_type new_sibling_ref, TreeInsertBase& state, bool is_append);

    static ref_type write(const Array* root, size_t slice_offset, size_t slice_size, size_t table_size, SliceHandler&,
                          _impl::OutputStream&);

#if defined(REALM_DEBUG)
    void tree_to_dot(std::ostream&) const;
#endif
};

class ColumnBaseWithIndex : public ColumnBase {
public:
    ~ColumnBaseWithIndex() noexcept override
    {
    }
    void set_ndx_in_parent(size_t ndx) noexcept override;
    void update_from_parent(size_t old_baseline) noexcept override;
    void refresh_accessor_tree(size_t, const Spec&) override;
    void move_assign(ColumnBaseWithIndex& col) noexcept;
    void destroy() noexcept override;

    virtual bool supports_search_index() const noexcept override
    {
        return true;
    }
    bool has_search_index() const noexcept final
    {
        return bool(m_search_index);
    }
    StringIndex* get_search_index() noexcept final
    {
        return m_search_index.get();
    }
    const StringIndex* get_search_index() const noexcept final
    {
        return m_search_index.get();
    }
    void destroy_search_index() noexcept override;
    void set_search_index_ref(ref_type ref, ArrayParent* parent, size_t ndx_in_parent) final;
    StringIndex* create_search_index() override = 0;

protected:
    using ColumnBase::ColumnBase;
    ColumnBaseWithIndex(ColumnBaseWithIndex&&) = default;
    std::unique_ptr<StringIndex> m_search_index;
};


/// A column (Column) is a single B+-tree, and the root of
/// the column is the root of the B+-tree. All leaf nodes are arrays.
template <class T>
class Column : public ColumnBaseWithIndex {
public:
    using value_type = T;
    using LeafInfo = typename BpTree<T>::LeafInfo;
    using LeafType = typename BpTree<T>::LeafType;

    static constexpr bool nullable = ImplicitNull<T>::value;

    struct unattached_root_tag {
    };

    explicit Column() noexcept
        : ColumnBaseWithIndex(npos)
        , m_tree(Allocator::get_default())
    {
    }
    REALM_DEPRECATED("Initialize with ref instead") explicit Column(std::unique_ptr<Array> root) noexcept;
    Column(Allocator&, ref_type, size_t column_ndx = npos);
    Column(unattached_root_tag, Allocator&);
    Column(Column&&) noexcept = default;
    ~Column() noexcept override;

    void init_from_parent();
    void init_from_ref(Allocator&, ref_type);
    void init_from_mem(Allocator&, MemRef);
    // Accessor concept:
    void destroy() noexcept override;
    Allocator& get_alloc() const noexcept final;
    ref_type get_ref() const noexcept final;
    MemRef get_mem() const noexcept final;
    void set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept override;
    size_t get_ndx_in_parent() const noexcept final;
    void set_ndx_in_parent(size_t ndx) noexcept final;
    void update_from_parent(size_t old_baseline) noexcept override;
    void refresh_accessor_tree(size_t, const Spec&) override;
    void detach() noexcept final;
    bool is_attached() const noexcept final;
    MemRef clone_deep(Allocator&) const override;

    void move_assign(Column&);

    static size_t get_size_from_ref(ref_type root_ref, Allocator& alloc)
    {
        return ColumnBase::get_size_from_ref(root_ref, alloc);
    }

    size_t size() const noexcept override;
    bool is_empty() const noexcept
    {
        return size() == 0;
    }
    bool is_nullable() const noexcept override;

    /// Provides access to the leaf that contains the element at the
    /// specified index. Upon return \a ndx_in_leaf will be set to the
    /// corresponding index relative to the beginning of the leaf.
    ///
    /// LeafInfo is a struct defined by the underlying BpTree<T>
    /// data structure, that provides a way for the caller to do
    /// leaf caching without instantiating too many objects along
    /// the way.
    ///
    /// This function cannot be used for modifying operations as it
    /// does not ensure the presence of an unbroken chain of parent
    /// accessors. For this reason, the identified leaf should always
    /// be accessed through the returned const-qualified reference,
    /// and never directly through the specfied fallback accessor.
    void get_leaf(size_t ndx, size_t& ndx_in_leaf, LeafInfo& inout_leaf) const noexcept;

    // Getting and setting values
    T get(size_t ndx) const noexcept;
    bool is_null(size_t ndx) const noexcept override;
    T back() const noexcept;
    void set(size_t, T value);
    void set_null(size_t) override;
    void add(T value = T{});
    void insert(size_t ndx, T value = T{}, size_t num_rows = 1);
    void erase(size_t row_ndx);
    void erase(size_t row_ndx, bool is_last);
    void move_last_over(size_t row_ndx, size_t last_row_ndx);
    void clear();

    // Index support
    StringData get_index_data(size_t ndx, StringIndex::StringConversionBuffer& buffer) const noexcept override;

    // FIXME: Remove these
    uint64_t get_uint(size_t ndx) const noexcept;
    ref_type get_as_ref(size_t ndx) const noexcept;
    void set_uint(size_t ndx, uint64_t value);
    void set_as_ref(size_t ndx, ref_type value);

    template <class U>
    void adjust(size_t ndx, U diff);

    template <class U>
    void adjust(U diff);

    template <class U>
    void adjust_ge(T limit, U diff);

    size_t count(T target) const;

    typename ColumnTypeTraits<T>::sum_type sum(size_t start = 0, size_t end = npos, size_t limit = npos,
                                               size_t* return_ndx = nullptr) const;

    typename ColumnTypeTraits<T>::minmax_type maximum(size_t start = 0, size_t end = npos, size_t limit = npos,
                                                      size_t* return_ndx = nullptr) const;

    typename ColumnTypeTraits<T>::minmax_type minimum(size_t start = 0, size_t end = npos, size_t limit = npos,
                                                      size_t* return_ndx = nullptr) const;

    double average(size_t start = 0, size_t end = npos, size_t limit = npos, size_t* return_ndx = nullptr) const;

    size_t find_first(T value, size_t begin = 0, size_t end = npos) const;
    void find_all(Column<int64_t>& out_indices, T value, size_t begin = 0, size_t end = npos) const;

    void populate_search_index();
    StringIndex* create_search_index() override;
    inline bool supports_search_index() const noexcept override
    {
        if (realm::is_any<T, float, double>::value)
            return false;
        else
            return true;
    }


    //@{
    /// Find the lower/upper bound for the specified value assuming
    /// that the elements are already sorted in ascending order
    /// according to ordinary integer comparison.
    size_t lower_bound(T value) const noexcept;
    size_t upper_bound(T value) const noexcept;
    //@}

    using const_iterator = ColumnRandIterator<T>;

    const_iterator cbegin() const
    {
        return const_iterator(this, 0); // `this` is const in a const method
    }
    const_iterator cend() const
    {
        return const_iterator(this, size());
    }

    size_t find_gte(T target, size_t start) const;

    bool compare(const Column&) const noexcept;
    int compare_values(size_t row1, size_t row2) const noexcept override;

    static ref_type create(Allocator&, Array::Type leaf_type = Array::type_Normal, size_t size = 0, T value = T{});

    // Overriding method in ColumnBase
    ref_type write(size_t, size_t, size_t, _impl::OutputStream&) const override;

    void insert_rows(size_t, size_t, size_t, bool) override;
    void erase_rows(size_t, size_t, size_t, bool) override;
    void move_last_row_over(size_t, size_t, bool) override;

    /// \brief Swap the elements at the specified indices.
    ///
    /// If this \c Column has a search index defined, it will be updated to
    /// reflect the changes induced by the swap.
    ///
    /// Behaviour is undefined if:
    /// - \a row_ndx_1 or \a row_ndx_2 point to an invalid element (out-of
    /// bounds)
    /// - \a row_ndx_1 and \a row_ndx_2 point to the same value
    void swap_rows(size_t, size_t) override;
    void clear(size_t, bool) override;

    /// \param row_ndx Must be `realm::npos` if appending.
    /// \param value The value to store at the specified row.
    /// \param num_rows The number of rows to insert.
    void insert_without_updating_index(size_t row_ndx, T value, size_t num_rows);

    void verify() const override;
    void to_dot(std::ostream&, StringData title) const override;
    void do_dump_node_structure(std::ostream&, int) const override;
#ifdef REALM_DEBUG
    using ColumnBase::verify;
    void tree_to_dot(std::ostream&) const;
    MemStats stats() const;
#endif

    //@{
    /// Returns the array node at the root of this column, but note
    /// that there is no guarantee that this node is an inner B+-tree
    /// node or a leaf. This is the case for a MixedColumn in
    /// particular.
    Array* get_root_array() noexcept
    {
        return &m_tree.root();
    }
    const Array* get_root_array() const noexcept
    {
        return &m_tree.root();
    }
    //@}

protected:
    bool root_is_leaf() const noexcept
    {
        return m_tree.root_is_leaf();
    }
    void replace_root_array(std::unique_ptr<Array> leaf) final
    {
        m_tree.replace_root(std::move(leaf));
    }

    void set_without_updating_index(size_t row_ndx, T value);
    void erase_without_updating_index(size_t row_ndx, bool is_last);
    void move_last_over_without_updating_index(size_t row_ndx, size_t last_row_ndx);
    void swap_rows_without_updating_index(size_t row_ndx_1, size_t row_ndx_2);

    /// If any element points to an array node, this function recursively
    /// destroys that array node. Note that the same is **not** true for
    /// IntegerColumn::do_erase() and IntegerColumn::do_move_last_over().
    ///
    /// FIXME: Be careful, clear_without_updating_index() currently forgets
    /// if the leaf type is Array::type_HasRefs.
    void clear_without_updating_index();

    void leaf_to_dot(MemRef, ArrayParent*, size_t ndx_in_parent, std::ostream&) const override;
#ifdef REALM_DEBUG
    static void dump_node_structure(const Array& root, std::ostream&, int level);
#endif
    std::pair<ref_type, size_t> get_to_dot_parent(size_t ndx_in_parent) const;

private:
    class EraseLeafElem;
    class CreateHandler;
    class SliceHandler;

    friend class Array;
    friend class ColumnBase;
    friend class StringIndex;

    BpTree<T> m_tree;

    void do_erase(size_t row_ndx, size_t num_rows_to_erase, bool is_last);
};

// Implementation:


template <>
inline size_t IntNullColumn::get_size_from_ref(ref_type root_ref, Allocator& alloc)
{
    // FIXME: Speed improvement possible by not creating instance, but tricky! This slow method is OK so far
    // because it's only invoked by Table::get_size_from_ref() which is only used for subtables which we
    // currently 2016) do not expose publicly.
    IntNullColumn inc(alloc, root_ref);
    return inc.size();
}


inline bool ColumnBase::supports_search_index() const noexcept
{
    REALM_ASSERT(!has_search_index());
    return false;
}

inline bool ColumnBase::has_search_index() const noexcept
{
    return get_search_index() != nullptr;
}

inline StringIndex* ColumnBase::create_search_index()
{
    return nullptr;
}

inline void ColumnBase::destroy_search_index() noexcept
{
}

inline const StringIndex* ColumnBase::get_search_index() const noexcept
{
    return nullptr;
}

inline StringIndex* ColumnBase::get_search_index() noexcept
{
    return nullptr;
}

inline void ColumnBase::set_search_index_ref(ref_type, ArrayParent*, size_t)
{
}

inline void ColumnBase::discard_child_accessors() noexcept
{
    do_discard_child_accessors();
}

inline void ColumnBase::discard_subtable_accessor(size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_insert_rows(size_t, size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_erase_row(size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_move_over(size_t, size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_swap_rows(size_t, size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_move_row(size_t, size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_merge_rows(size_t, size_t) noexcept
{
    // Noop
}

inline void ColumnBase::adj_acc_clear_root_table() noexcept
{
    // Noop
}

inline void ColumnBase::mark(int) noexcept
{
    // Noop
}

inline void ColumnBase::bump_link_origin_table_version() noexcept
{
    // Noop
}

template <class Column>
int ColumnBase::compare_values(const Column* column, size_t row1, size_t row2) noexcept
{
    // we negate nullability such that the two ternary statements in this method can look identical to reduce
    // risk of bugs
    bool v1 = !column->is_null(row1);
    bool v2 = !column->is_null(row2);

    if (!v1 || !v2)
        return v1 == v2 ? 0 : v1 < v2 ? 1 : -1;

    auto a = column->get(row1);
    auto b = column->get(row2);
    return a == b ? 0 : a < b ? 1 : -1;
}

template <class T>
void Column<T>::set_without_updating_index(size_t ndx, T value)
{
    m_tree.set(ndx, std::move(value));
}

template <class T>
void Column<T>::set(size_t ndx, T value)
{
    REALM_ASSERT_DEBUG(ndx < size());
    if (has_search_index()) {
        m_search_index->set(ndx, value);
    }
    set_without_updating_index(ndx, std::move(value));
}

template <class T>
void Column<T>::set_null(size_t ndx)
{
    REALM_ASSERT_DEBUG(ndx < size());
    if (!is_nullable()) {
        throw LogicError{LogicError::column_not_nullable};
    }
    if (has_search_index()) {
        m_search_index->set(ndx, null{});
    }
    m_tree.set_null(ndx);
}

// When a value of a signed type is converted to an unsigned type, the C++ standard guarantees that negative values
// are converted from the native representation to 2's complement, but the opposite conversion is left as undefined.
// realm::util::from_twos_compl() is used here to perform the correct opposite unsigned-to-signed conversion,
// which reduces to a no-op when 2's complement is the native representation of negative values.
template <class T>
void Column<T>::set_uint(size_t ndx, uint64_t value)
{
    set(ndx, util::from_twos_compl<int_fast64_t>(value));
}

template <class T>
void Column<T>::set_as_ref(size_t ndx, ref_type ref)
{
    set(ndx, from_ref(ref));
}

template <class T>
template <class U>
void Column<T>::adjust(size_t ndx, U diff)
{
    REALM_ASSERT_3(ndx, <, size());
    m_tree.adjust(ndx, diff);
}

template <class T>
template <class U>
void Column<T>::adjust(U diff)
{
    m_tree.adjust(diff);
}

template <class T>
template <class U>
void Column<T>::adjust_ge(T limit, U diff)
{
    m_tree.adjust_ge(limit, diff);
}

template <class T>
size_t Column<T>::count(T target) const
{
    if (has_search_index()) {
        return m_search_index->count(target);
    }
    return to_size_t(aggregate<T, int64_t, act_Count, Equal>(*this, target, 0, size(), npos, nullptr));
}

template <class T>
typename ColumnTypeTraits<T>::sum_type Column<T>::sum(size_t start, size_t end, size_t limit,
                                                      size_t* return_ndx) const
{
    using sum_type = typename ColumnTypeTraits<T>::sum_type;
    if (nullable)
        return aggregate<T, sum_type, act_Sum, NotNull>(*this, 0, start, end, limit, return_ndx);
    else
        return aggregate<T, sum_type, act_Sum, None>(*this, 0, start, end, limit, return_ndx);
}

template <class T>
double Column<T>::average(size_t start, size_t end, size_t limit, size_t* return_ndx) const
{
    if (end == size_t(-1))
        end = size();

    auto s = sum(start, end, limit);
    size_t cnt = to_size_t(aggregate<T, int64_t, act_Count, NotNull>(*this, 0, start, end, limit, nullptr));
    if (return_ndx)
        *return_ndx = cnt;
    double avg = double(s) / (cnt == 0 ? 1 : cnt);
    return avg;
}

template <class T>
typename ColumnTypeTraits<T>::minmax_type Column<T>::minimum(size_t start, size_t end, size_t limit,
                                                             size_t* return_ndx) const
{
    using R = typename ColumnTypeTraits<T>::minmax_type;
    return aggregate<T, R, act_Min, NotNull>(*this, 0, start, end, limit, return_ndx);
}

template <class T>
typename ColumnTypeTraits<T>::minmax_type Column<T>::maximum(size_t start, size_t end, size_t limit,
                                                             size_t* return_ndx) const
{
    using R = typename ColumnTypeTraits<T>::minmax_type;
    return aggregate<T, R, act_Max, NotNull>(*this, 0, start, end, limit, return_ndx);
}

template <class T>
void Column<T>::get_leaf(size_t ndx, size_t& ndx_in_leaf, LeafInfo& inout_leaf_info) const noexcept
{
    m_tree.get_leaf(ndx, ndx_in_leaf, inout_leaf_info);
}

template <class T>
StringData Column<T>::get_index_data(size_t ndx, StringIndex::StringConversionBuffer& buffer) const noexcept
{
    T x = get(ndx);
    return to_str(x, buffer);
}

template <class T>
void Column<T>::populate_search_index()
{
    REALM_ASSERT(has_search_index());
    // Populate the index
    size_t num_rows = size();
    for (size_t row_ndx = 0; row_ndx != num_rows; ++row_ndx) {
        bool is_append = true;
        if (is_null(row_ndx)) {
            m_search_index->insert(row_ndx, null{}, 1, is_append); // Throws
        }
        else {
            T value = get(row_ndx);
            m_search_index->insert(row_ndx, value, 1, is_append); // Throws
        }
    }
}

template <class T>
StringIndex* Column<T>::create_search_index()
{
    if (realm::is_any<T, float, double>::value)
        return nullptr;

    REALM_ASSERT(!has_search_index());
    REALM_ASSERT(supports_search_index());
    m_search_index.reset(new StringIndex(this, get_alloc())); // Throws
    populate_search_index();
    return m_search_index.get();
}

template <class T>
size_t Column<T>::find_first(T value, size_t begin, size_t end) const
{
    REALM_ASSERT_3(begin, <=, size());
    REALM_ASSERT(end == npos || (begin <= end && end <= size()));

    if (m_search_index && begin == 0 && end == npos)
        return m_search_index->find_first(value);
    return m_tree.find_first(value, begin, end);
}

template <class T>
void Column<T>::find_all(IntegerColumn& result, T value, size_t begin, size_t end) const
{
    REALM_ASSERT_3(begin, <=, size());
    REALM_ASSERT(end == npos || (begin <= end && end <= size()));

    if (m_search_index && begin == 0 && end == npos)
        return m_search_index->find_all(result, value);
    return m_tree.find_all(result, value, begin, end);
}

inline size_t ColumnBase::get_size_from_ref(ref_type root_ref, Allocator& alloc)
{
    const char* root_header = alloc.translate(root_ref);
    bool root_is_leaf = !Array::get_is_inner_bptree_node_from_header(root_header);
    if (root_is_leaf)
        return Array::get_size_from_header(root_header);
    return BpTreeNode::get_bptree_size_from_header(root_header);
}

template <class L, class T>
size_t ColumnBase::lower_bound(const L& list, T value) const noexcept
{
    size_t i = 0;
    size_t list_size = list.size();
    while (0 < list_size) {
        size_t half = list_size / 2;
        size_t mid = i + half;
        typename L::value_type probe = list.get(mid);
        if (probe < value) {
            i = mid + 1;
            list_size -= half + 1;
        }
        else {
            list_size = half;
        }
    }
    return i;
}

template <class L, class T>
size_t ColumnBase::upper_bound(const L& list, T value) const noexcept
{
    size_t i = 0;
    size_t list_size = list.size();
    while (0 < list_size) {
        size_t half = list_size / 2;
        size_t mid = i + half;
        typename L::value_type probe = list.get(mid);
        if (!(value < probe)) {
            i = mid + 1;
            list_size -= half + 1;
        }
        else {
            list_size = half;
        }
    }
    return i;
}


inline ref_type ColumnBase::create(Allocator& alloc, size_t column_size, CreateHandler& handler)
{
    size_t rest_size = column_size;
    size_t fixed_height = 0; // Not fixed
    return build(&rest_size, fixed_height, alloc, handler);
}

template <class T>
Column<T>::Column(Allocator& alloc, ref_type ref, size_t column_ndx)
    : ColumnBaseWithIndex(column_ndx)
    , m_tree(BpTreeBase::unattached_tag{})
{
    // fixme, must m_search_index be copied here?
    m_tree.init_from_ref(alloc, ref);
}

template <class T>
Column<T>::Column(unattached_root_tag, Allocator& alloc)
    : ColumnBaseWithIndex(npos)
    , m_tree(alloc)
{
}

template <class T>
Column<T>::Column(std::unique_ptr<Array> root) noexcept
    : m_tree(std::move(root))
{
}

template <class T>
Column<T>::~Column() noexcept
{
}

template <class T>
void Column<T>::init_from_parent()
{
    m_tree.init_from_parent();
}

template <class T>
void Column<T>::init_from_ref(Allocator& alloc, ref_type ref)
{
    m_tree.init_from_ref(alloc, ref);
}

template <class T>
void Column<T>::init_from_mem(Allocator& alloc, MemRef mem)
{
    m_tree.init_from_mem(alloc, mem);
}

template <class T>
void Column<T>::destroy() noexcept
{
    ColumnBaseWithIndex::destroy();
    m_tree.destroy();
}

template <class T>
void Column<T>::move_assign(Column<T>& col)
{
    ColumnBaseWithIndex::move_assign(col);
    m_tree = std::move(col.m_tree);
}

template <class T>
Allocator& Column<T>::get_alloc() const noexcept
{
    return m_tree.get_alloc();
}

template <class T>
void Column<T>::set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept
{
    m_tree.set_parent(parent, ndx_in_parent);
}

template <class T>
size_t Column<T>::get_ndx_in_parent() const noexcept
{
    return m_tree.get_ndx_in_parent();
}

template <class T>
void Column<T>::set_ndx_in_parent(size_t ndx_in_parent) noexcept
{
    ColumnBaseWithIndex::set_ndx_in_parent(ndx_in_parent);
    m_tree.set_ndx_in_parent(ndx_in_parent);
}

template <class T>
void Column<T>::detach() noexcept
{
    m_tree.detach();
}

template <class T>
bool Column<T>::is_attached() const noexcept
{
    return m_tree.is_attached();
}

template <class T>
ref_type Column<T>::get_ref() const noexcept
{
    return get_root_array()->get_ref();
}

template <class T>
MemRef Column<T>::get_mem() const noexcept
{
    return get_root_array()->get_mem();
}

template <class T>
void Column<T>::update_from_parent(size_t old_baseline) noexcept
{
    ColumnBaseWithIndex::update_from_parent(old_baseline);
    m_tree.update_from_parent(old_baseline);
}

template <class T>
MemRef Column<T>::clone_deep(Allocator& alloc) const
{
    return m_tree.clone_deep(alloc);
}

template <class T>
size_t Column<T>::size() const noexcept
{
    return m_tree.size();
}

template <class T>
bool Column<T>::is_nullable() const noexcept
{
    return nullable;
}

template <class T>
T Column<T>::get(size_t ndx) const noexcept
{
    return m_tree.get(ndx);
}

template <class T>
bool Column<T>::is_null(size_t ndx) const noexcept
{
    return nullable && m_tree.is_null(ndx);
}

template <class T>
T Column<T>::back() const noexcept
{
    return m_tree.back();
}

template <class T>
ref_type Column<T>::get_as_ref(size_t ndx) const noexcept
{
    return to_ref(get(ndx));
}

template <class T>
uint64_t Column<T>::get_uint(size_t ndx) const noexcept
{
    static_assert(std::is_convertible<T, uint64_t>::value, "T is not convertible to uint.");
    return static_cast<uint64_t>(get(ndx));
}

template <class T>
void Column<T>::add(T value)
{
    insert(npos, std::move(value));
}

template <class T>
void Column<T>::insert_without_updating_index(size_t row_ndx, T value, size_t num_rows)
{
    size_t column_size = this->size(); // Slow
    bool is_append = row_ndx == column_size || row_ndx == npos;
    size_t ndx_or_npos_if_append = is_append ? npos : row_ndx;

    m_tree.insert(ndx_or_npos_if_append, std::move(value), num_rows); // Throws
}

template <class T>
void Column<T>::insert(size_t row_ndx, T value, size_t num_rows)
{
    size_t column_size = this->size(); // Slow
    bool is_append = row_ndx == column_size || row_ndx == npos;
    size_t ndx_or_npos_if_append = is_append ? npos : row_ndx;

    m_tree.insert(ndx_or_npos_if_append, value, num_rows); // Throws

    if (has_search_index()) {
        row_ndx = is_append ? column_size : row_ndx;
        m_search_index->insert(row_ndx, value, num_rows, is_append); // Throws
    }
}

template <class T>
void Column<T>::erase_without_updating_index(size_t row_ndx, bool is_last)
{
    m_tree.erase(row_ndx, is_last);
}

template <class T>
void Column<T>::erase(size_t row_ndx)
{
    REALM_ASSERT(size() >= 1);
    size_t last_row_ndx = size() - 1; // Note that size() is slow
    bool is_last = (row_ndx == last_row_ndx);
    erase(row_ndx, is_last); // Throws
}

template <class T>
void Column<T>::erase(size_t row_ndx, bool is_last)
{
    size_t num_rows_to_erase = 1;
    do_erase(row_ndx, num_rows_to_erase, is_last); // Throws
}

template <class T>
void Column<T>::move_last_over_without_updating_index(size_t row_ndx, size_t last_row_ndx)
{
    m_tree.move_last_over(row_ndx, last_row_ndx);
}

template <class T>
void Column<T>::move_last_over(size_t row_ndx, size_t last_row_ndx)
{
    REALM_ASSERT_3(row_ndx, <=, last_row_ndx);
    REALM_ASSERT_DEBUG(last_row_ndx + 1 == size());

    if (has_search_index()) {
        // remove the value to be overwritten from index
        bool is_last = true; // This tells StringIndex::erase() to not adjust subsequent indexes
        m_search_index->erase<StringData>(row_ndx, is_last); // Throws

        // update index to point to new location
        if (row_ndx != last_row_ndx) {
            T moved_value = get(last_row_ndx);
            m_search_index->update_ref(moved_value, last_row_ndx, row_ndx); // Throws
        }
    }

    move_last_over_without_updating_index(row_ndx, last_row_ndx);
}

template <class T>
void Column<T>::swap_rows(size_t row_ndx_1, size_t row_ndx_2)
{
    REALM_ASSERT_3(row_ndx_1, <, size());
    REALM_ASSERT_3(row_ndx_2, <, size());
    REALM_ASSERT_DEBUG(row_ndx_1 != row_ndx_2);

    if (has_search_index()) {
        T value_1 = get(row_ndx_1);
        T value_2 = get(row_ndx_2);
        size_t column_size = this->size();
        bool row_ndx_1_is_last = row_ndx_1 == column_size - 1;
        bool row_ndx_2_is_last = row_ndx_2 == column_size - 1;
        m_search_index->erase<StringData>(row_ndx_1, row_ndx_1_is_last);
        m_search_index->insert(row_ndx_1, value_2, 1, row_ndx_1_is_last);

        m_search_index->erase<StringData>(row_ndx_2, row_ndx_2_is_last);
        m_search_index->insert(row_ndx_2, value_1, 1, row_ndx_2_is_last);
    }

    swap_rows_without_updating_index(row_ndx_1, row_ndx_2);
}

template <class T>
void Column<T>::swap_rows_without_updating_index(size_t row_ndx_1, size_t row_ndx_2)
{
    // FIXME: This can be optimized with direct getters and setters.
    T value_1 = get(row_ndx_1);
    T value_2 = get(row_ndx_2);
    m_tree.set(row_ndx_1, value_2);
    m_tree.set(row_ndx_2, value_1);
}

template <class T>
void Column<T>::clear_without_updating_index()
{
    m_tree.clear(); // Throws
}

template <class T>
void Column<T>::clear()
{
    if (has_search_index()) {
        m_search_index->clear();
    }
    clear_without_updating_index();
}

template <class T, class Enable = void>
struct NullOrDefaultValue;
template <class T>
struct NullOrDefaultValue<T, typename std::enable_if<std::is_floating_point<T>::value>::type> {
    static T null_or_default_value(bool is_null)
    {
        if (is_null) {
            return null::get_null_float<T>();
        }
        else {
            return T{};
        }
    }
};
template <class T>
struct NullOrDefaultValue<util::Optional<T>, void> {
    static util::Optional<T> null_or_default_value(bool is_null)
    {
        if (is_null) {
            return util::none;
        }
        else {
            return util::some<T>(T{});
        }
    }
};
template <class T>
struct NullOrDefaultValue<T, typename std::enable_if<!ImplicitNull<T>::value>::type> {
    static T null_or_default_value(bool is_null)
    {
        REALM_ASSERT(!is_null);
        return T{};
    }
};

// Implementing pure virtual method of ColumnBase.
template <class T>
void Column<T>::insert_rows(size_t row_ndx, size_t num_rows_to_insert, size_t prior_num_rows, bool insert_nulls)
{
    REALM_ASSERT_DEBUG(prior_num_rows == size());
    REALM_ASSERT(row_ndx <= prior_num_rows);

    size_t row_ndx_2 = (row_ndx == prior_num_rows ? realm::npos : row_ndx);
    T value = NullOrDefaultValue<T>::null_or_default_value(insert_nulls);
    insert(row_ndx_2, value, num_rows_to_insert); // Throws
}

// Implementing pure virtual method of ColumnBase.
template <class T>
void Column<T>::erase_rows(size_t row_ndx, size_t num_rows_to_erase, size_t prior_num_rows, bool)
{
    REALM_ASSERT_DEBUG(prior_num_rows == size());
    REALM_ASSERT(num_rows_to_erase <= prior_num_rows);
    REALM_ASSERT(row_ndx <= prior_num_rows - num_rows_to_erase);

    bool is_last = (row_ndx + num_rows_to_erase == prior_num_rows);
    do_erase(row_ndx, num_rows_to_erase, is_last); // Throws
}

// Implementing pure virtual method of ColumnBase.
template <class T>
void Column<T>::move_last_row_over(size_t row_ndx, size_t prior_num_rows, bool)
{
    REALM_ASSERT_DEBUG(prior_num_rows == size());
    REALM_ASSERT(row_ndx < prior_num_rows);

    size_t last_row_ndx = prior_num_rows - 1;
    move_last_over(row_ndx, last_row_ndx); // Throws
}

// Implementing pure virtual method of ColumnBase.
template <class T>
void Column<T>::clear(size_t, bool)
{
    clear(); // Throws
}


template <class T>
size_t Column<T>::lower_bound(T value) const noexcept
{
    if (root_is_leaf()) {
        auto root = static_cast<const LeafType*>(get_root_array());
        return root->lower_bound(value);
    }
    return ColumnBase::lower_bound(*this, value);
}

template <class T>
size_t Column<T>::upper_bound(T value) const noexcept
{
    if (root_is_leaf()) {
        auto root = static_cast<const LeafType*>(get_root_array());
        return root->upper_bound(value);
    }
    return ColumnBase::upper_bound(*this, value);
}

// For a *sorted* Column, return first element E for which E >= target or return -1 if none
template <class T>
size_t Column<T>::find_gte(T target, size_t start) const
{
    // fixme: slow reference implementation. See Array::find_gte for faster version
    size_t ref = 0;
    size_t idx;
    for (idx = start; idx < size(); ++idx) {
        if (get(idx) >= target) {
            ref = idx;
            break;
        }
    }
    if (idx == size())
        ref = not_found;

    return ref;
}


template <class T>
bool Column<T>::compare(const Column<T>& c) const noexcept
{
    size_t n = size();
    if (c.size() != n)
        return false;
    for (size_t i = 0; i < n; ++i) {
        bool left_is_null = is_null(i);
        bool right_is_null = c.is_null(i);
        if (left_is_null != right_is_null) {
            return false;
        }
        if (!left_is_null) {
            if (get(i) != c.get(i))
                return false;
        }
    }
    return true;
}

template <class T>
int Column<T>::compare_values(size_t row1, size_t row2) const noexcept
{
    return ColumnBase::compare_values(this, row1, row2);
}

template <class T>
class Column<T>::CreateHandler : public ColumnBase::CreateHandler {
public:
    CreateHandler(Array::Type leaf_type, T value, Allocator& alloc)
        : m_value(value)
        , m_alloc(alloc)
        , m_leaf_type(leaf_type)
    {
    }
    ref_type create_leaf(size_t size) override
    {
        MemRef mem = BpTree<T>::create_leaf(m_leaf_type, size, m_value, m_alloc); // Throws
        return mem.get_ref();
    }

private:
    const T m_value;
    Allocator& m_alloc;
    Array::Type m_leaf_type;
};

template <class T>
ref_type Column<T>::create(Allocator& alloc, Array::Type leaf_type, size_t size, T value)
{
    CreateHandler handler(leaf_type, std::move(value), alloc);
    return ColumnBase::create(alloc, size, handler);
}

template <class T>
ref_type Column<T>::write(size_t slice_offset, size_t slice_size, size_t table_size, _impl::OutputStream& out) const
{
    return m_tree.write(slice_offset, slice_size, table_size, out);
}

template <class T>
void Column<T>::refresh_accessor_tree(size_t new_col_ndx, const Spec& spec)
{
    m_tree.init_from_parent();
    ColumnBaseWithIndex::refresh_accessor_tree(new_col_ndx, spec);
}

template <class T>
void Column<T>::do_erase(size_t row_ndx, size_t num_rows_to_erase, bool is_last)
{
    if (has_search_index()) {
        for (size_t i = num_rows_to_erase; i > 0; --i) {
            size_t row_ndx_2 = row_ndx + i - 1;
            m_search_index->erase<T>(row_ndx_2, is_last); // Throws
        }
    }
    for (size_t i = num_rows_to_erase; i > 0; --i) {
        size_t row_ndx_2 = row_ndx + i - 1;
        erase_without_updating_index(row_ndx_2, is_last); // Throws
    }
}

template <class T>
void Column<T>::verify() const
{
#ifdef REALM_DEBUG
    m_tree.verify();
#endif
}

// LCOV_EXCL_START

template <class T>
void Column<T>::to_dot(std::ostream& out, StringData title) const
{
#ifdef REALM_DEBUG
    ref_type ref = get_root_array()->get_ref();
    out << "subgraph cluster_integer_column" << ref << " {" << std::endl;
    out << " label = \"Integer column";
    if (title.size() != 0)
        out << "\\n'" << title << "'";
    out << "\";" << std::endl;
    tree_to_dot(out);
    out << "}" << std::endl;
#else
    static_cast<void>(out);
    static_cast<void>(title);
#endif
}

template <class T>
void Column<T>::leaf_to_dot(MemRef leaf_mem, ArrayParent* parent, size_t ndx_in_parent, std::ostream& out) const
{
#ifdef REALM_DEBUG
    BpTree<T>::leaf_to_dot(leaf_mem, parent, ndx_in_parent, out, get_alloc());
#else
    static_cast<void>(leaf_mem);
    static_cast<void>(parent);
    static_cast<void>(ndx_in_parent);
    static_cast<void>(out);
#endif
}

template <class T>
void Column<T>::do_dump_node_structure(std::ostream& out, int level) const
{
#ifdef REALM_DEBUG
    dump_node_structure(*get_root_array(), out, level);
#else
    static_cast<void>(out);
    static_cast<void>(level);
#endif
}

#ifdef REALM_DEBUG

template <class T>
void Column<T>::tree_to_dot(std::ostream& out) const
{
    ColumnBase::bptree_to_dot(get_root_array(), out);
}


template <class T>
MemStats Column<T>::stats() const
{
    MemStats mem_stats;
    get_root_array()->stats(mem_stats);
    return mem_stats;
}

namespace _impl {
void leaf_dumper(MemRef mem, Allocator& alloc, std::ostream& out, int level);
}

template <class T>
void Column<T>::dump_node_structure(const Array& root, std::ostream& out, int level)
{
    root.dump_bptree_structure(out, level, &_impl::leaf_dumper);
}

#endif

template <class T>
std::pair<ref_type, size_t> Column<T>::get_to_dot_parent(size_t ndx_in_parent) const
{
    auto root = get_root_array();
    if (root->is_inner_bptree_node()) {
        std::pair<MemRef, size_t> p = static_cast<const BpTreeNode*>(root)->get_bptree_leaf(ndx_in_parent);
        return std::make_pair(p.first.get_ref(), p.second);
    }
    else {
        return std::make_pair(root->get_ref(), ndx_in_parent);
    }
}

// LCOV_EXCL_STOP ignore debug functions


template <class ColumnDataType>
ColumnRandIterator<ColumnDataType>::ColumnRandIterator(const Column<ColumnDataType>* src_col, size_t ndx)
    : m_col_ndx(ndx)
    , m_col(src_col)
{
}

template <class ColumnDataType>
bool ColumnRandIterator<ColumnDataType>::operator==(const ColumnRandIterator<ColumnDataType>& rhs) const
{
    return (m_col_ndx == rhs.m_col_ndx);
}

template <class ColumnDataType>
bool ColumnRandIterator<ColumnDataType>::operator!=(const ColumnRandIterator<ColumnDataType>& rhs) const
{
    return !(*this == rhs);
}

template <class ColumnDataType>
bool ColumnRandIterator<ColumnDataType>::operator<(const ColumnRandIterator<ColumnDataType>& rhs) const
{
    return m_col_ndx < rhs.m_col_ndx;
}

template <class ColumnDataType>
bool ColumnRandIterator<ColumnDataType>::operator>(const ColumnRandIterator<ColumnDataType>& rhs) const
{
    return rhs < *this;
}

template <class ColumnDataType>
bool ColumnRandIterator<ColumnDataType>::operator<=(const ColumnRandIterator<ColumnDataType>& rhs) const
{
    return !(rhs < *this);
}

template <class ColumnDataType>
bool ColumnRandIterator<ColumnDataType>::operator>=(const ColumnRandIterator<ColumnDataType>& rhs) const
{
    return !(*this < rhs);
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType>& ColumnRandIterator<ColumnDataType>::operator+=(ptrdiff_t movement)
{
    m_col_ndx += movement;
    return (*this);
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType>& ColumnRandIterator<ColumnDataType>::operator-=(ptrdiff_t movement)
{
    m_col_ndx -= movement;
    return (*this);
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType>& ColumnRandIterator<ColumnDataType>::operator++()
{
    ++m_col_ndx;
    return (*this);
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType>& ColumnRandIterator<ColumnDataType>::operator--()
{
    --m_col_ndx;
    return (*this);
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType> ColumnRandIterator<ColumnDataType>::operator++(int)
{
    auto temp(*this);
    ++m_col_ndx;
    return temp;
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType> ColumnRandIterator<ColumnDataType>::operator--(int)
{
    auto temp(*this);
    --m_col_ndx;
    return temp;
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType> ColumnRandIterator<ColumnDataType>::operator+(ptrdiff_t movement)
{
    return ColumnRandIterator(m_col, m_col_ndx + movement);
}

template <class ColumnDataType>
ColumnRandIterator<ColumnDataType> ColumnRandIterator<ColumnDataType>::operator-(ptrdiff_t movement)
{
    return ColumnRandIterator(m_col, m_col_ndx - movement);
}

template <class ColumnDataType>
ptrdiff_t ColumnRandIterator<ColumnDataType>::operator-(const ColumnRandIterator<ColumnDataType>& right) const
{
    return m_col_ndx - right.m_col_ndx;
}

template <class ColumnDataType>
const ColumnDataType ColumnRandIterator<ColumnDataType>::operator*() const
{
    return m_col->get(m_col_ndx);
}

template <class ColumnDataType>
const ColumnDataType ColumnRandIterator<ColumnDataType>::operator->() const
{
    return m_col->get(m_col_ndx);
}

template <class ColumnDataType>
const ColumnDataType ColumnRandIterator<ColumnDataType>::operator[](ptrdiff_t offset) const
{
    return m_col->get(m_col_ndx + offset);
}

template <class ColumnDataType>
size_t ColumnRandIterator<ColumnDataType>::get_col_ndx() const
{
    return m_col_ndx;
}

template <class ColumnDataType>
std::ostream& operator<<(std::ostream& out, const ColumnRandIterator<ColumnDataType>& it)
{
    out << "ColumnRandIterator at index: " << it.get_col_ndx();
    return out;
}

} // namespace realm

#endif // REALM_COLUMN_HPP