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#pragma once
27
28#include <wtf/Assertions.h>
29
30namespace WTF {
31
32// A UnionFind class can be used to compute disjoint sets using the
33// disjoint-set forest data structure. Each UnionFind instance is a
34// node in the forest. Typically you use it by using UnionFind as a
35// superclass:
36//
37// class MemberOfSet : public UnionFind<MemberOfSet> { ... }
38//
39// Calling x->find() gives you a MemberOfSet* that represents the
40// disjoint set that x belongs to. Calling x->unify(y) unifies x's
41// set with y's set, and ensures that:
42//
43// x->find() == y->find()
44//
45// and that:
46//
47// a->find() == b->find()
48//
49// for any a, b if prior to the call to x->unify(y), we would have
50// had:
51//
52// a->find() == x
53// b->find() == y
54//
55// This implementation is almost amortized O(1), but could be worse
56// in unlikely pathological cases. It favors having a non-recursive
57// single pass implementation of unify() and find() over ensuring the
58// theoretical O(InverseAckermann[n]) amortized bound, which is much
59// closer to amortized O(1).
60
61template<typename T>
62class UnionFind {
63public:
64 UnionFind()
65 : m_parent(0)
66 {
67 }
68
69 bool isRoot() const
70 {
71 bool result = !m_parent;
72 ASSERT(result == (const_cast<UnionFind<T>*>(this)->find() == this));
73 return result;
74 }
75
76 T* find()
77 {
78 T* result = static_cast<T*>(this);
79 T* next = result->m_parent;
80 while (next) {
81 result = next;
82 next = result->m_parent;
83 }
84 ASSERT(result);
85 if (result != this)
86 m_parent = result;
87 return result;
88 }
89
90 void unify(T* other)
91 {
92 T* a = static_cast<T*>(this)->find();
93 T* b = other->find();
94
95 ASSERT(!a->m_parent);
96 ASSERT(!b->m_parent);
97
98 if (a == b)
99 return;
100
101 a->m_parent = b;
102 }
103private:
104 T* m_parent;
105};
106
107} // namespace WTF
108
109using WTF::UnionFind;
110