libsemigroups
rwse.h
1 //
2 // libsemigroups - C++ library for semigroups and monoids
3 // Copyright (C) 2016 James D. Mitchell
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 3 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, see <http://www.gnu.org/licenses/>.
17 //
18 
19 #ifndef LIBSEMIGROUPS_SRC_RWSE_H_
20 #define LIBSEMIGROUPS_SRC_RWSE_H_
21 
22 #include <algorithm>
23 #include <stack>
24 #include <string>
25 #include <utility>
26 #include <vector>
27 
28 #include "elements.h"
29 #include "rws.h"
30 
31 namespace libsemigroups {
32 
37  class RWSE : public Element {
38  using rws_word_t = RWS::rws_word_t;
39 
40  private:
41  RWSE(RWS* rws, rws_word_t* w, bool reduce)
42  : Element(Element::elm_t::RWSE), _rws(rws), _rws_word(w) {
43  if (reduce) {
44  _rws->rewrite(_rws_word);
45  }
46  }
47 
48  public:
60  RWSE(RWS* rws, rws_word_t* w) : RWSE(rws, w, true) {
61  LIBSEMIGROUPS_ASSERT(w != nullptr);
62  }
63 
72  RWSE(RWS& rws, rws_word_t const& w) : RWSE(&rws, new rws_word_t(w)) {}
73 
77  RWSE(RWS& rws, letter_t const& a) : RWSE(&rws, RWS::uint_to_rws_word(a)) {}
78 
82  RWSE(RWS& rws, word_t const& w) : RWSE(&rws, RWS::word_to_rws_word(w)) {}
83 
89  bool operator==(Element const& that) const override {
90  LIBSEMIGROUPS_ASSERT(_rws_word != nullptr);
91  LIBSEMIGROUPS_ASSERT(static_cast<RWSE const&>(that)._rws_word != nullptr);
92  return *(static_cast<RWSE const&>(that)._rws_word) == *(this->_rws_word);
93  }
94 
100  // TODO should use the reduction ordering of RWS.
101  bool operator<(const Element& that) const override;
102 
108  Element* really_copy(size_t increase_deg_by) const override;
109 
114  void copy(Element const* x) override;
115  void swap(Element* x) override;
116 
120  void really_delete() override {
121  delete _rws_word;
122  _rws_word = nullptr;
123  }
124 
133  size_t complexity() const override {
134  return Semigroup::LIMIT_MAX;
135  }
136 
143  size_t degree() const override {
144  return 0;
145  }
146 
153  Element* identity() const override {
154  return new RWSE(_rws, new rws_word_t());
155  }
156 
160  void cache_hash_value() const override {
161  LIBSEMIGROUPS_ASSERT(_rws_word != nullptr);
162  this->_hash_value = std::hash<rws_word_t>()(*_rws_word);
163  }
164 
176  void redefine(Element const* x, Element const* y) override;
177 
179  rws_word_t const* get_rws_word() const {
180  return _rws_word;
181  }
182 
183  private:
184  // TODO const!
185  RWS* _rws;
186  rws_word_t* _rws_word;
187  };
188 } // namespace libsemigroups
189 
190 #endif // LIBSEMIGROUPS_SRC_RWSE_H_
std::string * rewrite(std::string *w) const
Rewrites the word w in-place according to the current rules in the rewriting system.
Definition: rws.h:271
void cache_hash_value() const override
Calculates a hash value for this object which is cached.
Definition: rwse.h:160
static index_t const LIMIT_MAX
This variable is used to indicate the maximum possible limit that can be used with Semigroup::enumera...
Definition: semigroups.h:870
Element(elm_t type=Element::elm_t::NOT_RWSE)
A constructor.
Definition: elements.h:63
std::vector< letter_t > word_t
Type for a word over the generators of a semigroup.
Definition: semigroups.h:55
void really_delete() override
Deletes the underlying rws_word_t that this object wraps.
Definition: rwse.h:120
void swap(Element *x) override
Swap another Element with this.
Definition: rwse.cc:54
Abstract base class for semigroup elements.
Definition: elements.h:44
size_t degree() const override
Returns the degree of an RWSE.
Definition: rwse.h:143
bool operator<(const Element &that) const override
Returns true if this is less than that and false if it is not.
Definition: rwse.cc:25
Element * really_copy(size_t increase_deg_by) const override
Returns a pointer to a copy of this.
Definition: rwse.cc:38
rws_word_t const * get_rws_word() const
Returns a pointer to the rws_word_t used to create this.
Definition: rwse.h:179
void redefine(Element const *x, Element const *y) override
Multiply x and y and stores the result in this.
Definition: rwse.cc:62
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
void copy(Element const *x) override
Copy x into this.
Definition: rwse.cc:46
size_t complexity() const override
Returns the approximate time complexity of multiplying two RWSE's.
Definition: rwse.h:133
RWSE(RWS *rws, rws_word_t *w)
Constructor from a rewriting system and a word.
Definition: rwse.h:60
Element * identity() const override
Return the identity RWSE.
Definition: rwse.h:153
This class is used to represent a string rewriting system defining a finitely presented monoid or sem...
Definition: rws.h:135
bool operator==(Element const &that) const override
Returns true if this equals that.
Definition: rwse.h:89
size_t letter_t
Type for the index of a generator of a semigroup.
Definition: semigroups.h:52
Subclass of Element that wraps an libsemigroups::rws_word_t.
Definition: rwse.h:37
RWSE(RWS &rws, letter_t const &a)
Constructor from a rewriting system and a letter.
Definition: rwse.h:77
RWSE(RWS &rws, rws_word_t const &w)
Constructor from a rewriting system and a word.
Definition: rwse.h:72
RWSE(RWS &rws, word_t const &w)
Constructor from a rewriting system and a word.
Definition: rwse.h:82