RhodeCode

    int _max_level;

    int _item_num;

    VitMap _where;

    IntMap _level;

    std::vector<Item> _items;

    std::vector<Vit> _first;

    std::vector<Vit> _last_active;

    int _highest_active;

    void copy(Item i, Vit p)

    {

    }

    void copy(Vit s, Vit p)

    {

      if(s!=p)

        {

          Item i=*s;

          *p=i;

        }

    }

    void swap(Vit i, Vit j)

    {

      Item ti=*i;

      Vit ct = _where[ti];

      *j=ti;

    }

  public:

    ///Constructor with given maximum level.

    ///Constructor with given maximum level.

    ///

    ///\param g The underlying graph

    ///\param max_level Set the range of the possible labels to

    ///[0...\c max_level]

    ///item.

    int highestActiveLevel() const

    {

      return _highest_active;

    }

    ///Lift the highest active item by one.

    ///Lift the item returned by highestActive() by one.

    ///

    void liftHighestActive()

    {

      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);

      --_first[++_highest_active];

    }

    ///Lift the highest active item.

    ///Lift the item returned by highestActive() to level \c new_level.

    ///

    ///\warning \c new_level must be strictly higher

    ///than the current level.

    ///

    void liftHighestActive(int new_level)

    {

      const Item li = *_last_active[_highest_active];

      copy(--_first[_highest_active+1],_last_active[_highest_active]--);

      for(int l=_highest_active+1;l<new_level;l++)

        {

          copy(--_first[l+1],_first[l]);

          --_last_active[l];

        }

      copy(li,_first[new_level]);

      _highest_active=new_level;

    }

    ///Lift the highest active item.

    ///Lift the item returned by highestActive() to the top level and

    ///deactivates it.

    ///

    ///\warning \c new_level must be strictly higher

    ///than the current level.

    ///

    void liftHighestActiveToTop()

    {

      const Item li = *_last_active[_highest_active];

      copy(--_first[_highest_active+1],_last_active[_highest_active]--);

      for(int l=_highest_active+1;l<_max_level;l++)

        {

          copy(--_first[l+1],_first[l]);

          --_last_active[l];

        }

      copy(li,_first[_max_level]);

      --_last_active[_max_level];

      while(_highest_active>=0 &&

            _last_active[_highest_active]<_first[_highest_active])

        _highest_active--;

    }

    ///@}

    ///\name Active Item on Certain Level

    ///Functions for working with the active items.

    ///@{

    ///an item. (\c l must be from the range [0...\c max_level].

    Item activeOn(int l) const

    {

      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;

    }

    ///Lifts the active item returned by \c activeOn() member function.

    ///Lifts the active item returned by \c activeOn() member function

    ///by one.

    Item liftActiveOn(int level)

    {

      swap(_last_active[level]--, --_first[level+1]);

      if (level+1>_highest_active) ++_highest_active;

    }

    ///Lifts the active item returned by \c activeOn() member function.

    ///Lifts the active item returned by \c activeOn() member function

    ///to the given level.

    void liftActiveOn(int level, int new_level)

    {

      const Item ai = *_last_active[level];

      copy(--_first[level+1], _last_active[level]--);

      for(int l=level+1;l<new_level;l++)

        {

          copy(_last_active[l],_first[l]);

          copy(--_first[l+1], _last_active[l]--);

        }

      copy(ai,_first[new_level]);

      if (new_level>_highest_active) _highest_active=new_level;

    }

    ///Lifts the active item returned by \c activeOn() member function.

    ///Lifts the active item returned by \c activeOn() member function

    ///to the top level.

    void liftActiveToTop(int level)

    {

      const Item ai = *_last_active[level];

      copy(--_first[level+1],_last_active[level]--);

      for(int l=level+1;l<_max_level;l++)

        {

          copy(_last_active[l],_first[l]);

          copy(--_first[l+1], _last_active[l]--);

        }

      copy(ai,_first[_max_level]);

      --_last_active[_max_level];

      if (_highest_active==level) {

        while(_highest_active>=0 &&

              _last_active[_highest_active]<_first[_highest_active])

          _highest_active--;

      }

    }

    ///@}

    ///Lift an active item to a higher level.

    {

      const int lo = _level[i];

      const Vit w = _where[i];

      copy(_last_active[lo],w);

      copy(--_first[lo+1],_last_active[lo]--);

      for(int l=lo+1;l<new_level;l++)

        {

          copy(_last_active[l],_first[l]);

          copy(--_first[l+1],_last_active[l]--);

        }

      copy(i,_first[new_level]);

      if(new_level>_highest_active) _highest_active=new_level;

    }

    ///Move an inactive item to the top but one level (in a dirty way).

    ///This function moves an inactive item to the top but one level.

    ///It makes the underlying datastructure corrupt, so use is only if

    ///you really know what it is for.

    ///\pre The item is on the top level.

    void dirtyTopButOne(Item i) {

    }

    ///Lift all items on and above a level to the top (and deactivate them).

    ///This function lifts all items on and above level \c l to \c

    ///maxLevel(), and also deactivates them.

    void liftToTop(int l)

    {

      const Vit f=_first[l];

      const Vit tl=_first[_max_level];

      for(Vit i=f;i!=tl;++i)

      for(int i=l;i<=_max_level;i++)

        {

          _first[i]=f;

          _last_active[i]=f-1;

        }

      for(_highest_active=l-1;

          _highest_active>=0 &&

            _last_active[_highest_active]<_first[_highest_active];

          _highest_active--) ;

    }

  private:

    ///Start the initialization process.

    void initStart()

    {

      _init_lev=0;

      _init_num=&_items[0];

      _first[0]=&_items[0];

      _last_active[0]=&_items[0]-1;

      Vit n=&_items[0];

      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)

        {

          *n=i;

          ++n;

        }

    }

    ///Add an item to the current level.

    void initAddItem(Item i)

    {

      ++_init_num;

    }

    ///Start a new level.

    ///Start a new level.

    ///It shouldn't be used before the items on level 0 are listed.

    void initNewLevel()

    {

      _init_lev++;

      _first[_init_lev]=_init_num;

      _last_active[_init_lev]=_init_num-1;