Advertisement
drankinatty

C++ Template Singly-Linked List w/Sort

Oct 9th, 2019
401
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. /* linked list node */
  5. template <class T>
  6. struct node_t {
  7.     T data;
  8.     node_t<T> *next;
  9. };
  10.  
  11. /* default compare function for types w/overload (ascending) */
  12. template <typename T>
  13. int compare_asc (const node_t<T> *a, const node_t<T> *b)
  14. {
  15.     return (a->data > b->data) - (a->data < b->data);
  16. }
  17.  
  18. /* compare function for types w/overload (descending) */
  19. template <typename T>
  20. int compare_desc (const node_t<T> *a, const node_t<T> *b)
  21. {
  22.     return (a->data < b->data) - (a->data > b->data);
  23. }
  24.  
  25. template <class T>
  26. class list_t {
  27.     node_t<T> *head, *tail;
  28.     int (*cmp)(const node_t<T>*, const node_t<T>*);
  29.     /* merge lists after mergesort_start */
  30.     node_t<T> *mergesorted (node_t<T> *a, node_t<T> *b);
  31.     void mergesort_run (list_t<T> *l);      /* mergesort function */
  32.  
  33.     public:
  34.     list_t (void);                          /* constructors */
  35.     list_t (int(*f)(const node_t<T>*, const node_t<T>*));
  36.     ~list_t (void);                         /* destructor */
  37.     list_t (const list_t&);                 /* copy constructor */
  38.     /* setter for compare function */
  39.     void setcmp (int (*f)(const node_t<T>*, const node_t<T>*));
  40.  
  41.     node_t<T> *addnode (T data);            /* simple add at end */
  42.     node_t<T> *addinorder (T data);         /* add in order */
  43.     void delnode (T data);                  /* delete node */
  44.     void prnlist (const char *delim = " "); /* print delim separated */
  45.     void prnfixed (const size_t w = 4, const char *delim = " ");
  46.  
  47.     list_t split (void);                    /* split list ~ 1/2 */
  48.     void join (list_t<T>&l);                /* join list l at end */
  49.  
  50.     void insertionsort (void);              /* insertion sort list */
  51.     void mergesort (void);                  /* wrapper for mergesort */
  52. };
  53.  
  54. /* constructor (default) */
  55. template <class T>
  56. list_t<T>::list_t (void)
  57. {
  58.     head = tail = nullptr;
  59.     cmp = compare_asc;
  60. }
  61.  
  62. /* constructor taking compare function as argument */
  63. template <class T>
  64. list_t<T>::list_t (int(*f)(const node_t<T>*, const node_t<T>*))
  65. {
  66.     head = tail = nullptr;
  67.     cmp = f;
  68. }
  69.  
  70. /* destructor free all list memory */
  71. template <class T>
  72. list_t<T>::~list_t (void)
  73. {
  74.     node_t<T> *pn = head;
  75.     while (pn) {
  76.         node_t<T> *victim = pn;
  77.         pn = pn->next;
  78.         delete victim;
  79.     }
  80. }
  81.  
  82. /* copy ctor - copy exising list */
  83. template <class T>
  84. list_t<T>::list_t (const list_t& l)
  85. {
  86.     cmp = l.cmp;                        /* assign compare function ptr */
  87.     head = tail = nullptr;              /* initialize head/tail */
  88.  
  89.     /* copy data to new list */
  90.     for (node_t<T> *pn = l.head; pn; pn = pn->next)
  91.         this->addnode (pn->data);
  92. }
  93.  
  94. /* setter compare function */
  95. template <class T>
  96. void list_t<T>::setcmp (int(*f)(const node_t<T>*, const node_t<T>*))
  97. {
  98.     cmp = f;
  99. }
  100.  
  101.  
  102. /* add using tail ptr */
  103. template <class T>
  104. node_t<T> *list_t<T>::addnode (T data)
  105. {
  106.     node_t<T> *node = new node_t<T>;        /* allocate/initialize node */
  107.     node->data = data;
  108.     node->next = nullptr;
  109.  
  110.     if (!head)
  111.         head = tail = node;
  112.     else {
  113.         tail->next = node;
  114.         tail = node;
  115.     }
  116.  
  117.     return node;
  118. }
  119.  
  120. template <class T>
  121. node_t<T> *list_t<T>::addinorder (T data)
  122. {
  123.     if (!cmp) {     /* validate compare function not nullptr */
  124.         std::cerr << "error: compare is nullptr.\n";
  125.         return nullptr;
  126.     }
  127.  
  128.     node_t<T> *node = new node_t<T>;        /* allocate/initialize node */
  129.     node->data = data;
  130.     node->next = nullptr;
  131.  
  132.     node_t<T> **ppn = &head,                /* ptr-to-ptr to head */
  133.               *pn = head;                   /* ptr to head */
  134.  
  135.     while (pn && cmp (node, pn) > 0) {      /* node sorts after current */
  136.         ppn = &pn->next;                    /* ppn to address of next */
  137.         pn = pn->next;                      /* advance pointer to next */
  138.     }
  139.  
  140.     node->next = pn;                        /* set node->next to next */
  141.     if (pn == nullptr)
  142.         tail = node;
  143.     *ppn = node;                            /* set current to node */
  144.  
  145.     return node;                            /* return node */
  146. }
  147.  
  148. template <class T>
  149. void list_t<T>::delnode (T data)
  150. {
  151.     node_t<T> **ppn = &head;        /* pointer to pointer to node */
  152.     node_t<T> *pn = head;           /* pointer to node */
  153.  
  154.     for (; pn; ppn = &pn->next, pn = pn->next) {
  155.         if (pn->data == data) {
  156.             *ppn = pn->next;        /* set address to next */
  157.             delete pn;
  158.             break;
  159.         }
  160.     }
  161. }
  162.  
  163. template <class T>
  164. void list_t<T>::prnlist (const char *delim)
  165. {
  166.     if (!head) {
  167.         std::cout << "empty-list\n";
  168.         return;
  169.     }
  170.     for (node_t<T> *pn = head; pn; pn = pn->next)
  171.         pn == head ? std::cout << pn->data : std::cout << delim << pn->data;
  172.     std::cout << '\n';
  173. }
  174.  
  175. template <class T>
  176. void list_t<T>::prnfixed (const size_t w, const char *delim)
  177. {
  178.     size_t c = 0;
  179.  
  180.     if (!head) {
  181.         std::cout << "empty-list\n";
  182.         return;
  183.     }
  184.     for (node_t<T> *pn = head; pn; pn = pn->next, c++) {
  185.         if (c && c % 20 == 0)
  186.             std::cout << '\n';
  187.         // pn == head ? std::cout << std::setw(w) << pn->data : std::cout << delim << std::setw(w) << pn->data;
  188.         std::cout << delim << std::setw(w) << pn->data;
  189.     }
  190.     std::cout << '\n';
  191. }
  192.  
  193. /* split list l into lists a & b */
  194. template <class T>
  195. list_t<T> list_t<T>::split (void)
  196. {
  197.     list_t<T> s;                /* new instance of class */
  198.  
  199.     node_t<T> *pa = head,       /* pointer to current head */
  200.             *pb = pa->next;     /* 2nd pointer to double-advance */
  201.  
  202.     while (pb) {                /* while not end of list */
  203.         pb = pb->next;          /* advance 2nd ptr */
  204.         if (pb) {               /* if not nullptr */
  205.             pa = pa->next;      /* advance current ptr */
  206.             pb = pb->next;      /* advance 2nd ptr again */
  207.         }
  208.     }
  209.  
  210.     s.tail = tail;              /* 2nd half tail will be current tail */
  211.     tail = pa;                  /* current tail is at pa */
  212.  
  213.     s.head = pa->next;          /* 2nd half head is next ptr */
  214.     pa->next = nullptr;         /* set next ptr NULL to end 1st 1/2 */
  215.  
  216.     return s;                   /* return new instance */
  217. }
  218.  
  219. /** join two lists setting head to nullptr
  220.  *  on the list that was joined to prevent destructor
  221.  *  from being called.
  222.  */
  223. template <class T>
  224. void list_t<T>::join (list_t<T>&l) {
  225.     this->tail->next = l.head;
  226.     this->tail = l.tail;
  227.     l.head = nullptr;
  228. }
  229.  
  230. /** insertion sort of linked list.
  231.  *  re-orders list in sorted order.
  232.  */
  233. template <class T>
  234. void list_t<T>::insertionsort (void)
  235. {
  236.     if (!cmp) {     /* validate compare function not nullptr */
  237.         std::cerr << "error: compare is nullptr.\n";
  238.         return;
  239.     }
  240.  
  241.     node_t<T> *sorted = head,       /* initialize sorted list to 1st node */
  242.               *pn = head->next;     /* advance original list node to next */
  243.  
  244.     sorted->next = NULL;            /* initialize sorted->next to NULL */
  245.  
  246.     while (pn) {                    /* iterate over existing from 2nd node */
  247.         node_t<T> **pps = &sorted,  /* ptr-to-ptr to sorted list */
  248.                 *ps = *pps,         /* ptr to sorted list */
  249.                 *next = pn->next;   /* save list next as separate pointer */
  250.  
  251.         while (ps && cmp(ps, pn) < 0) {  /* loop until sorted */
  252.             pps = &ps->next;        /* get address of next node */
  253.             ps = ps->next;          /* get next node pointer */
  254.         }
  255.  
  256.         *pps = pn;          /* insert existing in sort order as current */
  257.         pn->next = ps;      /* set next as sorted next */
  258.         pn = next;          /* reinitialize existing pointer to next */
  259.     }
  260.  
  261.     head = sorted;          /* update head to sorted head */
  262.  
  263.     /* set tail pointer to last node after sort */
  264.     for (pn = head; pn; pn = pn->next)
  265.         tail = pn;
  266. }
  267.  
  268. /** merge sublists in sort order */
  269. template <class T>
  270. node_t<T> *list_t<T>::mergesorted (node_t<T> *a, node_t<T> *b)
  271. {
  272.     node_t<T> *result = nullptr;
  273.  
  274.     /* Base cases */
  275.     if (!a)
  276.         return (b);
  277.     else if (!b)
  278.         return (a);
  279.  
  280.     /* Pick either a or b, and recur */
  281.     // if (a->data <= b->data) {
  282.     // if (compare_asc (a, b) <= 0) {
  283.     if (cmp (a, b) <= 0) {
  284.         result = a;
  285.         result->next = mergesorted (a->next, b);
  286.     }
  287.     else {
  288.         result = b;
  289.         result->next = mergesorted (a, b->next);
  290.     }
  291.  
  292.     return result;
  293. }
  294.  
  295. /* split list into sublists to be sorted when merged */
  296. template <class T>
  297. void list_t<T>::mergesort_run (list_t<T> *l)
  298. {
  299.     /* Base case -- length 0 or 1 */
  300.     if (!l->head || !l->head->next) {
  301.         return;
  302.     }
  303.  
  304.     /* Split head into 'a' and 'b' sublists */
  305.     list_t<T> la = l->split();
  306.  
  307.     /* Recursively sort the sublists */
  308.     mergesort_run(l);
  309.     mergesort_run(&la);
  310.  
  311.     /* merge the two sorted lists together */
  312.     l->head = mergesorted (l->head, la.head);
  313.  
  314.     /* set la.head NULL to prevent destructor from running */
  315.     la.head = nullptr;
  316. }
  317.  
  318. template <class T>
  319. void list_t<T>::mergesort(void)
  320. {
  321.     if (!cmp) {     /* validate compare function not nullptr */
  322.         std::cerr << "error: compare is nullptr.\n";
  323.         return;
  324.     }
  325.  
  326.     mergesort_run (this);
  327.  
  328.     /* set tail pointer to last node after sort */
  329.     for (node_t<T> *pn = head; pn; pn = pn->next)
  330.         tail = pn;
  331. }
  332.  
  333. int main (void) {
  334.  
  335.     list_t<int> l;
  336.  
  337.     int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,
  338.                   2, 9, 1, 13, 17, 6, 15, 5, 3, 18};
  339.     unsigned asz = sizeof arr / sizeof *arr;
  340.  
  341.     for (unsigned i = 0; i < asz; i++)
  342.         l.addnode (arr[i]);
  343.  
  344.     l.prnlist();
  345. #ifndef INSSORT
  346.     l.mergesort();
  347. #else
  348.     l.insertionsort();
  349. #endif
  350.     l.prnlist();
  351.  
  352.     l.setcmp (compare_desc);
  353. #ifndef INSSORT
  354.     l.mergesort();
  355. #else
  356.     l.insertionsort();
  357. #endif
  358.     l.prnlist();
  359. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement