#ifndef __TERRAIN_H__
#define __TERRAIN_H__

struct Stick
{
    ushort low, high;
    Stick *next;

    Stick(ushort low, ushort high) : low(low), high(high) {}
};

struct Sector;

struct Terrain
{
    static const int GRIDSIZE = 128;

    struct Grid
    {
        Stick *bottom, *top;

        Grid() : bottom(NULL), top(NULL) {}
    };

    Grid grid[GRIDSIZE*GRIDSIZE];

    Vector<Sector *> sectors;

    Terrain()
    {
    }

    void allocsectors();
    void buildsectors();

    void addstick(Grid &g, ushort low, ushort high)
    {
        Stick *prev = NULL, *cur = g.bottom;
        while(low < high)
        {
            while(cur && low <= cur->high)
            {
                prev = cur;
                cur = cur->next;
            }
            if(prev && low < prev->high) low = prev->high;
            Stick *s = new Stick(low, cur ? min(high, cur->low) : high);
            if(prev) prev->next = s;
            else g.bottom = s;
            s->next = cur;
            low = s->high;
            prev = s;
            if(!cur) g.top = s;
        }
    }

    void delstick(Grid &g, ushort low, ushort high)
    {
        Stick *prev = NULL, *cur = g.bottom;
        for(;;)
        {
            while(cur && low >= cur->high)
            {
                prev = cur;
                cur = cur->next;
            }
            if(!cur) break;
            if(high >= cur->high)
            {
                if(prev) prev->next = cur->next;
                else g.bottom = cur->next;
                if(!cur->next) 
                {
                    g.top = prev;
                    break;
                }
                cur = cur->next;
            }
            else 
            {
                if(high > cur->low) cur->low = high;
                break;
            }
        }
    }

    void addcube(Vec3i pos, int size)
    {
        loop(y, size) loop(x, size)
            addstick(grid[(y+pos.y)*GRIDSIZE + x+pos.x], (pos.z*USHRT_MAX)/GRIDSIZE, ((pos.z+size)*USHRT_MAX)/GRIDSIZE);
    }
};

struct Sector
{
    static const int GRIDSIZE = 16;

    struct Vertex
    {
        Vec3 pos, norm;
    };

    Vector<Vertex> verts;

    struct Triangle
    {
        uint a, b, c;

        Triangle(int a, int b, int c) : a(a), b(b), c(c) {}
    };

    Vector<Triangle> tris;
    int startindex[(GRIDSIZE+3)*(GRIDSIZE+3)];

    struct BuildVertex
    {
        Vec3 pos;
        int index, succ[3], pred;
        bool last;
    };

    Vector<BuildVertex> buildverts;
    bool border;

    Terrain *terrain;
    Vec3i origin;

    Sector(Terrain *terrain, const Vec3i &origin) : terrain(terrain), origin(origin) {}

    void addtriangle(int a, int b, int c)
    {
        BuildVertex &av = buildverts[a], &bv = buildverts[b], &cv = buildverts[c];
        int ai = av.index, bi = bv.index, ci = cv.index;
        if(ai >= 0 && bi >= 0 && ci >= 0) tris.add(Triangle(ai, bi, ci));

        Vec3 n = (cv.pos - bv.pos).cross(av.pos - bv.pos);
        if(ai >= 0) verts[ai].norm += n;
        if(bi >= 0) verts[bi].norm += n;
        if(ci >= 0) verts[ci].norm += n;
    }

    void buildpolys(int i)
    {
        int left, right, cur;
        int nextleft, nextright;
        bool top = false;
        while(i>=0)
        {
            bool polys = false;
            cur = top ? i+1 : i;
            BuildVertex &v = buildverts[cur];
            if(!v.pred)
            {
                if(v.succ[0]>=0)
                {
                    if(v.succ[1]>=0)
                    {
                        left = v.succ[top ? 1 : 0];
                        right = v.succ[top ? 0 : 1];
                        polys = true;
                    }
                    else if(v.succ[2]>=0)
                    {
                        left = v.succ[top ? 0 : 2];
                        right = v.succ[top ? 2 : 0];
                        polys = true;
                    }
                }
                else if(v.succ[1]>=0)
                {
                    if(v.succ[2]>=0)
                    {
                        left = v.succ[top ? 2 : 1];
                        right = v.succ[top ? 1 : 2];
                        polys = true;
                    }
                }
            }
            if(polys)
            {
                addtriangle(right, cur, left);
                while(left>=0 && right>=0)
                {
                    loop(k, 3) if(buildverts[left].succ[k]==right || buildverts[right].succ[k]==left) goto nextstrip;
                    nextleft = -1;
                    loop(k, 3) if(buildverts[left].succ[k]>=0) { nextleft = buildverts[left].succ[k]; break; }
                    nextright = -1;
                    loop(k, 3) if(buildverts[right].succ[k]>=0) { nextright = buildverts[right].succ[k]; break; }
                    if(nextleft>=0 && (nextright<0 || buildverts[nextleft].pos.z <= buildverts[nextright].pos.z))
                    {
                        addtriangle(right, left, nextleft);
                        left = nextleft;
                    }
                    else if(nextright>=0)
                    {
                        addtriangle(nextright, right, left);
                        right = nextright;
                    }
                    else break;
                }
                nextstrip:;
            }
            if(top)
            {
                if(v.last) break; else i += 2;
            }
            top = !top;
        }
    }

