structure.cpp

Go to the documentation of this file.

#include <structure.h>
#include <iostream>
#include <tbb/tbb.h>
#include <app/workerthread.h>

using namespace frechet;
using namespace data;
using namespace reach;

Structure::Structure(int concurrency, volatile bool* the_cancelFlag)
    : Structure(FreeSpace::ptr(nullptr),concurrency,the_cancelFlag)

{ }

Structure::Structure(const FreeSpace::ptr afs, int aconcurrency, volatile bool* the_cancelFlag)
    : fs(afs),
      _boundary{{BoundaryList(),BoundaryList()},
                {BoundaryList(),BoundaryList()}},
      concurrency(aconcurrency),
      cancelFlag(the_cancelFlag)
{ }

Structure::Structure(const Structure& that)
    : Structure()
{
    copy(that);
}

Structure::Structure(Structure&& that)
        : Structure()
{
    swap(that);
}

void Structure::copy(const Structure& that)
{

    //  TODO parallelize ?
    //  create and keep cloned segments
    for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
        for(Direction dir=FIRST; dir <= SECOND; ++dir)
            for(Pointer p=that.boundary(ori,dir).first(); p; p=p->next())
                p->createClone();

    //  adjust h/l pointers
    for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
        for(Direction dir=FIRST; dir <= SECOND; ++dir)
            for(Pointer p=that.boundary(ori,dir).first(); p; p=p->next())
            {
                if (p->l) {
                    Q_ASSERT(p->l==p->clone()->l);
                    p->clone()->l = p->l->clone();
                    Q_ASSERT(p->l!=p->clone()->l);
                }
                if (p->h) {
                    Q_ASSERT(p->h==p->clone()->h);
                    p->clone()->h = p->h->clone();
                    Q_ASSERT(p->h!=p->clone()->h);
                }
            }

    //  move cloned segments to 'this'
    for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
        for(Direction dir=FIRST; dir <= SECOND; ++dir)
        {
            BoundaryList& dest = this->boundary(ori,dir);
            for(Pointer p=that.boundary(ori,dir).first(); p; p=p->next())
            {
                dest.insert_last(p->clone());
#ifdef QT_DEBUG
                p->clone()->setOwner(this);
#endif
                //p->clearClone();
            }
        }
}

Structure& Structure::operator= (Structure&& that)
{
    swap(that);
    return *this;
}

Structure& Structure::operator= (const Structure& that)
{
    copy(that);
    return *this;
}

void Structure::swap(Structure& that)
{
    const_cast<FreeSpace::ptr&>(this->fs).swap( const_cast<FreeSpace::ptr&>(that.fs));

    for (Orientation ori = HORIZONTAL; ori <= VERTICAL; ++ori)
        for (Direction dir = FIRST; dir <= SECOND; ++dir)
            this->boundary(ori, dir).swap(that.boundary(ori, dir));
}




void Structure::shift(frechet::Point shift)
{
    //  TODO parallelize ?
    for(Direction dir=FIRST; dir <= SECOND; ++dir)
    {
        if (shift.x() != 0)
            for(Pointer p = boundary(HORIZONTAL,dir).first(); p; p = p->next())
                *p += shift.x();

        if (shift.y() != 0)
            for(Pointer p = boundary(VERTICAL,dir).first(); p; p = p->next())
                *p += shift.y();
    }
    //  most likely, the Free-Space is now ill-adjusted. Better not use it.
}

Structure::~Structure()
{ }

Pointer Structure::calculate()
{
    if (fs->wrapRight() || fs->wrapTop()) {
        //  Closed Curve (P)
        return calculateDouble();
    }
    else {
        //  open curve
        return calculateSingle();
    }
}

Pointer Structure::calculateSingle()
{
    calcRecursive(Rect(0,0,fs->n-1,fs->m-1));

    //  is [n-1,m-1] reachable from [0,0] ?

    for(Orientation o1=HORIZONTAL; o1 <= VERTICAL; ++o1)
        for(Orientation o2=HORIZONTAL; o2 <= VERTICAL; ++o2)
        {
            Pointer u = first(o1).first();
            Pointer v = second(o2).last();

            Q_ASSERT(u->contains(0.0));
            Q_ASSERT(v->contains(o2==HORIZONTAL ? (fs->n-1) : (fs->m-1)));

            if (u->type==NON_ACCESSIBLE || v->type==NON_ACCESSIBLE)
                continue;

            if ((!u->l || compare_interval(u->l,v) <= 0)
                    && (!u->h || compare_interval(v,u->h) <=0))
                return u;
        }
    return nullptr;
}

frechet::reach::Pointer Structure::calculateDouble()
{
    if (fs->wrapRight()) {
        calculateDouble(VERTICAL);
        return findStartingPoint(HORIZONTAL);
    }
    else if (fs->wrapTop()) {
        calculateDouble(HORIZONTAL);
        return findStartingPoint(VERTICAL);
    }
    Q_ASSERT(false);    //  at least one closed curve expected !
}

void Structure::calculateColumns(int i, int j)
{
    Q_ASSERT(i < fs->n-1);
    Q_ASSERT(i < j);

    if (j <= fs->n-1) {
        //  calculate one part
        Rect r (i,0, j,fs->m-1);
        calcRecursive(r);
    }
    else {
        //  calculate two parts
        Rect r1 (i,0, fs->n-1,fs->m-1);
        Rect r2 (0,0, j-(fs->n-1),fs->m-1);
        Rect s2 (fs->n-1,0, j,fs->m-1);

        calcRecursive(r1);

        Structure buddy(fs);
        buddy.calcRecursive(r2);
        buddy.shift(Point(fs->n-1,0));

        merge(VERTICAL, buddy, r1,s2);
    }
}


void Structure::calculateDouble(Orientation fringe)
{
    Rect r1 (0,0,fs->n-1,fs->m-1);
    calcRecursive(r1);

    Rect r2;
    if (fringe==VERTICAL)
        r2 = Rect(r1.i1, 0, 2*r1.i1, r1.j1);
    else
        r2 = Rect(0, r1.j1, r1.i1, 2*r1.j1);

    //  TODO copy & shift in parallel ?
    Structure buddy(*this);
    buddy.shift(Point(r2.i0,r2.j0));
    //  Free-Space does not fit shifted structure
    //  it is not needed, anyway
    //  TODO merge in parallel ?
    merge(fringe,buddy, r1,r2);
}
Pointer Structure::findStartingPoint(Orientation edge)
{
    //  iterate bottom and top edge
    int offset = (edge==HORIZONTAL) ? (fs->n-1) : (fs->m-1);
    Pointer u = first(edge).first();
    Pointer v = second(edge).first()->clone();

    for( ; u && v; u = u->next(), v = v->next())
    {
        if (u->type==NON_ACCESSIBLE ||
                v->type==NON_ACCESSIBLE)
            continue;

        Q_ASSERT(u->dir!=v->dir);
        Q_ASSERT(u->lower()+offset==v->lower());
        Q_ASSERT(u->upper()+offset==v->upper());

        if ((!u->l || compare_interval(u->l,v) <= 0)
                && (!u->h || compare_interval(v,u->h) <=0))
            return u;
    }

    return nullptr;
}

void Structure::calcRecursive(const frechet::Rect& r) {
    Q_ASSERT(r.i0 >= 0 && r.i1 < fs->n);
    Q_ASSERT(r.j0 >= 0 && r.j1 < fs->m);
    Q_ASSERT(r.i0 < r.i1);
    Q_ASSERT(r.j0 < r.j1);

    Q_ASSERT(r.i0 < r.i1);
    Q_ASSERT(r.j0 < r.j1);

    if (concurrency==1 || (r.width()==1 && r.height()==1)) {
        doCalcRecursive(r);
    }
    else {
        //  set up a TBB dependency graph
        tbb::flow::graph g;
        StructureTask* root_task = StructureTask::createTask(this,r,g,concurrency);
        root_task->start();
        g.wait_for_all();
        delete root_task;
    }
}

//Structure* owner;
StructureTask::StructureTask(Structure* the_owner)
:   owner(the_owner), node(nullptr)
{ }

StructureTask::~StructureTask() {
    delete node;
}

StructureTask* StructureTask::createTask(Structure* owner, const frechet::Rect& r, tbb::flow::graph& graph, int concurrency)
{
    if (concurrency <= 1 || (r.width()==1 && r.height()==1))
        return new CalculateTask(owner,r,graph);
    else
        return new MergeTask(owner,r,graph,concurrency);
}

//frechet::Rect r;
CalculateTask::CalculateTask(Structure* the_owner, frechet::Rect r, tbb::flow::graph& graph)
:   StructureTask(the_owner)
{
    node = new node_t(graph, [this,r] (msg_t) {
        this->owner->doCalcRecursive(r);
    });
}

void CalculateTask::start() {
    Q_ASSERT(node);
    node->try_put(msg_t());
}


MergeTask::MergeTask(Structure* owner, frechet::Rect r, tbb::flow::graph& graph, int concurrency)
:   StructureTask(owner),
    buddy(owner->fs),
    child1(), child2()    
{
    Rect r1,r2;
    Orientation ori;

    if ((r.i1-r.i0) > (r.j1-r.j0)){
        //  split along the vertical fringe
        r1 = Rect(r.i0, r.j0, (r.i0+r.i1)/2, r.j1);
        r2 = Rect((r.i0+r.i1)/2, r.j0, r.i1, r.j1);
        ori = VERTICAL;
    }
    else {
        //  split along the horizonal fringe
        r1 = Rect(r.i0,r.j0,  r.i1, (r.j0+r.j1)/2);
        r2 = Rect(r.i0, (r.j0+r.j1)/2,  r.i1, r.j1);
        ori = HORIZONTAL;
    }

    child1 = createTask(owner,r1,graph, concurrency/2);
    child2 = createTask(&buddy,r2,graph, concurrency/2);

    node = new node_t(graph, [this,ori,r1,r2](msg_t) {
        this->owner->merge(ori,this->buddy,r1,r2);
    });

    tbb::flow::make_edge(*child1->node,*node);
    tbb::flow::make_edge(*child2->node,*node);
}

void MergeTask::start() {
    Q_ASSERT(child1 && child2);
    child1->start();
    child2->start();
}

MergeTask::~MergeTask()
{
    delete child1;
    delete child2;
}

void Structure::doCalcRecursive(const frechet::Rect& r)
{
    testCancelFlag();
    if (r.width()==1 && r.height()==1) {
        //  single cell, recursion ends here
        singleCell(r.i0,r.j0);
    }
    else if ((r.i1-r.i0) > (r.j1-r.j0)){
        //  split along the vertical fringe
        Rect r1 (r.i0, r.j0, (r.i0+r.i1)/2, r.j1);
        Rect r2 ((r.i0+r.i1)/2, r.j0, r.i1, r.j1);
        Structure buddy(fs);
        this->doCalcRecursive(r1);
        buddy.doCalcRecursive(r2);
        merge(VERTICAL,buddy, r1,r2);
    }
    else {
        //  split along the horizonal fringe
        Rect r1 (r.i0,r.j0,  r.i1, (r.j0+r.j1)/2);
        Rect r2 (r.i0, (r.j0+r.j1)/2,  r.i1, r.j1);
        Structure buddy(fs);
        this->doCalcRecursive(r1);
        buddy.doCalcRecursive(r2);
        merge(HORIZONTAL,buddy, r1, r2);
    }
}

void Structure::synchIntervals(Orientation fringe, Structure& that)
{
    Pointer i1 = this->first(fringe).first();
    Pointer i2 = this->second(fringe).first();
    Pointer j1 = that.first(fringe).first();
    Pointer j2 = that.second(fringe).first();

    Q_ASSERT(this->first(fringe).size()==this->second(fringe).size());
    Q_ASSERT(that.first(fringe).size()==that.second(fringe).size());

    for( ; i1 && j1; i1=i1->next(), i2=i2->next(), j1=j1->next(), j2=j2->next())
    {
        Q_ASSERT(i1->lower()==i2->lower()); //  lower bounds are alreay in synch
        Q_ASSERT(i1->lower()==j1->lower());
        Q_ASSERT(i1->lower()==j2->lower());

        Q_ASSERT(i1->upper()==i2->upper()); //  i1 and i2 are already in synch
        Q_ASSERT(j1->upper()==j2->upper()); //  j1 and j2 are already in synch

        if (i1->upper() < j1->upper())
        {   //  split 'that'
            that.split2(j1, i1->upper(), j2);
        }
        else if (i1->upper() > j1->upper())
        {   //  split 'this'
            this->split2(i1, j1->upper(), i2);
        }

        //  connect inner intervals temporarily (needed during merge process)
        //  "brezel" shaped ring pointer
        crossLink(i1,i2,j1,j2);
    }

    if (i1)
    {
        //  single-point interval at the top of this
        for ( ; i1; i1=i1->next(), i2=i2->next(), j1=j1->next(), j2=j2->next())
        {
            Q_ASSERT(i1->lower()==i1->upper());

            j1 = that.first(fringe).last();
            j2 = that.second(fringe).last();

            that.split2(j1, i1->upper(), j2);

            crossLink(i1->prev(),i2->prev(), j1,j2);
            crossLink(i1,i2, j1->next(),j2->next());
        }
    }
    else if (j1)
    {
        //  single-point interval at the top of that
        for ( ; j1; i1=i1->next(), i2=i2->next(), j1=j1->next(), j2=j2->next())
        {
            Q_ASSERT(j1->lower()==j1->upper());

            i1 = this->first(fringe).last();
            i2 = this->second(fringe).last();

            this->split2(i1, j1->upper(), i2);

            crossLink(i1,i2, j1->prev(),j2->prev());
            crossLink(i1->next(),i2->next(), j1,j2);
        }
    }

   Q_ASSERT(this->first(fringe).size()==this->second(fringe).size());
   Q_ASSERT(this->first(fringe).size()==that.first(fringe).size());
   Q_ASSERT(this->first(fringe).size()==that.second(fringe).size());
}
void Structure::split2(Pointer& a, double x, Pointer& b)
{
    a = split(a,x,b);
    b = split(b,x,a);
}
void Structure::crossLink(Pointer i1, Pointer i2, Pointer j1, Pointer j2)
{
    i2->temp._twin = j2;     //  R1 -> R2
    j2->temp._twin = j1;     //  R2 -> L2
    j1->temp._twin = i1;    //  L2 -> L1
    i1->temp._twin = i2;    //  L1 -> R1
}

Structure::assert_hook Structure::before_merge = nullptr;
Structure::assert_hook Structure::after_merge = nullptr;
Structure::assert_hook Structure::after_single_cell = nullptr;

//int iteration=0;

void Structure::merge(Orientation fringe, Structure& that,
                      const frechet::Rect& r1, const frechet::Rect& r2)
{
    //Q_ASSERT(++iteration);
    testCancelFlag();

    Q_ASSERT(!before_merge || (before_merge(this,&r1, &that,&r2, fringe),true));

    //  adjust intervals
    synchIntervals(fringe, that);

    //  assumes that all intervals are already adjusted
    Q_ASSERT(assertSynchedIntervals(
                 first(fringe).first(), second(fringe).first(),
                 that.first(fringe).first(), that.second(fringe).first()));

    //TODO move to test classes
    //  synching must not affect the integrity of both structures:
    Q_ASSERT(!before_merge || (before_merge(this,&r1, &that,&r2, fringe),true));

    //  perform merge along the middle fringe
    markNonAccesible(fringe, that);

    Q_ASSERT(!before_merge || (before_merge(this,&r1, &that,&r2, fringe),true));

    //  Next we scan through B1 u L1
    this->scanAndMerge(bottom().first(), fringe);
    this->scanAndMerge(left().first(), fringe);
    //  analogous for T2 u R2
    that.scanAndMerge(that.right().first(), fringe);
    that.scanAndMerge(that.top().first(), fringe);

    //  swap R1 with R2
    this->second(fringe).swap( that.second(fringe) );
    //  concat top and bottom (that.bottomAndTop becomes empty)
    this->first(opposite(fringe)).concat(
                that.first(opposite(fringe)));
    this->second(opposite(fringe)).concat(
                that.second(opposite(fringe)));
#ifdef QT_DEBUG
    takeOwnership();
#endif

    Q_ASSERT(!after_merge || (after_merge(this,&r1, &that,&r2, fringe),true));

/*
    mergeConsecutive(HORIZONTAL);
    mergeConsecutive(VERTICAL);

    Q_ASSERT(!after_merge || after_merge(this,r1, &that,r2, fringe));
*/
}

void Structure::mergeConsecutive(Orientation ori)
{
    //  TODO merge consecutive equal intervals to reduce fragmentation
    //  Or, maybe, don't. Reachability Graphs rely on "refined" intervals.
    //  at least equal N intervals
    Pointer i1=first(ori).first();
    Pointer i2=second(ori).first();

    Pointer i1n = i1->next();
    Pointer i2n = i2->next();

    while(i1 && i1n)
    {
        Q_ASSERT(i2 && i2n);
        if ((*i1 == *i1n) && (*i2 == *i2n))
        {
            merge(first(ori), i1,i1n);
            merge(second(ori), i2,i2n);
        }
        else
        {
            i1 = i1n;
            i2 = i2n;
        }
        i1n = i1->next();
        i2n = i2->next();
    }
}

void Structure::takeOwnership()
{
#ifdef QT_DEBUG
    for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
        for(Direction dir=FIRST; dir <= SECOND; ++dir)
            for(Pointer p=boundary(ori,dir).first(); p; p=p->next())
                p->setOwner(this);
#endif
}

Pointer Structure::prevReachable(Pointer p)
{
    p = prev(p);
    while(p && p->type==NON_ACCESSIBLE)
        p = prev(p);
    return p;
}

Pointer Structure::nextReachable(Pointer p)
{
    p = next(p);
    while(p && p->type==NON_ACCESSIBLE)
        p = next(p);
    return p;
}

void Structure::updatePointers(Pointer K, Pointer l, Pointer h, Pointer K1)
{
    //  iterate all segments that point to K
    //  iterate from K.l to K.h
    StructureIterator L (*this, *K, K1);
    for( ; L; ++L) {
        //  update l,h pointers that point to K
        if ((L->l != K) && (L->h != K)) continue;

        if (L->h==K)    L->h = h;
        if (L->l==K)    L->l = l;

        switch(L->type)
        {
        case REACHABLE:
            if ((!L->l || !L->h) || empty_interval(*L)) {
                //  segment becomes empty (n)
                L->clear();
            }
            else {
                Q_ASSERT(!empty_interval(*L));
                Q_ASSERT(assertPointerInterval((Pointer)L,*L));
            }
            break;
        case SEE_THROUGH:
            //  l,h pointers must point UP, resp. DOWN
            if ((!L->l && !L->h) || empty_see_through_interval((Pointer)L))
            {
                L->clear();
                //  TODO simplify
            }
            else  {
                Q_ASSERT(assertPointerInterval((Pointer)L,*L));
            }
            break;
        }
    }
}
void Structure::markNonAccesible(Orientation fringe, Structure& that)
{

    Pointer K1 = this->first(fringe).first();
    Pointer K = this->second(fringe).first();
    Pointer I = that.first(fringe).first();
    Pointer I2 = that.second(fringe).first();

    for( ; K && I; K=K->next(), I=I->next(), K1=K1->next(), I2=I2->next())
    {
        //  see [alt95]
        if (K->type!=NON_ACCESSIBLE && I->type==NON_ACCESSIBLE) {
            //  R1 becomes n
            this->markNonAccesible(K,K1);
        }
        else if (I->type!=NON_ACCESSIBLE && K->type==NON_ACCESSIBLE) {
            //  L2 becomes n
            that.markNonAccesible(I,I2);
        }
    }
}

void Structure::markNonAccesible(Pointer K, Pointer K1)
{
    Q_ASSERT(K->type!=NON_ACCESSIBLE);
    K->type = NON_ACCESSIBLE;
    //  all h-pointers into that segment are lowered
    Pointer h2 = this->prevReachable(K);
    //  all l-pointers into that segment are increased
    Pointer l2 = this->nextReachable(K);

    Q_ASSERT(!l2 || (l2->type!=NON_ACCESSIBLE));
    Q_ASSERT(!h2 || (h2->type!=NON_ACCESSIBLE));

    //  update all segments pointing to K
    updatePointers(K, l2, h2, K1);

    if (K1->type==SEE_THROUGH)
    {
        //  s-n becomes r-n
        K1->type = REACHABLE;
        if (!K1->l) K1->l = l2;
        if (!K1->h) K1->h = h2;

        if (!K1->l || !K1->h || empty_interval(*K1)) {
            //  segment becomes empty (n)
            K1->type = NON_ACCESSIBLE;
            K1->clear();
        }
        else {
            Q_ASSERT(! empty_interval(*K1));
            Q_ASSERT(assertPointerInterval(K1,*K1));
        }

    }

    K->clear(); //  clear l and h
}
void Structure::scanAndMerge(Pointer K, Orientation fringe)
{
   //  TODO parallelize? or better not touch ...
    for( ; K; K=K->next())
    {
        if (K->type==NON_ACCESSIBLE) continue;
        Q_ASSERT(K->type==REACHABLE || K->type==SEE_THROUGH);

        //  1. if h(K) exists ...
        if (K->h && K->h->ori==fringe)
        {   //  ... and points into some r- or s- interval I of L2
            Pointer I = K->h->twin(2);
            Q_ASSERT(I->ori==K->h->ori);
            Q_ASSERT(I->dir!=K->h->dir);
            Q_ASSERT(((Interval)*I)==((Interval)*K->h));

            switch(I->type)
            {
            case REACHABLE:
                Q_ASSERT(! empty_interval(*I));
                Q_ASSERT(I->h);
                K->h = I->h;
                break;
            case SEE_THROUGH:
                if (I->h) {
                    K->h = I->h;
                }
                else {
                    Q_ASSERT(K->h->twin(1)==I->twin(3));
                    K->h = I->twin(3);
                }
                break;
            }
            Q_ASSERT(K->h);
        }
        //  2. if l(K) exists and points into some interval I in L2
        if (K->l && K->l->ori==fringe)
        {            
            Pointer I = K->l->twin(2);
            Q_ASSERT(I->ori==K->l->ori);
            Q_ASSERT(I->dir!=K->l->dir);
            Q_ASSERT(((Interval)*I)==((Interval)*K->l));

            switch(I->type)
            {
            case REACHABLE:
                //  2.1 if I is type r, then l(K) := l(I)
                Q_ASSERT(! empty_interval(*I));
                Q_ASSERT(I->l);
                K->l = I->l;
                break;
            case SEE_THROUGH:
                if (I->l) {
                    K->l = I->l;
                }
                else {
                    //  2.2 if I is type s then set l(K) to the lower endpoint of R2
                    Q_ASSERT(K->l->twin(1)==I->twin(3));
                    K->l = I->twin(3);
                }
                break;
            }
        }
        //  3. if K is type s and K' is the corresponding interval at L2
        if (K->type==SEE_THROUGH && K->ori==fringe)
        {
            //  3.1 if K' is type r then set K to type r and and l(K) := l(K')
            //Q_ASSERT(K->twin(3)==K2->twin(2));
            Pointer K3 = K->twin(3);
            Q_ASSERT(K3->dir==K->dir);
            Q_ASSERT(K3->ori==K->ori);
            if (K3->type==REACHABLE) {
                K->type = REACHABLE;
                //Q_ASSERT(!K->l);
                //Q_ASSERT(K3->l);
                if (!K->l) K->l = K3->l;
                if (!K->h) K->h = K3->h;
                Q_ASSERT(K->l && K->h);
            }
        }

        Q_ASSERT(!K->l || K->type!=NON_ACCESSIBLE);
        Q_ASSERT(!K->h || K->type!=NON_ACCESSIBLE);
        Q_ASSERT(K->type==SEE_THROUGH || ! empty_interval(*K));
        Q_ASSERT(assertPointerInterval(K,*K));
    }
}

Pointer Structure::split(Pointer seg, double y, Pointer twin)
{
    Q_ASSERT(seg->contains(y));
    //  split interval at 'y'
    BoundaryList& list = boundary(seg->ori,seg->dir);

    Pointer copy = new BoundarySegment(*seg);
    copy->upper() = seg->lower() = y;

    list.insert_before(copy,seg);

    Q_ASSERT(copy->next()==seg);
    Q_ASSERT(seg->prev()==copy);

    if (seg->type!=NON_ACCESSIBLE)
    {   //  update pointers that can see 'seg'
/*
 *      PointerInterval ival = *seg;
        if (!ival.l) {
            //  missing "see-through" pointer
            Q_ASSERT(seg->type==SEE_THROUGH);
            Q_ASSERT((seg->ori==VERTICAL && seg->dir==FIRST)
                     || (seg->ori==HORIZONTAL && seg->dir==SECOND));
            ival.l = twin;
        }
        if (!ival.h) {
            Q_ASSERT(seg->type==SEE_THROUGH);
            Q_ASSERT((seg->ori==VERTICAL && seg->dir==SECOND)
                     || (seg->ori==HORIZONTAL && seg->dir==FIRST));
            ival.h = twin;
        }

        Q_ASSERT(ival.l && ival.h);
*/
        StructureIterator i (*this, *seg, twin);
        if (seg->ori==VERTICAL)
        {
            //  l-pointers into vertical 'seg' are adjusted to 'copy'
            for( ; i; ++i)
                if (i->l == seg) {
                    i->l = copy;
                    Q_ASSERT(assertPointerInterval((Pointer)i,*i));
                }
        }
        else
        {
            //  h-pointers into horizontal 'seg' are adjusted to 'copy'
            //  EXCEPT h-pointers of S intervals
            Q_ASSERT(seg->ori==HORIZONTAL);
            for( ; i; ++i)
                if (i->h == seg) {
                    i->h = copy;
                    Q_ASSERT(assertPointerInterval((Pointer)i,*i));
                }
        }
    }

    return copy;
}

void Structure::merge(BoundaryList& list, Pointer a, Pointer b)
{
    b->lower() = a->lower();
    list.remove(a);
    //  TODO correct all pointers into a
    //  see split()

    delete a;
}

Pointer Structure::next(Pointer p) const
{
    Pointer result = p->next(p->ori);
    //  HORIZONTAL = 0 = p->prev()
    //  VERTICAL = 1 = p->next()
    if (!result)
    {
        //  bottom-left corner
        if (p->ori==HORIZONTAL && p->dir==BOTTOM_LEFT)
            result = left().first();
        //  right-top corner
        if (p->ori==VERTICAL && p->dir==RIGHT_TOP)
            result = top().last();
    }
    return result;
}

Pointer Structure::prev(Pointer p) const
{
    Pointer result = p->next(1 - p->ori);
    //  HORIZONTAL = 0 = p->next()
    //  VERTICAL = 1 = p->prev()
    if (!result)
    {
        //  left-bottom corner
        if (p->ori==VERTICAL && p->dir==BOTTOM_LEFT)
            result = bottom().first();
        //  top-right corner
        if (p->ori==HORIZONTAL && p->dir==RIGHT_TOP)
            result = right().last();
    }
    return result;
}


void Structure::testCancelFlag() {
    if (cancelFlag && *cancelFlag) {
        throw app::InterruptedException();
    }
}


bool Structure::assertPointerInterval(Pointer p, const PointerInterval& ival)
{
    if (p->dir==FIRST) {
        if (p->type==SEE_THROUGH) {
            //  l and h-pointers must point UP
            Q_ASSERT(ival.l || ival.h);
            Q_ASSERT(! ival.h || (compare_pointers(p,ival.h) <= 0) );
            Q_ASSERT(! ival.l || (compare_pointers(p,ival.l) <= 0) );
        }
        else {
            //  l and h-pointers must point UP (strictly, otherwise it would be a see-through)
            Q_ASSERT(ival.l && ival.h);
            Q_ASSERT( (compare_pointers(p,ival.h) <= 0) && (p!=ival.h) );
            Q_ASSERT( (compare_pointers(p,ival.l) <= 0) && (p!=ival.l) );
        }
    }
    else
    {
        if (p->type==SEE_THROUGH) {
            //  l and h-pointers must point DOWN
            Q_ASSERT(ival.l || ival.h);
            Q_ASSERT(! ival.h || (compare_pointers(p,ival.h) >= 0) );
            Q_ASSERT(! ival.l || (compare_pointers(p,ival.l) >= 0) );
        }
        else {
            //  l and h-pointers must point DOWN (strictly, otherwise it would be a see-through)
            Q_ASSERT(ival.l && ival.h);
            Q_ASSERT( (compare_pointers(p,ival.h) >= 0) && (p!=ival.h) );
            Q_ASSERT( (compare_pointers(p,ival.l) >= 0) && (p!=ival.l) );
        }
    }
    return true;
}

bool Structure::assertSynchedIntervals(Pointer i1, Pointer i2, Pointer i3, Pointer i4)
{
    for( ; i1; i1=i1->next(), i2=i2->next(), i3=i3->next(), i4=i4->next()) {
        Q_ASSERT(i1->lower()==i2->lower());
        Q_ASSERT(i1->upper()==i2->upper());

        Q_ASSERT(i1->lower()==i3->lower());
        Q_ASSERT(i1->upper()==i3->upper());

        Q_ASSERT(i1->lower()==i4->lower());
        Q_ASSERT(i1->upper()==i4->upper());

        //  Brezel-shaped ring pointer
        Q_ASSERT(i2->twin(1)==i4);
        Q_ASSERT(i2->twin(2)==i3);
        Q_ASSERT(i2->twin(3)==i1);
        Q_ASSERT(i2->twin(4)==i2);

        Q_ASSERT(i3->twin(1)==i1);
        Q_ASSERT(i3->twin(2)==i2);
        Q_ASSERT(i3->twin(3)==i4);
        Q_ASSERT(i3->twin(4)==i3);
    }

    Q_ASSERT(!i1 && !i2 && !i3 && !i4);
    return true;
}


StructureIterator::StructureIterator(const Structure& astr,
                                     const PointerInterval& ival,
                                     Pointer ifnull)
    : str(astr), current(ival.l), last(ival.h)
{
    if (!current) current = ifnull;
    if (!last) last = ifnull;

    Q_ASSERT(current && last);
    Q_ASSERT(current->dir == last->dir);
    Q_ASSERT(!empty_interval(current,last));
}

StructureIterator::StructureIterator(const Structure& astr, Pointer a, Pointer b)
    : str(astr), current(a), last(b)
{
    Q_ASSERT(current && last);
    Q_ASSERT(current->dir == last->dir);
    Q_ASSERT(!empty_interval(current,last));
}

StructureIterator &StructureIterator::operator++()     //  pre-increment
{
    if (current==last)
        current = NULL;   //  EOF
    else
        current = str.next(current);
    return *this;
}

std::ostream& frechet::reach::operator<<(std::ostream &out, const Structure &str)
{
    return out << "{" << str.bottom() << std::endl
               << " "<<str.top() << std::endl
               << " "<<str.left() << std::endl
               << " "<<str.right() << "}" << std::endl;
}