FactoryCraft-Client/FactoryCraft/QuestGraph.cpp

#include "QuestGraph.h"

#include <Bild.h>
#include <HashMap.h>
#include <Scroll.h>
#include <XML.h>

#include "Globals.h"
#include "Load.h"
#include "World.h"

QuestGraphElement::QuestGraphElement() {}

bool QuestGraphElement::isApplicableFor(Framework::XML::Element& element)
{
    return element.getName().istGleich("questGraph");
}

Framework::Zeichnung* QuestGraphElement::parseElement(
    Framework::XML::Element& element, Framework::UIMLContainer& generalFactory)
{
    QuestGraph* graph = new QuestGraph();
    graph->collectionName = element.getAttributeValue("collectionName");
    graph->id = element.getAttributeValue("id");

    auto children = element.selectChildsByName("questGraphItem");
    Framework::HashMap<Framework::Text, QuestGraphItem*> map(
        100, [](Framework::Text str) { return str.hashCode(); });
    // parse graph elements
    for (Framework::XML::Element* itemElement : children)
    {
        Framework::Zeichnung* parsed
            = generalFactory.parseElement(*itemElement, generalFactory);
        QuestGraphItem* item = dynamic_cast<QuestGraphItem*>(parsed);
        if (!item)
        {
            if (parsed)
            {
                parsed->release();
            }
        }
        else
        {
            map.put(item->getId(), item);
        }
        generalFactory.layout(*itemElement,
            *parsed,
            graph->getBreite(),
            graph->getHeight(),
            generalFactory);
    }
    // set connection references
    int connectionId = -1;
    for (MapEntry<Framework::Text, QuestGraphItem*> entry : map)
    {
        QuestGraphItem* item = entry.getValue();
        Framework::Text requirements = item->getRequirements();
        while (requirements.getLength() > 0)
        {
            connectionId++;
            Framework::Text* part = 0;
            if (requirements.hat("||"))
            {
                part = requirements.getTeilText(
                    0, requirements.positionVon("||"));
                requirements.remove(0, requirements.positionVon("||") + 2);
            }
            else
            {
                part = new Framework::Text(requirements);
                requirements = "";
            }
            while (part->getLength() > 0)
            {
                Framework::Text* requirement;
                if (part->hat("&&"))
                {
                    requirement = part->getTeilText(0, part->positionVon("&&"));
                    part->remove(0, part->positionVon("&&") + 2);
                }
                else
                {
                    requirement = new Text(part->getText());
                    part->setText("");
                }
                requirement->removeWhitespaceAfter(0);
                requirement->removeWhitespaceBefore(requirement->getLength());
                QuestGraphItem* requiredItem = map.get(*requirement);
                if (requiredItem)
                {
                    requiredItem->addNextLayerRef({item, connectionId});
                    item->addPreviousLayerRef({requiredItem, connectionId});
                }
                requirement->release();
            }
            part->release();
        }
    }
    // calculate layer index based on connections
    bool changed = 1;
    while (changed)
    {
        changed = 0;
        for (MapEntry<Framework::Text, QuestGraphItem*> entry : map)
        {
            changed |= entry.getValue()->calculateLaxerIndex();
        }
    }
    // add items to graph
    for (MapEntry<Framework::Text, QuestGraphItem*> entry : map)
    {
        if (entry.getValue()->getLayerIndex() < 0)
        {
            entry.getValue()->setVirtual(
                1); // hide nodes witch layers could not be calculated because
                    // of invalid circular connections
        }
        graph->addItem(entry.getValue());
    }
    graph->addVirtualConnectionNodes();
    graph->sortItems();
    return graph;
}

bool QuestGraphElement::updateElement(Framework::XML::Element& element,
    Framework::Zeichnung& z,
    Framework::UIMLContainer& generalFactory)
{
    return false;
}

void QuestGraphElement::layout(Framework::XML::Element& element,
    Framework::Zeichnung& z,
    int pWidth,
    int pHeight,
    Framework::UIMLContainer& generalLayouter)
{
    UIMLElement::layout(element, z, pWidth, pHeight, generalLayouter);
    QuestGraph* graph = dynamic_cast<QuestGraph*>(&z);
    graph->fixItemPositions();
}

QuestGraphItemElement::QuestGraphItemElement() {}

