/** * Copyright (c) 2006 Michele Mastrogiovanni. * *   Licensed under the Apache License, Version 2.0 (the "License"); *   you may not use this file except in compliance with the License. *   You may obtain a copy of the License at * *       http://www.apache.org/licenses/LICENSE-2.0 * *   Unless required by applicable law or agreed to in writing, software *   distributed under the License is distributed on an "AS IS" BASIS, *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *   See the License for the specific language governing permissions and *   limitations under the License. * */ #include "CyclesFinder.h"#include <algorithm>CyclesFinder::CyclesFinder(Paths paths) {     table = paths;    H = table.size();    W = table[0].size();                next.resize(H + 1);    for (int y = 0; y <= H; y++)        next[y].resize(W);                    calculated = false;}        voidCyclesFinder::find_cycle(int k, Cycles & cycles) {        if (!calculated) {        sort(table.begin(), table.end(), PathsCompare());            calculate_next();        calculated = true;    }        if (k % 2 == 0)        coppie(k / 2, k / 2, cycles);    else        coppie(k / 2, k / 2 + 1, cycles);    }/*    Nota: le coppie (1,2) e (2,1) sono differenti a meno che x = y.    in quel caso la coppia ripetuta va eliminata.    Si elimina quella che ha il primo valore piu' grande.*/void CyclesFinder::print_ciclo(int x, int y, int x_, int y_, Cycles & cycles) {    set<NodeAddress> s;    int i;    for (i = 0; i < x; i++)        s.insert(table[x_][W-i-1]);            for (i = 1; i < y; i++)        s.insert(table[y_][W-y+i]);    if (s.size() != (unsigned int)(x + y - 1))        return;    Path v(s.size());    for (i = 0; i < x; i++) {        v[i] = table[x_][W-i-1];    }    for (i = 1; i < y; i++) {        v[x + i - 1] = table[y_][W-y+i];    }    // print_path(v);    Cycles::iterator i_;    for (i_ = cycles.begin(); i_ != cycles.end(); i_++) {        Path & pp = (Path&)(*i_);        if (isPathEqual(pp, v))            break;    }    if (i_ != cycles.end())        return;    cycles.insert(v);        }            void CyclesFinder::coppie (int x, int y, Cycles & cycles) {    //printf("Cicli lunghi %d [x = %d, y = %d]\n", x+y, x, y);    for (int x_ = 0; next[x_][W-x] != -1; x_ = next[x_][W-x])        for (int y_ = 0; next[y_][W-y] != -1; y_ = next[y_][W-y])            if (x_ != y_)                if (table[x_][W-x] == table[y_][W-y]) {                    if (table[y_][W-x] == table[x_][W-y]) {                        if (x_ > y_)                            print_ciclo(x, y, x_, y_, cycles);                    }                    else                        print_ciclo(x, y, x_, y_, cycles);                }}voidCyclesFinder::calculate_next() {                next.resize(next.size() + 1);    next[H].resize(W);        for (int x = 0; x < W; x++)        next[0][x] = 0;    for (int y = 1; y < H; y++) {                int x;        for (x = 0; (x < W) && (table[y][W-x-1] == table[y-1][W-x-1]); x++)            next[y][W-x-1] = next[y-1][W-x-1];        for (int tmp = 0; tmp < W-x; tmp++) {            next[next[y-1][tmp]][tmp] = y;            next[y][tmp] = y;        }    }        for (int x = 0; x < W; x++) {        next[next[H-1][x]][x] = H;        next[H][x] = -1;    }}voidCyclesFinder::print_paths(Paths & t){	/*    for (unsigned int y = 0; y < t.size(); y++) {        printf("(%d) ", y);        for (unsigned int x = 0; x < t[y].size(); x++)            printf("%d  ", t[y][x]);        printf("\n");    }    // printf("--------------------\n");	*/}voidCyclesFinder::print_path(const Path & t){    for (unsigned int x = 0; x < t.size(); x++)        printf("%d ", t[x]);    printf("\n");    printf("--------------------\n");}bool CyclesFinder::isPathEqual(Path & a, Path & b) {    unsigned i;    for (i = 0; i < a.size() && a[i] == b[i]; i++);    if (i == a.size())        return true;    for (i = 0; i < a.size() && a[i] == b[b.size()-i-1]; i++);    return i == a.size();}