/*
 * Copyright (C) 2008-2012 Delft University of Technology - All rights reserved.
 *
 * Author: Reijer Idema
 */

/*
 * Power System Branch Adjacency List source.
 */
#include <deque>					// USES deque (IsConnected())
#include "AdjacencyList.h"

POWERSYSTEM_NAMESPACE_BEGIN

/////////////////////////////// PUBLIC ///////////////////////////////////////

//============================= LIFECYCLE ====================================

AdjacencyList::AdjacencyList(void) : mConnections() { }

//============================= OPERATIONS ===================================

void AdjacencyList::Clear(void)
{
	mConnections.clear();
} // AdjacencyList::Clear

bool AdjacencyList::IsEmpty(void)
{
	return mConnections.empty();
} // AdjacencyList::IsEmpty

void AdjacencyList::Initialize(BusIndexType busCount)
{
	Clear();
	mConnections.resize(busCount);
} // AdjacencyList::Initialize

void AdjacencyList::AddBranch(BusIndexType i, BusIndexType j)
{
	if (mConnections.empty()) return;

	// :TODO: range checking?
	std::multiset<BusIndexType>::const_iterator it;
//	it = --(mConnections[i].end());
	mConnections[i].insert(j);
//	it = --(mConnections[j].end());
	mConnections[j].insert(i);
} // AdjacencyList::AddConnection

void AdjacencyList::RemoveBranch(BusIndexType i, BusIndexType j)
{
	if (mConnections.empty()) return;

	// :TODO: range checking?
	std::multiset<BusIndexType>::const_iterator it;
	it = mConnections[i].find(j);
	mConnections[i].erase(it);
	it = mConnections[j].find(i);
	mConnections[j].erase(it);
} // AdjacencyList::AddConnection

bool AdjacencyList::IsConnected(BusIndexType i, BusIndexType j)
{
	if (mConnections.empty()) false;
	// :TODO: range checking?

	// Vector of booleans that are set true if the bus of that index is found to be connected to bus i.
	std::vector<bool> isConnected(mConnections.size(), false);
	isConnected[i] = true;			// Initial node is part of the connected (sub)graph

	// Queue of nodes of which to follow the connections.
	std::deque<BusIndexType> nodeQueue;
	nodeQueue.push_back(i);			// Add initial node to the queue

	BusIndexType node;
	std::multiset<BusIndexType>::const_iterator connIt, connItEnd;
	while (!nodeQueue.empty())
	{
		node = nodeQueue.front();				// Process first node in queue
		connIt = mConnections[node].begin();
		connItEnd = mConnections[node].end();
		while (connIt != connItEnd)
		{
			if (*connIt == j) return true;		// Found path from i to j

			if (!isConnected[*connIt])			// Found a new node connected to i
			{
				isConnected[*connIt] = true;	// Set new node to be connected
				nodeQueue.push_back(*connIt);	// Add new node to queue
			}
			++connIt;
		}
		nodeQueue.pop_front();					// Remove the processed node from queue
	}

	return false;
} // AdjacencyList::IsConnected

//============================= ACCESS     ===================================

POWERSYSTEM_NAMESPACE_END
