queensgui/src/containerhash.cpp

/***************************************************************************
 *   Copyright (C) 2005 by Torben Nielsen   *
 *   torben@t-hoerup.dk   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#include "solutionhash.h"

SolutionHash::SolutionHash(GUIUpdate* update)
  : SolutionContainer(update)
{
    total = -1;
    m_size = 0;
    m_hashroof = max_size;
    for (int i=0; i< max_size; i++)
        solutions[i] = new SolList();

}


SolutionHash::~SolutionHash()
{
}

int SolutionHash::numSolutions()
{
        int size = 0;
        for (int i=0; i<m_hashroof; i++) {
                size += solutions[i]->size();
        }
        return size;
}

int SolutionHash::totalSolutions()
{
        return total;
}


void SolutionHash::uniqueSolutions()
{
        while (m_hashroof >1 ) {
                for (int bucket=0; bucket < m_hashroof; bucket++) {
                        for (int i=1;i<=4;i++) {
                                if (m_halt)
                                        return;
                                uniqueSolutionsWorker(bucket, i,false);
                                uniqueSolutionsWorker(bucket, i,true);
                        }
                }
                for (int i=0; i< (m_hashroof/2); i++) {
                        //int base = i*2;
                        int base2 = (m_hashroof/2)+i;
                        
                        /*if (i!=0) {
                                solutions[i] = solutions[base];
                        }

                        ListIt p = solutions[i]->end();
                        solutions[i]->splice(p, *solutions[base+1] );
                        */
                        
                        ListIt p = solutions[i]->end();
                        solutions[i]->splice(p, *solutions[base2]);
                }
                m_hashroof /= 2;
        }

        for (int i=1;i<=4;i++) {
                uniqueSolutionsWorker(0, i, false);
                uniqueSolutionsWorker(0, i, true);
        }
}


void SolutionHash::uniqueSolutionsWorker(int bucket, int rot,bool mirror)
{
        int match_count;

        if (solutions[bucket]->size() == 0)
                return;
        if (total == -1)
                total = solutions[bucket]->size();
        
        for (ListIt i=solutions[bucket]->begin(); i != solutions[bucket]->end(); i++) {
                if (m_halt)
                        return;
                match_count = 0;
                Solution tmp(*i);
                if (mirror)
                        tmp.mirror();
                for (int k=0;k<rot;k++)
                        tmp.rotate90();

                //unders�g kun resten af m�ngden, start ved i+1             
                ListIt j =i;
                j++;
                for ( ; j!=solutions[bucket]->end();j++) {
                        if ( tmp == (*j) ) {
                                solutions[bucket]->erase(j);
                                break;
                        }
                }
        }
}


/* BACKUP
void SolutionHash::uniqueSolutionsWorker(int rot,bool mirror)
{
        int match_count;

        unique = true;
        if (total == -1)
                total = solutions.size();
        
        for (ListIt i=solutions.begin(); i != solutions.end(); i++) {
                match_count = 0;
                Solution tmp(*i);
                if (mirror)
                        tmp.mirror();
                for (int k=0;k<rot;k++)
                        tmp.rotate90();

                //unders�g kun resten af m�ngden, start ved i+1             
                ListIt j =i;
                j++;
                for ( ; j!=solutions.end();j++) {
                        if ( tmp == (*j) ) {
                                solutions.erase(j);
                                break;
                        }
                }
        }
}
*/

void SolutionHash::addSolution(Solution sol)
{
    int hash = m_size % max_size;
    solutions[hash]->push_back(sol);   
    m_size++;
}

Solution SolutionHash::solution(int index)
{
    int count=0;
    Solution returndata;
    for (ListIt it = solutions[0]->begin(); it != solutions[0]->end(); it++, count++) {
        if (count == index) {
            returndata =  *it ;
            break;
        } 
    }
    return returndata;
}
1	torben	1	/***************************************************************************
2			* Copyright (C) 2005 by Torben Nielsen *
3			* torben@t-hoerup.dk *
4			* *
5			* This program is free software; you can redistribute it and/or modify *
6			* it under the terms of the GNU General Public License as published by *
7			* the Free Software Foundation; either version 2 of the License, or *
8			* (at your option) any later version. *
9			* *
10			* This program is distributed in the hope that it will be useful, *
11			* but WITHOUT ANY WARRANTY; without even the implied warranty of *
12			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13			* GNU General Public License for more details. *
14			* *
15			* You should have received a copy of the GNU General Public License *
16			* along with this program; if not, write to the *
17			* Free Software Foundation, Inc., *
18			* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19			***************************************************************************/
20			#include "solutionhash.h"
21
22			SolutionHash::SolutionHash(GUIUpdate* update)
23			: SolutionContainer(update)
24			{
25			total = -1;
26			m_size = 0;
27			m_hashroof = max_size;
28			for (int i=0; i< max_size; i++)
29			solutions[i] = new SolList();
30
31			}
32
33
34			SolutionHash::~SolutionHash()
35			{
36			}
37
38			int SolutionHash::numSolutions()
39			{
40			int size = 0;
41			for (int i=0; i<m_hashroof; i++) {
42			size += solutions[i]->size();
43			}
44			return size;
45			}
46
47			int SolutionHash::totalSolutions()
48			{
49			return total;
50			}
51
52
53			void SolutionHash::uniqueSolutions()
54			{
55			while (m_hashroof >1 ) {
56			for (int bucket=0; bucket < m_hashroof; bucket++) {
57			for (int i=1;i<=4;i++) {
58			if (m_halt)
59			return;
60			uniqueSolutionsWorker(bucket, i,false);
61			uniqueSolutionsWorker(bucket, i,true);
62			}
63			}
64			for (int i=0; i< (m_hashroof/2); i++) {
65			//int base = i*2;
66			int base2 = (m_hashroof/2)+i;
67
68			/*if (i!=0) {
69			solutions[i] = solutions[base];
70			}
71
72			ListIt p = solutions[i]->end();
73			solutions[i]->splice(p, *solutions[base+1] );
74			*/
75
76			ListIt p = solutions[i]->end();
77			solutions[i]->splice(p, *solutions[base2]);
78			}
79			m_hashroof /= 2;
80			}
81
82			for (int i=1;i<=4;i++) {
83			uniqueSolutionsWorker(0, i, false);
84			uniqueSolutionsWorker(0, i, true);
85			}
86			}
87
88
89
90
91			void SolutionHash::uniqueSolutionsWorker(int bucket, int rot,bool mirror)
92			{
93			int match_count;
94
95			if (solutions[bucket]->size() == 0)
96			return;
97			if (total == -1)
98			total = solutions[bucket]->size();
99
100			for (ListIt i=solutions[bucket]->begin(); i != solutions[bucket]->end(); i++) {
101			if (m_halt)
102			return;
103			match_count = 0;
104			Solution tmp(*i);
105			if (mirror)
106			tmp.mirror();
107			for (int k=0;k<rot;k++)
108			tmp.rotate90();
109
110			//unders�g kun resten af m�ngden, start ved i+1
111			ListIt j =i;
112			j++;
113			for ( ; j!=solutions[bucket]->end();j++) {
114			if ( tmp == (*j) ) {
115			solutions[bucket]->erase(j);
116			break;
117			}
118			}
119			}
120			}
121
122
123			/* BACKUP
124			void SolutionHash::uniqueSolutionsWorker(int rot,bool mirror)
125			{
126			int match_count;
127
128			unique = true;
129			if (total == -1)
130			total = solutions.size();
131
132			for (ListIt i=solutions.begin(); i != solutions.end(); i++) {
133			match_count = 0;
134			Solution tmp(*i);
135			if (mirror)
136			tmp.mirror();
137			for (int k=0;k<rot;k++)
138			tmp.rotate90();
139
140			//unders�g kun resten af m�ngden, start ved i+1
141			ListIt j =i;
142			j++;
143			for ( ; j!=solutions.end();j++) {
144			if ( tmp == (*j) ) {
145			solutions.erase(j);
146			break;
147			}
148			}
149			}
150			}
151			*/
152
153			void SolutionHash::addSolution(Solution sol)
154			{
155			int hash = m_size % max_size;
156			solutions[hash]->push_back(sol);
157			m_size++;
158			}
159
160			Solution SolutionHash::solution(int index)
161			{
162			int count=0;
163			Solution returndata;
164			for (ListIt it = solutions[0]->begin(); it != solutions[0]->end(); it++, count++) {
165			if (count == index) {
166			returndata = *it ;
167			break;
168			}
169			}
170			return returndata;
171			}