Lab1SLL

void Polynomial::insertTerm(const Term& term) {
    this->terms->add(term);
    return;
}
void Polynomial::insertTerm(double coeff, int exp) {
    if (coeff == 0) return;
    Term myTerm(coeff,exp);
            SLinkedList<Term>::Iterator it;
  for (it = this->terms->begin(); it != this->terms->end(); it++) {
            if ((*it).exp == exp) {
                (*it).coeff += coeff;
                if ((*it).coeff == 0) this->terms->removeItem(*it);
                return;
            }
        }
    int size = terms->size();
    if (size == 0) {
            terms->add(myTerm);
        return;
    }
    if (size == 1){
        auto temp = terms->get(0);
        if (temp.exp < exp) terms->add(0,myTerm);
        else terms->add(myTerm);
        return;
    }
    int cnt = 0;
      for (it = this->terms->begin(); it != this->terms->end(); it++) {
          auto val = *it;
          if (val.exp < exp)
          {
            terms->add(cnt,myTerm);
            return;
          }
          ++cnt;
        }
        terms->add(myTerm);
    return;
}
template <class T>
SLinkedList<T>::Iterator::Iterator(SLinkedList<T>* pList, bool begin)
{
    this->pList = pList;
    if (begin == true){
        if (pList != NULL) {
            current = pList->head;
            index = 0;
        }
        else {
            current = NULL;
            index = -1;
        }
        return;
    }
    current = NULL;
    if (pList != NULL) index = pList->size();
    else index = 0;
    return;
    /*
        Constructor of iterator
        * Set pList to pList
        * begin = true:
        * * Set current (index = 0) to pList's head if pList is not NULL
        * * Otherwise set to NULL (index = -1)
        * begin = false:
        * * Always set current to NULL
        * * Set index to pList's size if pList is not NULL, otherwise 0
    */
}

template <class T>
typename SLinkedList<T>::Iterator& SLinkedList<T>::Iterator::operator=(const Iterator& iterator)
{
    /*
        Assignment operator
        * Set this current, index, pList to iterator corresponding elements.
    */
    this->pList = iterator.pList;
    this->current = iterator.current;
    this->index = iterator.index;
    return *this;
}

template <class T>
void SLinkedList<T>::Iterator::remove()
{
    if (current == NULL) throw std::out_of_range("Segmentation fault!");
    SLinkedList<T>::Iterator it;
    if (current->data == *(pList->begin()))
    {
        pList->removeAt(0);
        current = NULL;
        index = -1;
        return;
    }
    /*
        Remove a node which is pointed by current
        * After remove current points to the previous node of this position (or node with index - 1)
        * If remove at front, current points to previous "node" of head (current = NULL, index = -1)
        * Exception: throw std::out_of_range("Segmentation fault!") if remove when current is NULL
    */
}

template <class T>
void SLinkedList<T>::Iterator::set(const T& e)
{
    /*
        Set the new value for current node
        * Exception: throw std::out_of_range("Segmentation fault!") if current is NULL
    */
    if (current == NULL)throw std::out_of_range("Segmentation fault!");
    current->data = e;
    return;
}

template <class T>
T& SLinkedList<T>::Iterator::operator*()
{
    /*
        Get data stored in current node
        * Exception: throw std::out_of_range("Segmentation fault!") if current is NULL
    */
     if (current == NULL)throw std::out_of_range("Segmentation fault!");
     return current->data;
}

template <class T>
bool SLinkedList<T>::Iterator::operator!=(const Iterator& iterator)
{
    /*
        Operator not equals
        * Returns true if two iterators points the same node and index
    */
    if (iterator.index != this->index) return false;
    if (iterator.current != this->current) return false;
    return true;
}
// Prefix ++ overload
template <class T>
typename SLinkedList<T>::Iterator& SLinkedList<T>::Iterator::operator++()
{
    /*
        Prefix ++ overload
        * Set current to the next node
        * If iterator corresponds to the previous "node" of head, set it to head
        * Exception: throw std::out_of_range("Segmentation fault!") if iterator corresponds to the end
    */
    if (current == NULL)  throw std::out_of_range("Segmentation fault!");
    else current = current->next;
    return *this;
}
// Postfix ++ overload
template <class T>
typename SLinkedList<T>::Iterator SLinkedList<T>::Iterator::operator++(int)
{
    /*
        Postfix ++ overload
        * Set current to the next node
        * If iterator corresponds to the previous "node" of head, set it to head
        * Exception: throw std::out_of_range("Segmentation fault!") if iterator corresponds to the end
    */
                Iterator iterator = *this;
                ++*this;
                return iterator;
}
template <class T>
void SLinkedList<T>::add(const T& e) {
    /* Insert an element into the end of the list. */
    if (this->count == 0){
        Node* newNode = new Node(e,NULL);
        this->head = newNode;
        this->tail = newNode;
        this->head->next = this->tail;
        ++this->count;
        return;
    }
    if (this->count == 1){
        Node* newNode = new Node(e,NULL);
        this->tail = newNode;
        tail->next = NULL;
        this->head->next  = this->tail;
        ++this->count;
        return;
    }
            Node* newNode = new Node(e,NULL);
            tail->next = newNode;
            tail = newNode;
            newNode->next = NULL;
            ++this->count;
            return;
}
template<class T>
void SLinkedList<T>::add(int index, const T& e) {
    /* Insert an element into the list at given index. */
    if (index == 0){
                Node* newNode = new Node(e,NULL);
                newNode->next = head;
                head = newNode;
                if (this->count == 0) {
                    tail = newNode;
                    head->next = tail;
                }
                ++this->count;
                return;
    }
    if (index == this->count){
        Node* newNode = new Node(e,NULL);
        tail->next = newNode;
        tail = newNode;
        if (this->count == 1) this->head->next = tail;
                        ++this->count;
        return;
    }
    int idx = 0;
    Node* curr = this->head;
    Node* prev = NULL;
    while (curr != NULL){
        if (idx == index) break;
        prev = curr;
        curr = curr->next;
        ++idx;
    }
    Node* newNode = new Node (e,NULL);
    prev->next = newNode;
    newNode->next = curr;
    ++this->count;
    return;
}