bool QuestGraphItemElement::isApplicableFor(Framework::XML::Element& element)
{
    return element.getName().istGleich("questGraphItem");
}

Framework::Zeichnung* QuestGraphItemElement::parseElement(
    Framework::XML::Element& element, Framework::UIMLContainer& generalFactory)
{
    QuestGraphItem* item = new QuestGraphItem();
    Framework::Text name = element.getAttributeValue("name");
    Framework::Text description = element.getAttributeValue("description");
    item->setToolTipText(name + "\n" + description,
        generalFactory.getFactory().initParam.bildschirm,
        generalFactory.getFactory().initParam.schrift);
    item->setHintergrundBildZ(loadImage(element.getAttributeValue("image")));
    item->finished = (int)element.getAttributeValue("finished") != 0;
    if (item->finished)
    {
        item->setRahmenFarbe(0xFF55FF00);
    }
    item->rewarded = (int)element.getAttributeValue("rewarded") != 0;
    item->mainQuest = (int)element.getAttributeValue("mainQuest") != 0;
    if (item->mainQuest)
    {
        item->setRahmenBreite(3);
    }
    item->id = element.getAttributeValue("id");
    item->requirements = element.getAttributeValue("requirements");
    item->virtualNode = 0;
    return item;
}

bool QuestGraphItemElement::updateElement(Framework::XML::Element& element,
    Framework::Zeichnung& z,
    Framework::UIMLContainer& generalFactory)
{
    return false;
}

void QuestGraphItemElement::layout(Framework::XML::Element& element,
    Framework::Zeichnung& z,
    int pWidth,
    int pHeight,
    Framework::UIMLContainer& generalLayouter)
{
    UIMLElement::layout(element, z, pWidth, pHeight, generalLayouter);
}

Connection::Connection(QuestGraphItem* zSource)
    : ReferenceCounter(),
      zSource(zSource),
      vx(0),
      minY(0),
      maxY(0)
{}

void Connection::renderVertical(Framework::Bild& rObj)
{
    if (targets.getEintragAnzahl())
    {
        rObj.drawLinieV(
            vx, minY, maxY - minY, isActive() ? 0xFFFFFFFF : 0xFF52525E);
    }
}

void Connection::renderHorizontal(Framework::Bild& rObj)
{
    if (targets.getEintragAnzahl())
    {
        Framework::Punkt start = zSource->getPosition();
        start.x += zSource->getBreite();
        start.y += zSource->getHeight() / 2;
        rObj.drawLinieH(start.x, start.y - 2, vx - start.x, 0xA0000000);
        rObj.drawLinieH(start.x, start.y - 1, vx - start.x, 0xA0000000);
        rObj.drawLinieH(start.x,
            start.y,
            vx - start.x,
            isActive() ? 0xFFFFFFFF : 0xFF52525E);
        rObj.drawLinieH(start.x, start.y + 1, vx - start.x, 0xA0000000);
        rObj.drawLinieH(start.x, start.y + 2, vx - start.x, 0xA0000000);
        for (const ConnectionTarget& target : targets)
        {
            Framework::Punkt end
                = target.zTarget->getTargetPosition(target.targetIndex);
            rObj.drawLinieH(vx + 1, end.y - 2, end.x - vx - 1, 0xA0000000);
            rObj.drawLinieH(vx + 1, end.y - 1, end.x - vx - 1, 0xA0000000);
            rObj.drawLinieH(vx + 1,
                end.y,
                end.x - vx - 1,
                isActive() ? 0xFFFFFFFF : 0xFF52525E);
            rObj.drawLinieH(vx + 1, end.y + 1, end.x - vx - 1, 0xA0000000);
            rObj.drawLinieH(vx + 1, end.y + 2, end.x - vx - 1, 0xA0000000);
        }
    }
}

void Connection::setVx(int vx)
{
    this->vx = vx;
}

void Connection::addConnectionTarget(ConnectionTarget target)
{
    targets.add(target);
}

void Connection::setTargetIndex(AndNode* zTarget, int index)
{
    for (auto target = targets.begin(); target; target++)
    {
        if (target.val().zTarget == zTarget)
        {
            target.set({index, target.val().zTarget});
            return;
        }
    }
}

void Connection::layout()
{
    minY = 0;
    maxY = 0;
    bool start = 1;
    for (const ConnectionTarget& target : targets)
    {
        Framework::Punkt end
            = target.zTarget->getTargetPosition(target.targetIndex);
        if (start || end.y < minY)
        {
            minY = end.y;
        }
        if (start || end.y > maxY)
        {
            maxY = end.y;
        }
        start = 0;
    }
    Framework::Punkt origin = zSource->getPosition();
    origin.x += zSource->getBreite();
    origin.y += zSource->getHeight() / 2;
    if (minY > origin.y) minY = origin.y;
    if (maxY < origin.y) maxY = origin.y;
    maxY++;
}

bool Connection::isActive() const
{
    return zSource->isFinished();
}

int Connection::getOrderNum() const
{
    return zSource->getNodeIndex();
}

int Connection::getTargetCount() const
{
    return targets.getEintragAnzahl();
}

int Connection::getVerticalLength() const
{
    return maxY - minY;
}

int Connection::getVx() const
{
    return vx;
}

AndNode::AndNode()
    : ZeichnungHintergrund()
{
    setStyle(ZeichnungHintergrund::Style::Sichtbar
             | ZeichnungHintergrund::Style::Rahmen);
    setRahmenBreite(1);
    setRahmenFarbe(0xFF52525E);
    tr.setSchriftSize(12);
    tr.setSchriftZ(
        dynamic_cast<Schrift*>(uiFactory.initParam.schrift->getThis()));
}

void AndNode::addConnection(Connection* zConnection)
{
    int pos = 0;
    for (Connection* other : connections)
    {
        if (other->getOrderNum() > zConnection->getOrderNum()) break;
        pos++;
    }
    zConnection->addConnectionTarget({pos, this});
    connections.add(zConnection, pos);
    pos = 0;
    for (Connection* con : connections)
    {
        con->setTargetIndex(this, pos);
        pos++;
    }
}

void AndNode::render(Framework::Bild& rObj)
{
    setRahmenFarbe(isActive() ? 0xFFFFFFFF : 0xFF52525E);
    if (connections.getEintragAnzahl() > 1)
    {
        ZeichnungHintergrund::render(rObj);
        if (rObj.setDrawOptions(pos.x + getRahmenBreite(),
                pos.y + getRahmenBreite(),
                getInnenBreite(),
                getInnenHeight()))
        {
            tr.renderText(getInnenBreite() / 2 - tr.getTextBreite("&") / 2,
                getInnenHeight() / 2 - tr.getTextHeight("&") / 2,
                "&",
                rObj,
                isActive() ? 0xFFFFFFFF : 0xFF52525E);
            rObj.releaseDrawOptions();
        }
    }
    else if (connections.getEintragAnzahl() > 0)
    {
        if (rObj.setDrawOptions(pos, gr))
        {
            rObj.drawLinieH(0,
                0,
                gr.x,
                connections.get(0)->isActive() ? 0xFFFFFFFF : 0xFF52525E);
            rObj.releaseDrawOptions();
        }
    }
}

Framework::Punkt AndNode::getTargetPosition(int index)
{
    if (connections.getEintragAnzahl() == 1)
    {
        return pos;
    }
    return pos + Framework::Punkt(0, 10 + index * 11);
}

void AndNode::layout()
{
    if (connections.getEintragAnzahl() == 1)
    {
        setSize(20, 1);
    }
    else
    {
        setSize(20, 10 + connections.getEintragAnzahl() * 11);
    }
}

bool AndNode::isActive() const
{
    for (Connection* connection : connections)
    {
        if (!connection->isActive()) return false;
    }
    return connections.getEintragAnzahl() > 0;
}

int AndNode::getConnectionCount() const
{
    return connections.getEintragAnzahl();
}

OrConnection::OrConnection(QuestGraphItem* zTarget,
    const Framework::Array<ConnectionInfo>& connections)
    : ReferenceCounter(),
      zTarget(zTarget),
      minY(0),
      maxY(0)
{
    int currId = -1;
    AndNode* currNode = 0;
    for (const ConnectionInfo& info : connections)
    {
        if (info.id != currId)
        {
            currNode = new AndNode();
            andNodes.add(currNode);
            currId = info.id;
        }
        currNode->addConnection(info.target->zOutgoingConnection());
    }
}

void OrConnection::render(Framework::Bild& rObj)
{
    if (andNodes.getEintragAnzahl() == 0) return;
    bool active = isActive();
    rObj.drawLinieV(zTarget->getX() - 11,
        minY,
        maxY - minY,
        active ? 0xFFFFFFFF : 0xFF52525E);
    rObj.drawLinieH(zTarget->getX() - 10,
        zTarget->getY() + zTarget->getHeight() / 2,
        10,
        active ? 0xFFFFFFFF : 0xFF52525E);
    for (AndNode* node : andNodes)
    {
        rObj.drawLinieH(node->getX() + node->getBreite(),
            node->getY() + node->getHeight() / 2,
            10,
            active ? 0xFFFFFFFF : 0xFF52525E);
        node->render(rObj);
    }
}

void OrConnection::layout()
{
    int nodeHeight = -10;
    for (AndNode* node : andNodes)
    {
        node->layout();
        nodeHeight += node->getHeight() + 10;
    }
    int y = zTarget->getY() + zTarget->getHeight() / 2 - nodeHeight / 2;
    bool start = 1;
    AndNode* last = 0;
    for (AndNode* node : andNodes)
    {
        node->setPosition(zTarget->getX() - 21 - node->getBreite(), y);
        if (start)
        {
            minY = y + node->getHeight() / 2;
        }
        y += node->getHeight() + 10;
        start = 0;
        last = node;
    }
    if (last)
    {
        y -= 10 + last->getHeight();
        maxY = y + last->getHeight() / 2 + 1;
    }
    else
    {
        maxY = minY + 1;
    }
}

int OrConnection::getNeededHeight() const
{
    int minY = 0;
    int maxY = 0;
    bool first = 1;
    for (AndNode* node : andNodes)
    {
        if (first || node->getY() < minY)
        {
            minY = node->getY();
        }
        if (first || node->getY() + node->getHeight() > maxY)
        {
            maxY = node->getY() + node->getHeight();
        }
        first = 0;
    }
    return maxY - minY;
}

bool OrConnection::isActive() const
{
    for (AndNode* node : andNodes)
    {
        if (node->isActive()) return 1;
    }
    return 0;
}

bool OrConnection::isHorizontalLineConflict(int y) const
{
    for (AndNode* node : andNodes)
    {
        for (int i = 0; i < node->getConnectionCount(); i++)
        {
            Punkt connection = node->getTargetPosition(i);
            if (abs(y - connection.y) < 5) return 1;
        }
    }
    return 0;
}

QuestGraphItem::QuestGraphItem()
    : ZeichnungHintergrund(),
      layerIndex(-1),
      nodeIndex(-1),
      outgoingConnection(0),
      incommingConnection(0),
      finished(0),
      rewarded(0),
      mainQuest(0),
      virtualNode(0),
      animationProgress(0)
{
    addStyle(ZeichnungHintergrund::Style::Sichtbar
             | ZeichnungHintergrund::Style::Rahmen
             | ZeichnungHintergrund::Style::Erlaubt
             | ZeichnungHintergrund::Style::HBild
             | ZeichnungHintergrund::Style::HBildScale
             | ZeichnungHintergrund::Style::HAlpha
             | ZeichnungHintergrund::Style::Hintergrund);
    setRahmenFarbe(0xFF52525E);
    setRahmenBreite(1);
    setMausEreignis(Framework::_ret1ME);
}

QuestGraphItem::~QuestGraphItem()
{
    if (outgoingConnection) outgoingConnection->release();
    if (incommingConnection) incommingConnection->release();
}

bool QuestGraphItem::tick(double tickVal)
{
    animationProgress += tickVal * 20;
    if (animationProgress > getBreite() * 2 + getHeight() * 2 - 4)
    {
        animationProgress -= getBreite() * 2 + getHeight() * 2 - 4;
    }
    rend = 1;
    return ZeichnungHintergrund::tick(tickVal);
}

int getBorderX(int p, int width, int height)
{
    if (p < width)
    {
        return p;
    }
    else if (p < width + height - 1)
    {
        return width - 1;
    }
    else if (p < width * 2 + height - 2)
    {
        return width - (p - width - height + 2);
    }
    else
    {
        return 0;
    }
}

int getBorderY(int p, int width, int height)
{
    if (p < width)
    {
        return 0;
    }
    else if (p < width + height - 1)
    {
        return p - width + 1;
    }
    else if (p < width * 2 + height - 2)
    {
        return height - 1;
    }
    else
    {
        return height - (p - width * 2 - height + 3);
    }
}

void QuestGraphItem::render(Framework::Bild& rObj)
{
    if (incommingConnection) incommingConnection->render(rObj);
    if (isVirtual())
    {
        rObj.drawLinieH(
            pos.x, pos.y, gr.x, isFinished() ? 0xFFFFFFFF : 0xFF52525E);
        return;
    }
    ZeichnungHintergrund::render(rObj);
    if (finished && !rewarded)
    {
        if (rObj.setDrawOptions(pos.x, pos.y, gr.x - 1, gr.y - 1))
        {
            for (int i = 0; i < 7; i++)
            {
                int p
                    = ((int)animationProgress + i) % (gr.x * 2 + gr.y * 2 - 4);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) - 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) - 1,
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) + 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) + 1,
                    0xFFFFFF00);
                p = ((int)animationProgress + i + gr.x - 1)
                  % (gr.x * 2 + gr.y * 2 - 4);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) - 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) - 1,
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) + 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) + 1,
                    0xFFFFFF00);
                p = ((int)animationProgress + i + gr.x + gr.y - 2)
                  % (gr.x * 2 + gr.y * 2 - 4);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) - 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) - 1,
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) + 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) + 1,
                    0xFFFFFF00);
                p = ((int)animationProgress + i + gr.x * 2 + gr.y - 3)
                  % (gr.x * 2 + gr.y * 2 - 4);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) - 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) - 1,
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y) + 1,
                    getBorderY(p, gr.x, gr.y),
                    0xFFFFFF00);
                rObj.setPixelDP(getBorderX(p, gr.x, gr.y),
                    getBorderY(p, gr.x, gr.y) + 1,
                    0xFFFFFF00);
            }
            rObj.releaseDrawOptions();
        }
    }
}

void QuestGraphItem::renderVerticalConnections(Framework::Bild& rObj)
{
    if (outgoingConnection) outgoingConnection->renderVertical(rObj);
}

void QuestGraphItem::renderHorizontalConnections(Framework::Bild& rObj)
{
    if (outgoingConnection) outgoingConnection->renderHorizontal(rObj);
}

void QuestGraphItem::replacePreviousConnections(
    QuestGraphItem* zBefore, QuestGraphItem* zAfter)
{
    for (auto con = previousLayersConnections.begin(); con; con++)
    {
        if (con.val().target == zBefore) con.set({zAfter, con.val().id});
    }
}

const Framework::Text& QuestGraphItem::getId() const
{
    return id;
}

const Framework::Text& QuestGraphItem::getRequirements() const
{
    return requirements;
}

bool QuestGraphItem::calculateLaxerIndex()
{
    int oldLayerIndex = layerIndex;
    int maxLayerIndex = -1;
    for (const ConnectionInfo& item : previousLayersConnections)
    {
        if (item.target->getLayerIndex() < 0) return 0;
        if (item.target->getLayerIndex() > maxLayerIndex)
        {
            maxLayerIndex = item.target->getLayerIndex();
        }
    }
    layerIndex = maxLayerIndex + 1;
    return oldLayerIndex != layerIndex;
}

int QuestGraphItem::getLayerIndex() const
{
    return layerIndex;
}

void QuestGraphItem::setVirtual(bool virtualNode)
{
    this->virtualNode = virtualNode;
    gr.y = virtualNode ? 1 : gr.y;
    gr.x = 1;
    setStyle(ZeichnungHintergrund::Style::Sichtbar, virtualNode);
}

void QuestGraphItem::setNodeIndex(int index)
{
    this->nodeIndex = index;
}

void QuestGraphItem::addNextLayerRef(ConnectionInfo zItem)
{
    nextLayersConnections.add(zItem);
}

void QuestGraphItem::addPreviousLayerRef(ConnectionInfo zItem)
{
    previousLayersConnections.add(zItem);
}

void QuestGraphItem::initializeConnections()
{
    outgoingConnection = new Connection(this);
    incommingConnection = new OrConnection(this, previousLayersConnections);
}

const Framework::Array<ConnectionInfo>&
QuestGraphItem::getNextLayersConnections() const
{
    return nextLayersConnections;
}

int QuestGraphItem::getNodeIndex() const
{
    return nodeIndex;
}

bool QuestGraphItem::isMainQuest() const
{
    return mainQuest;
}

bool QuestGraphItem::isVirtual() const
{
    return virtualNode;
}

