src/collection/list.hpp

Idź do dokumentacji tego pliku.

/*
 panaLiX, Adrian Panasiuk 2002-5,8
 http://panalix.sourceforge.net/
 ad.ek336@gmail.com
 
 small osdev project
 provided under GPLv3 license.
 */


#ifndef __PANALIX_LIST_HPP
#define __PANALIX_LIST_HPP

#include "src/common/shared.hpp"
#include "src/collection/collection.hpp"

namespace Collection {


   template <typename T>
   struct List {
      struct ListNode {
         struct ListNode *next;
         T v;
      };
      struct ListNode *head, *tail;

      List() : head(null), tail(null) { }

      void push_front(T v) {
         struct ListNode *l = static_cast<struct ListNode*>(Collection::Mem::kmalloc(sizeof(struct ListNode), const_cast<char*>("listnode")));
         l->next=head;
         l->v=v;
         head= l;
         if (tail == null)
            tail= l;
      }
      
      void push_back(T v) {
         struct ListNode *l = static_cast<struct ListNode*>(Collection::Mem::kmalloc(sizeof(struct ListNode), "listnode"));
         l->next=null;
         l->v=v;
         l->tail->next=l;
         tail= l;
      }

      T get_front() {
         return head->v;
      }

      T get_back() {
         return tail->v;
      }

      T pop_front() {
      //throws if list is empty
         T v = head->v;
         struct ListNode *l= head;
         head=head->next;
         if (head==null)
            tail=null;
         Collection::Mem::kfree(l);
         return v;
      }

      //czas liniowy
      //throws if list is empty
      T pop_back() {
         struct ListNode *l;
         T v;
         if (head==tail) {
            v= head->v;
            Collection::Mem::kfree(head);
            head=tail=null;
            return v;
         }
         for (l=head; l->next->next; l=l->next) ;
         v= l->next->v;
         l->next=null;
         Collection::Mem::kfree(tail);
         tail=l;
         return v;
      }

      bool isEmpty() {
         return head==null;
      }

   };
}

#endif

---