VCList Class Reference

Sorted list of VCs. More...

#include <VCList.hpp>

Public Member Functions
	VCList (HexPoint x, HexPoint y, unsigned int soft)
	Creates a list with given limits.
HexPoint	getX () const
HexPoint	getY () const
int	softlimit () const
	Returns the soft limit.
void	setSoftLimit (int limit)
	See softlimit().
void	clear ()
	Empties the list and the changelog.
std::size_t	size () const
	Returns the number of VCs in this list.
bool	empty () const
	Returns true if the list is empty.
std::string	dump () const
	Dumps the contents of this list to a string.
bool	isSupersetOfAny (const bitset_t &vc) const
	Returns true if bs is superset of connection in list.
bool	isSubsetOfAny (const bitset_t &vc) const
	Returns true if vc is subset of connection in list.
int	removeSuperSetsOf (const bitset_t &vc, ChangeLog< VC > *log, bool dirty_intersections=true)
	Removes any connection whose carrier is a superset of the given VC's carrier.
bitset_t	getUnion () const
	Returns the union of all carriers in the list.
bitset_t	getGreedyUnion () const
	Returns the union of all carriers in the list.
bitset_t	softIntersection () const
	Returns soft-limit intersection.
bitset_t	hardIntersection () const
	Returns hard-limit intersection.
int	removeAllContaining (HexPoint cell, std::list< VC > &out, ChangeLog< VC > *log)
	Removes all VCs that intersect with b.
int	removeAllContaining (const bitset_t &b, std::list< VC > &out, ChangeLog< VC > *log)
int	removeAllContaining (const bitset_t &b, ChangeLog< VC > *log)
bool	operator== (const VCList &other) const
	Performs list equality.
bool	operator!= (const VCList &other) const
	Performs list inequality.
Protected Member Functions
void	dirty_list_unions ()
	Invalidates the precomputed list unions.
void	dirty_list_intersections ()
	Invalidates the list intersection.
void	computeUnions () const
	Computes list unions in one pass: normal and greedy.
void	computeIntersections () const
	Computes list intersections in one pass: soft and hard.
Protected Attributes
HexPoint	m_x
HexPoint	m_y
unsigned int	m_softlimit
	See softlimit().
std::list< VC >	m_vcs
bool	m_dirty_intersection
bitset_t	m_soft_intersection
bitset_t	m_hard_intersection
bool	m_dirty_union
bitset_t	m_union
bitset_t	m_greedy_union
Adding connections

enum	AddResult { ADD_FAILED = 0, ADDED_INSIDE_SOFT_LIMIT = 1, ADDED_INSIDE_HARD_LIMIT = 2 }
	Return type for add() methods. More...
AddResult	add (const VC &vc, ChangeLog< VC > *log)
	Adds vc to the list.
int	add (const VCList &other, ChangeLog< VC > *log)
	Adds the elements of other to list.
void	simple_add (const VC &vc)
	Force the addition of this vc.
Iterators

typedef std::list< VC >::iterator	iterator
typedef std::list< VC > ::const_iterator	const_iterator
iterator	find (const VC &vc)
	Returns an iterator to the given VC, or end() if vc is not in the list.
iterator	find (const VC &vc, const iterator &b, const iterator &e)
const_iterator	find (const VC &vc) const
	Returns a constant iterator to the given VC, or end() if vc is not in the list.
const_iterator	find (const VC &vc, const const_iterator &b, const const_iterator &e) const
iterator	remove (iterator i, ChangeLog< VC > *log)
	Removes the element pointed to by i from the list.
bool	remove (const VC &vc, ChangeLog< VC > *log)
	Removes the given vc from the list.
iterator	begin ()
	Returns an iterator to the start of the list.
iterator	end ()
	Returns an iterator just past the end of the list.
const_iterator	begin () const
	Returns a constant iterator to the start of the list.
const_iterator	end () const
	Returns a constant iterator just past the end of the list.

Detailed Description

Sorted list of VCs.

The list is sorted by VC carrier size. When VCs are added, only VCs that are not duplicates or supersets of existing VCs in the list are considered; any elements currently in the list that are supersets of the new vc are removed. This means an add operation will run in linear time.

The soft limit is the number of vcs used in vc calculations. VCs that appear after the soft limit are not considered in vc calculations, but may be later on if some vcs are removed. The idea is to keep around extra vcs that may be important later, but not at the expense of slower vc calculations now.

Definition at line 30 of file VCList.hpp.

Member Typedef Documentation

typedef std::list<VC>::const_iterator VCList::const_iterator

Definition at line 136 of file VCList.hpp.

typedef std::list<VC>::iterator VCList::iterator

Definition at line 134 of file VCList.hpp.

Member Enumeration Documentation

enum VCList::AddResult

Return type for add() methods.

Enumerator:

ADD_FAILED	Add did not succeed, list is unchanged.
ADDED_INSIDE_SOFT_LIMIT	Added connection within the soft limit.
ADDED_INSIDE_HARD_LIMIT	Add connection within the hard limit.

Definition at line 82 of file VCList.hpp.

Constructor & Destructor Documentation

VCList::VCList	(	HexPoint	x,
		HexPoint	y,
		unsigned int	soft
	)

Creates a list with given limits.

Definition at line 13 of file VCList.cpp.

References m_hard_intersection, m_soft_intersection, and benzene_bitset< _Nb >::set().

Member Function Documentation

int VCList::add	(	const VCList &	other,
		ChangeLog< VC > *	log
	)

Adds the elements of other to list.

Returns number of vcs added. Vcs are added as unprocessed. Operations will be recorded in the log if log is not 0.

Definition at line 144 of file VCList.cpp.

References add(), begin(), end(), getX(), and getY().

VCList::AddResult VCList::add	(	const VC &	vc,
		ChangeLog< VC > *	log
	)

Adds vc to the list.

Requires a single pass over the entire list. The add will fail if vc is a superset of some vc already in the list. Supersets of this vc that are already in the list are removed.

Operations will be recorded in the log if log is not 0.

Returns:: true if the VC was added, false otherwise.

Definition at line 102 of file VCList.cpp.

References ADD_FAILED, ADDED_INSIDE_HARD_LIMIT, ADDED_INSIDE_SOFT_LIMIT, VC::carrier(), dirty_list_unions(), getX(), getY(), HexAssert, VC::isSubsetOf(), m_hard_intersection, m_soft_intersection, m_softlimit, m_vcs, ChangeLog< T >::push(), VC::x(), and VC::y().

Referenced by VCSet::Add(), add(), VCBuilder::AddNewSemi(), VCBuilder::MergeAndShrink(), VCBuilder::OrRule::operator()(), and VCBuilder::ProcessSemis().

VCList::const_iterator VCList::begin ( ) const [inline]

Returns a constant iterator to the start of the list.

Definition at line 320 of file VCList.hpp.

References m_vcs.

VCList::iterator VCList::begin ( ) [inline]

Returns an iterator to the start of the list.

Definition at line 310 of file VCList.hpp.

References m_vcs.

Referenced by add(), VCBuilder::doAnd(), find(), operator!=(), VCBuilder::OrRule::operator()(), operator==(), VCBuilder::ProcessFulls(), VCBuilder::ProcessSemis(), VCSet::SmallestVC(), and VCSet::VCs().

void VCList::clear ( ) [inline]

Empties the list and the changelog.

Definition at line 299 of file VCList.hpp.

References dirty_list_unions(), m_dirty_intersection, m_hard_intersection, m_soft_intersection, m_vcs, and benzene_bitset< _Nb >::set().

Referenced by VCSet::Clear().

void VCList::computeIntersections ( ) const [protected]

Computes list intersections in one pass: soft and hard.

Definition at line 255 of file VCList.cpp.

References end(), m_dirty_intersection, m_hard_intersection, m_soft_intersection, m_vcs, benzene_bitset< _Nb >::set(), and softlimit().

Referenced by hardIntersection(), and softIntersection().

void VCList::computeUnions ( ) const [protected]

Computes list unions in one pass: normal and greedy.

Definition at line 217 of file VCList.cpp.

References end(), m_dirty_union, m_greedy_union, m_union, m_vcs, benzene_bitset< _Nb >::reset(), and benzene_bitset< _Nb >::set().

Referenced by getGreedyUnion(), and getUnion().

void VCList::dirty_list_intersections ( ) [inline, protected]

Invalidates the list intersection.

Definition at line 294 of file VCList.hpp.

References m_dirty_intersection.