bool QuestGraphItem::isFinished() const
{
    return virtualNode ? incommingConnection->isActive() : finished;
}

Connection* QuestGraphItem::zOutgoingConnection() const
{
    return outgoingConnection;
}

OrConnection* QuestGraphItem::zIncommingConnection() const
{
    return incommingConnection;
}

QuestGraphItemLayer::QuestGraphItemLayer()
    : ReferenceCounter()
{}

bool QuestGraphItemLayer::tick(double tickVal)
{
    bool result = 0;
    for (QuestGraphItem* item : items)
    {
        result |= item->tick(tickVal);
    }
    return result;
}

void QuestGraphItemLayer::render(Framework::Bild& rObj)
{
    for (QuestGraphItem* item : items)
    {
        item->render(rObj);
        item->renderVerticalConnections(rObj);
    }
    for (QuestGraphItem* item : items)
    {
        item->renderHorizontalConnections(rObj);
    }
}

void QuestGraphItemLayer::doMausEreignis(Framework::MausEreignis& me)
{
    for (QuestGraphItem* item : items)
    {
        item->doPublicMausEreignis(me);
    }
}

void QuestGraphItemLayer::addItem(QuestGraphItem* item)
{
    items.add(item);
    item->setNodeIndex(items.getEintragAnzahl() - 1);
}

bool QuestGraphItemLayer::sortItems()
{
    bool changed = 0;
    for (int index = 0; index < items.getEintragAnzahl() - 1; index++)
    {
        QuestGraphItem* current = items.z(index);
        int conflicts = 0;
        int afterSwapConflicts = 0;
        QuestGraphItem* other = items.z(index + 1);
        for (const ConnectionInfo& connection :
            current->getNextLayersConnections())
        {
            for (const ConnectionInfo& otherConnection :
                other->getNextLayersConnections())
            {
                if ((otherConnection.target->getNodeIndex()
                        < connection.target->getNodeIndex()))
                {
                    conflicts++;
                }
                if ((otherConnection.target->getNodeIndex()
                        > connection.target->getNodeIndex()))
                {
                    afterSwapConflicts++;
                }
            }
        }
        if (conflicts > afterSwapConflicts)
        {
            // move node down
            QuestGraphItem* after = items.z(index + 1);
            after->setNodeIndex(index);
            current->setNodeIndex(index + 1);
            items.tausch(index, index + 1);
            changed = 1;
        }
    }
    return changed;
}

int QuestGraphItemLayer::fixItemPositions(int x)
{
    // calculate size needed for & nodes and | nodes
    int maxWidth = 0;
    for (QuestGraphItem* item : items)
    {
        item->initializeConnections();
        item->zIncommingConnection()->layout();
        if (item->getBreite() > maxWidth)
        {
            maxWidth = item->getBreite();
        }
    }
    x += 20 + 21; // ofset for incomming connections
    int y = 0;
    // calculate y positions of nodes
    for (QuestGraphItem* item : items)
    {
        int height = 0;
        int lastId = -1;
        int nodeHeight = item->zIncommingConnection()->getNeededHeight();
        if (nodeHeight < item->getHeight()) nodeHeight = item->getHeight();
        item->setPosition(x + maxWidth / 2 - item->getBreite() / 2,
            y + nodeHeight / 2 - item->getHeight() / 2);
        y += nodeHeight + 20;
    }
    x += maxWidth; // this layers node size
    for (QuestGraphItem* item : items)
    {
        item->zIncommingConnection()->layout();
        item->zOutgoingConnection()->setVx(x);
        item->zOutgoingConnection()->layout();
    }
    x += items.getEintragAnzahl() * 11 + 10; // offset for outgoing connections
    return x + 20;                           // min space between layers
}

