Branch data     Line data    Source code

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