Referenced by remove(), removeAllContaining(), and removeSuperSetsOf().

void VCList::dirty_list_unions ( ) [inline, protected]

Invalidates the precomputed list unions.

Definition at line 289 of file VCList.hpp.

References m_dirty_union.

Referenced by add(), clear(), remove(), removeAllContaining(), removeSuperSetsOf(), and simple_add().

std::string VCList::dump ( ) const

Dumps the contents of this list to a string.

Definition at line 26 of file VCList.cpp.

References end(), and m_vcs.

Referenced by VCSetUtil::EqualOnGroups().

bool VCList::empty ( ) const [inline]

Returns true if the list is empty.

Definition at line 284 of file VCList.hpp.

References m_vcs.

Referenced by VCBuilder::AddNewSemi(), VCBuilder::doAnd(), VCSet::Exists(), VCBuilder::OrRule::operator()(), and VCBuilder::ProcessSemis().

VCList::const_iterator VCList::end ( ) const [inline]

Returns a constant iterator just past the end of the list.

Definition at line 325 of file VCList.hpp.

References m_vcs.

VCList::iterator VCList::end ( ) [inline]

Returns an iterator just past the end of the list.

Definition at line 315 of file VCList.hpp.

References m_vcs.

Referenced by add(), computeIntersections(), computeUnions(), VCBuilder::doAnd(), dump(), find(), operator!=(), VCBuilder::OrRule::operator()(), operator==(), VCBuilder::ProcessFulls(), VCBuilder::ProcessSemis(), remove(), VCSet::Revert(), and VCSet::VCs().

VCList::const_iterator VCList::find	(	const VC &	vc,
		const const_iterator &	b,
		const const_iterator &	e
	)			const

Definition at line 181 of file VCList.cpp.

VCList::const_iterator VCList::find ( const VC & vc ) const

Returns a constant iterator to the given VC, or end() if vc is not in the list.

Definition at line 193 of file VCList.cpp.

References begin(), end(), and find().

VCList::iterator VCList::find	(	const VC &	vc,
		const iterator &	b,
		const iterator &	e
	)

Definition at line 198 of file VCList.cpp.

VCList::iterator VCList::find ( const VC & vc )

Returns an iterator to the given VC, or end() if vc is not in the list.

Note that these methods are not constant, but as long as VCs are immutable (except for their processed flags) then the list cannot be altered by these methods.

Definition at line 210 of file VCList.cpp.

References begin(), and end().

Referenced by find(), remove(), and VCSet::Revert().

bitset_t VCList::getGreedyUnion ( ) const

Returns the union of all carriers in the list.

Only includes carriers of VCs in the union if they shrink the intersection at each step (considered in the sorted order).

Note:: Doing this may result in different sets of connections depending upon the relative order of the vcs in the list. So, on an empty board, BLACK can have a slightly different connection set that WHITE. Can also result in different vc connections between non-rotated and rotated versions of the board.

Definition at line 245 of file VCList.cpp.

References computeUnions(), m_dirty_union, and m_greedy_union.

Referenced by VCBuilder::AddNewSemi(), VCCommands::CmdVCUnion(), ProofUtil::InitialProofForOpponent(), and VCBuilder::ProcessSemis().

bitset_t VCList::getUnion ( ) const

Returns the union of all carriers in the list.

Definition at line 237 of file VCList.cpp.

References computeUnions(), m_dirty_union, and m_union.

Referenced by VCBuilder::AddNewSemi(), ProofUtil::InitialProofForOpponent(), VCBuilder::ProcessSemis(), and removeAllContaining().

HexPoint VCList::getX ( ) const [inline]

Definition at line 253 of file VCList.hpp.

References m_x.

Referenced by add(), VCBuilder::AddNewSemi(), VCBuilder::OrRule::operator()(), and simple_add().

HexPoint VCList::getY ( ) const [inline]

Definition at line 258 of file VCList.hpp.

References m_y.

Referenced by add(), VCBuilder::AddNewSemi(), VCBuilder::OrRule::operator()(), and simple_add().

bitset_t VCList::hardIntersection ( ) const

Returns hard-limit intersection.

If list is empty, the bitset will have all of its bits set.

Definition at line 282 of file VCList.cpp.

References computeIntersections(), m_dirty_intersection, and m_hard_intersection.

