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 = -1;
    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++;

}

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	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	torben	3	#include "containerhash.h"
21	torben	1
22	torben	6
23	torben	3	ContainerHash::ContainerHash(GUIUpdate* update)
24	torben	1	: SolutionContainer(update)
25			{
26			total = -1;
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	torben	3	ContainerHash::~ContainerHash()
36	torben	1	{
37	torben	6	for (int i=0; i<max_size; i++)
38			{
39			delete solutions[i];
40			}
41	torben	1	}
42
43	torben	3	int ContainerHash::numSolutions()
44	torben	1	{
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	torben	3	int ContainerHash::totalSolutions()
53	torben	1	{
54			return total;
55			}
56
57
58	torben	3	void ContainerHash::uniqueSolutions()
59	torben	1	{
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	torben	3	void ContainerHash::uniqueSolutionsWorker(int bucket, int rot,bool mirror)
89	torben	1	{
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	torben	6
102			std::auto_ptr<Solution> tmp( (*i).get()->copy() );
103
104	torben	1	if (mirror)
105	torben	2	tmp->mirror();
106	torben	1	for (int k=0;k<rot;k++)
107	torben	2	tmp->rotate90();
108	torben	1
109			//unders�g kun resten af m�ngden, start ved i+1
110			ListIt j =i;
111			j++;
112	torben	6	for ( ; j!=solutions[bucket]->end();j++)
113			{
114			if ( tmp == (*j) )
115			{
116	torben	1	solutions[bucket]->erase(j);
117			break;
118			}
119			}
120			}
121			}
122
123	torben	3	void ContainerHash::addSolution(Solution* sol)
124	torben	1	{
125			int hash = m_size % max_size;
126	torben	6	solutions[hash]->push_back( boost::shared_ptr<Solution>(sol) );
127	torben	1	m_size++;
128	torben	6
129	torben	1	}
130
131	torben	3	Solution* ContainerHash::solution(int index)
132	torben	1	{
133			int count=0;
134	torben	2	ListIt it;
135			for (it = solutions[0]->begin(); it != solutions[0]->end(); it++, count++) {
136	torben	1	if (count == index) {
137	torben	2	break;
138			}
139	torben	1	}
140	torben	6	return (*it).get();
141	torben	1	}