class EquivalenceClasses

Declaration

template <class ElemTy, class Compare = std::less<ElemTy>>
class EquivalenceClasses { /* full declaration omitted */ };

Description

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient operations: insert an element into a class of its own, union two classes, and find the class for a given element. In addition to these modification methods, it is possible to iterate over all of the equivalence classes and all of the elements in a class. This implementation is an efficient implementation that only stores one copy of the element being indexed per entry in the set, and allows any arbitrary type to be indexed (as long as it can be ordered with operator < or a comparator is provided). Here is a simple example using integers: This example prints: 4 5 1 2

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:60

Templates

ElemTy

Compare = std::less<ElemTy>

Member Variables

private std::set<ECValue, ECValueComparator> TheMapping

TheMapping - This implicitly provides a mapping from ElemTy values to the ECValues, it just keeps the key as part of the value.

Method Overview

• public EquivalenceClasses<ElemTy, Compare>(const EquivalenceClasses<ElemTy, Compare> & RHS)
• public EquivalenceClasses<ElemTy, Compare>()
• public llvm::EquivalenceClasses::iterator begin() const
• public bool empty() const
• public llvm::EquivalenceClasses::iterator end() const
• public llvm::EquivalenceClasses::member_iterator findLeader(const ElemTy & V) const
• public llvm::EquivalenceClasses::member_iterator findLeader(llvm::EquivalenceClasses::iterator I) const
• public llvm::EquivalenceClasses::iterator findValue(const ElemTy & V) const
• public const ElemTy & getLeaderValue(const ElemTy & V) const
• public unsigned int getNumClasses() const
• public const ElemTy & getOrInsertLeaderValue(const ElemTy & V)
• public llvm::EquivalenceClasses::iterator insert(const ElemTy & Data)
• public bool isEquivalent(const ElemTy & V1, const ElemTy & V2) const
• public llvm::EquivalenceClasses::member_iterator member_begin(llvm::EquivalenceClasses::iterator I) const
• public llvm::EquivalenceClasses::member_iterator member_end() const
• public llvm::EquivalenceClasses::member_iterator unionSets(const ElemTy & V1, const ElemTy & V2)
• public llvm::EquivalenceClasses::member_iterator unionSets(llvm::EquivalenceClasses::member_iterator L1, llvm::EquivalenceClasses::member_iterator L2)

Methods

¶EquivalenceClasses<ElemTy, Compare>(
    const EquivalenceClasses<ElemTy, Compare>&
        RHS)

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:143

Parameters

const EquivalenceClasses<ElemTy, Compare>& RHS

¶EquivalenceClasses<ElemTy, Compare>()

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:142

¶llvm::EquivalenceClasses::iterator begin() const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:167

¶bool empty() const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:170

¶llvm::EquivalenceClasses::iterator end() const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:168

¶llvm::EquivalenceClasses::member_iterator
findLeader(const ElemTy& V) const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:232

Parameters

const ElemTy& V

¶llvm::EquivalenceClasses::member_iterator
findLeader(
    llvm::EquivalenceClasses::iterator I) const

Description

findLeader - Given a value in the set, return a member iterator for the equivalence class it is in. This does the path-compression part that makes union-find "union findy". This returns an end iterator if the value is not in the equivalence class.

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:228

Parameters

llvm::EquivalenceClasses::iterator I

¶llvm::EquivalenceClasses::iterator findValue(
    const ElemTy& V) const

Description

findValue - Return an iterator to the specified value. If it does not exist, end() is returned.

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:184

Parameters

const ElemTy& V

¶const ElemTy& getLeaderValue(
    const ElemTy& V) const

Description

getLeaderValue - Return the leader for the specified value that is in the set. It is an error to call this method for a value that is not yet in the set. For that, call getOrInsertLeaderValue(V).

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:191

Parameters

const ElemTy& V

¶unsigned int getNumClasses() const

Description

getNumClasses - Return the number of equivalence classes in this set. Note that this is a linear time operation.

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:208

¶const ElemTy& getOrInsertLeaderValue(
    const ElemTy& V)

Description

getOrInsertLeaderValue - Return the leader for the specified value that is in the set. If the member is not in the set, it is inserted, then returned.

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:200

Parameters

const ElemTy& V

¶llvm::EquivalenceClasses::iterator insert(
    const ElemTy& Data)

Description

insert - Insert a new value into the union/find set, ignoring the request if the value already exists.

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:220

Parameters

const ElemTy& Data

¶bool isEquivalent(const ElemTy& V1,
                  const ElemTy& V2) const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:264

Parameters

const ElemTy& V1

const ElemTy& V2

¶llvm::EquivalenceClasses::member_iterator
member_begin(
    llvm::EquivalenceClasses::iterator I) const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:174

Parameters

llvm::EquivalenceClasses::iterator I

¶llvm::EquivalenceClasses::member_iterator
member_end() const

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:178

¶llvm::EquivalenceClasses::member_iterator
unionSets(const ElemTy& V1, const ElemTy& V2)

Description

union - Merge the two equivalence sets for the specified values, inserting them if they do not already exist in the equivalence set.

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:238

Parameters

const ElemTy& V1

const ElemTy& V2

¶llvm::EquivalenceClasses::member_iterator
unionSets(
    llvm::EquivalenceClasses::member_iterator L1,
    llvm::EquivalenceClasses::member_iterator L2)

Declared at: llvm/include/llvm/ADT/EquivalenceClasses.h:242

Parameters

llvm::EquivalenceClasses::member_iterator L1

llvm::EquivalenceClasses::member_iterator L2