Referenced by VCBuilder::AddNewSemi(), VCCommands::CmdVCIntersection(), VCUtils::GetMustplay(), and VCBuilder::ProcessSemis().

bool VCList::isSubsetOfAny ( const bitset_t & vc ) const

Returns true if vc is subset of connection in list.

Definition at line 49 of file VCList.cpp.

References BitsetUtil::IsSubsetOf(), and m_vcs.

bool VCList::isSupersetOfAny ( const bitset_t & vc ) const

Returns true if bs is superset of connection in list.

Definition at line 41 of file VCList.cpp.

References BitsetUtil::IsSubsetOf(), and m_vcs.

Referenced by VCBuilder::AddNewSemi().

bool VCList::operator!= ( const VCList & other ) const

Performs list inequality.

Definition at line 385 of file VCList.cpp.

References begin(), end(), and size().

bool VCList::operator== ( const VCList & other ) const

Performs list equality.

Definition at line 367 of file VCList.cpp.

References begin(), end(), m_softlimit, and size().

bool VCList::remove	(	const VC &	vc,
		ChangeLog< VC > *	log
	)

Removes the given vc from the list.

Does nothing if vc is not actually in the list. Takes O(n) time. Returns true if vc was actually removed, false otherwise.

Definition at line 169 of file VCList.cpp.

References end(), and find().

VCList::iterator VCList::remove	(	iterator	i,
		ChangeLog< VC > *	log
	)

Removes the element pointed to by i from the list.

Returns:: the next element.

Definition at line 159 of file VCList.cpp.

References dirty_list_intersections(), dirty_list_unions(), m_vcs, and ChangeLog< T >::push().

Referenced by VCSet::Revert().

int VCList::removeAllContaining	(	const bitset_t &	b,
		ChangeLog< VC > *	log
	)

Definition at line 342 of file VCList.cpp.

References dirty_list_intersections(), dirty_list_unions(), getUnion(), m_vcs, and ChangeLog< T >::push().

int VCList::removeAllContaining	(	const bitset_t &	b,
		std::list< VC > &	out,
		ChangeLog< VC > *	log
	)

Definition at line 317 of file VCList.cpp.

References dirty_list_intersections(), dirty_list_unions(), getUnion(), m_vcs, and ChangeLog< T >::push().

int VCList::removeAllContaining	(	HexPoint	cell,
		std::list< VC > &	out,
		ChangeLog< VC > *	log
	)

Removes all VCs that intersect with b.

Removed VCs are appended to out if out---note that the order of the vcs in out is the same as it was in the original list! Returns number of vcs removed.

Definition at line 292 of file VCList.cpp.

References dirty_list_intersections(), dirty_list_unions(), getUnion(), m_vcs, and ChangeLog< T >::push().

Referenced by VCBuilder::MergeAndShrink(), and VCBuilder::RemoveAllContaining().

int VCList::removeSuperSetsOf	(	const bitset_t &	vc,
		ChangeLog< VC > *	log,
		bool	dirty_intersections = `true`
	)

Removes any connection whose carrier is a superset of the given VC's carrier.

Returns number of connections removed. Does not dirty intersections if flag is set to false; only use this if you are for sure only removing supersets of a member of this list!

Definition at line 57 of file VCList.cpp.

References dirty_list_intersections(), dirty_list_unions(), BitsetUtil::IsSubsetOf(), m_vcs, and ChangeLog< T >::push().

Referenced by VCBuilder::MergeAndShrink().

void VCList::setSoftLimit ( int limit ) [inline]

See softlimit().

Definition at line 268 of file VCList.hpp.

References m_dirty_intersection, and m_softlimit.

void VCList::simple_add ( const VC & vc )

Force the addition of this vc.

Used by VCSet::revert():

1) add(vc) can cause a superset to vc to be removed. 2) this superset is then added to the log 3) when reverting the log, we try to add the superset, but the add fails because vc is still in it. 4) Ooops!

This method does NO checks. It simply adds vc into the proper position according to the ordering on the vcs.

Definition at line 83 of file VCList.cpp.

References VC::carrier(), dirty_list_unions(), getX(), getY(), HexAssert, m_hard_intersection, m_soft_intersection, m_softlimit, m_vcs, VC::x(), and VC::y().