Source/WTF/wtf/UnionFind.h

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef UnionFind_h
  27 #define UnionFind_h
  28
  29 #include <wtf/Assertions.h>
  30
  31 namespace WTF {
  32
  33 // A UnionFind class can be used to compute disjoint sets using the
  34 // disjoint-set forest data structure. Each UnionFind instance is a
  35 // node in the forest. Typically you use it by using UnionFind as a
  36 // superclass:
  37 //
  38 // class MemberOfSet : public UnionFind<MemberOfSet> { ... }
  39 //
  40 // Calling x->find() gives you a MemberOfSet* that represents the
  41 // disjoint set that x belongs to. Calling x->unify(y) unifies x's
  42 // set with y's set, and ensures that:
  43 //
  44 // x->find() == y->find()
  45 //
  46 // and that:
  47 //
  48 // a->find() == b->find()
  49 //
  50 // for any a, b if prior to the call to x->unify(y), we would have
  51 // had:
  52 //
  53 // a->find() == x
  54 // b->find() == y
  55 //
  56 // This implementation is almost amortized O(1), but could be worse
  57 // in unlikely pathological cases. It favors having a non-recursive
  58 // single pass implementation of unify() and find() over ensuring the
  59 // theoretical O(InverseAckermann[n]) amortized bound, which is much
  60 // closer to amortized O(1).
  61
  62 template<typename T>
  63 class UnionFind {
  64 public:
  65     UnionFind()
  66         : m_parent(0)
  67     {
  68     }
  69
  70     bool isRoot() const
  71     {
  72         bool result = !m_parent;
  73         ASSERT(result == (const_cast<UnionFind<T>*>(this)->find() == this));
  74         return result;
  75     }
  76
  77     T* find()
  78     {
  79         T* result = static_cast<T*>(this);
  80         T* next = result->m_parent;
  81         while (next) {
  82             result = next;
  83             next = result->m_parent;
  84         }
  85         ASSERT(result);
  86         if (result != this)
  87             m_parent = result;
  88         return result;
  89     }
  90
  91     void unify(T* other)
  92     {
  93         T* a = static_cast<T*>(this)->find();
  94         T* b = other->find();
  95
  96         ASSERT(!a->m_parent);
  97         ASSERT(!b->m_parent);
  98
  99         if (a == b)
 100             return;
 101
 102         a->m_parent = b;
 103     }
 104 private:
 105     T* m_parent;
 106 };
 107
 108 } // namespace WTF
 109
 110 using WTF::UnionFind;
 111
 112 #endif // UnionFind_h