Compute Adjacent pair

/****

Integer V lies strictly between integers U and W if U < V < W or if U > V > W.

A non-empty zero-indexed array A consisting of N integers is given. A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q].

For example, in array A such that:

A[0] = 0 A[1] = 3 A[2] = 3

A[3] = 7 A[4] = 5 A[5] = 3

A[6] = 11 A[7] = 1

the following pairs of indices have adjacent values:

(0, 7), (1, 2), (1, 4),

(1, 5), (1, 7), (2, 4),

(2, 5), (2, 7), (3, 4),

(3, 6), (4, 5), (5, 7).

For example, indices 4 and 5 have adjacent values because there is no value in array A that lies strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4, and it is not present in the array.

Write a function that returns number of adjacent values ****/

#include<iostream>

#include<map>

#include<vector>

#include<algorithm>

using namespace std;

class find_adjacent_pair

{

public:

       find_adjacent_pair();

       ~find_adjacent_pair();

       void print_adjacent_pairs(int*);

private:

       map<int, vector<int>> mymap;

       void map_input(int*);

       void add_new_entry(int, int);

       void compute_self_pair(vector<int>);

       void compute_neighbour_pair(vector<int>, vector<int>);

};

find_adjacent_pair::find_adjacent_pair()

{

       mymap.clear();

}

find_adjacent_pair::~find_adjacent_pair()

{

       mymap.clear();

}

void find_adjacent_pair::print_adjacent_pairs(int* in) {

       map<int, vector<int>>::iterator its;

       map<int, vector<int>>::iterator itd;

       map_input(in);

       //key in the map is already sorted

       its = mymap.begin();

       compute_self_pair(its->second);

       while(its != mymap.end()) {

              itd=its;

              its++;

              compute_self_pair(its->second);

              compute_neighbour_pair(itd->second, its->second);            

       }

}

void find_adjacent_pair::map_input(int* in) {

       int *ptr, val, pos; 

       map<int, vector<int>>::iterator it;

       ptr = in;

       pos = 0;

       while (ptr != NULL)

       {

              val = *ptr;

              it = mymap.find(val);

              if (it != mymap.end()) it->second.push_back(pos);

              else add_new_entry(val, pos);

              ptr++;

              pos++;

       }

}

void find_adjacent_pair::add_new_entry(int value, int pos) {

       vector<int> ps;

       ps.push_back(pos);

       mymap.insert(pair<int, vector<int>>(value, ps));

}

void find_adjacent_pair::compute_self_pair(vector<int> ps) {

      

       vector<int> :: iterator it;

       vector<int> :: iterator itv;

       int i = 0;

       for(itv = ps.begin(); i < ps.size()-1; itv++) {

              for(it = itv+1; it != ps.end(); it++)

                     cout << “(“<<*itv<<“, “<<*it<<“)  “;

              i++;

       }

}

void find_adjacent_pair::compute_neighbour_pair(vector<int> ps1, vector<int>ps2) {

       vector<int> :: iterator it1;

       vector<int> :: iterator it2;

       for(it1 = ps1.begin(); it1 != ps1.end(); it1++)

              for(it2 = ps2.begin(); it2 != ps2.end(); it2++)

                     cout<<“(“<<*it1<<“, “<<*it2<<“) “;

}