void QuestGraphItemLayer::sortConnections()
{
    for (QuestGraphItem* item : items)
    {
        item->zIncommingConnection()->layout();
        item->zOutgoingConnection()->layout();
    }
    int connectionCount = 0;
    bool* sorted = new bool[items.getEintragAnzahl()];
    memset(sorted, 0, sizeof(bool) * items.getEintragAnzahl());
    int sortedCount = 0;
    while (true)
    {
        int minHeight = -1;
        QuestGraphItem* next = 0;
        for (QuestGraphItem* item : items)
        {
            if (sorted[item->getNodeIndex()]) continue;
            if (item->zOutgoingConnection()->getTargetCount()
                == connectionCount)
            {
                if (minHeight < 0
                    || item->zOutgoingConnection()->getVerticalLength()
                           < minHeight)
                {
                    minHeight
                        = item->zOutgoingConnection()->getVerticalLength();
                    next = item;
                }
            }
        }
        if (!next)
        {
            if (sortedCount < items.getEintragAnzahl())
            {
                connectionCount++;
            }
            else
            {
                break;
            }
        }
        else
        {
            next->zOutgoingConnection()->setVx(
                next->zOutgoingConnection()->getVx() + 10 + sortedCount * 11);
            sorted[next->getNodeIndex()] = 1;
            sortedCount++;
        }
    }
    delete[] sorted;
}

const Framework::RCArray<QuestGraphItem>& QuestGraphItemLayer::getItems() const
{
    return items;
}

int QuestGraphItemLayer::getLeyerHeight() const
{
    int start = 0;
    int end = 0;
    bool first = 1;
    for (QuestGraphItem* item : items)
    {
        if (first || item->getY() < start) start = item->getY();
        if (first || item->getY() + item->getHeight() > end)
            end = item->getY() + item->getHeight();
        first = 0;
    }
    return end - start;
}

void QuestGraphItemLayer::centerVertically(int pos)
{
    int height = getLeyerHeight();
    int yOffset = pos - height / 2;
    for (QuestGraphItem* item : items)
    {
        item->setPosition(item->getX(), item->getY() + yOffset);
        item->zIncommingConnection()->layout();
        item->zOutgoingConnection()->layout();
    }
}

void QuestGraphItemLayer::resolveHorizontalConflicts(
    const QuestGraphItemLayer* zNextLayer)
{
    for (QuestGraphItem* item : items)
    {
        int outgoingY = item->getY() + item->getHeight() / 2;
        if (zNextLayer->isHorizontalLineConflict(outgoingY))
        {
            int offset = 0;
            for (int i = 1; i <= 10; i++)
            {
                if (!zNextLayer->isHorizontalLineConflict(outgoingY - i))
				{
					offset = -i;
					break;
                }
                if (!zNextLayer->isHorizontalLineConflict(outgoingY + i))
                {
                    offset = i;
                    break;
                }
            }
            item->setPosition(item->getX(), item->getY() + offset);
            item->zIncommingConnection()->layout();
            item->zOutgoingConnection()->layout();
        }
    }
}

bool QuestGraphItemLayer::isHorizontalLineConflict(int y) const
{
    for (QuestGraphItem* item : items)
    {
        if (item->zIncommingConnection()->isHorizontalLineConflict(y)) return 1;
    }
    return 0;
}

QuestGraph::QuestGraph()
    : ZeichnungHintergrund()
{
    addStyle(ZeichnungHintergrund::Style::Sichtbar
             | ZeichnungHintergrund::Style::Erlaubt
             | ZeichnungHintergrund::Style::Rahmen);
    setRahmenBreite(1);
    setRahmenFarbe(0xFF52525E);
    setMausEreignis(Framework::_ret1ME);
}

bool QuestGraph::tick(double tickVal)
{
    for (QuestGraphItemLayer* layer : layers)
    {
        rend |= layer->tick(tickVal);
    }
    return ZeichnungHintergrund::tick(tickVal);
}

void QuestGraph::render(Framework::Bild& rObj)
{
    if (hatStyle(ZeichnungHintergrund::Style::Sichtbar)
        && layers.getEintragAnzahl() > 0)
    {
        ZeichnungHintergrund::render(rObj);
        if (rObj.setDrawOptions(pos, gr))
        {
            if (rObj.setDrawOptions(getRahmenBreite(),
                    getRahmenBreite(),
                    getInnenBreite(),
                    getInnenHeight()))
            {
                int hScrollOffset = 0;
                if (hatStyle(ZeichnungHintergrund::Style::HScroll)
                    && horizontalScrollBar)
                {
                    hScrollOffset = horizontalScrollBar->getScroll();
                }
                int vScrollOffset = 0;
                if (hatStyle(ZeichnungHintergrund::Style::VScroll)
                    && vertikalScrollBar)
                {
                    vScrollOffset = vertikalScrollBar->getScroll();
                }
                if (hScrollOffset || vScrollOffset)
                {
                    rObj.addScrollOffset(hScrollOffset, vScrollOffset);
                }
                for (QuestGraphItemLayer* layer : layers)
                {
                    layer->render(rObj);
                }
                rObj.releaseDrawOptions();
            }
            rObj.releaseDrawOptions();
        }
    }
}

