DSFMap.h

Go to the documentation of this file.

/* ----------------------------------------------------------------------------

 * GTSAM Copyright 2010, Georgia Tech Research Corporation,
 * Atlanta, Georgia 30332-0415
 * All Rights Reserved
 * Authors: Frank Dellaert, et al. (see THANKS for the full author list)

 * See LICENSE for the license information

 * -------------------------------------------------------------------------- */

#pragma once

#include <cstdlib>  // Provides size_t
#include <map>
#include <set>

namespace gtsam {

template <class KEY>
class DSFMap {
 protected:
  struct Entry {
    typename std::map<KEY, Entry>::iterator parent_;
    size_t rank_;
    Entry() {}
  };

  typedef typename std::map<KEY, Entry> Map;
  typedef typename Map::iterator iterator;
  mutable Map entries_;

  iterator find__(const KEY& key) const {
    static const Entry empty;
    iterator it = entries_.find(key);
    // if key does not exist, create and return itself
    if (it == entries_.end()) {
      it = entries_.insert(std::make_pair(key, empty)).first;
      it->second.parent_ = it;
      it->second.rank_ = 0;
    }
    return it;
  }

  iterator find_(const iterator& it) const {
    // follow parent pointers until we reach set representative
    iterator& parent = it->second.parent_;
    if (parent != it) parent = find_(parent);  // not yet, recurse!
    return parent;
  }

  inline iterator find_(const KEY& key) const {
    iterator initial = find__(key);
    return find_(initial);
  }

 public:
  typedef std::set<KEY> Set;

  DSFMap() {}

  inline KEY find(const KEY& key) const {
    iterator root = find_(key);
    return root->first;
  }

  void merge(const KEY& x, const KEY& y) {
    // straight from http://en.wikipedia.org/wiki/Disjoint-set_data_structure
    iterator xRoot = find_(x);
    iterator yRoot = find_(y);
    if (xRoot == yRoot) return;

    // Merge sets
    if (xRoot->second.rank_ < yRoot->second.rank_)
      xRoot->second.parent_ = yRoot;
    else if (xRoot->second.rank_ > yRoot->second.rank_)
      yRoot->second.parent_ = xRoot;
    else {
      yRoot->second.parent_ = xRoot;
      xRoot->second.rank_ = xRoot->second.rank_ + 1;
    }
  }

  std::map<KEY, Set> sets() const {
    std::map<KEY, Set> sets;
    iterator it = entries_.begin();
    for (; it != entries_.end(); it++) {
      iterator root = find_(it);
      sets[root->first].insert(it->first);
    }
    return sets;
  }
};

class IndexPair : public std::pair<size_t,size_t> {
 public:
  IndexPair(): std::pair<size_t,size_t>(0,0) {}
  IndexPair(size_t i, size_t j) : std::pair<size_t,size_t>(i,j) {}
  inline size_t i() const { return first; };
  inline size_t j() const { return second; };
};
}  // namespace gtsam