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