/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

/*

 * Copyright 2007 University of Washington

 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada

 * 

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License version 2 as

 * published by the Free Software Foundation;

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 * Authors:  Tom Henderson (tomhend@u.washington.edu)

 * 

 * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors

 * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here

 */

#include <utility>

#include <vector>

#include <queue>

#include <algorithm>

#include <iostream>

#include "ns3/assert.h"

#include "ns3/fatal-error.h"

#include "ns3/log.h"

#include "ns3/node-list.h"

#include "ns3/ipv4.h"

#include "ns3/ipv4-routing-protocol.h"

#include "ns3/ipv4-list-routing.h"

#include "ns3/mpi-interface.h"

#include "global-router-interface.h"

#include "global-route-manager-impl.h"

#include "candidate-queue.h"

#include "ipv4-global-routing.h"

NS_LOG_COMPONENT_DEFINE ("GlobalRouteManagerImpl");

namespace ns3 {

/**

 * \brief Stream insertion operator.

 *

 * \param os the reference to the output stream

 * \param exit the exit node

 * \returns the reference to the output stream

 */

std::ostream& 

operator<< (std::ostream& os, const SPFVertex::NodeExit_t& exit)

{

  os << "(" << exit.first << " ," << exit.second << ")";

  return os;

}

std::ostream& 

operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs)

{

  typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t;

  os << "{";

  for (CIter_t iter = vs.begin (); iter != vs.end ();)

    {

      os << (*iter)->m_vertexId;

      if (++iter != vs.end ()) 

        {

          os << ", ";

        }

      else 

        { 

          break;

        }

    }

  os << "}";

  return os;

}

// ---------------------------------------------------------------------------

//

// SPFVertex Implementation

//

// ---------------------------------------------------------------------------

SPFVertex::SPFVertex () : 

  m_vertexType (VertexUnknown), 

  m_vertexId ("255.255.255.255"), 

  m_lsa (0),

  m_distanceFromRoot (SPF_INFINITY), 

  m_rootOif (SPF_INFINITY),

  m_nextHop ("0.0.0.0"),

  m_parents (),

  m_children (),

  m_vertexProcessed (false)

{

  NS_LOG_FUNCTION (this);

}

SPFVertex::SPFVertex (GlobalRoutingLSA* lsa) : 

  m_vertexId (lsa->GetLinkStateId ()),

  m_lsa (lsa),

  m_distanceFromRoot (SPF_INFINITY), 

  m_rootOif (SPF_INFINITY),

  m_nextHop ("0.0.0.0"),

  m_parents (),

  m_children (),

  m_vertexProcessed (false)

{

  NS_LOG_FUNCTION (this << lsa);

  if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) 

    {

      NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter");

      m_vertexType = SPFVertex::VertexRouter;

    }

  else if (lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA) 

    { 

      NS_LOG_LOGIC ("Setting m_vertexType to VertexNetwork");

      m_vertexType = SPFVertex::VertexNetwork;

    }

}

SPFVertex::~SPFVertex ()

{

  NS_LOG_FUNCTION (this);

  NS_LOG_LOGIC ("Children vertices - " << m_children);

  NS_LOG_LOGIC ("Parent verteices - " << m_parents);

  // find this node from all its parents and remove the entry of this node

  // from all its parents

  for (ListOfSPFVertex_t::iterator piter = m_parents.begin (); 

       piter != m_parents.end ();

       piter++)

    {

      // remove the current vertex from its parent's children list. Check

      // if the size of the list is reduced, or the child<->parent relation

      // is not bidirectional

      uint32_t orgCount = (*piter)->m_children.size ();

      (*piter)->m_children.remove (this);

      uint32_t newCount = (*piter)->m_children.size ();

      if (orgCount > newCount)

        {

          NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!");

        }

    }

  // delete children

  while (m_children.size () > 0)

    {

      // pop out children one by one. Some children may disapper 

      // when deleting some other children in the list. As a result,

      // it is necessary to use pop to walk through all children, instead

      // of using iterator.

      //

      // Note that m_children.pop_front () is not necessary as this

      // p is removed from the children list when p is deleted

      SPFVertex* p = m_children.front ();

      // 'p' == 0, this child is already deleted by its other parent

      if (p == 0) continue;

      NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ());

      delete p;

      p = 0;

    }

  m_children.clear ();

  // delete parents

  m_parents.clear ();

  // delete root exit direction

  m_ecmpRootExits.clear ();

  NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted");

}

