#include <stdio.h>
#include <map>
#include <algorithm>
/*
lower_bound(range, x) = min( y, x >= y && y in range )
upper_bound(range, x) = min( y, x > y && y in range )
upper_bound_min1(range, x) = max( y, x <= y && y in range )
lower_bound_min1(range, x) = max( x, x < y && y in range )


 */
typedef std::map<int, int> blockmap_t;
char compare(int x, int y)
{
    if (x<y) return '<';
    if (x==y) return '=';
    if (x>y) return '>';
}


int main(int,char**)
{
    blockmap_t m0;
    blockmap_t m;

    m[0]= 0;
    m[0x626200]= 0xc40;
    m[0xacac00]= 0x1500;

    int tests[]= {-0x808, 0, 0x808, 0x626200-0x808, 0x626200, 0x626200+0x808, 0xacac00-0x808, 0xacac00, 0xacac00+0x808};

    printf("   x              lb       ub      lb--      ub--  min(x<=R) min(x<R) max(x>R) max(x>=R) min(x>=R) min(x>R) max(x<R) max(x<=R)\n");
    for (unsigned i=0 ; i<sizeof(tests)/sizeof(*tests) ; i++) {
        printf("%08x %c %c %c ", tests[i], compare(tests[i], 0), compare(tests[i], 0x626200), compare(tests[i], 0xacac00));
        auto lb= m.lower_bound(tests[i]);
        if (lb==m.end()) printf(" --------"); else printf(" %08x", lb->first);

        auto ub= m.upper_bound(tests[i]);
        if (ub==m.end()) printf(" --------"); else printf(" %08x", ub->first);

        auto yb= m.lower_bound(tests[i]);
        if (yb==m.begin())
            yb= m.end();
        else
            yb--;
        if (yb==m.end()) printf(" --------"); else printf(" %08x", yb->first);

        auto xb= m.upper_bound(tests[i]);
        if (xb==m.begin())
            xb= m.end();
        else
            xb--;
        if (xb==m.end()) printf(" --------"); else printf(" %08x", xb->first);

        int x= tests[i];
        auto za= std::find_if(m.begin(),  m.end(),  [x](blockmap_t::value_type y) { return x<=y.first; });
        auto zb= std::find_if(m.begin(),  m.end(),  [x](blockmap_t::value_type y) { return x<y.first; });
        auto zc= std::find_if(m.rbegin(), m.rend(), [x](blockmap_t::value_type y) { return x>y.first; });
        auto zd= std::find_if(m.rbegin(), m.rend(), [x](blockmap_t::value_type y) { return x>=y.first; });

        if (za==m.end()) printf(" --------"); else printf(" %08x", za->first);
        if (zb==m.end()) printf(" --------"); else printf(" %08x", zb->first);
        if (zc==m.rend()) printf(" --------"); else printf(" %08x", zc->first);
        if (zd==m.rend()) printf(" --------"); else printf(" %08x", zd->first);

        // boring functions
        auto wa= std::find_if(m.begin(),  m.end(),  [x](blockmap_t::value_type y) { return x>=y.first; });
        auto wb= std::find_if(m.begin(),  m.end(),  [x](blockmap_t::value_type y) { return x>y.first; });
        auto wc= std::find_if(m.rbegin(), m.rend(), [x](blockmap_t::value_type y) { return x<y.first; });
        auto wd= std::find_if(m.rbegin(), m.rend(), [x](blockmap_t::value_type y) { return x<=y.first; });

        if (wa==m.end()) printf(" --------"); else printf(" %08x", wa->first);
        if (wb==m.end()) printf(" --------"); else printf(" %08x", wb->first);
        if (wc==m.rend()) printf(" --------"); else printf(" %08x", wc->first);
        if (wd==m.rend()) printf(" --------"); else printf(" %08x", wd->first);

        printf("\n");
    }

    if (true)
    {
        printf("--------       ");
        auto lb= m0.lower_bound(0);
        if (lb==m0.end()) printf(" --------"); else printf(" %08x", lb->first);

        auto ub= m0.upper_bound(0);
        if (ub==m0.end()) printf(" --------"); else printf(" %08x", ub->first);

        auto yb= m0.lower_bound(0);
        if (yb==m0.begin())
            yb= m0.end();
        else
            yb--;
        if (yb==m0.end()) printf(" --------"); else printf(" %08x", yb->first);

        auto xb= m0.upper_bound(0);
        if (xb==m0.begin())
            xb= m0.end();
        else
            xb--;
        if (xb==m0.end()) printf(" --------"); else printf(" %08x", xb->first);


        auto za= std::find_if(m0.begin(),  m0.end(),  [](blockmap_t::value_type y) { return 0<=y.first; });
        auto zb= std::find_if(m0.begin(),  m0.end(),  [](blockmap_t::value_type y) { return 0<y.first; });
        auto zc= std::find_if(m0.rbegin(), m0.rend(), [](blockmap_t::value_type y) { return 0>y.first; });
        auto zd= std::find_if(m0.rbegin(), m0.rend(), [](blockmap_t::value_type y) { return 0>=y.first; });

        if (za==m0.end()) printf(" --------"); else printf(" %08x", za->first);
        if (zb==m0.end()) printf(" --------"); else printf(" %08x", zb->first);
        if (zc==m0.rend()) printf(" --------"); else printf(" %08x", zc->first);
        if (zd==m0.rend()) printf(" --------"); else printf(" %08x", zd->first);


        printf("\n");
    }
    return 0;

}