1/*
24ti2 -- A software package for algebraic, geometric and combinatorial
3problems on linear spaces.
4
5Copyright (C) 2006 4ti2 team.
6
7This program is free software; you can redistribute it and/or
8modify it under the terms of the GNU General Public License
9as published by the Free Software Foundation; either version 2
10of the License, or (at your option) any later version.
11
12This program is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with this program; if not, write to the Free Software
19Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20*/
21
22#include "groebner/OnesTree.h"
23
24#include <iostream>
25#include <string>
26
27using namespace _4ti2_;
28
29template <class IndexSet>
30const int OnesTreeNode<IndexSet>::INDENT = 4;
31
32template <class IndexSet>
33OnesTreeNode<IndexSet>::OnesTreeNode()
34{
35}
36
37template <class IndexSet>
38OnesTreeNode<IndexSet>::~OnesTreeNode()
39{
40}
41
42template <class IndexSet>
43OnesTreeBranch<IndexSet>::OnesTreeBranch()
44        : OnesTreeNode<IndexSet>()
45{
46}
47
48template <class IndexSet>
49OnesTreeBranch<IndexSet>::~OnesTreeBranch()
50{
51    for (unsigned int i = 0; i < nodes.size(); ++i)  { delete nodes[i].second; }
52}
53
54template <class IndexSet>
55void
56OnesTreeBranch<IndexSet>::insert(const IndexSet& support, int start, int remaining, int index)
57{
58    assert(remaining != 0);
59    // There should always be another unless remaining == 0.
60    int next_one = start;
61    while (!support[next_one]) { ++next_one; }
62
63    int i = 0;
64    while (i < (int) nodes.size() && next_one != nodes[i].first) { ++i; }
65    if (i < (int) nodes.size())
66    {
67        nodes[i].second->insert(support, next_one+1, remaining-1, index);
68    }
69    else
70    {
71        OnesTreeNode<IndexSet>* new_node;
72        if (remaining > 1) { new_node = new OnesTreeBranch<IndexSet>(); }
73        else { new_node = new OnesTreeLeaf<IndexSet>(); }
74        nodes.push_back(std::pair<int,OnesTreeNode<IndexSet>*>(next_one,new_node));
75        new_node->insert(support, next_one+1, remaining-1, index);
76    }
77}
78
79template <class IndexSet>
80bool
81OnesTreeBranch<IndexSet>::dominated(const IndexSet& b, int index1, int index2)
82{
83    for (unsigned int i = 0; i < nodes.size(); ++i)
84    {
85        if (b[nodes[i].first] && nodes[i].second->dominated(b, index1, index2)) { return true; }
86    }
87    return false;
88}
89
90template <class IndexSet>
91int
92OnesTreeBranch<IndexSet>::index_dominated(const IndexSet& b, int index1, int index2)
93{
94    int index;
95    for (unsigned int i = 0; i < nodes.size(); ++i)
96    {
97        if (b[nodes[i].first])
98        {
99            index = nodes[i].second->index_dominated(b, index1, index2);
100            if (index >= 0) { return index; }
101        }
102    }
103    return -1;
104}
105
106template <class IndexSet>
107int
108OnesTreeBranch<IndexSet>::find(const IndexSet& support, int start, int remaining)
109{
110    assert(remaining != 0);
111    // There should always be another unless remaining == 0.
112    int next_one = start;
113    while (!support[next_one]) { ++next_one; }
114
115    int i = 0;
116    while (i < (int) nodes.size() && next_one != nodes[i].first) { ++i; }
117    if (i < (int) nodes.size())
118    {
119        return nodes[i].second->find(support, next_one+1, remaining-1);
120    }
121    return -1;
122}
123
124template <class IndexSet>
125void
126OnesTreeBranch<IndexSet>::find_diff(std::vector<int>& indices, const IndexSet& supp, int diff)
127{
128    for (unsigned int i = 0; i < nodes.size(); ++i)
129    {
130        if (supp[nodes[i].first])
131        {
132            if (diff > 0) { nodes[i].second->find_diff(indices, supp, diff-1); }
133        }
134        else
135        {
136            nodes[i].second->find_diff(indices, supp, diff);
137        }
138    }
139}
140
141template <class IndexSet>
142void
143OnesTreeBranch<IndexSet>::find_diff(std::vector<int>& indices, const IndexSet& supp1, int diff1, const IndexSet& supp2, int diff2)
144{
145    for (unsigned int i = 0; i < nodes.size(); ++i)
146    {
147#if 0
148        int temp_diff1 = diff1;
149        int temp_diff2 = diff2;
150        if (supp1[nodes[i].first]) { --temp_diff1; }
151        if (temp_diff1 < 0) { continue; }
152        if (supp2[nodes[i].first]) { --temp_diff2; }
153        if (temp_diff2 < 0) { continue; }
154        nodes[i].second->find_diff(indices, supp1, temp_diff1, supp2, temp_diff2);
155#endif
156#if 1
157        if (supp1[nodes[i].first])
158        {
159            if (diff1 > 0)
160            {
161                if (supp2[nodes[i].first])
162                {
163                    if (diff2 > 0)
164                    {
165                        nodes[i].second->find_diff(indices, supp1, diff1-1, supp2, diff2-1);
166                    }
167                }
168                else
169                {
170                    nodes[i].second->find_diff(indices, supp1, diff1-1, supp2, diff2);
171                }
172            }
173        }
174        else
175        {
176            if (supp2[nodes[i].first])
177            {
178                if (diff2 > 0)
179                {
180                    nodes[i].second->find_diff(indices, supp1, diff1, supp2, diff2-1);
181                }
182            }
183            else
184            {
185                nodes[i].second->find_diff(indices, supp1, diff1, supp2, diff2);
186            }
187        }
188#endif
189    }
190}
191
192template <class IndexSet>
193void
194OnesTreeBranch<IndexSet>::dump(int level)
195{
196    std::string indent(level*OnesTreeNode<IndexSet>::INDENT, ' ');
197    //*out << indent << level << "\n";
198    for (unsigned int i = 0; i < nodes.size(); ++i)
199    {
200        *out << indent << nodes[i].first << "\n";
201        nodes[i].second->dump(level+1);
202    }
203}
204
205template <class IndexSet>
206OnesTreeLeaf<IndexSet>::OnesTreeLeaf()
207        : OnesTreeNode<IndexSet>()
208{
209    index = -1;
210}
211
212template <class IndexSet>
213OnesTreeLeaf<IndexSet>::~OnesTreeLeaf()
214{
215}
216
217template <class IndexSet>
218void
219OnesTreeLeaf<IndexSet>::insert(const IndexSet& support, int start, int remaining, int _index)
220{
221    // If index != -1, then this implies that the leaf already exists.
222    assert(index == -1);
223    assert(remaining == 0);
224    index = _index;
225    //*out << "Start = " << start << " Rem = " << remaining;
226    //*out << " Index = " << index << "\n";
227}
228
229template <class IndexSet>
230bool
231OnesTreeLeaf<IndexSet>::dominated(const IndexSet& b, int index1, int index2)
232{
233    if (index != index1 && index != index2) { return true; }
234    return false;
235}
236
237template <class IndexSet>
238int
239OnesTreeLeaf<IndexSet>::index_dominated(const IndexSet& b, int index1, int index2)
240{
241    if (index != index1 && index != index2) { return index; }
242    return -1;
243}
244
245template <class IndexSet>
246int
247OnesTreeLeaf<IndexSet>::find(const IndexSet& support, int start, int remaining)
248{
249    if (remaining == 0) { return index; }
250    return -1;
251}
252
253template <class IndexSet>
254void
255OnesTreeLeaf<IndexSet>::find_diff(std::vector<int>& indices, const IndexSet& supp, int diff)
256{
257    indices.push_back(index);
258}
259
260template <class IndexSet>
261void
262OnesTreeLeaf<IndexSet>::find_diff(std::vector<int>& indices, const IndexSet& supp1, int diff1, const IndexSet& supp2, int diff2)
263{
264    indices.push_back(index);
265}
266
267template <class IndexSet>
268void
269OnesTreeLeaf<IndexSet>::dump(int level)
270{
271    std::string indent(level*OnesTreeNode<IndexSet>::INDENT, ' ');
272    *out << indent << index << "\n";
273}
274
275template <class IndexSet>
276OnesTree<IndexSet>::OnesTree(const std::vector<IndexSet>& supports, int num)
277{
278    root = new OnesTreeBranch<IndexSet>();
279    insert(supports,num);
280}
281
282template <class IndexSet>
283void
284OnesTree<IndexSet>::insert(const std::vector<IndexSet>& supports, int num)
285{
286    assert(!supports.empty());
287    for (int i = 0; i < num; ++i)
288    {
289        //*out << "Inserting Support:\n" << supports[i] << "\n";
290        root->insert(supports[i], 0, supports[i].count(), i);
291    }
292}
293
294template <class IndexSet>
295OnesTree<IndexSet>::OnesTree()
296{
297    root = new OnesTreeBranch<IndexSet>();
298}
299
300template <class IndexSet>
301OnesTree<IndexSet>::~OnesTree()
302{
303    delete root;
304}
305
306template <class IndexSet>
307bool
308OnesTree<IndexSet>::dominated(const IndexSet& b, int index1, int index2)
309{
310    return root->dominated(b, index1, index2);
311}
312
313template <class IndexSet>
314int
315OnesTree<IndexSet>::index_dominated(const IndexSet& b, int index1, int index2)
316{
317    return root->index_dominated(b, index1, index2);
318}
319
320template <class IndexSet>
321void
322OnesTree<IndexSet>::insert(const IndexSet& support, int index)
323{
324    root->insert(support, 0, support.count(), index);
325}
326
327template <class IndexSet>
328void
329OnesTree<IndexSet>::find_diff(std::vector<int>& indices, const IndexSet& supp, int diff)
330{
331    root->find_diff(indices, supp, diff);
332}
333
334template <class IndexSet>
335void
336OnesTree<IndexSet>::find_diff(std::vector<int>& indices, const IndexSet& supp1, int diff1, const IndexSet& supp2, int diff2)
337{
338    root->find_diff(indices, supp1, diff1, supp2, diff2);
339}
340
341template <class IndexSet>
342void
343OnesTree<IndexSet>::dump()
344{
345    *out << "Tree Dump:\n";
346    root->dump(0);
347}
348
349
350