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