Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Feb 10th, 2010  |  syntax: C++  |  size: 7.12 KB  |  hits: 69  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef _SALIST_H
  2. #define _SALIST_H
  3.  
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <cstring>
  8. using namespace std;
  9.  
  10. template <class T>
  11. class SAList;
  12.  
  13. template<class T>
  14. class Node
  15. {
  16.     //data=Stores information of almost any data type- ie. char, int, double, etc
  17.     //prev=the current node previous node
  18.     //next=the current node next node
  19. //    T data_;
  20. //    Node<T> *prev_;
  21. //    Node<T> *next_;
  22.  
  23. public:
  24.     T data_;
  25.     Node<T> *prev_;
  26.     Node<T> *next_;
  27.     //Functions to return addresses of next and prev nodes and also to return a
  28.     // reference of whatever is in data. Made class SAList a friend in order to
  29.     //use the class to manipulate data within the double link list
  30.     Node(T);
  31.     const Node<T>* next() const;
  32.     const Node<T>* prev() const;
  33.     const T& data() const;
  34.     template <class U> friend class SAList;
  35.  
  36. };
  37.  
  38. template<class T>
  39. class SAList
  40. {
  41.     //front=pointed to the front of the double link list
  42.     //back=pointed to the back of the double link list
  43.   //  Node<T> *head;
  44.   //  Node<T> *tail;
  45. public:
  46.     Node<T> *head;
  47.     Node<T> *tail;
  48.     SAList();
  49.     SAList(T*, int);
  50.     SAList(const SAList&);
  51.     SAList<T>& operator= (SAList<T> &);
  52.     ~SAList();
  53.  
  54.     bool isEmpty() const;
  55.     void insert(const T& data);
  56.     bool remove(const T& key, bool (*match)(const T&,const T&));
  57.     bool get(T passback[], int max) const;
  58.     Node<T>* search(const T& key, bool (*match)(const T&,const T&));
  59. };
  60.  
  61. //
  62. template<class T>
  63. Node<T>::Node(T info) {
  64.     prev_=NULL;
  65.     next_=NULL;
  66.     data_=info;
  67. }
  68.  
  69. template<class T>
  70. const Node<T>* Node<T>::next() const
  71. {
  72.     return next_;
  73. }
  74.  
  75. template<class T>
  76. const Node<T>* Node<T>::prev() const
  77. {
  78.     return prev_;
  79. }
  80. template<class T>
  81. const T & Node<T>::data() const
  82. {
  83.    // data_ = data;
  84.     return data_;
  85. }
  86.  
  87. template<class T>
  88. SAList<T>::SAList()
  89. {
  90.     head = NULL;
  91.     tail = NULL;
  92. }
  93.  
  94. template<class T>
  95. SAList<T>::SAList(T* info, int size)
  96. {
  97.     int i;  //Counter
  98.     Node<T> *temp;
  99.     Node<T> *add;
  100.  
  101.         for(i=0;i<=size-1;i++)
  102.     {
  103.                 add=new Node<T>(info[i]);
  104.  
  105.                 if(head==NULL)
  106.                 {
  107.                         head=add;
  108.                 //      add->prev_=tail;
  109.                         temp=head;
  110.                 }
  111.                 else
  112.                 {
  113.                         if(i==(size-1))
  114.                                 tail=add;
  115.  
  116.                         if(temp->next_==NULL)
  117.                         {
  118.                                 temp->next_=add;
  119.                                 add->prev_=temp;
  120.                                 temp=temp->next;
  121.                         }
  122.                 }
  123.     }
  124. }
  125.  
  126. template<class T>
  127. SAList<T>::SAList(const SAList<T> &right)
  128. {
  129.     Node<T> *current;
  130.     Node<T> *previous;
  131.     head = new Node<T>(right.head->data_);
  132.     current = right.head->next_;
  133.     while(current != NULL) {
  134.         Node<T>* temp = new Node<T>(current->data_);
  135.         if(head->next_ == NULL){
  136.             head->next_ = temp;
  137.             temp->prev_ = head;
  138.             previous = temp;
  139.         }
  140.         else{
  141.          temp->prev_ = previous;
  142.          previous->next_ = temp;
  143.          previous = temp;
  144.       }
  145.       current = current->next_;
  146.    }
  147. }
  148.  
  149. template <class T>
  150. SAList<T>& SAList<T>::operator= (SAList<T> &right){
  151.         Node<T> *cur;
  152.         Node<T> *temp;
  153.         Node<T> *add;
  154.  
  155.         cur = right.head;
  156.  
  157.         while(cur != NULL)
  158.         {
  159.                 add=new Node<T>(cur->data_);
  160.  
  161.                 if(this->head==NULL)
  162.                 {
  163.                         head = add;
  164.                         add->prev_ = tail;
  165.                         cur = cur->next_;
  166.                         temp = head;
  167.                 }
  168.                 else
  169.                 {
  170.                         if(cur->next_==right.tail)
  171.                         {
  172.                                 temp->next_=add;
  173.                                 add->prev_=temp;
  174.                                 tail=temp;
  175.  
  176.                                 temp=temp->next_;
  177.                                 cur=cur->next_;
  178.                         }
  179.  
  180.                         if(temp->next_==NULL)
  181.                         {
  182.                                 temp->next_=add;
  183.                                 add->prev_=temp;
  184.  
  185.                                 temp=temp->next_;
  186.                                 cur=cur->next_;
  187.                         }
  188.                 }
  189.         }
  190.         return *this;
  191. }
  192.  
  193. template<class T>
  194. SAList<T>::~SAList()
  195. {
  196.         Node<T> *temp;
  197.         while(head)
  198.         {
  199.                 temp=head;
  200.                 head=head->next_;
  201.                 delete temp;
  202.         }
  203. }
  204.  
  205. template<class T>
  206. bool SAList<T>::isEmpty() const
  207. {
  208.     //check is used to return true or false based on whether the list is empty
  209.     //or not
  210.     bool check;
  211.  
  212.     if(head!=NULL)
  213.     {
  214.         check=false;
  215.     }
  216.     else
  217.     {
  218.         check=true;
  219.     }
  220.  
  221.     return check;
  222. }
  223.  
  224. template<class T>
  225. void SAList<T>::insert(const T& data)
  226. {
  227.     Node<T> *add;
  228.     Node<T> *temp;
  229.  
  230.     add=new Node<T>(data);
  231.  
  232.     if(head==NULL)
  233.     {
  234.         head = add;
  235.     }
  236.     else
  237.     {
  238.         temp = head;
  239.         head = add;
  240.         head->next_ = temp;
  241.         temp->prev_ = head;
  242.     }
  243. }
  244.  
  245. template<class T>
  246. bool SAList<T>::get(T passback [], int max) const
  247. {
  248.  
  249.         Node<T>* temp;
  250.         bool check;
  251.         int i=0;
  252.  
  253.         temp = head;
  254.  
  255.         while(temp != NULL && i < (max))
  256.         {
  257.                 passback[i]=temp->data_;
  258.                 temp=temp->next_;
  259.                 i++;
  260.         }
  261.  
  262.         if(i == (max))
  263.                 check=true;
  264.         else
  265.                 check=false;
  266.  
  267.         return check;
  268. }
  269.  
  270. template<class T>
  271. Node<T>* SAList<T>::search(const T& key, bool (*match)(const T&,const T&))
  272. {
  273.     Node<T> *curr;
  274.  
  275.     bool stop = false;
  276.  
  277.     curr = head;
  278.    
  279.     Node<T>* n = curr->next_;
  280.     Node<T>* p = curr->prev_;
  281.  
  282.     while(curr != NULL && stop != true) {
  283.         if((*match)(curr->data_,key) == true) {
  284.             if (p != NULL) {
  285.                 if(curr != NULL) {
  286.                     p = NULL;
  287.                     head->prev_ = curr;
  288.                     n = head;
  289.                     stop = true;
  290.                 }
  291.                 else {
  292.                     curr = p;
  293.                     n = NULL;
  294.                 }
  295.             }
  296.             if(stop == false) {
  297.                 curr = head->next_;
  298.             }
  299.         }
  300.     }
  301.     return curr;
  302. }
  303.  /*   while(curr != NULL && stop != true){
  304.       if((*match)(curr->data_,key) == true){
  305.           temp = curr;
  306.           if(temp->prev_ != NULL) {
  307.              if(temp != NULL){
  308.                 temp = temp->next_;
  309.                 temp->prev_ = curr->prev_;
  310.                 temp = temp->prev_;
  311.                 temp->next_ = curr->next_;
  312.                 curr->prev_ = NULL;
  313.                 head->prev_ = NULL;
  314.                 head = curr;
  315.                 head->next_ = curr->next_;
  316.              }
  317.              else{
  318.                 temp = temp->prev_;
  319.                 temp->next_ = NULL;
  320.              }
  321.           }
  322.          stop = true;
  323.      
  324.       if(stop == false)
  325.         curr = curr->next_;
  326.     }
  327.     return curr; */
  328.  
  329. template<class T>
  330. bool SAList<T>::remove(const T& key, bool (*match)(const T&,const T&))
  331. {
  332.     Node<T> *curr, *temp, *removed;
  333.     bool retval, stop;
  334.  
  335.     while(curr != NULL && stop != true){
  336.       if((*match)(curr->data_,key) == true){
  337.           temp = curr;
  338.           if(temp->prev_ != NULL){
  339.              if(temp->next_ !=NULL){
  340.                 temp = temp->next_;
  341.                 temp->prev_ = curr->prev_;
  342.                 temp = temp->prev_;
  343.                 temp->next_ = curr->next_;
  344.              }
  345.              else{
  346.               temp = temp->prev_;
  347.                 temp->next_ = NULL;
  348.              }
  349.           }
  350.           else{
  351.              if(head->next_ != NULL){
  352.                 head = head->next_;
  353.                 head->prev_ = NULL;
  354.              }
  355.           }
  356.          stop = true;
  357.          removed = curr;
  358.          if(removed != NULL){
  359.             delete removed;
  360.          }
  361.          retval = true;
  362. }
  363.       curr = curr->next_;
  364.     }
  365. }
  366.  
  367.  
  368. #endif  /* _SALIST_H */
create a new version of this paste RAW Paste Data