/*
* 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_CSORTEDLINKER_H
#define KONCLUDE_UTILITIES_CSORTEDLINKER_H
// Libraries includes
#include
// Namespace includes
#include "CAllocationObject.h"
// Other includes
// Logger includes
#include "Logger/CLogger.h"
namespace Konclude {
namespace Utilities {
template class CSortedLinker;
/*!
*
* \class CSortedLinker
* \author Andreas Steigmiller
* \version 0.1
* \brief Spezialised Pointer Version to avoid comparison between addresses
*
*/
template
class CSortedLinker : public CAllocationObject {
// public methods
public:
//! Constructor
CSortedLinker();
CSortedLinker(T* dataElement, CSortedLinker *nextLink = 0);
//! Destructor
virtual ~CSortedLinker();
CSortedLinker *init(T* dataElement, CSortedLinker *nextLink = 0);
bool hasNext();
CSortedLinker *insertSortedNextSorted(CSortedLinker *nextLink);
CSortedLinker *insertNextSorted(CSortedLinker *nextLink);
CSortedLinker *insertNext(CSortedLinker *nextLink);
CSortedLinker *getNext();
CSortedLinker *setNext(CSortedLinker *nextLink);
T* getData();
CSortedLinker *setData(T* dataElement);
CSortedLinker *append(CSortedLinker *appendingList);
CSortedLinker *removeNext();
CSortedLinker *removeOne(T* dataElement);
CSortedLinker *removeAll(T* dataElement);
CSortedLinker *getLastListLink();
// protected methods
protected:
// private methods
private:
// private variables
private:
CSortedLinker *next;
T* data;
};
template
CSortedLinker::CSortedLinker() {
next = 0;
}
template
CSortedLinker::CSortedLinker(T* dataElement, CSortedLinker *nextLink) {
next = 0;
setNext(nextLink);
data = dataElement;
}
template
CSortedLinker *CSortedLinker::init(T* dataElement, CSortedLinker *nextLink) {
next = 0;
setNext(nextLink);
data = dataElement;
return this;
}
template
CSortedLinker::~CSortedLinker() {
}
template
bool CSortedLinker::hasNext() {
return next != 0;
}
template
CSortedLinker *CSortedLinker::insertNext(CSortedLinker *nextLink) {
if (nextLink) {
CSortedLinker *tmpNext = next;
next = nextLink;
if (tmpNext) {
nextLink->append(tmpNext);
}
}
return this;
}
template
CSortedLinker *CSortedLinker::insertNextSorted(CSortedLinker *nextLink) {
CSortedLinker *firstLinker = this;
while (nextLink) {
CSortedLinker *nIns = nextLink;
if (nextLink->hasNext()) {
nextLink = nextLink->getNext();
} else {
nextLink = 0;
}
nIns->setNext(0);
CSortedLinker *list = firstLinker;
CSortedLinker *lastList = 0;
bool inserted = false;
T* dataIns = nIns->getData();
while (list) {
T* dataList = list->getData();
if (*dataIns <= *dataList) {
if (lastList == 0){
firstLinker = nIns->insertNext(firstLinker);
} else {
lastList->insertNext(nIns);
}
inserted = true;
break;
}
lastList = list;
list = list->next;
}
if (!inserted) {
lastList->insertNext(nIns);
}
}
return firstLinker;
}
template
CSortedLinker *CSortedLinker::insertSortedNextSorted(CSortedLinker *nextLink) {
// items from nextLink are already sorted!
CSortedLinker *firstLinker = this;
CSortedLinker *list = firstLinker;
CSortedLinker *lastList = 0;
while (nextLink) {
CSortedLinker *nIns = nextLink;
if (nextLink->hasNext()) {
nextLink = nextLink->getNext();
} else {
nextLink = 0;
}
nIns->setNext(0);
bool inserted = false;
T* dataIns = nIns->getData();
while (list) {
T* dataList = list->getData();
if (*dataIns <= *dataList) {
if (lastList == 0){
firstLinker = nIns->insertNext(firstLinker);
list = firstLinker->next;
lastList = firstLinker;
} else {
lastList->insertNext(nIns);
lastList = lastList->next;
// list is already on the correct position
}
inserted = true;
break;
}
lastList = list;
list = list->next;
}
if (!inserted) {
lastList->insertNext(nIns);
}
}
return firstLinker;
}
template
CSortedLinker *CSortedLinker::setNext(CSortedLinker *nextLink) {
next = nextLink;
return this;
}
template
CSortedLinker *CSortedLinker::getNext() {
return next;
}
template
T* CSortedLinker::getData() {
return data;
}
template
CSortedLinker *CSortedLinker::setData(T* dataElement) {
data = dataElement;
return this;
}
template
CSortedLinker *CSortedLinker::append(CSortedLinker *appendingList) {
CSortedLinker *last = getLastListLink();
last->insertNext(appendingList);
return this;
}
template
CSortedLinker *CSortedLinker::removeNext() {
CSortedLinker *tmpNext = next;
if (next) {
CSortedLinker *tmpNextNext = next->next;
next->next = 0;
setNext(tmpNextNext);
}
return tmpNext;
}
template
CSortedLinker *CSortedLinker::removeOne(T* dataElement) {
CSortedLinker *loc = this;
if (loc->getData() == dataElement) {
loc = loc->getNext();
return loc;
} else {
while (loc) {
CSortedLinker *nxt = loc->getNext();
if (nxt) {
if (nxt->getData() == dataElement) {
loc->setNext(nxt->getNext());
return this;
}
}
loc = loc->getNext();
}
}
return this;
}
template
CSortedLinker *CSortedLinker::removeAll(T* dataElement) {
CSortedLinker *loc = this;
if (loc->getData() == dataElement) {
loc = loc->getNext();
return loc;
} else {
while (loc) {
CSortedLinker *nxt = loc->getNext();
if (nxt) {
if (nxt->getData() == dataElement) {
loc->setNext(nxt->getNext());
}
}
loc = loc->getNext();
}
}
return this;
}
template
CSortedLinker *CSortedLinker::getLastListLink() {
CSortedLinker *lastListLink = this;
while (lastListLink->hasNext()) {
lastListLink = lastListLink->getNext();
}
return lastListLink;
}
/*!
*
* \class CSortedLinker
* \author Andreas Steigmiller
* \version 0.1
* \brief TODO
*
*/
template
class CSortedLinker : public CAllocationObject {
// public methods
public:
//! Constructor
CSortedLinker();
CSortedLinker(T dataElement, CSortedLinker *nextLink = 0);
//! Destructor
virtual ~CSortedLinker();
CSortedLinker *init(T dataElement, CSortedLinker *nextLink = 0);
bool hasNext();
CSortedLinker *insertSortedNextSorted(CSortedLinker *nextLink);
CSortedLinker *insertNextSorted(CSortedLinker *nextLink);
CSortedLinker *insertNext(CSortedLinker *nextLink);
CSortedLinker *getNext();
CSortedLinker *setNext(CSortedLinker *nextLink);
T getData();
CSortedLinker *setData(T dataElement);
CSortedLinker *append(CSortedLinker *appendingList);
CSortedLinker *removeNext();
CSortedLinker *getLastListLink();
CSortedLinker *removeOne(T dataElement);
CSortedLinker *removeAll(T dataElement);
// protected methods
protected:
// private methods
private:
// private variables
private:
CSortedLinker *next;
T data;
};
template
CSortedLinker::CSortedLinker() {
next = 0;
}
template
CSortedLinker::CSortedLinker(T dataElement, CSortedLinker *nextLink) {
next = 0;
setNext(nextLink);
data = dataElement;
}
template
CSortedLinker *CSortedLinker::init(T dataElement, CSortedLinker *nextLink) {
next = 0;
setNext(nextLink);
data = dataElement;
return this;
}
template
CSortedLinker::~CSortedLinker() {
}
template
bool CSortedLinker::hasNext() {
return next != 0;
}
template
CSortedLinker *CSortedLinker::insertNext(CSortedLinker *nextLink) {
if (nextLink) {
CSortedLinker *tmpNext = next;
next = nextLink;
if (tmpNext) {
nextLink->append(tmpNext);
}
}
return this;
}
template
CSortedLinker *CSortedLinker::insertNextSorted(CSortedLinker *nextLink) {
CSortedLinker *firstLinker = this;
while (nextLink) {
CSortedLinker *nIns = nextLink;
if (nextLink->hasNext()) {
nextLink = nextLink->getNext();
} else {
nextLink = 0;
}
nIns->setNext(0);
CSortedLinker *list = firstLinker;
CSortedLinker *lastList = 0;
bool inserted = false;
T dataIns = nIns->getData();
while (list) {
T dataList = list->getData();
if (dataIns <= dataList) {
if (lastList == 0){
firstLinker = nIns->insertNext(firstLinker);
} else {
lastList->insertNext(nIns);
}
inserted = true;
break;
}
lastList = list;
list = list->next;
}
if (!inserted) {
lastList->insertNext(nIns);
}
}
return firstLinker;
}
template
CSortedLinker *CSortedLinker::insertSortedNextSorted(CSortedLinker *nextLink) {
// items from nextLink are already sorted!
CSortedLinker *firstLinker = this;
CSortedLinker *list = firstLinker;
CSortedLinker *lastList = 0;
while (nextLink) {
CSortedLinker *nIns = nextLink;
if (nextLink->hasNext()) {
nextLink = nextLink->getNext();
} else {
nextLink = 0;
}
nIns->setNext(0);
bool inserted = false;
T dataIns = nIns->getData();
while (list) {
T dataList = list->getData();
if (dataIns <= dataList) {
if (lastList == 0){
firstLinker = nIns->insertNext(firstLinker);
list = firstLinker->next;
lastList = firstLinker;
} else {
lastList->insertNext(nIns);
lastList = lastList->next;
// list is already on the correct position
}
inserted = true;
break;
}
lastList = list;
list = list->next;
}
if (!inserted) {
lastList->insertNext(nIns);
}
}
return firstLinker;
}
template
CSortedLinker *CSortedLinker::setNext(CSortedLinker *nextLink) {
next = nextLink;
return this;
}
template
CSortedLinker *CSortedLinker::getNext() {
return next;
}
template
T CSortedLinker::getData() {
return data;
}
template
CSortedLinker *CSortedLinker::setData(T dataElement) {
data = dataElement;
return this;
}
template
CSortedLinker *CSortedLinker::append(CSortedLinker *appendingList) {
CSortedLinker *last = getLastListLink();
last->insertNext(appendingList);
return this;
}
template
CSortedLinker *CSortedLinker::removeNext() {
CSortedLinker *tmpNext = next;
if (next) {
CSortedLinker *tmpNextNext = next->next;
next->next = 0;
setNext(tmpNextNext);
}
return tmpNext;
}
template
CSortedLinker *CSortedLinker::removeOne(T dataElement) {
CSortedLinker *loc = this;
if (loc->getData() == dataElement) {
loc = loc->getNext();
return loc;
} else {
while (loc) {
CSortedLinker *nxt = loc->getNext();
if (nxt) {
if (nxt->getData() == dataElement) {
loc->setNext(nxt->getNext());
return this;
}
}
loc = loc->getNext();
}
}
return this;
}
template
CSortedLinker *CSortedLinker::removeAll(T dataElement) {
CSortedLinker *loc = this;
if (loc->getData() == dataElement) {
loc = loc->getNext();
return loc;
} else {
while (loc) {
CSortedLinker *nxt = loc->getNext();
if (nxt) {
if (nxt->getData() == dataElement) {
loc->setNext(nxt->getNext());
}
}
loc = loc->getNext();
}
}
return this;
}
template
CSortedLinker *CSortedLinker::getLastListLink() {
CSortedLinker *lastListLink = this;
while (lastListLink->hasNext()) {
lastListLink = lastListLink->getNext();
}
return lastListLink;
}
}; // end namespace Utilities
}; // end namespace Konclude
#endif // KONCLUDE_UTILITIES_CSortedLinker_H