import { IActionCreator } from './action';
import { FlowfulError } from './error';
import { ActionHandler } from './action-handler';

type ActionHandlersByType = Map<IActionCreator, Set<ActionHandler>>;

export type CyclicStack = ActionHandler[];

function visitDown(
  handler: ActionHandler,
  visitedHandlers: WeakSet<ActionHandler>,
  handlersByInput: ActionHandlersByType,
  sorted: ActionHandler[],
  stack: Set<ActionHandler>,
  cyclic: CyclicStack[]
) {
  visitedHandlers.add(handler);
  stack.add(handler);
  const outputActionCreators = handler.getOutputs();
  if (outputActionCreators) {
    for (let i = 0, len = outputActionCreators.length; i < len; i++) {
      const Output = outputActionCreators[i];
      const interestedHandlers = handlersByInput.get(Output);
      if (interestedHandlers) {
        for (const interestedHandler of interestedHandlers) {
          if (!visitedHandlers.has(interestedHandler)) {
            visitDown(interestedHandler, visitedHandlers, handlersByInput, sorted, stack, cyclic);
          }
          if (stack.has(interestedHandler)) {
            const _stack = [...stack];
            const index = _stack.indexOf(interestedHandler);
            _stack.splice(0, index);
            _stack.push(interestedHandler);
            cyclic.push(_stack);
          }
        }
      }
    }
  }
  stack.delete(handler);
  sorted.push(handler);
}

export function sortDown(handlers: ActionHandler[], handlersByInput: ActionHandlersByType): ActionHandler[] {
  const sorted: ActionHandler[] = [];
  const visitedHandlers: WeakSet<ActionHandler> = new Set();
  const stack: Set<ActionHandler> = new Set();
  const cyclic: CyclicStack[] = [];
  for (let i = 0, len = handlers.length; i < len; i++) {
    const handler = handlers[i];
    if (!visitedHandlers.has(handler)) {
      visitDown(handler, visitedHandlers, handlersByInput, sorted, stack, cyclic);
    }
  }
  if (cyclic.length) {
    throw new FlowfulError(`[Flowful] The action handler dependency graph contains a cycle.`, cyclic);
  }
  return sorted.reverse();
}

function visitUp(
  handler: ActionHandler,
  visitedHandlers: WeakSet<ActionHandler>,
  handlersByOutput: ActionHandlersByType,
  sorted: ActionHandler[],
  stack: Set<ActionHandler>,
  cyclic: CyclicStack[]
) {
  visitedHandlers.add(handler);
  stack.add(handler);
  const inputs = handler.getInputs();
  if (inputs) {
    for (let i = 0, len = inputs.length; i < len; i++) {
      const Input = inputs[i];
      const producers = handlersByOutput.get(Input);
      if (producers) {
        for (const producer of producers) {
          if (!visitedHandlers.has(producer)) {
            visitUp(producer, visitedHandlers, handlersByOutput, sorted, stack, cyclic);
          }
          if (stack.has(producer)) {
            const _stack = [...stack];
            const index = _stack.indexOf(producer);
            _stack.splice(0, index);
            _stack.push(producer);
            cyclic.push(_stack.reverse());
          }
        }
      }
    }
  }
  stack.delete(handler);
  sorted.push(handler);
}

export function sortUp(handlers: ActionHandler[], handlersByOutput: ActionHandlersByType) {
  const sorted: ActionHandler[] = [];
  const visitedHandlers: WeakSet<ActionHandler> = new Set();
  const stack = new Set<ActionHandler>();
  const cyclic: CyclicStack[] = [];

  for (let i = 0, len = handlers.length; i < len; i++) {
    const handler = handlers[i];
    if (!visitedHandlers.has(handler)) {
      visitUp(handler, visitedHandlers, handlersByOutput, sorted, stack, cyclic);
    }
  }
  if (cyclic.length) {
    throw new FlowfulError(`[Flowful] The action handler dependency graph contains a cycle.`, cyclic);
  }
  return sorted;
}

function getInDegree(handlers: ActionHandler[], handlersByInput: ActionHandlersByType) {
  const inDegree: Map<ActionHandler, number> = new Map();
  for (let i = 0, len = handlers.length; i < len; i++) {
    inDegree.set(handlers[i], 0);
  }
  for (let handlerIndex = 0, len = handlers.length; handlerIndex < len; handlerIndex++) {
    const handler = handlers[handlerIndex];
    const outputActionCreators = handler.getOutputs();
    if (!outputActionCreators) {
      continue;
    }
    for (let actionIndex = 0, len = outputActionCreators.length; actionIndex < len; actionIndex++) {
      const OutputAction = outputActionCreators[actionIndex];
      const interestedHandlers = handlersByInput.get(OutputAction);
      if (interestedHandlers?.size) {
        for (const interestedHandler of interestedHandlers) {
          inDegree.set(interestedHandler, inDegree.get(interestedHandler)! + 1);
        }
      }
    }
  }
  return inDegree;
}

