Skip to content

Instantly share code, notes, and snippets.

@Fs02

Fs02/Multilist.cpp

Last active December 25, 2015 14:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Fs02/dd3e224b7c8e92c05410 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Fs02/dd3e224b7c8e92c05410 to your computer and use it in GitHub Desktop.
Download ZIP
Multilist
Raw
main.cpp
#include "multilist.hpp"
#include <iostream>
using namespace std;
int main()
{
cout << "Hello World!" << endl;
Multilist::Multilist m;
Multilist::insertFirst(m, new Multilist::Element(10));
Multilist::insertAfter(m, new Multilist::Element(30), m.first);
Multilist::insertLast(m, new Multilist::Element(40));
Multilist::insertFirst(m.first->child, new Multilist::Element(20));
Multilist::insertAfter(m.first->child, new Multilist::Element(20), m.first->child.first);
Multilist::insertLast(m.first->child, new Multilist::Element(20));
if (Multilist::find(m, 10)) cout<<"as";
if (Multilist::find(m.first->child, 280)) cout<<"bs";
Multilist::delFirst(m);
if (Multilist::find(m, 10)) cout<<"as";
return 0;
}
Raw
Multilist.cpp
#include "multilist.hpp"
bool Multilist::isEmpty(const Multilist &list)
{
return list.first == nullptr;
}
bool Multilist::isEmpty(const Childlist &list)
{
return list.first == nullptr;
}
bool Multilist::find(Element *first, Element *target)
{
for (auto it = first; it != nullptr; it = it->next)
if (it == target) return true;
return false;
}
Multilist::Element* Multilist::find(Element *first, infoType info)
{
for (auto it = first; it != nullptr; it = it->next)
if (it->info == info) return it;
return nullptr;
}
Multilist::parentElm* Multilist::find(const Multilist &list, infoType info)
{
return static_cast<parentElm*>(find(list.first, info));
}
Multilist::Element* Multilist::find(const Childlist &list, infoType info)
{
return find(list.first, info);
}
void Multilist::insert(Element *first, Element* last, Element *newElm, Element *flag, int index)
{
if (!first) return;
// is it insert last
auto it = first;
if (flag == last){
it = last;
} else {
for ( ; it != nullptr; it = it->next)
if (it == flag) break;
}
// insert before or after
it = (index < 0 && it->prev) ? it->prev : it;
newElm->next = it->next;
newElm->prev = it;
if (it->next) it->next->prev = newElm;
it->next = newElm;
}
void Multilist::insertFirst(Multilist &list, Element *elm)
{
auto pElm = static_cast<parentElm*>(elm);
pElm->child = Childlist();
if (isEmpty(list)) list.first = list.last = pElm;
else insert(list.first, list.last, pElm, list.first, -1);
}
void Multilist::insertFirst(Childlist &list, Element *elm)
{
if (isEmpty(list)) list.first = list.last = elm;
else insert(list.first, list.last, elm, list.first, -1);
}
void Multilist::insertAfter(Multilist &list, Element *elm, Element* flag)
{
auto pElm = static_cast<parentElm*>(elm);
pElm->child = Childlist();
if (isEmpty(list)) list.first = list.last = pElm;
else insert(list.first, list.last, pElm, flag);
}
void Multilist::insertAfter(Childlist &list, Element *elm, Element *flag)
{
if (isEmpty(list)) list.first = list.last = elm;
else insert(list.first, list.last, elm, flag);
}
void Multilist::insertLast(Multilist &list, Element *elm)
{
auto pElm = static_cast<parentElm*>(elm);
pElm->child = Childlist();
if (isEmpty(list)) list.first = list.last = pElm;
else insert(list.first, list.last, pElm, list.last);
}
void Multilist::insertLast(Childlist &list, Element *elm)
{
if (isEmpty(list)) list.first = list.last = elm;
else insert(list.first, list.last, elm, list.last);
}
void Multilist::del(Element *first, Element *toDel)
{
if (!find(first, toDel) && !toDel) return;
if (toDel->prev) toDel->prev->next = toDel->next;
if (toDel->next) toDel->next->prev = toDel->prev;
delete toDel;
}
void Multilist::delFirst(Multilist &list)
{
if (isEmpty(list)) return;
auto newFirst = list.first->next;
del(list.first, list.first);
list.first = (parentElm*)newFirst;
}
void Multilist::delFirst(Childlist &list)
{
if (isEmpty(list)) return;
auto newFirst = list.first->next;
del(list.first, list.first);
list.first = newFirst;
}
void Multilist::delAfter(Multilist &list, Element *flag)
{
del(list.first, flag->next);
}
void Multilist::delAfter(Childlist &list, Element *flag)
{
del(list.first, flag->next);
}
void Multilist::delLast(Multilist &list)
{
if (isEmpty(list)) return;
auto newLast = list.last->prev;
del(list.first, list.last);
list.last = (parentElm*)newLast;
}
void Multilist::delLast(Childlist &list)
{
if (isEmpty(list)) return;
auto newLast = list.last->prev;
del(list.first, list.last);
list.last = newLast;
}
Raw
Multilist.hpp
#ifndef MULTILIST_HPP
#define MULTILIST_HPP
namespace Multilist
{
/*!
* \brief infoType
* another name for int
*/
typedef int infoType;
/*!
* \brief The Element struct
*/
struct Element
{
Element(infoType _info) : info(_info)
{}
infoType info = 0;
Element* next = nullptr;
Element* prev = nullptr;
};
/*!
* \brief The Childlist struct
*/
struct Childlist
{
Element* first = nullptr;
Element* last = nullptr;
};
/*!
* \brief The parentElm struct
*/
struct parentElm : public Element
{
Childlist child = Childlist();
};
/*!
* \brief The Multilist struct
*/
struct Multilist
{
parentElm* first = nullptr;
parentElm* last = nullptr;
};
/*!
* \brief isEmpty
* \param list to be checked
* \return true if list is empty
*/
bool isEmpty(const Multilist& list);
/*!
* \brief isEmpty
* \param list to be checed
* \return true if list is empty
*/
bool isEmpty(const Childlist& list);
/*!
* \brief find, basic helper function to check any element in a list
* \param first element of the list
* \param target element to be searched
* \return true is element is part of the list
*/
bool find(Element *first, Element* target);
/*!
* \brief find, basic helper function to check any value in a list
* \param first element of the list
* \param info to be searched
* \return pointer to element of info
*/
Element* find(Element* first, infoType info);
/*!
* \brief find an element in a list
* \param host list
* \param info to be checked
* \return pointer to element of info
*/
parentElm* find(const Multilist& list, infoType info);
/*!
* \brief find an element in a list
* \param host list
* \param info to be checked
* \return pointer to element of info
*/
Element* find(const Childlist& list, infoType info);
/*!
* \brief helper function to insert element to a list
* \param first element of the list
* \param last element of the list
* \param Element to be inserted
* \param Element flag
* \param index, negative mean before flag
*/
void insert(Element* first, Element* last, Element* newElm, Element* flag, int index = 0);
/*!
* \brief Insert element to the list's first
* \param target list
* \param Element to be inserted
*/
void insertFirst(Multilist& list, Element* elm);
/*!
* \brief Insert element to the list's first
* \param target list
* \param Element to be inserted
*/
void insertFirst(Childlist& list, Element* elm);
/*!
* \brief Insert element to after an element
* \param target list
* \param Element to be inserted
*/
void insertAfter(Multilist& list, Element* elm, Element* flag);
/*!
* \brief Insert element to list's last
* \param target list
* \param Element to be inserted
* \param flag
*/
void insertAfter(Childlist& list, Element* elm, Element* flag);
/*!
* \brief Insert element to list's last
* \param target list
* \param Element to be inserted
* \param flag
*/
void insertLast(Multilist& list, Element* elm);
/*!
* \brief Insert element to list's last
* \param target list
* \param Element to be inserted
*/
void insertLast(Childlist& list, Element* elm);
/*!
* \brief Delete helper function
* \param first element of list
* \param element to delete
*/
void del(Element* first, Element* toDel);
/*!
* \brief Delete first element of list
* \param list
*/
void delFirst(Multilist& list);
/*!
* \brief Delete first element of list
* \param list
*/
void delFirst(Childlist& list);
/*!
* \brief Delete element After
* \param list
* \param flag
*/
void delAfter(Multilist& list, Element* flag);
/*!
* \brief Delete element After
* \param list
* \param flag
*/
void delAfter(Childlist& list, Element* flag);
/*!
* \brief Delete last element of list
* \param list
*/
void delLast(Multilist& list);
/*!
* \brief Delete last element of list
* \param list
*/
void delLast(Childlist& list);
}
#endif // MULTILIST_HPP
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment