#include<iostream>

#include<stdio.h>

using namespace std;

template < typename Key, typename Info >

  class Sequence {

    private:

     typedef struct SequenceList {
        Key id;
        Info information;
        SequenceList * next;
      };

    SequenceList * head;
    SequenceList * tail;

    int numberOfSequences;

    void removeAll() {

      if (head == NULL)
        return;

      SequenceList * sequenceToDelete = head;

      while (sequenceToDelete != NULL) {
        head = head -> next;
        delete sequenceToDelete;
        sequenceToDelete = head;
      }

      tail = NULL;
      numberOfSequences = 0;

    };

    public:

      Sequence() {
        head = NULL;
        tail = NULL;
        numberOfSequences = 0;
      }

      ~Sequence() {
        removeAll();
      }

    //add sequence in the end of the list
    void push_back(const Key & newid, const Info & newInfo) {

      SequenceList * newSequence = new SequenceList();
      newSequence -> id = newid;
      newSequence -> information = newInfo;
      newSequence -> next = NULL;

      if (head == NULL) {
        head = newSequence;
        tail = head;
      } else {
        tail -> next = newSequence;
        tail = tail -> next;
      }

      numberOfSequences++;
    }

    //add sequence in front of the list
    void push_front(const Key & newid, const Info & newInfo) {

      SequenceList * newSequence = new SequenceList(newid, newInfo, head);

      if (head == NULL) {
        head = newSequence;
        tail = head;
      } else
        head = newSequence;

      numberOfSequences++;
    }

    bool remove(const Key & where) {

      if (head == NULL)
        return false;

      SequenceList * sequenceToDelete = head;
      SequenceList * previous = NULL; // looking for position of sequence to be deleted

      while (sequenceToDelete != NULL && sequenceToDelete -> id != where) {
        previous = sequenceToDelete;
        sequenceToDelete = sequenceToDelete -> next;
      } // if sequence is found

      if (sequenceToDelete) { // if we want to delete the first sequence
        if (!previous) {

          head = head -> next;
          delete sequenceToDelete;
          numberOfSequences--;

          if (size() == 0)
            tail = NULL;

        } else {
          previous -> next = sequenceToDelete -> next;
          delete sequenceToDelete;

          numberOfSequences--; // if we have deleted tail sequence
          if (!previous -> next)
            tail = previous;
        }

        return true;

      } // sequence not found

      else
        return false;

    }

    bool isKeyExisting(int place) const {

      if (head != NULL && place >= 0) {

        SequenceList * temp = head;
        int i = 0;

        while (i < place && temp != NULL) {
          temp = temp -> next;
          i++;
        }

        if (temp != NULL)
          return true;
      }

      return false;
    }

    Key & getKeyByIndex(int place) const {

      SequenceList * temp = head;

      int i = 0;

      while (i < place && temp != NULL) {
        temp = temp -> next;
        i++;
      }

      return temp -> id;
    }

    bool isInfoExisting(int place) const {

      if (head != NULL && place >= 0) {
        SequenceList * temp = head;

        int i = 0;

        while (i < place && temp != NULL) {
          temp = temp -> next;
          i++;
        }

        if (temp != NULL)
          return true;

      }

      return false;
    }

    Info & getInfoByIndex(int place) const {

      SequenceList * temp = head;

      int i = 0;

      while (i < place && temp != NULL) {
        temp = temp -> next;
        i++;
      }

      return temp -> information;
    }

    void reset() {
      removeAll();
    }


 void print() const {

   SequenceList * current = head;

   cout << "Printing sequence!" << endl;

   while (current != NULL) {

     cout << "id: " << current -> id;
     cout << "   Information: " << current -> information << endl;
     current = current -> next;

   }
   cout << "______END______" << endl;

 }


    int size() const {
      return numberOfSequences;
    }

    bool isEmpty() const {
      return numberOfSequences == 0;
    }

    void sortList() {

      SequenceList * curr;
      SequenceList * prev;

      for (bool didSwap = true; didSwap;) {

        didSwap = false;

        prev = head;

        for (curr = head; curr -> next != NULL; curr = curr -> next) {

          if (curr -> id > curr -> next -> id) {

            if (head == curr) {

              head = curr -> next;
              curr -> next = head -> next;
              head -> next = curr;
              prev = head;

            } else {
              prev -> next = curr -> next;
              curr -> next = prev -> next -> next;
              prev -> next -> next = curr;
            }

            didSwap = true;

          } else if (head != curr) {
            prev = prev -> next;
          }

          //cout << curr->next->id << endl; // <- this may cause crash if curr->next now points to NULL; (i,e last element)
        }
      }
    }

  };

template < typename Key, typename Info >
  void split(Sequence < Key, Info > & result,
             int start1, int len1, int start2, int len2,
             Sequence < Key, Info > & r1, Sequence < Key, Info > & r2, int repeat) {

  int start;

  if (!r1.isEmpty()) {
    r1.reset();
  }

  if (!r2.isEmpty()) {
    r2.reset();
  }

  for (int i = 0; i < repeat; ++i) {

    cout << "----------------------------------------" << endl;
    cout << "Current loop is " << (i + 1) << " repeat is " << repeat << endl;

    start = start1;

    if (start >= 0 && len1 >= 0) {

      int arrayLength = result.size() - 1;

      cout << "start " << start << " length " << len1 << " sequences list size " << arrayLength << endl;

      int length = 0;

      while (length < len1 && start <= arrayLength) {

        cout << "length " << length << endl;

        if (result.isKeyExisting(start) && result.isInfoExisting(start)) {

          cout << "we are pushing back " << result.isKeyExisting(start) << " info " << result.getInfoByIndex(start) << " whos start is " << start << endl;

          r1.push_back(result.getKeyByIndex(start), result.getInfoByIndex(start));
          result.remove(result.getKeyByIndex(start));

        } else {
          start++;
        }
        length++;
      }
    }

    cout << "------------------ Starting the other part ------------------" << endl;

    start = start2;

    if (start >= 0 && len2 >= 0) {

      int arrayLength = result.size() - 1;

      cout << "start " << start << " length " << len2 << " sequences list size " << arrayLength <<
        endl;

      int length = 0;

      while (length < len2 && start <= arrayLength) {

        cout << "length " << length << endl;

        if (result.isKeyExisting(start) && result.isInfoExisting(start)) {

          cout << "we are pushing back " << result.isKeyExisting(start) << " info " << result.getInfoByIndex(start) <<
            " whos start is " << start << endl;

            r2.push_back(result.getKeyByIndex(start),
            result.getInfoByIndex(start));
            result.remove(result.getKeyByIndex(start));

        } else {
          start++;
        }
        length++;
      }
    }
  }

  r1.sortList();
  r2.sortList();

}

int
main() {

  Sequence < int, int > sequence;

  sequence.push_back(1, 1);
  sequence.push_back(2, 2);
  sequence.push_back(3, 3);
  sequence.push_back(10, 10); // where we start from
  sequence.push_back(20, 20); // this is over for the first sequence splitting
  sequence.push_back(4, 4);
  sequence.push_back(5, 5);
  sequence.push_back(6, 6);
  sequence.push_back(7, 7);
  sequence.push_back(30, 30); // index 9
  sequence.push_back(40, 40); //index 10
  sequence.push_back(8, 8);
  sequence.push_back(9, 9);
  sequence.push_back(10, 10);
  sequence.push_back(11, 11);
  sequence.push_back(50, 50);

  puts("--------------------sequence-----------------------");
  sequence.print();

  Sequence < int, int > r1;
  Sequence < int, int > r2;

  split(sequence, 3, 2, 3, 4, r1, r2, 2);

  //start 1 = 3 length1 = 2
  //start 2 = 3 length = 4
  //repetition = 2

  puts("--------------------r1-----------------------");
  r1.print();

  puts("--------------------r2----------------------");
  r2.print();

  return 0;

}