export function sortKahn(handlers: ActionHandler[], handlersByInput: ActionHandlersByType) {
  const queue: ActionHandler[] = [];
  const sorted: ActionHandler[] = [];
  const inDegree = getInDegree(handlers, handlersByInput);

  const actionWeight: Map<IActionCreator, number> = new Map();
  for (let i = 0, len = handlers.length; i < len; i++) {
    const handler = handlers[i];
    for (const InputAction of handler.getInputs()) {
      if (!actionWeight.has(InputAction)) {
        actionWeight.set(InputAction, i);
      }
    }
  }

  for (const [handler, degree] of inDegree) {
    const output = handler.getOutputs();
    if (output) {
      // @ts-expect-error - sort is readonly but we need to sort it anyway :D - we know what we are doing
      output.sort((a, b) => {
        const aWeight = actionWeight.get(a) || 0;
        const bWeight = actionWeight.get(b) || 0;
        return aWeight - bWeight;
      });
    }
    if (degree === 0) {
      queue.push(handler);
    }
  }

  while (queue.length) {
    const handler = queue.shift()!;
    sorted.push(handler);
    const handlerOutput = handler.getOutputs();
    if (!handlerOutput) {
      continue;
    }
    for (let i = 0, len = handlerOutput.length; i < len; i++) {
      const Output = handlerOutput[i];
      const interestedHandlers = handlersByInput.get(Output);
      if (interestedHandlers) {
        for (const interestedHandler of interestedHandlers) {
          inDegree.set(interestedHandler, inDegree.get(interestedHandler)! - 1);
          if (inDegree.get(interestedHandler)! === 0) {
            queue.push(interestedHandler);
          }
        }
      }
    }
  }

  if (sorted.length !== handlers.length) {
    const cyclic = orderAwareCycleDetection(handlers, handlersByInput);
    throw new FlowfulError('[Flowful] The action handler dependency graph contains a cycle.', cyclic);
  }

  return sorted;
}

export interface Cyclic {
  actionHandler: ActionHandler;
  actionCreator: IActionCreator;
}

function visitCyclicAccurate(
  rootHandler: ActionHandler,
  handler: ActionHandler,
  visitedHandlers: WeakSet<ActionHandler>,
  handlersByInput: ActionHandlersByType,
  stack: WeakSet<ActionHandler>,
  cyclic: Cyclic[]
) {
  visitedHandlers.add(handler);
  stack.add(handler);
  const output = handler.getOutputs();
  if (output) {
    for (const Output of output) {
      const interestedHandlers = handlersByInput.get(Output);
      if (interestedHandlers) {
        for (const interestedHandler of interestedHandlers) {
          if (!visitedHandlers.has(interestedHandler)) {
            visitCyclicAccurate(rootHandler, interestedHandler, visitedHandlers, handlersByInput, stack, cyclic);
          }
          if (stack.has(interestedHandler) && interestedHandler === rootHandler) {
            // add cyclic dependencies for root handler
            cyclic.push({ actionHandler: handler, actionCreator: Output });
          }
        }
      }
    }
  }
  stack.delete(handler);
}

export function orderAwareCycleDetection(handlers: ActionHandler[], handlersByInput: ActionHandlersByType) {
  const cyclic: Cyclic[] = [];
  for (const handler of handlers) {
    visitCyclicAccurate(handler, handler, new WeakSet(), handlersByInput, new WeakSet(), cyclic);
  }
  return cyclic;
}

function visitConnected(
  handler: ActionHandler,
  stack: WeakSet<ActionHandler>,
  visitedHandlers: WeakSet<ActionHandler>,
  handlersByActionCreator: ActionHandlersByType,
  connectedComponent: Set<ActionHandler>
) {
  visitedHandlers.add(handler);
  stack.add(handler);
  connectedComponent.add(handler);
  const creators = handler.getInputsAndOutputs();
  for (let i = 0, len = creators.length; i < len; i++) {
    const actionHandlers = handlersByActionCreator.get(creators[i])!;
    for (const actionHandler of actionHandlers) {
      if (!visitedHandlers.has(actionHandler)) {
        visitConnected(actionHandler, stack, visitedHandlers, handlersByActionCreator, connectedComponent);
      }
    }
  }
  stack.delete(handler);
}

export function connectedComponentsDFS(
  handlers: Set<ActionHandler>,
  handlersByActionCreator: ActionHandlersByType,
  handlersByInput: ActionHandlersByType
) {
  const visitedActionHandlers: WeakSet<ActionHandler> = new Set();
  const stackOutput: WeakSet<ActionHandler> = new Set();
  const connectedComponents: ActionHandler[][] = [];

  for (const handler of handlers) {
    if (!visitedActionHandlers.has(handler)) {
      const connectedComponent = new Set<ActionHandler>();
      visitConnected(handler, stackOutput, visitedActionHandlers, handlersByActionCreator, connectedComponent);
      connectedComponents.push(sortDown([...connectedComponent], handlersByInput));
    }
  }

  return connectedComponents;
}

export function connectedComponentsByActionCreator(connectedComponents: ActionHandler[][]) {
  const connectedComponentsByActionCreator: Map<IActionCreator, ActionHandler[]> = new Map();
  for (let componentIndex = 0, len = connectedComponents.length; componentIndex < len; componentIndex++) {
    const connectedComponent = connectedComponents[componentIndex];
    for (const handler of connectedComponent) {
      const input = handler.getInputs();
      if (input) {
        for (let inputIndex = 0, len = input.length; inputIndex < len; inputIndex++) {
          const Input = input[inputIndex];
          if (
            connectedComponentsByActionCreator.has(Input) &&
            connectedComponentsByActionCreator.get(Input) !== connectedComponent
          ) {
            throw new FlowfulError(`[Flowful] Connected components already exists for this action.`, {
              actionCreator: Input,
              connectedComponent,
              connectedComponents,
              current: connectedComponentsByActionCreator.get(Input),
            });
          }
          connectedComponentsByActionCreator.set(Input, connectedComponent);
        }
      }
    }
  }
  return connectedComponentsByActionCreator;
}