void

SPFVertex::SetVertexType (SPFVertex::VertexType type)

{

  NS_LOG_FUNCTION (this << type);

  m_vertexType = type;

}

SPFVertex::VertexType

SPFVertex::GetVertexType (void) const

{

  NS_LOG_FUNCTION (this);

  return m_vertexType;

}

void

SPFVertex::SetVertexId (Ipv4Address id)

{

  NS_LOG_FUNCTION (this << id);

  m_vertexId = id;

}

Ipv4Address

SPFVertex::GetVertexId (void) const

{

  NS_LOG_FUNCTION (this);

  return m_vertexId;

}

void

SPFVertex::SetLSA (GlobalRoutingLSA* lsa)

{

  NS_LOG_FUNCTION (this << lsa);

  m_lsa = lsa;

}

GlobalRoutingLSA*

SPFVertex::GetLSA (void) const

{

  NS_LOG_FUNCTION (this);

  return m_lsa;

}

void

SPFVertex::SetDistanceFromRoot (uint32_t distance)

{

  NS_LOG_FUNCTION (this << distance);

  m_distanceFromRoot = distance;

}

uint32_t

SPFVertex::GetDistanceFromRoot (void) const

{

  NS_LOG_FUNCTION (this);

  return m_distanceFromRoot;

}

void

SPFVertex::SetParent (SPFVertex* parent)

{

  NS_LOG_FUNCTION (this << parent);

  // always maintain only one parent when using setter/getter methods

  m_parents.clear ();

  m_parents.push_back (parent);

}

SPFVertex*

SPFVertex::GetParent (uint32_t i) const

{

  NS_LOG_FUNCTION (this << i);

  // If the index i is out-of-range, return 0 and do nothing

  if (m_parents.size () <= i)

    {

      NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range.");

      return 0;

    }

  ListOfSPFVertex_t::const_iterator iter = m_parents.begin ();

  while (i-- > 0) 

    {

      iter++;

    }

  return *iter;

}

void 

SPFVertex::MergeParent (const SPFVertex* v)

{

  NS_LOG_FUNCTION (this << v);

  NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents);

  // combine the two lists first, and then remove any duplicated after

  m_parents.insert (m_parents.end (), 

                    v->m_parents.begin (), v->m_parents.end ());

  // remove duplication

  m_parents.sort ();

  m_parents.unique ();

  NS_LOG_LOGIC ("After merge, list of parents = " << m_parents);

}

void 

SPFVertex::SetRootExitDirection (Ipv4Address nextHop, int32_t id)

{

  NS_LOG_FUNCTION (this << nextHop << id);

  // always maintain only one root's exit

  m_ecmpRootExits.clear ();

  m_ecmpRootExits.push_back (NodeExit_t (nextHop, id));

  // update the following in order to be backward compatitable with

  // GetNextHop and GetOutgoingInterface methods

  m_nextHop = nextHop;

  m_rootOif = id;

}

void 

SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit)

{

  NS_LOG_FUNCTION (this << exit);

  SetRootExitDirection (exit.first, exit.second);

}

SPFVertex::NodeExit_t

SPFVertex::GetRootExitDirection (uint32_t i) const

{

  NS_LOG_FUNCTION (this << i);

  typedef ListOfNodeExit_t::const_iterator CIter_t;

  NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!");

  CIter_t iter = m_ecmpRootExits.begin ();

  while (i-- > 0) { iter++; }

  return *iter;

}

SPFVertex::NodeExit_t 

SPFVertex::GetRootExitDirection () const

{

  NS_LOG_FUNCTION (this);

  NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex");

  return GetRootExitDirection (0);

}

void 

SPFVertex::MergeRootExitDirections (const SPFVertex* vertex)

{

  NS_LOG_FUNCTION (this << vertex);

  // obtain the external list of exit directions

  //

  // Append the external list into 'this' and remove duplication afterward

  const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits;

  m_ecmpRootExits.insert (m_ecmpRootExits.end (), 

                          extList.begin (), extList.end ());

  m_ecmpRootExits.sort ();

  m_ecmpRootExits.unique ();

}

void 

SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex)

{

  NS_LOG_FUNCTION (this << vertex);

  // discard all exit direction currently associated with this vertex,

  // and copy all the exit directions from the given vertex

  if (m_ecmpRootExits.size () > 0)

    {

      NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded");

    }

  m_ecmpRootExits.clear ();

  m_ecmpRootExits.insert (m_ecmpRootExits.end (), 

                          vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ());

}

uint32_t 

SPFVertex::GetNRootExitDirections () const

{

  NS_LOG_FUNCTION (this);

  return m_ecmpRootExits.size ();

}

uint32_t 

SPFVertex::GetNChildren (void) const

{

  NS_LOG_FUNCTION (this);

  return m_children.size ();

}

SPFVertex*

SPFVertex::GetChild (uint32_t n) const

{

  NS_LOG_FUNCTION (this << n);

  uint32_t j = 0;

  for ( ListOfSPFVertex_t::const_iterator i = m_children.begin ();

        i != m_children.end ();

        i++, j++)

    {

      if (j == n)

        {

          return *i;

        }

    }

  NS_ASSERT_MSG (false, "Index <n> out of range.");

  return 0;

}

uint32_t

SPFVertex::AddChild (SPFVertex* child)

{

  NS_LOG_FUNCTION (this << child);

  m_children.push_back (child);

  return m_children.size ();

}

void 

SPFVertex::SetVertexProcessed (bool value)

{

  NS_LOG_FUNCTION (this << value);

  m_vertexProcessed = value;

}

bool 

SPFVertex::IsVertexProcessed (void) const

{

  NS_LOG_FUNCTION (this);

  return m_vertexProcessed;

}

void

SPFVertex::ClearVertexProcessed (void)

{

  NS_LOG_FUNCTION (this);

  for (uint32_t i = 0; i < this->GetNChildren (); i++)

    {

      this->GetChild (i)->ClearVertexProcessed ();

    }

  this->SetVertexProcessed (false);

}

// ---------------------------------------------------------------------------

//

// GlobalRouteManagerLSDB Implementation

//

// ---------------------------------------------------------------------------

GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()

  :

    m_database (),

    m_extdatabase ()

{

  NS_LOG_FUNCTION (this);

}

GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()

{

  NS_LOG_FUNCTION (this);

  LSDBMap_t::iterator i;

  for (i= m_database.begin (); i!= m_database.end (); i++)

    {

      NS_LOG_LOGIC ("free LSA");

      GlobalRoutingLSA* temp = i->second;

      delete temp;

    }

  for (uint32_t j = 0; j < m_extdatabase.size (); j++)

    {

      NS_LOG_LOGIC ("free ASexternalLSA");

      GlobalRoutingLSA* temp = m_extdatabase.at (j);

      delete temp;

    }

  NS_LOG_LOGIC ("clear map");

  m_database.clear ();

}

void

GlobalRouteManagerLSDB::Initialize ()

{

  NS_LOG_FUNCTION (this);

  LSDBMap_t::iterator i;

  for (i= m_database.begin (); i!= m_database.end (); i++)

    {

      GlobalRoutingLSA* temp = i->second;

      temp->SetStatus (GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED);

    }

}

void

GlobalRouteManagerLSDB::Insert (Ipv4Address addr, GlobalRoutingLSA* lsa)

{

  NS_LOG_FUNCTION (this << addr << lsa);

  if (lsa->GetLSType () == GlobalRoutingLSA::ASExternalLSAs) 

    {

      m_extdatabase.push_back (lsa);

    } 

  else

    {

      m_database.insert (LSDBPair_t (addr, lsa));

    }

}

GlobalRoutingLSA*

GlobalRouteManagerLSDB::GetExtLSA (uint32_t index) const

{

  NS_LOG_FUNCTION (this << index);

  return m_extdatabase.at (index);

}

uint32_t

GlobalRouteManagerLSDB::GetNumExtLSAs () const

{

  NS_LOG_FUNCTION (this);

  return m_extdatabase.size ();

}

GlobalRoutingLSA*

GlobalRouteManagerLSDB::GetLSA (Ipv4Address addr) const

{

  NS_LOG_FUNCTION (this << addr);

//