/* * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team. * * This file is part of the reasoning system Konclude. * For details and support, see . * * Konclude is free software: you can redistribute it and/or modify * it under the terms of version 3 of the GNU Lesser General Public * License (LGPLv3) as published by the Free Software Foundation. * * Konclude 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 (Lesser) General Public License for more details. * * You should have received a copy of the GNU (Lesser) General Public * License along with Konclude. If not, see . * */ #ifndef KONCLUDE_UTILITIES_CONTAINER_CSORTEDLINKER_CPP #define KONCLUDE_UTILITIES_CONTAINER_CSORTEDLINKER_CPP #include "CSortedLinker.h" namespace Konclude { namespace Utilities { namespace Container { template CSortedLinkerBase::CSortedLinkerBase() : CLinkerBase() { } template CSortedLinkerBase::CSortedLinkerBase(const T& dataElement, CSortedLinkerBase* nextLink) : CLinkerBase(dataElement,nextLink) { } template CSortedLinkerBase::~CSortedLinkerBase() { } template S* CSortedLinkerBase::insertNextSorted(CSortedLinkerBase* nextLink) { CSortedLinkerBase* firstLinker = this; while (nextLink) { CSortedLinkerBase* nIns = nextLink; nextLink = nextLink->getNext(); nIns->setNext(nullptr); CSortedLinkerBase* list = firstLinker; CSortedLinkerBase* lastList = nullptr; bool inserted = false; const T& dataIns = nIns->getData(); while (list) { const T& dataList = list->getData(); // compare items if (isSortedBeforeCompare(dataIns,dataList)) { if (lastList == nullptr){ firstLinker = nIns->insertNext(firstLinker); } else { lastList->insertNext(nIns); } inserted = true; break; } lastList = list; list = (CSortedLinkerBase*)list->next; } if (!inserted) { lastList->insertNext(nIns); } } return (S*)firstLinker; } template S* CSortedLinkerBase::insertSortedNextSorted(CSortedLinkerBase* nextLink) { // items from nextLink are already sorted! CSortedLinkerBase* firstLinker = this; CSortedLinkerBase* list = firstLinker; CSortedLinkerBase* lastList = nullptr; while (nextLink) { CSortedLinkerBase* nIns = nextLink; nextLink = nextLink->getNext(); nIns->setNext(nullptr); bool inserted = false; const T& dataIns = nIns->getData(); while (list) { const T& dataList = list->getData(); if (isSortedBeforeCompare(dataIns,dataList)) { if (lastList == 0){ firstLinker = nIns->insertNext(firstLinker); list = (CSortedLinkerBase*)firstLinker->next; lastList = firstLinker; } else { lastList->insertNext(nIns); lastList = (CSortedLinkerBase*)lastList->next; // list is already on the correct position } inserted = true; break; } lastList = list; list = (CSortedLinkerBase*)list->next; } if (!inserted) { lastList->insertNext(nIns); lastList = nIns; } } return (S*)firstLinker; } template bool CSortedLinkerBase::isSortedBeforeCompare(const T& checkData, const T& linkedData) const { return C::sortedLinkerDataCompare(checkData,linkedData); } }; // end namespace Container }; // end namespace Utilities }; // end namespace Konclude #endif // KONCLUDE_UTILITIES_CONTAINER_CSORTEDLINKER_CPP