1 /* Copyright (c) 1997-2021 2 Ewgenij Gawrilow, Michael Joswig, and the polymake team 3 Technische Universität Berlin, Germany 4 https://polymake.org 5 6 This program is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 2, or (at your option) any 9 later version: http://www.gnu.org/licenses/gpl.txt. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 -------------------------------------------------------------------------------- 16 */ 17 18 #pragma once 19 20 #include "polymake/client.h" 21 #include "polymake/Graph.h" 22 #include "polymake/Set.h" 23 #include "polymake/Array.h" 24 #include "polymake/vector" 25 #include "polymake/list" 26 #include <algorithm> 27 28 namespace polymake { namespace graph { namespace lattice { 29 30 // A sequential lattice is one in which all nodes are sorted to rank (forwards or backwards). 31 // In this case, the list of nodes of given rank is a sequence and can be stored more efficiently. 32 struct Sequential : std::true_type { 33 using map_value_type = std::pair<Int, Int>; 34 using nodes_of_rank_type = sequence; 35 using nodes_of_rank_ref_type = nodes_of_rank_type; //Intentionally not a reference, as we convert pairs to sequences 36 make_map_value_typeSequential37 static map_value_type make_map_value_type(const Sequential::map_value_type& x) { return x; } make_map_value_typeSequential38 static map_value_type make_map_value_type(Int a, Int b) { return map_value_type(a,b); } trivialSequential39 static bool trivial(const map_value_type& x) { return x.second < x.first; } map_value_as_containerSequential40 static nodes_of_rank_ref_type map_value_as_container(const map_value_type& x) 41 { 42 return nodes_of_rank_ref_type(x.first, x.second - x.first+1); 43 } 44 }; 45 46 // In a nonsequential lattice, no guarantee can be made as to the order of the nodes with respect to their 47 // rank. 48 struct Nonsequential : std::false_type { 49 using map_value_type = std::list<Int>; 50 using nodes_of_rank_type = std::list<Int>; 51 using nodes_of_rank_ref_type = const nodes_of_rank_type&; 52 make_map_value_typeNonsequential53 static map_value_type make_map_value_type(const Sequential::map_value_type& x) 54 { 55 Sequential::nodes_of_rank_ref_type lseq = Sequential::map_value_as_container(x); 56 return map_value_type( lseq.begin(), lseq.end() ); 57 } make_map_value_typeNonsequential58 static map_value_type make_map_value_type(Int a, Int b) 59 { 60 return make_map_value_type(Sequential::map_value_type(a, b)); 61 } trivialNonsequential62 static bool trivial(const map_value_type& x) { return x.empty(); } map_value_as_containerNonsequential63 static nodes_of_rank_ref_type map_value_as_container(const map_value_type& x) { return x; } 64 }; 65 66 67 /* 68 * This stores, for a given lattice, the inverse map from rank to corresponding set of nodes. 69 * It is assumed that nodes are only added or deleted, never modified. 70 */ 71 template <typename SeqType> 72 class InverseRankMap { 73 protected: 74 Map<Int, typename SeqType::map_value_type > inverse_rank_map; 75 76 template <typename> 77 friend struct pm::spec_object_traits; 78 79 public: InverseRankMap()80 InverseRankMap() {} InverseRankMap(const InverseRankMap & other)81 InverseRankMap(const InverseRankMap& other) : inverse_rank_map(other.inverse_rank_map) {} 82 83 typename SeqType::nodes_of_rank_ref_type nodes_of_rank(Int d) const; 84 typename SeqType::nodes_of_rank_type nodes_of_rank_range(Int d1, Int d2) const; 85 86 void set_rank(Int n, Int r); 87 88 template <typename NodeList> set_rank_list(Int r,const NodeList & l)89 void set_rank_list(Int r, const NodeList& l) { inverse_rank_map[r] = l;} 90 91 void delete_node_and_squeeze(Int n, Int r); 92 93 template <typename Output> friend 94 Output& operator<< (GenericOutput<Output>& out, const InverseRankMap& me) 95 { 96 out.top() << me.inverse_rank_map; 97 return out.top(); 98 } 99 100 bool operator==(const InverseRankMap& other) const 101 { 102 return inverse_rank_map == other.inverse_rank_map; 103 } 104 get_map()105 const Map<Int, typename SeqType::map_value_type >& get_map() const { return inverse_rank_map; } 106 }; 107 108 109 // This is the basic data attached to a lattice node: Its face and its rank. 110 struct BasicDecoration : public GenericStruct<BasicDecoration> { 111 DeclSTRUCT( DeclFIELD(face, Set<Int>) 112 DeclFIELD(rank, Int) ); 113 BasicDecorationBasicDecoration114 BasicDecoration() {} BasicDecorationBasicDecoration115 BasicDecoration(const Set<Int>& f, Int r) : face(f), rank(r) {} 116 }; 117 118 119 } } } 120 121 namespace pm { 122 123 template <typename SeqType> 124 struct spec_object_traits< Serialized< polymake::graph::lattice::InverseRankMap<SeqType> > > : spec_object_traits<is_composite> { 125 126 typedef polymake::graph::lattice::InverseRankMap<SeqType> masquerade_for; 127 128 typedef Map<Int, typename SeqType::map_value_type> elements; 129 130 template <typename Me, typename Visitor> 131 static void visit_elements(Me &me, Visitor& v) 132 { 133 v << me.inverse_rank_map; 134 } 135 }; 136 137 } 138 139 140 // Local Variables: 141 // mode:C++ 142 // c-basic-offset:3 143 // indent-tabs-mode:nil 144 // End: 145