class EquivalenceClasses

Declaration

template <class 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 < ). Here is a simple example using integers: This example prints: 4 5 1 2

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

Templates

ElemTy

Method Overview

• public EquivalenceClasses<ElemTy>(const EquivalenceClasses<ElemTy> & RHS)
• public EquivalenceClasses<ElemTy>()
• 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>(
    const EquivalenceClasses<ElemTy>& RHS)

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

Parameters

const EquivalenceClasses<ElemTy>& RHS

¶EquivalenceClasses<ElemTy>()

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

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

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

¶bool empty() const

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

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

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

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

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

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:207

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:163

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:170

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:187

¶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:179

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:199

Parameters

const ElemTy& Data

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

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

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:153

Parameters

llvm::EquivalenceClasses::iterator I

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

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

¶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:217

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:221

Parameters

llvm::EquivalenceClasses::member_iterator L1

llvm::EquivalenceClasses::member_iterator L2