contract multiowned {

	// TYPES

	// struct for the status of a pending operation.
	struct MultiOwnedOperationPendingState {
		// count of confirmations needed
		uint256 yetNeeded;

		// bitmap of confirmations where owner #ownerIndex's decision corresponds to 2**ownerIndex bit
		uint256 ownersDone;

		// position of this operation key in m_multiOwnedPendingIndex
		uint256 index;
	}

	// EVENTS

	event Confirmation(address owner, bytes32 operation);
	event Revoke(address owner, bytes32 operation);
	event FinalConfirmation(address owner, bytes32 operation);

	// some others are in the case of an owner changing.
	event OwnerChanged(address oldOwner, address newOwner);
	event OwnerAdded(address newOwner);
	event OwnerRemoved(address oldOwner);

	// the last one is emitted if the required signatures change
	event RequirementChanged(uint256 newRequirement);

	// MODIFIERS

	// simple single-sig function modifier.
	modifier onlyOwner {
		require(isOwner(msg.sender), "Auth");
		_;
	}
	// multi-sig function modifier: the operation must have an intrinsic hash in order
	// that later attempts can be realised as the same underlying operation and
	// thus count as confirmations.
	modifier onlyManyOwners(bytes32 _operation) {
		if (confirmAndCheck(_operation)) {
			_;
		}
		// Even if required number of confirmations has't been collected yet,
		// we can't throw here - because changes to the state have to be preserved.
		// But, confirmAndCheck itself will throw in case sender is not an owner.
	}

	modifier validNumOwners(uint256 _numOwners) {
		require(_numOwners > 0 && _numOwners <= c_maxOwners, "NumOwners OOR");
		_;
	}

	modifier multiOwnedValidRequirement(uint256 _required, uint256 _numOwners) {
		require(_required > 0 && _required <= _numOwners, "Req OOR");
		_;
	}

	modifier ownerExists(address _address) {
		require(isOwner(_address), "Auth");
		_;
	}

	modifier ownerDoesNotExist(address _address) {
		require(!isOwner(_address), "Is owner");
		_;
	}

	modifier multiOwnedOperationIsActive(bytes32 _operation) {
		require(isOperationActive(_operation), "NoOp");
		_;
	}

	// METHODS

	// constructor is given number of sigs required to do protected "onlyManyOwners" transactions
	// as well as the selection of addresses capable of confirming them (msg.sender is not added to the owners!).
	constructor (address[] memory _owners, uint256 _required)
		public
		validNumOwners(_owners.length)
		multiOwnedValidRequirement(_required, _owners.length)
	{
		assert(c_maxOwners <= 255);

		m_numOwners = _owners.length;
		m_multiOwnedRequired = _required;

		for (uint256 i = 0; i < _owners.length; ++i)
		{
			address owner = _owners[i];
			// invalid and duplicate addresses are not allowed
			require(address(0) != owner && !isOwner(owner), "Exists");  /* not isOwner yet! */

			uint256 currentOwnerIndex = checkOwnerIndex(i + 1);  /* first slot is unused */
			m_owners[currentOwnerIndex] = owner;
			m_ownerIndex[owner] = currentOwnerIndex;
		}

		assertOwnersAreConsistent();
	}

	/// @notice replaces an owner `_from` with another `_to`.
	/// @param _from address of owner to replace
	/// @param _to address of new owner
	// All pending operations will be canceled!
	function changeOwner(address _from, address _to)
		external
		ownerExists(_from)
		ownerDoesNotExist(_to)
		onlyManyOwners(keccak256(msg.data))
	{
		assertOwnersAreConsistent();

		clearPending();
		uint256 ownerIndex = checkOwnerIndex(m_ownerIndex[_from]);
		m_owners[ownerIndex] = _to;
		m_ownerIndex[_from] = 0;
		m_ownerIndex[_to] = ownerIndex;

		assertOwnersAreConsistent();
		emit OwnerChanged(_from, _to);
	}

	/// @notice adds an owner
	/// @param _owner address of new owner
	// All pending operations will be canceled!
	function addOwner(address _owner)
		external
		ownerDoesNotExist(_owner)
		validNumOwners(m_numOwners + 1)
		onlyManyOwners(keccak256(msg.data))
	{
		assertOwnersAreConsistent();

		clearPending();
		m_numOwners++;
		m_owners[m_numOwners] = _owner;
		m_ownerIndex[_owner] = checkOwnerIndex(m_numOwners);

		assertOwnersAreConsistent();
		emit OwnerAdded(_owner);
	}

	/// @notice removes an owner
	/// @param _owner address of owner to remove
	// All pending operations will be canceled!
	function removeOwner(address _owner)
		external
		ownerExists(_owner)
		validNumOwners(m_numOwners - 1)
		multiOwnedValidRequirement(m_multiOwnedRequired, m_numOwners - 1)
		onlyManyOwners(keccak256(msg.data))
	{
		assertOwnersAreConsistent();

		clearPending();
		uint256 ownerIndex = checkOwnerIndex(m_ownerIndex[_owner]);
		m_owners[ownerIndex] = address(0);
		m_ownerIndex[_owner] = 0;
		//make sure m_numOwners is equal to the number of owners and always points to the last owner
		reorganizeOwners();

		assertOwnersAreConsistent();
		emit OwnerRemoved(_owner);
	}

	/// @notice changes the required number of owner signatures
	/// @param _newRequired new number of signatures required
	// All pending operations will be canceled!
	function changeRequirement(uint256 _newRequired)
		external
		multiOwnedValidRequirement(_newRequired, m_numOwners)
		onlyManyOwners(keccak256(msg.data))
	{
		m_multiOwnedRequired = _newRequired;
		clearPending();
		emit RequirementChanged(_newRequired);
	}

	/// @notice Gets an owner by 0-indexed position
	/// @param ownerIndex 0-indexed owner position
	function getOwner(uint256 ownerIndex) public view returns (address) {
		return m_owners[ownerIndex + 1];
	}

	/// @notice Gets owners
	/// @return memory array of owners
	function getOwners() public view returns (address[] memory) {
		address[] memory result = new address[](m_numOwners);
		for (uint256 i = 0; i < m_numOwners; i++)
			result[i] = getOwner(i);

		return result;
	}

	/// @notice checks if provided address is an owner address
	/// @param _addr address to check
	/// @return true if it's an owner
	function isOwner(address _addr) public view returns (bool) {
		return m_ownerIndex[_addr] > 0;
	}

	/// @notice Tests ownership of the current caller.
	/// @return true if it's an owner
	// It's advisable to call it by new owner to make sure that the same erroneous address is not copy-pasted to
	// addOwner/changeOwner and to isOwner.
	function amIOwner() external view onlyOwner returns (bool) {
		return true;
	}

	/// @notice Revokes a prior confirmation of the given operation
	/// @param _operation operation value, typically keccak256(msg.data)
	function revoke(bytes32 _operation)
		external
		multiOwnedOperationIsActive(_operation)
		onlyOwner
	{
		uint256 ownerIndexBit = makeOwnerBitmapBit(msg.sender);
		MultiOwnedOperationPendingState storage pending = m_multiOwnedPending[_operation];
		require(pending.ownersDone & ownerIndexBit > 0, "Auth");

		assertOperationIsConsistent(_operation);

		pending.yetNeeded++;
		pending.ownersDone -= ownerIndexBit;

		assertOperationIsConsistent(_operation);
		emit Revoke(msg.sender, _operation);
	}

	/// @notice Checks if owner confirmed given operation
	/// @param _operation operation value, typically keccak256(msg.data)
	/// @param _owner an owner address
	function hasConfirmed(bytes32 _operation, address _owner)
		external
		view
		multiOwnedOperationIsActive(_operation)
		ownerExists(_owner)
		returns (bool)
	{
		return !(m_multiOwnedPending[_operation].ownersDone & makeOwnerBitmapBit(_owner) == 0);
	}

	// INTERNAL METHODS

	function confirmAndCheck(bytes32 _operation)
		internal
		onlyOwner
		returns (bool)
	{
		if (512 == m_multiOwnedPendingIndex.length)
			// In case m_multiOwnedPendingIndex grows too much we have to shrink it: otherwise at some point
			// we won't be able to do it because of block gas limit.
			// Yes, pending confirmations will be lost. Dont see any security or stability implications.
			// TODO use more graceful approach like compact or removal of clearPending completely
			clearPending();

		MultiOwnedOperationPendingState storage pending = m_multiOwnedPending[_operation];

		// if we're not yet working on this operation, switch over and reset the confirmation status.
		if (! isOperationActive(_operation)) {
			// reset count of confirmations needed.
			pending.yetNeeded = m_multiOwnedRequired;
			// reset which owners have confirmed (none) - set our bitmap to 0.
			pending.ownersDone = 0;
			pending.index = m_multiOwnedPendingIndex.length++;
			m_multiOwnedPendingIndex[pending.index] = _operation;
			assertOperationIsConsistent(_operation);
		}

		// determine the bit to set for this owner.
		uint256 ownerIndexBit = makeOwnerBitmapBit(msg.sender);
		// make sure we (the message sender) haven't confirmed this operation previously.
		if (pending.ownersDone & ownerIndexBit == 0) {
			// ok - check if count is enough to go ahead.
			assert(pending.yetNeeded > 0);
			if (pending.yetNeeded == 1) {
				// enough confirmations: reset and run interior.
				delete m_multiOwnedPendingIndex[m_multiOwnedPending[_operation].index];
				delete m_multiOwnedPending[_operation];
				emit FinalConfirmation(msg.sender, _operation);
				return true;
			}
			else
			{
				// not enough: record that this owner in particular confirmed.
				pending.yetNeeded--;
				pending.ownersDone |= ownerIndexBit;
				assertOperationIsConsistent(_operation);
				emit Confirmation(msg.sender, _operation);
			}
		}
	}

	// Reclaims free slots between valid owners in m_owners.
	// TODO given that its called after each removal, it could be simplified.
	function reorganizeOwners() private {
		uint256 free = 1;
		while (free < m_numOwners)
		{
			// iterating to the first free slot from the beginning
			while (free < m_numOwners && m_owners[free] != address(0)) free++;

			// iterating to the first occupied slot from the end
			while (m_numOwners > 1 && m_owners[m_numOwners] == address(0)) m_numOwners--;

			// swap, if possible, so free slot is located at the end after the swap
			if (free < m_numOwners && m_owners[m_numOwners] != address(0) && m_owners[free] == address(0))
			{
				// owners between swapped slots should't be renumbered - that saves a lot of gas
				m_owners[free] = m_owners[m_numOwners];
				m_ownerIndex[m_owners[free]] = free;
				m_owners[m_numOwners] = address(0);
			}
		}
	}

	function clearPending() private onlyOwner {
		uint256 length = m_multiOwnedPendingIndex.length;
		// TODO block gas limit
		for (uint256 i = 0; i < length; ++i) {
			if (m_multiOwnedPendingIndex[i] != 0)
				delete m_multiOwnedPending[m_multiOwnedPendingIndex[i]];
		}
		delete m_multiOwnedPendingIndex;
	}

	function checkOwnerIndex(uint256 ownerIndex) internal pure returns (uint256) {
		assert(0 != ownerIndex && ownerIndex <= c_maxOwners);
		return ownerIndex;
	}

	function makeOwnerBitmapBit(address owner) private view returns (uint256) {
		uint256 ownerIndex = checkOwnerIndex(m_ownerIndex[owner]);
		return 2 ** ownerIndex;
	}

	function isOperationActive(bytes32 _operation) private view returns (bool) {
		return 0 != m_multiOwnedPending[_operation].yetNeeded;
	}


	function assertOwnersAreConsistent() private view {
		assert(m_numOwners > 0);
		assert(m_numOwners <= c_maxOwners);
		assert(m_owners[0] == address(0));
		assert(0 != m_multiOwnedRequired && m_multiOwnedRequired <= m_numOwners);
	}

	function assertOperationIsConsistent(bytes32 _operation) private view {
		MultiOwnedOperationPendingState storage pending = m_multiOwnedPending[_operation];
		assert(0 != pending.yetNeeded);
		assert(m_multiOwnedPendingIndex[pending.index] == _operation);
		assert(pending.yetNeeded <= m_multiOwnedRequired);
	}


	// FIELDS

	uint256 constant c_maxOwners = 250;

	// the number of owners that must confirm the same operation before it is run.
	uint256 public m_multiOwnedRequired;


	// pointer used to find a free slot in m_owners
	uint256 public m_numOwners;

	// list of owners (addresses),
	// slot 0 is unused so there are no owner which index is 0.
	// TODO could we save space at the end of the array for the common case of <10 owners? and should we?
	address[256] internal m_owners;

	// index on the list of owners to allow reverse lookup: owner address => index in m_owners
	mapping(address => uint256) internal m_ownerIndex;


	// the ongoing operations.
	mapping(bytes32 => MultiOwnedOperationPendingState) internal m_multiOwnedPending;
	bytes32[] internal m_multiOwnedPendingIndex;
}
// TODO acceptOwnership
function confirmAndCheck(bytes32 _operation)
	internal
	onlyOwner
	returns (bool)
{
	if (512 == m_multiOwnedPendingIndex.length)
		// In case m_multiOwnedPendingIndex grows too much we have to shrink it: otherwise at some point
		// we won't be able to do it because of block gas limit.
		// Yes, pending confirmations will be lost. Dont see any security or stability implications.
		// TODO use more graceful approach like compact or removal of clearPending completely
		clearPending();

	MultiOwnedOperationPendingState storage pending = m_multiOwnedPending[_operation];

	// if we're not yet working on this operation, switch over and reset the confirmation status.
	if (! isOperationActive(_operation)) {
		// reset count of confirmations needed.
		pending.yetNeeded = m_multiOwnedRequired;
		// reset which owners have confirmed (none) - set our bitmap to 0.
		pending.ownersDone = 0;
		pending.index = m_multiOwnedPendingIndex.length++;
		m_multiOwnedPendingIndex[pending.index] = _operation;
		assertOperationIsConsistent(_operation);
	}

	// determine the bit to set for this owner.
	uint256 ownerIndexBit = makeOwnerBitmapBit(msg.sender);
	// make sure we (the message sender) haven't confirmed this operation previously.
	if (pending.ownersDone & ownerIndexBit == 0) {
		// ok - check if count is enough to go ahead.
		assert(pending.yetNeeded > 0);
		if (pending.yetNeeded == 1) {
			// enough confirmations: reset and run interior.
			delete m_multiOwnedPendingIndex[m_multiOwnedPending[_operation].index];
			delete m_multiOwnedPending[_operation];
			emit FinalConfirmation(msg.sender, _operation);
			return true;
		}
		else
		{
			// not enough: record that this owner in particular confirmed.
			pending.yetNeeded--;
			pending.ownersDone |= ownerIndexBit;
			assertOperationIsConsistent(_operation);
			emit Confirmation(msg.sender, _operation);
		}
	}
}

// INTERNAL METHODS