    void buildedges(float cx, float cy, int a, int b, int face)
    {
        bool top = false;
        while(a>=0 || b>=0)
        {
            if(!top)
            {
                if(a<0) swap(a, b);
                else if(b>=0)
                {
                    BuildVertex &av = buildverts[a], &bv = buildverts[b];
                    if(bv.pos.z < av.pos.z || (bv.pos.z == av.pos.z && bv.pos.x < av.pos.x)) swap(a, b);
                }
                if(b>=0 && buildverts[a+1].pos.z > buildverts[b].pos.z)
                {
                    buildverts[a].succ[face] = b;
                    buildverts[b].pred++;
                    top = true;
                }
                else
                {
                    BuildVertex &v = buildverts.add();
                    loop(k, 3) v.succ[k] = -1;
                    v.last = true;
                    v.pos = Vec3(cx, cy, 0.5f*(buildverts[a].pos.z + buildverts[a+1].pos.z));

                    int ai1 = buildverts[a].index, ai2 = buildverts[a+1].index;
                    if(ai1 < 0 || ai2 < 0) v.index = -1;    
                    else
                    {
                        v.index = verts.size();
                        Vertex &vd = verts.add();
                        vd.pos = v.pos;
                        vd.norm = (verts[ai1].norm + verts[ai2].norm) * 0.5f;
                    }

                    buildverts[a].succ[face] = buildverts.size()-1;
                    v.pred = 1;
                    v.succ[face] = a+1;
                    buildverts[a+1].pred++;

                    if(buildverts[a+1].last) a = -1; else a += 2;
                }
            }
            else
            {
                if(a<0) swap(a, b);
                else if(b>=0)
                {
                    BuildVertex &av = buildverts[a+1], &bv = buildverts[b+1];
                    if(bv.pos.z < av.pos.z || (bv.pos.z == av.pos.z && bv.pos.x < av.pos.x)) swap(a, b);
                }
                if(b>=0 && (buildverts[a+1].last || buildverts[a+2].pos.z > buildverts[b+1].pos.z))
                {
                    buildverts[a+1].succ[face] = b+1;
                    buildverts[b+1].pred++;
                    if(buildverts[a+1].last) a = -1; else a += 2;
                    if(buildverts[b+1].last) b = -1; else b += 2;
                    top = false;
                }
                else if(!buildverts[a+1].last)
                {
                    BuildVertex &v = buildverts.add();
                    loop(k, 3) v.succ[k] = -1;
                    v.last = true;
                    v.pos = Vec3(cx, cy, 0.5f*(buildverts[a+1].pos.z + buildverts[a+2].pos.z));
                   
                    int ai1 = buildverts[a+1].index, ai2 = buildverts[a+2].index;
                    if(ai1 < 0 || ai2 < 0) v.index = -1;
                    else
                    {
                        v.index = verts.size();
                        Vertex &vd = verts.add();
                        vd.pos = v.pos;
                        vd.norm = (verts[ai1].norm + verts[ai2].norm) * 0.5f;
                    }

                    buildverts[a+1].succ[face] = buildverts.size()-1;
                    v.pred = 1;
                    v.succ[face] = a+2;
                    buildverts[a+2].pred++;

                    if(buildverts[a+1].last) a = -1; else a += 2;
                }
            }
        }
    }

