Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Andrew Reynolds, Andres Noetzli, Aina Niemetz
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2024 by the authors listed in the file AUTHORS
       8                 :            :  * in the top-level source directory and their institutional affiliations.
       9                 :            :  * All rights reserved.  See the file COPYING in the top-level source
      10                 :            :  * directory for licensing information.
      11                 :            :  * ****************************************************************************
      12                 :            :  *
      13                 :            :  * The sequence data type.
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "cvc5_public.h"
      17                 :            : 
      18                 :            : #ifndef CVC5__EXPR__SEQUENCE_H
      19                 :            : #define CVC5__EXPR__SEQUENCE_H
      20                 :            : 
      21                 :            : #include <memory>
      22                 :            : #include <vector>
      23                 :            : 
      24                 :            : namespace cvc5::internal {
      25                 :            : 
      26                 :            : template <bool ref_count>
      27                 :            : class NodeTemplate;
      28                 :            : typedef NodeTemplate<true> Node;
      29                 :            : class TypeNode;
      30                 :            : 
      31                 :            : /** The cvc5 sequence class
      32                 :            :  *
      33                 :            :  * This data structure is the domain of values for the sequence type.
      34                 :            :  */
      35                 :            : class Sequence
      36                 :            : {
      37                 :            :  public:
      38                 :            :   /** constructors for Sequence
      39                 :            :    *
      40                 :            :    * Internally, a cvc5::internal::Sequence is represented by a vector of Nodes (d_seq),
      41                 :            :    * where each Node in this vector must be a constant.
      42                 :            :    */
      43                 :            :   Sequence() = default;
      44                 :            :   explicit Sequence(const TypeNode& t, const std::vector<Node>& s);
      45                 :            :   Sequence(const Sequence& seq);
      46                 :            : 
      47                 :            :   ~Sequence();
      48                 :            : 
      49                 :            :   Sequence& operator=(const Sequence& y);
      50                 :            : 
      51                 :            :   Sequence concat(const Sequence& other) const;
      52                 :            : 
      53                 :     167835 :   bool operator==(const Sequence& y) const { return cmp(y) == 0; }
      54                 :            :   bool operator!=(const Sequence& y) const { return cmp(y) != 0; }
      55                 :            :   bool operator<(const Sequence& y) const { return cmp(y) < 0; }
      56                 :            :   bool operator>(const Sequence& y) const { return cmp(y) > 0; }
      57                 :            :   bool operator<=(const Sequence& y) const { return cmp(y) <= 0; }
      58                 :            :   bool operator>=(const Sequence& y) const { return cmp(y) >= 0; }
      59                 :            : 
      60                 :            :   bool strncmp(const Sequence& y, size_t n) const;
      61                 :            :   bool rstrncmp(const Sequence& y, size_t n) const;
      62                 :            : 
      63                 :            :   /** is this the empty sequence? */
      64                 :            :   bool empty() const;
      65                 :            :   /** is less than or equal to sequence y */
      66                 :            :   bool isLeq(const Sequence& y) const;
      67                 :            :   /** Return the length of the sequence */
      68                 :            :   size_t size() const;
      69                 :            : 
      70                 :            :   /** Return true if this sequence is a repetition of the same element */
      71                 :            :   bool isRepeated() const;
      72                 :            : 
      73                 :            :   /**
      74                 :            :    * Return the first position y occurs in this sequence, or std::string::npos
      75                 :            :    * otherwise.
      76                 :            :    */
      77                 :            :   size_t find(const Sequence& y, size_t start = 0) const;
      78                 :            :   /**
      79                 :            :    * Return the first position y occurs in this sequence searching from the end,
      80                 :            :    * or std::string::npos otherwise.
      81                 :            :    */
      82                 :            :   size_t rfind(const Sequence& y, size_t start = 0) const;
      83                 :            :   /** Returns true if y is a prefix of this */
      84                 :            :   bool hasPrefix(const Sequence& y) const;
      85                 :            :   /** Returns true if y is a suffix of this */
      86                 :            :   bool hasSuffix(const Sequence& y) const;
      87                 :            :   /** Replace the character at index i in this sequence with t */
      88                 :            :   Sequence update(size_t i, const Sequence& t) const;
      89                 :            :   /** Replace the first occurrence of s in this sequence with t */
      90                 :            :   Sequence replace(const Sequence& s, const Sequence& t) const;
      91                 :            :   /** Return the subsequence of this sequence starting at index i */
      92                 :            :   Sequence substr(size_t i) const;
      93                 :            :   /**
      94                 :            :    * Return the subsequence of this sequence starting at index i with size at
      95                 :            :    * most j.
      96                 :            :    */
      97                 :            :   Sequence substr(size_t i, size_t j) const;
      98                 :            :   /** Return the prefix of this sequence of size at most i */
      99                 :         67 :   Sequence prefix(size_t i) const { return substr(0, i); }
     100                 :            :   /** Return the suffix of this sequence of size at most i */
     101                 :        113 :   Sequence suffix(size_t i) const { return substr(size() - i, i); }
     102                 :            : 
     103                 :            :   /**
     104                 :            :    * Checks if there is any overlap between this sequence and another sequence.
     105                 :            :    * This corresponds to checking whether one sequence contains the other and
     106                 :            :    * whether a subsequence of one is a prefix of the other and vice-versa.
     107                 :            :    *
     108                 :            :    * @param y The other sequence
     109                 :            :    * @return True if there is an overlap, false otherwise
     110                 :            :    */
     111                 :            :   bool noOverlapWith(const Sequence& y) const;
     112                 :            : 
     113                 :            :   /** sequence overlap
     114                 :            :    *
     115                 :            :    * if overlap returns m>0,
     116                 :            :    * then the maximal suffix of this sequence that is a prefix of y is of length
     117                 :            :    * m.
     118                 :            :    *
     119                 :            :    * For example, if x is "abcdef", then:
     120                 :            :    * x.overlap("defg") = 3
     121                 :            :    * x.overlap("ab") = 0
     122                 :            :    * x.overlap("d") = 0
     123                 :            :    * x.overlap("bcdefdef") = 5
     124                 :            :    */
     125                 :            :   size_t overlap(const Sequence& y) const;
     126                 :            :   /** sequence reverse overlap
     127                 :            :    *
     128                 :            :    * if roverlap returns m>0,
     129                 :            :    * then the maximal prefix of this sequence that is a suffix of y is of length
     130                 :            :    * m.
     131                 :            :    *
     132                 :            :    * For example, if x is "abcdef", then:
     133                 :            :    * x.roverlap("aaabc") = 3
     134                 :            :    * x.roverlap("def") = 0
     135                 :            :    * x.roverlap("d") = 0
     136                 :            :    * x.roverlap("defabcde") = 5
     137                 :            :    *
     138                 :            :    * Notice that x.overlap(y) = y.roverlap(x)
     139                 :            :    */
     140                 :            :   size_t roverlap(const Sequence& y) const;
     141                 :            : 
     142                 :            :   /** get the element type of the sequence */
     143                 :            :   const TypeNode& getType() const;
     144                 :            :   /** get the internal Node representation of this sequence */
     145                 :            :   const std::vector<Node>& getVec() const;
     146                 :            :   /** get the internal node value of the first element in this sequence */
     147                 :            :   const Node& front() const;
     148                 :            :   /** get the internal node value of the last element in this sequence */
     149                 :            :   const Node& back() const;
     150                 :            :   /** @return The element at the i-th position */
     151                 :            :   const Node& nth(size_t i) const;
     152                 :            :   /**
     153                 :            :    * Returns the maximum sequence length representable by this class.
     154                 :            :    * Corresponds to the maximum size of d_seq.
     155                 :            :    */
     156                 :            :   static size_t maxSize();
     157                 :            : 
     158                 :            :  private:
     159                 :            :   /**
     160                 :            :    * Returns a negative number if *this < y, 0 if *this and y are equal and a
     161                 :            :    * positive number if *this > y.
     162                 :            :    */
     163                 :            :   int cmp(const Sequence& y) const;
     164                 :            :   /** The element type of the sequence */
     165                 :            :   std::unique_ptr<TypeNode> d_type;
     166                 :            :   /** The data of the sequence */
     167                 :            :   std::vector<Node> d_seq;
     168                 :            : };
     169                 :            : 
     170                 :            : struct SequenceHashFunction
     171                 :            : {
     172                 :            :   size_t operator()(const Sequence& s) const;
     173                 :            : };
     174                 :            : 
     175                 :            : std::ostream& operator<<(std::ostream& os, const Sequence& s);
     176                 :            : 
     177                 :            : }  // namespace cvc5::internal
     178                 :            : 
     179                 :            : #endif /* CVC5__EXPR__SEQUENCE_H */