RhodeCode

        int idx = firstFreeItem;

        firstFreeItem = items[idx].next;

        return idx;

      } else {

        items.push_back(ItemT());

        return items.size() - 1;

      }

    }

  public:

    /// \brief Constructor

    ExtendFindEnum(ItemIntMap& _index)

      : index(_index), items(), firstFreeItem(-1),

        classes(), firstClass(-1), firstFreeClass(-1) {}

    /// \brief Inserts the given element into a new component.

    ///

    /// This method creates a new component consisting only of the

    /// given element.

    int insert(const Item& item) {

      int cdx = newClass();

      classes[cdx].prev = -1;

      classes[cdx].next = firstClass;

      if (firstClass != -1) {

        classes[firstClass].prev = cdx;

      }

      firstClass = cdx;

      int idx = newItem();

      items[idx].item = item;

      items[idx].cls = cdx;

      items[idx].prev = idx;

      items[idx].next = idx;

      classes[cdx].firstItem = idx;

      index.set(item, idx);

      return cdx;

    }

    /// \brief Inserts the given element into the given component.

    ///

    /// This methods inserts the element \e item a into the \e cls class.

    void insert(const Item& item, int cls) {

      int idx = newItem();

      int rdx = classes[cls].firstItem;

      items[idx].item = item;

      items[idx].cls = cls;

      items[idx].prev = rdx;

      items[idx].next = items[rdx].next;

      items[items[rdx].next].prev = idx;

      items[rdx].next = idx;

      index.set(item, idx);

    }

    /// \brief Clears the union-find data structure

    ///

    /// Erase each item from the data structure.

    void clear() {

      items.clear();

      firstClass = firstFreeClass = firstFreeItem = -1;

    }

    /// \brief Gives back the class of the \e item.

    ///

    /// Gives back the class of the \e item.

    int find(const Item &item) const {

      return items[index[item]].cls;

    }

    /// \brief Gives back a representant item of the component.

    ///

    /// Gives back a representant item of the component.

    Item item(int cls) const {

      return items[classes[cls].firstItem].item;

    }

    /// \brief Removes the given element from the structure.

    ///

    /// Removes the element from its component and if the component becomes

    /// empty then removes that component from the component list.

    ///

    /// \warning It is an error to remove an element which is not in

    /// the structure.

    void erase(const Item &item) {

      int idx = index[item];

      int cdx = items[idx].cls;

      if (idx == items[idx].next) {

        if (classes[cdx].prev != -1) {

          classes[classes[cdx].prev].next = classes[cdx].next;

        } else {

          firstClass = classes[cdx].next;

        }

        if (classes[cdx].next != -1) {

          classes[classes[cdx].next].prev = classes[cdx].prev;

        }

        classes[cdx].next = firstFreeClass;

        firstFreeClass = cdx;

      } else {

        classes[cdx].firstItem = items[idx].next;

        items[items[idx].next].prev = items[idx].prev;

        items[items[idx].prev].next = items[idx].next;

      }

      items[idx].next = firstFreeItem;

      firstFreeItem = idx;

    }

    /// \brief Removes the component of the given element from the structure.

    ///

    /// Removes the component of the given element from the structure.

    ///

    /// \warning It is an error to give an element which is not in the

    /// structure.

    void eraseClass(int cdx) {

      int idx = classes[cdx].firstItem;

      items[items[idx].prev].next = firstFreeItem;

      firstFreeItem = idx;

      if (classes[cdx].prev != -1) {

        classes[classes[cdx].prev].next = classes[cdx].next;

      } else {