// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity >0.8.0;

import '@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol';
import '../interfaces/IMajorCandidates.sol';

/// @dev MajorCandidates contract
/// @author Alexandas
contract MajorCandidates is IMajorCandidates, Initializable {
	struct Candidate {
		address prev;
		address next;
		uint256 amount;
	}

	/// @dev return `Stake` contract address
	IStake public override stake;

	/// @dev return `Election` contract address
	IElection public override election;

	/// @dev return head candidate address
	address public headCandidate;

	/// @dev return tail candidate address
	address public tailCandidate;

	/// @dev return total candidates
	uint256 public totalCandidates;

	/// @dev return candidate inforamtion
	mapping(address => Candidate) public candidates;

	/// @dev return max major candidates
	uint256 public override MAX_MAJOR_CANDIDATES;

	modifier onlyStake() {
		require(msg.sender == address(stake), 'MajorCandidates: caller must be Stake contract');
		_;
	}

	modifier onlyElection() {
		require(msg.sender == address(election), 'MajorCandidates: caller must be Election contract');
		_;
	}

	modifier validateGrades() {
		address[] memory olds = majorCandidateList();
		_;
		address[] memory news = majorCandidateList();
		address downgrade = _differOne(olds, news);
		address upgrade = _differOne(news, olds);
		if (downgrade != address(0)) {
			stake.downgrade(downgrade);
		}
		if (upgrade != address(0)) {
			stake.upgrade(upgrade);
		}
	}

	/// @dev proxy initialize function
	/// @param _stake `Stake` contract
	/// @param _election `Election` contract
	function initialize(IStake _stake, IElection _election) external initializer {
		_setStake(_stake);
		_setElection(_election);
		_setMaxMajorLength(1);
	}

	/// @dev return whether a candidate is a major candidate
	/// @param candidate candidate address
	/// @return existed the candidate is a major candidate
	function isMajor(address candidate) public view override returns (bool existed) {
		if (headCandidate != address(0)) {
			address from = headCandidate;
			for (uint256 i = 0; i < MAX_MAJOR_CANDIDATES; i++) {
				if (from == candidate) {
					existed = true;
					break;
				}
				from = candidates[from].next;
				if (from == address(0)) {
					break;
				}
			}
		}
	}

	/// @dev return all major candidates
	/// @return majors all major candidates
	function majorCandidateList() public view override returns (address[] memory majors) {
		uint256 limit = totalCandidates > MAX_MAJOR_CANDIDATES ? MAX_MAJOR_CANDIDATES : totalCandidates;
		if (headCandidate != address(0)) {
			majors = new address[](limit);
			address candidate = headCandidate;
			for (uint256 i = 0; i < limit; i++) {
				majors[i] = candidate;
				candidate = candidates[candidate].next;
				if (candidate == address(0)) {
					break;
				}
			}
		}
	}

	function _differOne(address[] memory inner, address[] memory outer) internal pure returns (address one) {
		for (uint256 i = 0; i < inner.length; i++) {
			bool _exists = false;
			for (uint256 j = 0; j < outer.length; j++) {
				if (inner[i] == outer[j]) {
					_exists = true;
					break;
				}
			}
			if (!_exists) {
				one = inner[i];
				break;
			}
		}
	}

	/// @dev insert or update a candidate in the sorted list
	/// @param candidate candidate address
	/// @param amount candidate votes
	/// @param anchor anchor candidate address
	/// @param maxSlippage maximum rank change value for the candidate from the anchor candidate
	function upsetCandidateWithAnchor(
		address candidate,
		uint256 amount,
		address anchor,
		uint256 maxSlippage
	) external override onlyElection validateGrades {
		require(candidate != address(0), 'MajorCandidates: invalid candidate');
		if (totalCandidates == 0) {
			// insert the first candidate into the list
			require(amount > 0, 'MajorCandidates: zero amount');
			totalCandidates++;
			headCandidate = candidate;
			tailCandidate = candidate;
		} else {
			if (amount == 0) {
				if (!exists(candidate)) {
					return;
				}
				return _removeCandidate(candidate);
			}
			if (!exists(anchor)) {
				if (exists(candidate)) {
					anchor = candidate;
				} else {
					anchor = tailCandidate;
				}
			}
			if (!exists(candidate)) {
				totalCandidates++;
			}
			address start = anchor;
			if (amount > candidates[start].amount) {
				for (uint256 i = 0; i < maxSlippage; i++) {
					if (start == headCandidate) {
						if (start != candidate) {
							_resetCandidate(candidate);
							candidates[candidate].prev = address(0);
							headCandidate = candidate;
							candidates[start].prev = candidate;
							candidates[candidate].next = start;
						}
						break;
					}
					address startPrev = candidates[start].prev;
					uint256 startPrevAmount = candidates[startPrev].amount;
					if (startPrevAmount > amount) {
						if (startPrev != candidate) {
							_resetCandidate(candidate);
							candidates[start].prev = candidate;
							candidates[startPrev].next = candidate;
							candidates[candidate].prev = startPrev;
							candidates[candidate].next = start;
						}
						break;
					}
					start = startPrev;
				}
			} else if (amount < candidates[start].amount) {
				for (uint256 i = 0; i < maxSlippage; i++) {
					if (start == tailCandidate) {
						if (start != candidate) {
							_resetCandidate(candidate);
							candidates[candidate].next = address(0);
							tailCandidate = candidate;
							candidates[start].next = candidate;
							candidates[candidate].prev = start;
						}
						break;
					}
					address startNext = candidates[start].next;
					uint256 startNextAmount = candidates[startNext].amount;
					if (startNextAmount < amount) {
						if (startNext != candidate) {
							_resetCandidate(candidate);
							candidates[start].next = candidate;
							candidates[startNext].prev = candidate;
							candidates[candidate].prev = start;
							candidates[candidate].next = startNext;
						}
						break;
					}
					start = startNext;
				}
			}
		}
		candidates[candidate].amount = amount;
		address prev = candidates[candidate].prev;
		address next = candidates[candidate].next;
		if (prev == address(0)) {
			require(candidate == headCandidate, 'MajorCandidates: invalid order 1');
		} else {
			require(candidates[prev].amount > amount, 'MajorCandidates: invalid order 2');
		}
		if (next == address(0)) {
			require(candidate == tailCandidate, 'MajorCandidates: invalid order 3');
		} else {
			require(candidates[next].amount < amount, 'MajorCandidates: invalid order 4');
		}
		emit UpsetCandidate(candidate, amount);
	}

	/// @dev emit removed a candidate from the sorted list
	/// @param candidate candidate address
	function remove(address candidate) external override onlyStake validateGrades {
		_removeCandidate(candidate);
	}

	function _resetCandidate(address candidate) internal {
		if (!exists(candidate)) {
			return;
		}
		if (headCandidate == candidate) {
			address candidateNext = candidates[candidate].next;
			if (candidateNext != address(0)) {
				candidates[candidateNext].prev = address(0);
				headCandidate = candidateNext;
			}
		} else if (tailCandidate == candidate) {
			address candidatePrev = candidates[candidate].prev;
			if (candidatePrev != address(0)) {
				candidates[candidatePrev].next = address(0);
			}
			tailCandidate = candidatePrev;
		} else {
			address candidatePrev = candidates[candidate].prev;
			address candidateNext = candidates[candidate].next;
			candidates[candidateNext].prev = candidatePrev;
			candidates[candidatePrev].next = candidateNext;
		}
	}

	function _removeCandidate(address candidate) internal {
		require(exists(candidate), 'MajorCandidates: nonexistent candidate');
		address curPrev = candidates[candidate].prev;
		address curNext = candidates[candidate].next;
		if (curPrev == address(0)) {
			// remove head
			if (curNext == address(0)) {
				headCandidate = address(0);
			} else {
				candidates[curNext].prev = address(0);
				headCandidate = curNext;
			}
		} else if (curNext == address(0)) {
			// remove tail
			candidates[curPrev].next = address(0);
			tailCandidate = curPrev;
		} else {
			// remove body
			candidates[curPrev].next = curNext;
			candidates[curNext].prev = curPrev;
		}
		delete candidates[candidate];
		totalCandidates--;
		if (totalCandidates == 0) {
			headCandidate = address(0);
			tailCandidate = address(0);
		}
		emit RemoveCandidate(candidate);
	}

	/// @dev return whether a candidate is existed in the sorted list
	/// @param candidate candidate address
	/// @return whether the candidate is existed in the sorted list
	function exists(address candidate) public view override returns (bool) {
		return candidates[candidate].amount > 0;
	}

	function _setStake(IStake _stake) internal {
		stake = _stake;
		emit StakeUpdated(_stake);
	}

	function _setElection(IElection _election) internal {
		election = _election;
		emit ElectionUpdated(_election);
	}

	function _setMaxMajorLength(uint256 max) internal {
		MAX_MAJOR_CANDIDATES = max;
		emit MaxMajorCandidateUpdated(max);
	}
}