Re: [Boost-users] [Multi-Index] New "hierarchical" indexing?

Subject: Re: [Boost-users] [Multi-Index] New "hierarchical" indexing?
From: JOAQUIN M. LOPEZ MUÑOZ (joaquin_at_[hidden])
Date: 2009-07-11 06:17:20

________________________________________
De: boost-users-bounces_at_[hidden] [boost-users-bounces_at_[hidden]] En nombre de Dominique Devienne [ddevienne_at_[hidden]]
Enviado el: viernes, 10 de julio de 2009 20:29
Para: boost-users
Asunto: [Boost-users] [Multi-Index] New "hierarchical" indexing?

> In another use case, entries have a "scenario" key, where scenario is
> hierarchical, and I want all entries in BMI A from a given scenario
> and all its ancestors, with the scenarios being in BMI B (i.e.
> "cross-bmi"). Of course I can do a "full scan" but I'm looking for
> something hopefully faster/smarter.

Not entirely sure if the following is directly applicable to your
problem, but anyway. If one of the keys of an index has a hierarchical
nature, one can do child-of queries by taking advantage of compatible
sorting criteria. Let me introduce an example. Suppose we have entries
having an associated scenario which we simply model by a path
showing the hierarchical relations among them:

  typedef std::vector<std::string> path_t;
  typedef flyweight<path_t> scenario_t;

  struct entry
  {
    entry(const scenario_t& scenario):scenario(scenario){}

    scenario_t scenario;
    // payload
  };

Note that we're compressing scenarios with Boost.Flyweight. This
lets us dispose of an auxiliary container to hold the scenarios, which
is what you're likely doing now. Our container of entries indexed by
scenario is

  typedef multi_index_container<
    entry,
    indexed_by<
      ordered_non_unique<member<entry,scenario_t,&entry::scenario> >
    >
  > entry_container_t;

Now we define:

  struct parent_t:scenario_t
  {
    parent_t(const scenario_t& s):scenario_t(s){}
  };

  struct children
  {
    bool operator()(const parent_t& p,const scenario_t& s)const
    {
      return std::lexicographical_compare(
        p.get().begin(),p.get().end(),
        s.get().begin(),s.get().begin()+std::min(p.get().size(),s.get().size()));
    }
    bool operator()(const scenario_t& s,const parent_t& p)const
    {
      return std::lexicographical_compare(
        s.get().begin(),s.get().begin()+std::min(p.get().size(),s.get().size()),
        p.get().begin(),p.get().end());
    }
  };

What is this? parent_t is just a sort of alias to scenario_t that
allows us to differentiate between a "terminal" scenario and
a scenario used for purposes of recursive lookup. children
is a compatible (with the order of entry_container_t) compare
predicate that levels off scenario paths in a way that, for
instance, if we have parent "a" then "a/b", "a/d", "a/b/e" etc.
are deemed equivalent to the parent. This allows us to
locate and count children:

  // count children entries of scenario s
  c.count(parent_t(s),children())

Please find attached a complete example shwoing the technique.
Is this of any help to your particular problem? Thanks for using
Boost.MultiIndex.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo