//
// Copyright (C) 2006 Institut fuer Telematik, Universitaet Karlsruhe (TH)
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// 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.
//

/**
 * @file MyChordFingerTable.cc
 * @author Markus Mauch, Ingmar Baumgart, Dilum Bandara
 * @version 0.1
 * @date 07/06/2010
 */

#include <cfloat>
#include "hashWatch.h"
#include "MyChord.h"
#include "MyChordSuccessorList.h"
#include "MyChordFingerTable.h"

namespace oversim {

Define_Module(MyChordFingerTable);

void MyChordFingerTable::initialize(int stage)
{
    // because of IPAddressResolver, we need to wait until interfaces
    // are registered, address auto-assignment takes place etc.
    if(stage != MIN_STAGE_OVERLAY)
        return;

    maxSize = 0;
    WATCH_DEQUE(fingerTable);
}


void MyChordFingerTable::handleMessage(cMessage* msg)
{
    error("this module doesn't handle messages, it runs only in initialize()");
}


void MyChordFingerTable::initializeTable(uint32_t size, const NodeHandle& owner,
                                       MyChord* overlay)
{
    maxSize = size;
    this->overlay = overlay;
    fingerTable.clear();
}


uint32_t MyChordFingerTable::getSize()
{
    return maxSize;
}


void MyChordFingerTable::setFinger(uint32_t pos, const NodeHandle& node,
                                 MySuccessors const* sucNodes)
{
    if (pos >= maxSize) {
        throw new cRuntimeError("MyChordFingerTable::setFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;
    MySuccessors tempSuccessors;

    while (fingerTable.size() <= p) 
	{
        fingerTable.push_back(MyFingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                          tempSuccessors));
    }

    if (sucNodes != NULL)
        fingerTable[p] = MyFingerEntry(node, *sucNodes);
    else
        fingerTable[p] = MyFingerEntry(node, tempSuccessors);
}


void MyChordFingerTable::setFinger(uint32_t pos, const MySuccessors& nodes)
{
    setFinger(pos, nodes.begin()->second.nodeHandle, &nodes);
}


void MyChordFingerTable::setAddtionalFinger(uint32_t pos, simtime_t rtt, const MySuccessorEntry& entry)
{
    if (pos >= maxSize) {
        throw new cRuntimeError("MyChordFingerTable::setFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;
    MySuccessors tempSuccessors;

    while (fingerTable.size() <= p) 
	{
        fingerTable.push_back(MyFingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                          tempSuccessors));
    }

	//TODO enable following line if fingertable size should be fixed. Else enable remining lines
	tempSuccessors.insert(std::make_pair(rtt, entry));
	setFinger(pos, entry.nodeHandle, &tempSuccessors);
	//MyFingerEntry tmpEntry = fingerTable[p];
	////MySuccessors tmpSuccessor = tmpEntry.second;
	//tmpEntry.second.insert(std::make_pair(rtt, entry));	// Add new one
    //fingerTable[p] = tmpEntry;
}


bool MyChordFingerTable::updateFinger(uint32_t pos, const NodeHandle& node,
                                    simtime_t rtt, int id)
{
    if (rtt < 0)
        return false;

    if (pos >= maxSize)
	{
         throw new cRuntimeError("MyChordFingerTable::updateFinger(): "
                                 "Index out of bound");
     }

    uint32_t p = maxSize - pos - 1;

    while (fingerTable.size() <= p) 
	{
        MySuccessors tempSuccessors;
        fingerTable.push_back(MyFingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                          tempSuccessors));
    }

	//For each successor    
	MySuccessors::iterator it;
    for (it = fingerTable[p].second.begin(); it != fingerTable[p].second.end(); it++) 
	{
        if (it->second.nodeHandle == node)
            break;
    }

    if (it == fingerTable[p].second.end())	//If entry is not found
        return false;

    fingerTable[p].second.erase(it);
	MySuccessorEntry tmpEntry;
	tmpEntry.nodeHandle = node;
	tmpEntry.groupId = id;
    fingerTable[p].second.insert(std::make_pair(rtt, tmpEntry));

    return true;
}


bool MyChordFingerTable::handleFailedNode(const TransportAddress& failed)
{
    bool ret = false;
    for (int p = fingerTable.size() - 1; p >= 0; p--) 
	{
        if (!fingerTable[p].first.isUnspecified() &&
            failed == fingerTable[p].first) 
		{
            //No longer available
			fingerTable[p].first = NodeHandle::UNSPECIFIED_NODE;
            ret = true;
        }
        //std::multimap<simtime_t, NodeHandle>::iterator it;
        std::multimap<simtime_t, MySuccessorEntry>::iterator it;
        for (it = fingerTable[p].second.begin(); it != fingerTable[p].second.end(); ++it) 
		{
            if (failed == it->second.nodeHandle) 
			{
                fingerTable[p].second.erase(it);
                break;
            }
        }
    }

    return ret;
}


void MyChordFingerTable::removeFinger(uint32_t pos)
{
    if (pos >= maxSize) 
	{
        throw new cRuntimeError("MyChordFingerTable::removeFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;
    if (p >= fingerTable.size())	//Out of bound
        return;
    else if (p == (fingerTable.size() - 1)) //remove last entry
        fingerTable.pop_back();
    else
	{
        MySuccessors tempSuccessors;
        fingerTable[p] = MyFingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                     tempSuccessors);
    }
}

//TODO double check whether we need to modify this function
const NodeHandle& MyChordFingerTable::getFinger(uint32_t pos)
{
    if (pos >= maxSize) 
	{
        throw new cRuntimeError("MyChordFingerTable::getFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;
    if (p >= fingerTable.size())
        return overlay->successorList->getSuccessor().nodeHandle;

    while (fingerTable[p].first.isUnspecified() && (p < (fingerTable.size() - 1)))
        ++p;

    if (fingerTable[p].first.isUnspecified())	//If we don't have an entry go to my successor
        return overlay->successorList->getSuccessor().nodeHandle;
    return fingerTable[p].first;
}


MySuccessorEntryVector* MyChordFingerTable::getFinger(uint32_t pos, const OverlayKey& key,
														int id, bool givePriorityToGroup,
														const OverlayKey& baseKey)
{
    if (pos >= maxSize) {
        throw new cRuntimeError("MyChordFingerTable::getFinger(): "
                                "Index out of bound");
    }
	if(givePriorityToGroup && (id == -1))
	{
        throw new cRuntimeError("MyChordFingerTable::getFinger(): "
                                "There has to be a groupID if giving priority to group");
	}

    MySuccessorEntryVector* nextHop = new MySuccessorEntryVector();
	MySuccessorEntry tmpEntry;

    uint32_t p = maxSize - pos - 1;

	//If we have a position & no priority is given to group
    if((p < fingerTable.size()) && !givePriorityToGroup)
	{
        MySuccessors::const_iterator it;
        for (it = fingerTable[p].second.begin(); it != fingerTable[p].second.end(); it++) 
		{
			//Make sure not to over or under shoot
            if(!key.isBetweenLR(fingerTable[p].first.getKey(), it->second.nodeHandle.getKey()))
			{
				if(id != -1)	//If group ID is given, we should match to it
				{
					if(it->second.groupId == id)
    	            	nextHop->push_back(it->second);
				}
				else	//Group ID doesn't matter
    	            nextHop->push_back(it->second);
        	}
		}

		//Suppose to use group ID, but couldn't find a finger for the group. Retry without group Id
		if((id != -1) && (nextHop->size() == 0)) 
		{
        	for (MySuccessors::const_iterator it = fingerTable[p].second.begin();
            	 it != fingerTable[p].second.end(); it++) 
			{
				if(!key.isBetweenLR(fingerTable[p].first.getKey(), it->second.nodeHandle.getKey()))
					nextHop->push_back(it->second);
			}
		}
    }
	else if((p < fingerTable.size()) && givePriorityToGroup)	//Give priority to group regardless of finger position
	{
		MySuccessors::const_iterator it;
		for (it = fingerTable[p].second.begin(); it != fingerTable[p].second.end(); it++)
		{
			//Make sure not to over or under shoot 
			if(!key.isBetweenLR(fingerTable[p].first.getKey(), it->second.nodeHandle.getKey()))
			{
				if(it->second.groupId == id)
					nextHop->push_back(it->second);
			}
		}

	/*
		for (unsigned int i = 0 ; i < fingerTable.size(); i++)	//For each finger position
    	{
		    if (fingerTable[i].first.isUnspecified())
				continue;
			else
			{
				//For each list of finger entires for position i
        		MySuccessors::const_iterator it;
		        for (it = fingerTable[i].second.begin(); it != fingerTable[i].second.end(); it++)
				{
					//Should be in range & group ID should match
					if(it->second.nodeHandle.getKey().isBetweenLR(baseKey, key)
						&& it->second.groupId == id)
					{
						nextHop->push_back(it->second);
					}
				}
			}
		}
	*/
		//Suppose to use group ID, but couldn't find a finger for the group. Retry without group Id
		if((id != -1) && (nextHop->size() == 0)) 
		{
        	for (MySuccessors::const_iterator it = fingerTable[p].second.begin();
            	 it != fingerTable[p].second.end(); it++) 
			{
				if(!key.isBetweenLR(fingerTable[p].first.getKey(), it->second.nodeHandle.getKey()))
					nextHop->push_back(it->second);
			}
		}
	}
	else //Can't find send to successor
	{
        tmpEntry.nodeHandle = overlay->successorList->getSuccessor().nodeHandle;
		tmpEntry.groupId = -1;	//Don't care, no choice
		nextHop->push_back(tmpEntry);
        return nextHop;
    }

    if (nextHop->size() == 0) 
	{
        if (fingerTable[p].first.isUnspecified()) 
            //TODO use other finger
            tmpEntry.nodeHandle = overlay->successorList->getSuccessor().nodeHandle;
		else
            tmpEntry.nodeHandle = fingerTable[p].first;

		tmpEntry.groupId = -1;
		nextHop->push_back(tmpEntry);
    }

    return nextHop;
}


NodeVector* MyChordFingerTable::getMembersFromFingerTable(const OverlayKey& base,
														const OverlayKey& limit, int groupId)
{
	NodeVector* members = new NodeVector();

	for (unsigned int i = 0 ; i < fingerTable.size(); i++)  //For each finger position
	{
		if (fingerTable[i].first.isUnspecified())
			continue;
		else
		{
			//For each list of finger entires for position i
			MySuccessors::const_iterator it;
			for (it = fingerTable[i].second.begin(); it != fingerTable[i].second.end(); it++)
			{
				//Should be in range & group ID should match
				if(it->second.nodeHandle.getKey().isBetween(base, limit)
								&& it->second.groupId == groupId)
				{
					//Make sure not to send same node several times
					unsigned int k;
					for(k = 0; k < members->size(); k++)
					{
						if( (*members)[k].getKey() == it->second.nodeHandle.getKey())
							break;
					}
					if(k == members->size())
						members->push_back(it->second.nodeHandle);
				}
			}
		}
	}

	//Sort so that largest key is first
	if(members->size() > 0)
	{
		bool swap = true;
		OverlayKey halfKey = OverlayKey("8000000000000000000000000000000000000000");
		while(swap)
		{
			swap = false;
			for(unsigned int i = 0; i < members->size() - 1; i++)
			{
				if( (*members)[i + 1] > (*members)[i])
				{
					if (( (*members)[i + 1].getKey() - (*members)[i].getKey() )  < halfKey)
					{
						NodeHandle tmp = (*members)[i];
						(*members)[i] = (*members)[i + 1];
						(*members)[i + 1] = tmp;
						swap= true;
					}
				}
				else
				{
					if (( (*members)[i].getKey() - (*members)[i + 1].getKey() )  > halfKey)
					{
						NodeHandle tmp = (*members)[i];
						(*members)[i] = (*members)[i + 1];
						(*members)[i + 1] = tmp;
						swap= true;
					}
				}
			}
		}
	}
    return members;
}

}; //namespace

using namespace oversim;

std::ostream& operator<<(std::ostream& os, const MySuccessors& suc)
{
    for (MySuccessors::const_iterator i = suc.begin(); i != suc.end(); i++) {
        if (i != suc.begin()) {
            os << endl;
        }

        os << i->second.nodeHandle;

        if (i->first == -1) {
            continue;
        } else if (i->first == MAXTIME) {
            os << "; RTT:  --- ";
        } else {
            os << "; RTT: " << i->first;
        }
    }

    return os;
}

std::ostream& operator<<(std::ostream& os, const MyFingerEntry& entry)
{
    if (entry.second.size() > 0) {
        os << "[ " << entry.first << " ]\n" << entry.second;
    } else {
        os << entry.first;
    }

    return os;
}
