COIN-OR::LEMON - Graph Library

Changeset 2003:cf012a7c7f69 in lemon-0.x


Ignore:
Timestamp:
03/10/06 19:06:26 (14 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2615
Message:

UnionFindEnum? revision:

  • 0 is _not_ convertible to list<...>::iterator, so we have to use other means to define/check validity
  • standard LEMON iterator interface for ClassIt? and ItemIt?
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/unionfind.h

    r1993 r2003  
    258258    }
    259259
     260    const ItemList& classOf(const T &a) const {
     261      return *_find(m[a])->my_class;
     262    }
     263
    260264  public:
    261265    UnionFindEnum(MapType& _m) : m(_m) {}
     
    344348
    345349        classes.erase(cb->my_class);
    346         cb->my_class = 0;
     350        // ehem: cb->my_class = 0;
    347351      }
    348352      else {
     
    355359
    356360        classes.erase(ca->my_class);
    357         ca->my_class = 0;
     361        // ehem: ca->my_class = 0;
    358362      }
    359363
     
    417421
    418422      ia->my_class = la->my_class;
    419       la->my_class = 0;
     423      // ehem: la->my_class = 0;
    420424
    421425      ia->size = la->size;
     
    475479
    476480      ai->parent = clit;
    477       ai->my_class = 0;
     481      // ehem: ai->my_class = 0;
    478482      ++clit->size;
    479483
     
    484488    /**
    485489     * \brief Removes the given element from the structure.
    486      *
    487      * Removes the given element from the structure.
    488490     *
    489491     * Removes the element from its component and if the component becomes
    490492     * empty then removes that component from the component list.
     493     *
     494     * It is an error to remove an element which is not in the structure.
    491495     */
    492496    void erase(const T &a) {
    493497
    494498      IIter ma = m[a];
    495       if (ma == 0) return;
     499      // ehem: if (ma == 0) return;
    496500
    497501      IIter la = _find(ma);
     
    499503        if (ma -> size == 1){
    500504          classes.erase(ma->my_class);
    501           m.set(a,0);
     505          // ehem: m.set(a,0);
    502506          return;
    503507        }
     
    513517      la->size--;
    514518      la->my_class->erase(ma);
    515       m.set(a,0);
     519      // ehem: m.set(a,0);
    516520    }
    517521
     
    520524     *
    521525     * Removes the component of the given element from the structure.
     526     *
     527     * It is an error to give an element which is not in the structure.
    522528     */
    523529
    524530    void eraseClass(const T &a) {
    525531      IIter ma = m[a];
    526       if (ma == 0) return;
    527 #     ifdef DEBUG
    528       CIter c = _find(ma)->my_class;
    529       for (IIter i=c->begin(); i!=c->end(); ++i)
    530         m.set(i->me, 0);
    531 #     endif
     532      // ehem: if (ma == 0) return;
     533// #     ifdef DEBUG
     534//       CIter c = _find(ma)->my_class;
     535//       for (IIter i=c->begin(); i!=c->end(); ++i)
     536//      m.set(i->me, 0);
     537// #     endif
    532538      classes.erase(_find(ma)->my_class);
    533539    }
     
    538544
    539545      CcIter i;
     546      const ClassList *l;
     547
    540548    public:
    541       ClassIt(Invalid): i(0) {}
     549      ClassIt(Invalid): l(0) {}
    542550      ClassIt() {}
     551      ClassIt(UnionFindEnum const &ufe) {
     552        l = &ufe.classes;
     553        i = l->begin();
     554      }
    543555     
    544556      operator const T& () const {
    545557        ItemList const &ll = *i;
    546         return (ll.begin())->me; }
    547       bool operator == (ClassIt it) const {
    548         return (i == it.i);
    549       }
    550       bool operator != (ClassIt it) const {
    551         return (i != it.i);
    552       }
    553       bool operator < (ClassIt it) const {
     558        return (ll.begin())->me;
     559      }
     560      bool operator == (ClassIt const &it) const {
     561        return (l==it.l && i==it.i) || (!valid() && !it.valid());
     562      }
     563      bool operator != (ClassIt const &it) const {
     564        return !(*this == it);
     565      }
     566      bool operator < (ClassIt const &it) const {
    554567        return (i < it.i);
    555568      }
    556569
    557       bool valid() const { return i != 0; }
     570      bool operator==(Invalid) const {
     571        return !valid();
     572      }
     573      bool operator!=(Invalid) const {
     574        return valid();
     575      }
     576
     577      ClassIt& operator++() {
     578        ++i;
     579        return *this;
     580      }
     581
     582      // obsoleted:
     583      bool valid() const { return l!=0 && i!=l->end(); }
    558584    private:
    559       void first(const ClassList &l) { i = l.begin(); validate(l); }
    560       void next(const ClassList &l) {
    561         ++i;
    562         validate(l);
    563       }
    564       void validate(const ClassList &l) {
    565         if ( i == l.end() )
    566           i = 0;
    567       }
     585      //void first(const ClassList &l) { i = l.begin(); validate(l); }
     586//       void next(const ClassList &l) {
     587//      ++i;
     588//      validate(l);
     589//       }
     590//       void validate(const ClassList &l) {
     591//      if ( i == l.end() )
     592//        i = 0;
     593//       }
    568594    };
    569595
     
    584610     *  }
    585611     * \endcode
     612     *
     613     * \bug obsoleted, use the new LEMON iterator interface instead
    586614     */
    587615
    588616    ClassIt& first(ClassIt& it) const {
    589       it.first(classes);
     617      it = ClassIt(*this);
    590618      return it;
    591619    }
     
    598626     * With the \ref first, \ref valid and \ref next methods you can
    599627     * iterate through the components. See the example here: \ref first.
     628     *
     629     * \bug obsoleted, use the new LEMON iterator interface instead
    600630     */
    601631
     
    614644
    615645    ClassIt& next(ClassIt& it) const {
    616       it.next(classes);
    617       return it;
     646      return ++it;
    618647    }
    619648
     
    625654      const ItemList *l;
    626655    public:
    627       ItemIt(Invalid): i(0) {}
     656      ItemIt(Invalid): l(0) {}
    628657      ItemIt() {}
     658      ItemIt(UnionFindEnum const &ufe, const T& a) {
     659        l = &ufe.classOf(a);
     660        i = l->begin();
     661      }
    629662     
    630663      operator const T& () const { return i->me; }
    631664      bool operator == (ItemIt it) const {
    632         return (i == it.i);
     665        return (l==it.l && i==it.i) || (!valid() && !it.valid());
    633666      }
    634667      bool operator != (ItemIt it) const {
    635         return (i != it.i);
     668        return !(*this == it);
    636669      }
    637670      bool operator < (ItemIt it) const {
     
    639672      }
    640673
    641       bool valid() const { return i != 0; }
     674      bool operator==(Invalid) const {
     675        return !valid();
     676      }
     677      bool operator!=(Invalid) const {
     678        return valid();
     679      }
     680
     681      ItemIt& operator++() {
     682        ++i;
     683        return *this;
     684      }
     685
     686      // obsoleted:
     687      bool valid() const { return l!=0 && i!=l->end(); }
    642688    private:
    643       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
    644       void next() {
    645         ++i;
    646         validate();
    647       }
    648       void validate() {
    649         if ( i == l->end() )
    650           i = 0;
    651       }
     689//       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
     690//       void next() {
     691//      ++i;
     692//      validate();
     693//       }
     694//       void validate() {
     695//      if ( i == l->end() )
     696//        i = 0;
     697//       }
    652698    };
    653699
     
    674720     *   }
    675721     * \endcode
     722     *
     723     * \bug obsoleted, use the new LEMON iterator interface instead
    676724     */
    677725   
    678726    ItemIt& first(ItemIt& it, const T& a) const {
    679       it.first( * _find(m[a])->my_class );
     727      it = ItemIt(*this, a);
    680728      return it;
    681729    }
     
    691739     * iterate through the elements of a component.
    692740     * See the example here: \ref first2 "first".
     741     *
     742     * \bug obsoleted, use the new LEMON iterator interface instead
    693743     */
    694744
    695745    bool valid(ItemIt const &it) const {
    696       return it.valid(); 
     746      return it.valid();
    697747    }
    698748
     
    707757     * iterate through the elements of a component.
    708758     * See the example here: \ref first2 "first".
     759     *
     760     * \bug obsoleted, use the new LEMON iterator interface instead
    709761     */
    710762
    711763    ItemIt& next(ItemIt& it) const {
    712       it.next();
    713       return it;
     764      return ++it;
    714765    }
    715766   
Note: See TracChangeset for help on using the changeset viewer.