cif::category_index Class Reference

Public Member Functions
	category_index (category *cat)
	~category_index ()
row *	find (row *k) const
row *	find_by_value (row_initializer k) const
void	insert (row *r)
void	erase (row *r)
void	reconstruct ()
std::tuple< row *, row * >	reorder ()
size_t	size () const

Detailed Description

Definition at line 139 of file category.cpp.

Constructor & Destructor Documentation

category_index()

cif::category_index::category_index ( category *  cat )

inline

Definition at line 142 of file category.cpp.

        : m_category(*cat)
        , m_row_comparator(m_category)
        , m_root(nullptr)
    {
        reconstruct();
    }

~category_index()

cif::category_index::~category_index ( )

inline

Definition at line 150 of file category.cpp.

    {
        delete m_root;
    }

Member Function Documentation

erase()

void cif::category_index::erase

(

row *

r

)

Definition at line 435 of file category.cpp.

{
    assert(find(k) == k);

    m_root = erase(m_root, k);
    if (m_root != nullptr)
        m_root->m_red = false;
}

find()

row * cif::category_index::find

(

row *

k

)

const

Definition at line 345 of file category.cpp.

{
    const entry *r = m_root;
    while (r != nullptr)
    {
        int d = m_row_comparator(k, r->m_row);
        if (d < 0)
            r = r->m_left;
        else if (d > 0)
            r = r->m_right;
        else
            break;
    }

    return r ? r->m_row : nullptr;
}

find_by_value()

row * cif::category_index::find_by_value

(

row_initializer

k

)

const

Definition at line 362 of file category.cpp.

{
    // sort the values in k first

    row_initializer k2;
    for (auto &f : m_category.key_field_indices())
    {
        auto fld = m_category.get_column_name(f);

        auto ki = find_if(k.begin(), k.end(), [&fld](auto &i) { return i.name() == fld; });
        if (ki == k.end())
            k2.emplace_back(fld, "");
        else
            k2.emplace_back(*ki);
    }

    const entry *r = m_root;
    while (r != nullptr)
    {
        int d = m_row_comparator(k2, r->m_row);
        if (d < 0)
            r = r->m_left;
        else if (d > 0)
            r = r->m_right;
        else
            break;
    }

    return r ? r->m_row : nullptr;
}

insert()

void cif::category_index::insert

(

row *

r

)

Definition at line 393 of file category.cpp.

{
    m_root = insert(m_root, k);
    m_root->m_red = false;
}

reconstruct()

void cif::category_index::reconstruct

(

)

Definition at line 485 of file category.cpp.

{
    delete m_root;
    m_root = nullptr;

    for (auto r : m_category)
        insert(r.get_row());

    // maybe reconstruction can be done quicker by using the following commented code.
    // however, I've not had the time to think of a way to set the red/black flag correctly in that case.

    //  std::vector<row*> rows;
    //  transform(mCat.begin(), mCat.end(), backInserter(rows),
    //      [](Row r) -> row* { assert(r.mData); return r.mData; });
    //
    //  assert(std::find(rows.begin(), rows.end(), nullptr) == rows.end());
    //
    //  // don't use sort here, it will run out of the stack of something.
    //  // quicksort is notorious for using excessive recursion.
    //  // Besides, most of the time, the data is ordered already anyway.
    //
    //  stable_sort(rows.begin(), rows.end(), [this](row* a, row* b) -> bool { return this->mComp(a, b) < 0; });
    //
    //  for (size_t i = 0; i < rows.size() - 1; ++i)
    //      assert(mComp(rows[i], rows[i + 1]) < 0);
    //
    //  deque<entry*> e;
    //  transform(rows.begin(), rows.end(), back_inserter(e),
    //      [](row* r) -> entry* { return new entry(r); });
    //
    //  while (e.size() > 1)
    //  {
    //      deque<entry*> ne;
    //
    //      while (not e.empty())
    //      {
    //          entry* a = e.front();
    //          e.pop_front();
    //
    //          if (e.empty())
    //              ne.push_back(a);
    //          else
    //          {
    //              entry* b = e.front();
    //              b->mLeft = a;
    //
    //              assert(mComp(a->mRow, b->mRow) < 0);
    //
    //              e.pop_front();
    //
    //              if (not e.empty())
    //              {
    //                  entry* c = e.front();
    //                  e.pop_front();
    //
    //                  assert(mComp(b->mRow, c->mRow) < 0);
    //
    //                  b->mRight = c;
    //              }
    //
    //              ne.push_back(b);
    //
    //              if (not e.empty())
    //              {
    //                  ne.push_back(e.front());
    //                  e.pop_front();
    //              }
    //          }
    //      }
    //
    //      swap (e, ne);
    //  }
    //
    //  assert(e.size() == 1);
    //  mRoot = e.front();
}

reorder()

std::tuple<row *, row *> cif::category_index::reorder ( )

inline

Definition at line 165 of file category.cpp.

    {
        std::tuple<row *, row *> result = std::make_tuple(nullptr, nullptr);

        if (m_root != nullptr)
        {
            entry *head = find_min(m_root);
            entry *tail = reorder(m_root);

            tail->m_row->m_next = nullptr;

            result = std::make_tuple(head->m_row, tail->m_row);
        }

        return result;
    }

size()

size_t cif::category_index::size

(

)

const

Definition at line 562 of file category.cpp.

{
    std::stack<entry *> s;
    s.push(m_root);

    size_t result = 0;

    while (not s.empty())
    {
        entry *e = s.top();
        s.pop();

        if (e == nullptr)
            continue;

        ++result;

        s.push(e->m_left);
        s.push(e->m_right);
    }

    return result;
}

---

The documentation for this class was generated from the following file:

• libcifpp/src/category.cpp