    void buildcell(float x, float y, float e0x_dx, float exy_dx, float exy_dy, float e0y_dx, float e0y_dy, int s0, int sx, int sy)
    {
        if(s0 >= 0) for(int v = s0; v==s0 || !buildverts[v-1].last; v++) { loop(k, 3) buildverts[v].succ[k] = -1; buildverts[v].pred = 0; }
        if(sx >= 0) for(int v = sx; v==sx || !buildverts[v-1].last; v++) { loop(k, 3) buildverts[v].succ[k] = -1; buildverts[v].pred = 0; }
        if(sy >= 0) for(int v = sy; v==sy || !buildverts[v-1].last; v++) { loop(k, 3) buildverts[v].succ[k] = -1; buildverts[v].pred = 0; }

        buildedges(x + e0x_dx, y, s0, sx, 0);
        buildedges(x + exy_dx, y + exy_dy, sx, sy, 1);
        buildedges(x + e0y_dx, y + e0y_dy, sy, s0, 2);

        buildpolys(s0);
        buildpolys(sx);
        buildpolys(sy);
    }

    void setupverts()
    {
        buildverts.setsize(0);
        tris.setsize(0);
        verts.setsize(0);
        loop(y, GRIDSIZE+3) loop(x, GRIDSIZE+3)
        {
            int &start = startindex[y*(GRIDSIZE+3) + x];
            Vec3i pos(origin.x + x - 1, origin.y + y - 1, origin.z);
            if(pos.x < 0 || pos.y < 0 || pos.x >= Terrain::GRIDSIZE || pos.y >= Terrain::GRIDSIZE)
            {
                start = -1;
                continue;
            }

            Terrain::Grid &g = terrain->grid[pos.y*Terrain::GRIDSIZE + pos.x];
            if(!g.bottom)
            {
                start = -1;
                continue;
            }

            bool border = !x || !y || x > GRIDSIZE + 1 || y > GRIDSIZE + 1;
            start = buildverts.size();
            for(Stick *s = g.bottom; s; s = s->next)
            {
                BuildVertex &v1 = buildverts.add();
                v1.pos = Vec3(pos.x, pos.y, s->low*float(Terrain::GRIDSIZE)/float(USHRT_MAX));
                loop(k, 3) v1.succ[k] = -1;
                v1.pred = 0;
                v1.last = false;

                if(border || !s->low) v1.index = -1;
                else
                {
                    v1.index = verts.size();
                    Vertex &vd1 = verts.add();
                    vd1.norm = Vec3(0, 0, 0);
                    vd1.pos = v1.pos;
                }

                BuildVertex &v2 = buildverts.add();
                v2.pos = Vec3(pos.x, pos.y, s->high*float(Terrain::GRIDSIZE)/float(USHRT_MAX));
                loop(k, 3) v2.succ[k] = -1;
                v2.pred = 0;
                v2.last = !s->next;

                if(border || s->high==USHRT_MAX) v2.index = -1;
                else
                {
                    v2.index = verts.size();
                    Vertex &vd2 = verts.add();
                    vd2.norm = Vec3(0, 0, 0);
                    vd2.pos = v2.pos;
                }
            }
        }
        loop(y, GRIDSIZE+2) loop(x, GRIDSIZE+2)
        {
            Vec3i pos(origin.x + x - 1, origin.y + y - 1, origin.z);

            int s00 = startindex[y*(GRIDSIZE+3) + x],
                s01 = startindex[y*(GRIDSIZE+3) + x+1],
                s10 = startindex[(y+1)*(GRIDSIZE+3) + x],
                s11 = startindex[(y+1)*(GRIDSIZE+3) + x+1];

            border = !x || !y || x >= GRIDSIZE || y >= GRIDSIZE;

            buildcell(pos.x, pos.y, 0.5f, 0.5f, 0.5f, 0, 0.5f, s00, s01, s10);
            buildcell(pos.x+1, pos.y+1, -0.5f, -0.5f, -0.5f, -0, -0.5f, s11, s10, s01);
        }
    }

    void render()
    {
        if(tris.empty()) return;

        glEnableClientState(GL_VERTEX_ARRAY);
        glVertexPointer(3, GL_FLOAT, sizeof(Vertex), &verts[0].pos.x);
    
        glDrawElements(GL_TRIANGLES, 3*tris.size(), GL_UNSIGNED_INT, &tris[0].a);

        glDisableClientState(GL_VERTEX_ARRAY);
    }
};

void Terrain::allocsectors()
{
    addcube(Vec3i(GRIDSIZE/4, GRIDSIZE/4, GRIDSIZE/4), GRIDSIZE/4);

    for(int y = 0; y < GRIDSIZE; y += Sector::GRIDSIZE)
    for(int x = 0; x < GRIDSIZE; x += Sector::GRIDSIZE)
        sectors.add(new Sector(this, Vec3i(x, y, 0)));
}

void Terrain::buildsectors()
{
    loopv(sectors) sectors[i]->setupverts();
}

#endif