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 "containerhash.h"


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

}


ContainerHash::~ContainerHash()
{
        for (int i=0; i<max_size; i++)
        {
                delete solutions[i];
        }
}

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

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


void ContainerHash::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 base2 = (m_hashroof/2)+i;
                        

                        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 ContainerHash::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;
                
                std::auto_ptr<Solution> tmp( (*i).get()->copy() );
                
                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;
                        }
                }
        }
}

void ContainerHash::addSolution(Solution* sol)
{
    int hash = m_size % max_size;
        solutions[hash]->push_back( boost::shared_ptr<Solution>(sol) );   
    m_size++;
        total++;

}

Solution* ContainerHash::solution(int index)
{
    int count=0;
        ListIt it;
    for (it = solutions[0]->begin(); it != solutions[0]->end(); it++, count++) {
        if (count == index) {
                break;
                } 
    }
    return (*it).get();
}
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 "containerhash.h"
21
22
23	ContainerHash::ContainerHash(GUIUpdate* update)
24	: SolutionContainer(update)
25	{
26	total = 0;
27	m_size = 0;
28	m_hashroof = max_size;
29	for (int i=0; i< max_size; i++)
30	solutions[i] = new SolList();
31
32	}
33
34
35	ContainerHash::~ContainerHash()
36	{
37	for (int i=0; i<max_size; i++)
38	{
39	delete solutions[i];
40	}
41	}
42
43	int ContainerHash::numSolutions()
44	{
45	int size = 0;
46	for (int i=0; i<m_hashroof; i++) {
47	size += solutions[i]->size();
48	}
49	return size;
50	}
51
52	int ContainerHash::totalSolutions()
53	{
54	return total;
55	}
56
57
58	void ContainerHash::uniqueSolutions()
59	{
60	while (m_hashroof >1 ) {
61	for (int bucket=0; bucket < m_hashroof; bucket++) {
62	for (int i=1;i<=4;i++) {
63	if (m_halt)
64	return;
65	uniqueSolutionsWorker(bucket, i,false);
66	uniqueSolutionsWorker(bucket, i,true);
67	}
68	}
69	for (int i=0; i< (m_hashroof/2); i++) {
70	int base2 = (m_hashroof/2)+i;
71
72
73	ListIt p = solutions[i]->end();
74	solutions[i]->splice(p, *solutions[base2]);
75	}
76	m_hashroof /= 2;
77	}
78
79	for (int i=1;i<=4;i++) {
80	uniqueSolutionsWorker(0, i, false);
81	uniqueSolutionsWorker(0, i, true);
82	}
83	}
84
85
86
87
88	void ContainerHash::uniqueSolutionsWorker(int bucket, int rot,bool mirror)
89	{
90	int match_count;
91
92	if (solutions[bucket]->size() == 0)
93	return;
94	if (total == -1)
95	total = solutions[bucket]->size();
96
97	for (ListIt i=solutions[bucket]->begin(); i != solutions[bucket]->end(); i++) {
98	if (m_halt)
99	return;
100	match_count = 0;
101
102	std::auto_ptr<Solution> tmp( (*i).get()->copy() );
103
104	if (mirror)
105	tmp->mirror();
106	for (int k=0;k<rot;k++)
107	tmp->rotate90();
108
109	//unders�g kun resten af m�ngden, start ved i+1
110	ListIt j =i;
111	j++;
112	for ( ; j!=solutions[bucket]->end();j++)
113	{
114	if ( tmp == (*j) )
115	{
116	solutions[bucket]->erase(j);
117	break;
118	}
119	}
120	}
121	}
122
123	void ContainerHash::addSolution(Solution* sol)
124	{
125	int hash = m_size % max_size;
126	solutions[hash]->push_back( boost::shared_ptr<Solution>(sol) );
127	m_size++;
128	total++;
129
130	}
131
132	Solution* ContainerHash::solution(int index)
133	{
134	int count=0;
135	ListIt it;
136	for (it = solutions[0]->begin(); it != solutions[0]->end(); it++, count++) {
137	if (count == index) {
138	break;
139	}
140	}
141	return (*it).get();
142	}