void QuestGraph::doMausEreignis(Framework::MausEreignis& me, bool userRet)
{
    userRet &= hatStyle(ZeichnungHintergrund::Style::Sichtbar);
    bool vera = me.verarbeitet;
    if (!userRet)
    {
        me.verarbeitet = 1;
    }
    for (QuestGraphItemLayer* layer : layers)
    {
        layer->doMausEreignis(me);
    }
    if (!userRet)
    {
        me.verarbeitet = vera;
    }
}

void QuestGraph::addVirtualConnectionNodes()
{
    int layerIndex = 0;
    // add virtual items for connections that do not go directly to the next
    // layer after this operation each node only have connections to the
    // immediate following layer
    for (QuestGraphItemLayer* layer : layers)
    {
        for (int i = 0; i < layer->getItems().getEintragAnzahl(); i++)
        {
            QuestGraphItem* item = layer->getItems().z(i);
            auto iterator = item->getNextLayersConnections().begin();
            QuestGraphItem* virtualItem = 0;
            while (iterator)
            {
                if (iterator.val().target->getLayerIndex() > layerIndex + 1)
                {
                    if (!virtualItem)
                    {
                        virtualItem = new QuestGraphItem();
                        virtualItem->addPreviousLayerRef(
                            {item, iterator.val().id});
                        virtualItem->addNextLayerRef(
                            {iterator.val().target, iterator.val().id});
                        iterator.val().target->replacePreviousConnections(
                            item, virtualItem);
                        virtualItem->setVirtual(true);
                        virtualItem->calculateLaxerIndex();
                        iterator.set({virtualItem, iterator.val().id});
                        iterator++;
                    }
                    else
                    {
                        virtualItem->addNextLayerRef(
                            {iterator.val().target, iterator.val().id});
                        iterator.val().target->replacePreviousConnections(
                            item, virtualItem);
                        iterator.remove();
                    }
                }
                else if (iterator.val().target->getLayerIndex() < 0)
                { // remove connections to invalid nodes
                    iterator.remove();
                }
                else
                {
                    iterator++;
                }
            }
            if (virtualItem)
            {
                addItem(virtualItem);
            }
        }
        layerIndex++;
    }
}

void QuestGraph::sortItems()
{
    bool changed = 1;
    while (changed)
    {
        changed = 0;
        for (QuestGraphItemLayer* layer : layers)
        {
            changed |= layer->sortItems();
        }
    }
}

void QuestGraph::fixItemPositions()
{
    int height = 0;
    int x = 0;
    for (QuestGraphItemLayer* layer : layers)
    {
        x = layer->fixItemPositions(x);
        if (layer->getLeyerHeight() > height)
        {
            height = layer->getLeyerHeight();
        }
    }
    for (QuestGraphItemLayer* layer : layers)
    {
        layer->sortConnections();
    }
    if (height > getInnenHeight())
    {
        addStyle(ZeichnungHintergrund::Style::VScroll);
        setVertikalKlickScroll(10);
        vertikalScrollBar->update(height, getInnenHeight());
    }
    if (layers.getEintragAnzahl() * 150 - 80 > getInnenBreite())
    {
        addStyle(ZeichnungHintergrund::Style::HScroll);
        setHorizontalKlickScroll(10);
        horizontalScrollBar->update(
            layers.getEintragAnzahl() * 150 - 80, getInnenBreite());
    }
    QuestGraphItemLayer *last = 0;
    for (int i = layers.getEintragAnzahl() - 1; i >= 0; i--)
    {
        QuestGraphItemLayer* layer = layers.z(i);
        layer->centerVertically(getHeight() / 2);
        if (last) layer->resolveHorizontalConflicts(last);
        last = layer;
    }
}

void QuestGraph::addItem(QuestGraphItem* item)
{
    int layerInex = item->getLayerIndex();
    if (layerInex >= 0)
    {
        while (layerInex >= layers.getEintragAnzahl())
        {
            layers.add(new QuestGraphItemLayer());
        }
        layers.z(layerInex)->addItem(item);
    }
    else
    {
        invalidNodes.addItem(item);
    }
}