#include <iostream>
#include <memory>
#include <vector>
#include <string>

using namespace std;

template <typename Key> 
class Interval
{
public:
    Key low;
    //Key high;//previous implementation
    std::vector<Key> high;//to implement... may be better to use a max priority queue
    //A priority queue is better since accessing a value is in o(log N) - vector is in o(N)
    //as well deleting and inserting is in o(log N) for priority queue
    //a binary tree is good as well.
    Key max;//to implement
    Key back;//represent the maximum of the list of high
    bool color;
    int N; //number of nodes under this subtree
    Interval *left, *right;
    Interval(Key lo, Key hi, Key val, bool c) : low(lo), max(val), back(val), color(c), N(1), left(NULL), right(NULL)
    {
        high.push_back(hi);
    }
    bool intersects(Key lo, Key hi) const;
};


template <typename Key> 
bool Interval<Key>::intersects(Key lo, Key hi) const
{
    if (lo <= this->low && this->back <= hi) return true;
    if (this->low <= lo && hi <= this->back) return true;
    if (lo <= this->low && hi <= this->back) return true;
    if (this->low <= lo && this->back <= hi) return true;
    return false;

}

template <class Type> class Segment
{
private:
    Type x1, y1, x2, y2;

public:
    Segment(Type x1, Type y1, Type x2, Type y2):x1(x1), y1(y1), x2(x2), y2(y2){}
    inline bool isHorizontal(){return x1 == x2;}
    inline bool isVertical  (){return y1 == y2;}
    //int compare(Segment segment);
    inline Type getx1(){return x1;}
    inline Type getx2(){return x2;}
    inline Type gety1(){return y1;}
    inline Type gety2(){return y2;}

};

template <typename Key> 
std::vector<Segment<Key> > findIntersections(const Interval<Key> &interval, Segment<Key> segment)
{
    const Interval<Key> *x = &interval;
    std::vector<Segment<Key> > intersections;

    while (x != NULL)
    {
        if (x->intersects(segment.gety1(), segment.gety2())) intersections.push_back(segment);
        else if (x->left == NULL)                x = x->right;
        else if (x->left->max < segment.gety1()) x = x->right;//this line gives the error
        else if (segment.gety1() > x->left->max) x = x->right;//this line is OK
        else                                     x = x->left;
    }
    return intersections;
}

int main()
{
    return 0;
}