template<class T>
int SLinkedList<T>::size() {
    /* Return the length (size) of list */
    return this->count;
}
template<class T>
T SLinkedList<T>::get(int index) {
    int cnt = 0;
    Node* list = this->head;
    while (list != NULL){
        if (cnt == index) break;
        list = list->next;
        ++cnt;
    }
    if (list == NULL) return -1;
    return list->data;
}

template <class T>
void SLinkedList<T>::set(int index, const T& e) {
    /* Assign new value for element at given index in the list */
    int cnt = 0;
    Node* list = this->head;
    while (list != NULL){
           if (cnt == index) break;
        list  = list->next;
        ++cnt;
    }
    if (list == NULL) return;
    list->data = e;
    return;
}

template<class T>
bool SLinkedList<T>::empty() {
    /* Check if the list is empty or not. */
    if (this->count == 0) return true;
    return false;
}

template<class T>
int SLinkedList<T>::indexOf(const T& item) {
    /* Return the first index wheter item appears in list, otherwise return -1 */
    Node* list = this->head;
    int cnt = 0;
    while (list != NULL){
        if (list->data == item) return cnt;
        list = list->next;
        ++cnt;
    }
    return -1;
}

template<class T>
bool SLinkedList<T>::contains(const T& item) {
    /* Check if item appears in the list */
     Node* list = this->head;
    while (list != NULL){
        if (list->data == item) return true;
        list = list->next;
    }
    return false;
}
template <class T>
T SLinkedList<T>::removeAt(int index)
{
    if (this->head == NULL) return -1;
    if (index > this->count - 1) return -1;
    if (index == 0){
        Node* temp = head;
        head = head->next;
        T temp_data = temp->data;
        delete temp;
        --this->count;
        return temp_data;
    }
    Node* curr = this->head;
    Node*prev = NULL;
    int cnt = 0;
    while (curr != NULL){
        if (cnt == index) break;
        prev = curr;
        curr = curr->next;
        ++cnt;
    }
    if (index == this->count -1 ){
        prev->next = curr->next;
        tail = prev;
        T temp_data = curr->data;
        delete curr;
        --this->count;
        return temp_data;
    }
    prev->next = curr->next;
    T temp_data = curr->data;
    --this->count;
    delete curr;
    return temp_data;
}

template <class T>
bool SLinkedList<T>::removeItem(const T& item)
{
    /* Remove the first apperance of item in list and return true, otherwise return false */
    if (this->head == NULL) return  false;
    if (item == head->data){
        Node* temp = head;
        head = head->next;
        //int temp_data = temp->data;
        delete temp;
        --this->count;
        return true;
    }
    Node* curr = this->head;
    Node*prev = NULL;
    while (curr != NULL){
        if (item == curr->data) break;
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL) return false;
    if (curr->next == NULL){
        prev->next = curr->next;
        this->tail = prev;
        delete curr;
        --this->count;
        return true;
    }
    prev->next = curr->next;
    --this->count;
    delete curr;
    return true;
}

template<class T>
void SLinkedList<T>::clear(){
    while (head != NULL){
        Node* temp = head;
        head = head->next;
        delete temp;
    }
    this->count = 0;
    this->head = this->tail = NULL;
}
vector<int> topologicalSorting(vector<vector<int>> graph)
{
    // Create a vector to store
    // indegrees of all
    // vertices. Initialize all
    // indegrees as 0.
    int size = graph.size();
    vector<int> in_degree(size, 0);

    // Traverse adjacency lists
    // to fill indegrees of
    // vertices.  This step
    // takes O(V+E) time
    for (int u = 0; u < size; u++) {
        vector<int>::iterator itr;
        for (itr = graph[u].begin();
             itr != graph[u].end(); itr++)
            in_degree[*itr]++;
    }

    // Create an queue and enqueue
    // all vertices with indegree 0
    queue<int> q;
    for (int i = 0; i < size; i++)
        if (in_degree[i] == 0)
            q.push(i);

    // Initialize count of visited vertices
    int cnt = 0;

    // Create a vector to store
    // result (A topological
    // ordering of the vertices)
    vector<int> top_order;

    // One by one dequeue vertices
    // from queue and enqueue
    // adjacents if indegree of
    // adjacent becomes 0
    while (!q.empty()) {
        // Extract front of queue
        // (or perform dequeue)
        // and add it to topological order
        int u = q.front();
        q.pop();
        top_order.push_back(u);

        // Iterate through all its
        // neighbouring nodes
        // of dequeued node u and
        // decrease their in-degree
        // by 1
        vector<int>::iterator itr;
        for (itr = graph[u].begin();
             itr != graph[u].end(); itr++)

            // If in-degree becomes zero,
            // add it to queue
            if (--in_degree[*itr] == 0)
                q.push(*itr);

        cnt++;
    }
    if (cnt != size){
        vector<int> res;
        res.push_back(-1);
        return res;
    }
    return top_order;
}