#ifndef __STL_SET
#define __STL_SET

#define MAX 500

#include "definitions.h"
#include "utility"
#include "iterator"
#include "iostream"
#include "algorithm"
#include "functional"

namespace std
{
template <
  class Key,
  class Compare = less<Key> /*,class Allocator = allocator<Key> */>
class multiset
{
public:
  Key buf[MAX];
  size_t _size = 0;
  Compare rule;

  // types:

  typedef Key key_type;
  typedef Key value_type;
  //typedef  pair<Key, Compare> element_type;
  typedef Compare key_compare;
  typedef Compare value_compare;

  typedef int size_type;
  typedef int difference_type;

  class iterator
  {
  public:
    int pos;
    key_type *base;

    iterator(const iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    // Constructor that accepts const pointer (for const methods)
    iterator(const key_type *bbase, int ppos)
      : pos(ppos), base(const_cast<key_type *>(bbase))
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
    }

    iterator()
    {
    }

    iterator &operator=(const iterator &i)
    {
      pos = i.pos;
      base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    iterator &operator++()
    {
      ++pos;
      return *this;
    }
    iterator operator++(int b)
    {
      return iterator(base, pos++);
    }

    iterator operator+(int var)
    {
      return iterator(base, pos + var);
    }

    iterator &operator--()
    {
      --pos;
      return *this;
    }
    iterator operator--(int b)
    {
      return iterator(base, pos--);
    }

    iterator operator-(int var)
    {
      return iterator(base, pos - var);
    }

    bool operator==(const iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }

    bool operator!=(const iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(const iterator &it) const
    {
      return (pos < it.pos);
    }
  };

  class const_iterator
  {
  public:
  public:
    int pos;
    key_type *base;

    const_iterator(const const_iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    const_iterator(const iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    const_iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    const_iterator()
    {
    }
    const_iterator &operator=(const const_iterator &i)
    {
      this->pos = i.pos;
      this->base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    const_iterator &operator++()
    {
      ++pos;
      return *this;
    }
    const_iterator operator++(int b)
    {
      return const_iterator(base, pos++);
    }

    const_iterator operator+(int var)
    {
      return const_iterator(base, pos + var);
    }

    const_iterator &operator--()
    {
      --pos;
      return *this;
    }
    const_iterator operator--(int b)
    {
      return const_iterator(base, pos--);
    }

    const_iterator operator-(int var)
    {
      return const_iterator(base, pos - var);
    }

    bool operator==(const const_iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }

    bool operator!=(const const_iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(const const_iterator &it) const
    {
      return (pos < it.pos);
    }
  };

  class reverse_iterator
  {
  public:
    int pos;
    key_type *base;

    reverse_iterator(const reverse_iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    reverse_iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    reverse_iterator()
    {
    }
    reverse_iterator &operator=(const reverse_iterator &i)
    {
      pos = i.pos;
      base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    reverse_iterator &operator++()
    {
      --pos;
      return *this;
    }
    reverse_iterator operator++(int b)
    {
      return reverse_iterator(base, pos--);
    }

    reverse_iterator operator+(int var)
    {
      return reverse_iterator(base, pos - var);
    }

    reverse_iterator &operator--()
    {
      ++pos;
      return *this;
    }
    reverse_iterator operator--(int b)
    {
      return reverse_iterator(base, pos++);
    }

    reverse_iterator operator-(int var)
    {
      return reverse_iterator(base, pos + var);
    }

    bool operator==(reverse_iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }
    bool operator!=(reverse_iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(reverse_iterator &it) const
    {
      return (it.pos < pos);
    }
  };

  class const_reverse_iterator
  {
  public:
    int pos;
    key_type *base;

    const_reverse_iterator(const const_reverse_iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    const_reverse_iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    const_reverse_iterator()
    {
    }
    const_reverse_iterator &operator=(const const_reverse_iterator &i)
    {
      this->pos = i.pos;
      this->base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    const_reverse_iterator &operator++()
    {
      --pos;
      return *this;
    }
    const_reverse_iterator operator++(int b)
    {
      return const_reverse_iterator(base, pos--);
    }

    const_reverse_iterator operator+(int var)
    {
      return const_reverse_iterator(base, pos - var);
    }

    const_reverse_iterator &operator--()
    {
      ++pos;
      return *this;
    }
    const_reverse_iterator operator--(int b)
    {
      return const_reverse_iterator(base, pos++);
    }

    const_reverse_iterator operator-(int var)
    {
      return const_reverse_iterator(base, pos + var);
    }

    bool operator==(const_reverse_iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }
    bool operator!=(const_reverse_iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(const_reverse_iterator &it) const
    {
      return (it.pos < pos);
    }
  };

  // construct/copy/destroy:
  explicit multiset(const Compare &comp) : _size(0), rule(comp)
  {
  }

  explicit multiset(Key v1[], Key *v2)
  {
    __ESBMC_assert(
      v2 > v1,
      "Invalid pointer range: the second argument must be greater than the "
      "first one");
    _size = 0;
    int i = 0;
    while (v1 != v2)
    {
      buf[i] = *v1;
      i++;
      v1++;
    }
    _size = i;
    std::sort(buf, buf + _size /*,rule*/);
  }

  template <class Iterator>
  explicit multiset(Iterator first, Iterator last)
  {
    __ESBMC_assert(
      first < last,
      "Invalid iterator range: the second argument must be greater than the "
      "first one");
    _size = 0;
    int i = 0;
    while (first != last)
    {
      buf[i] = *first;
      i++;
      first++;
    }
    _size = i;
    std::sort(buf, buf + _size, rule);
  }

  multiset() : _size(0)
  {
    _size = 0;
  }

  ~multiset()
  {
    this->clear();
  }

  multiset(const multiset &x)
  {
    _size = 0;
    for (int i = 0; i < x._size; i++)
    {
      buf[i] = x.buf[i];
    }
    _size = x.size();
    buf[_size] = Key();
  }

  multiset &operator=(const multiset &x)
  {
    _size = 0;
    for (int i = 0; i < x._size; i++)
    {
      buf[i] = x.buf[i];
    }
    _size = x.size();
    buf[_size] = Key();
    return *this;
  }

  // iterators:
  iterator begin()
  {
    return iterator(buf, 0);
  }

  iterator end()
  {
    iterator buffer;
    buffer.base = buf;
    buffer.pos = _size;
    return buffer;
  }

  const_iterator begin() const
  {
    return const_iterator(buf, 0);
  }
  const_iterator end() const
  {
    const_iterator buffer;
    buffer.base = buf;
    buffer.pos = _size;
    return buffer;
  }

  reverse_iterator rbegin()
  {
    return reverse_iterator(buf, _size - 1);
  }
  reverse_iterator rend()
  {
    return reverse_iterator(buf, _size);
  }

  const_reverse_iterator rbegin() const
  {
    return const_reverse_iterator(buf, _size - 1);
  }
  const_reverse_iterator rend() const
  {
    return const_reverse_iterator(buf, 0);
  }

  // capacity:
  bool empty() const
  {
    return (_size == 0);
  }
  size_type size() const
  {
    return _size;
  }
  size_type max_size() const
  {
    return 9999999999;
  }

  template <class Iterator>
  void insert(Iterator first, Iterator last)
  {
    __ESBMC_assert(
      last > first,
      "Invalid iterator range: the second argument must be greater than the "
      "first one");
    while (first != last)
      insert(*first++);
  }

  // modifiers:
  // multiset insert should maintain sorted order and allow duplicates.
  // Returns iterator (not pair<iterator,bool>): the bool would be meaningless
  // for multiset since duplicates are always inserted (C++ standard).
  iterator insert(const value_type &x)
  {
    // Find the correct position to insert while maintaining sorted order
    int insert_pos = 0;
    while (insert_pos < _size && buf[insert_pos] < x)
    {
      insert_pos++;
    }

    // Shift elements to the right to make space
    for (int i = _size; i > insert_pos; i--)
    {
      buf[i] = buf[i - 1];
    }

    // Insert the new element
    buf[insert_pos] = x;
    _size++;

    return iterator(buf, insert_pos);
  }

  iterator insert(iterator position, const value_type &x)
  {
    // For multiset, we ignore position hint and maintain sorted order
    return insert(x);
  }

  void erase(iterator position)
  {
    __ESBMC_assert(
      (position.pos >= 0) && (position.pos < size()) &&
        (position.base == buf),
      "Invalid argument: iterator out of range");
    int j;
    for (int i = position.pos + 1; i < _size; i++)
    {
      j = i - 1;
      buf[j] = buf[i];
    }
    _size--;
    j = _size + 1;
    buf[j] = Key();
  }

  size_type erase(const key_type &x)
  {
    int k;
    for (k = 0; k != _size; k++)
      if (buf[k] == x)
        break;

    if (k == _size)
    {
      return 0; // Element not found, nothing erased
    }

    // Element found, erase it
    for (int i = k + 1; i < _size; i++)
    {
      buf[i - 1] = buf[i];
    }
    _size--;
    buf[_size] = Key();
    return 1; // One element erased
  }

  void erase(iterator first, iterator last)
  {
    __ESBMC_assert(
      first.pos <= last.pos && first.base == last.base,
      "Invalid iterator range");

    // Calculate how many elements to erase
    int num_to_erase = last.pos - first.pos;

    // Erase elements by repeatedly erasing at the first position
    // Always erase at the same position since elements shift left
    for (int i = 0; i < num_to_erase; i++)
      erase(first);
  }

  void swap(multiset &x)
  {
    multiset aux;
    aux = *this;
    *this = x;
    x = aux;
  }
  void clear()
  {
    _size = 0;
  }

  // observers:

  key_compare key_comp() const
  {
    return Compare();
  }

  value_compare value_comp() const
  {
    return Compare();
  }
  // set operations:

  iterator find(const key_type &x)
  {
    int i;
    for (i = 0; i != _size; i++)
      if (buf[i] == x)
        break;
    return iterator(buf, i); // Non-const version
  }

  const_iterator find(const key_type &x) const
  {
    int i;
    for (i = 0; i != _size; i++)
      if (buf[i] == x)
        break;
    return const_iterator(buf, i);
  }

  size_type count(const key_type &x) const
  {
    size_type counter = 0;
    int i = 0;
    while (i != _size)
    {
      if (buf[i] == x)
        counter++;
      i++;
    }
    return counter;
  }

  // lower_bound returns iterator to first element >= x
  iterator lower_bound(const key_type &x)
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] >= x)
      {
        return iterator(buf, i);
      }
    }
    return end();
  }

  const_iterator lower_bound(const key_type &x) const
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] >= x)
      {
        return const_iterator(buf, i);
      }
    }
    return end();
  }

  // upper_bound returns iterator to first element > x
  iterator upper_bound(const key_type &x)
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] > x)
      {
        return iterator(buf, i);
      }
    }
    return end();
  }

  const_iterator upper_bound(const key_type &x) const
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] > x)
      {
        return const_iterator(buf, i);
      }
    }
    return end();
  }

  // equal_range returns pair<lower_bound, upper_bound>
  pair<iterator, iterator> equal_range(const key_type &x)
  {
    return make_pair(lower_bound(x), upper_bound(x));
  }

  pair<const_iterator, const_iterator> equal_range(const key_type &x) const
  {
    return make_pair(lower_bound(x), upper_bound(x));
  }
};

template <class Key, class Compare = less<Key>>
class set
{
public:
  Key buf[MAX];
  size_t _size = 0;
  Compare rule;

  // types:

  typedef Key key_type;
  typedef Key value_type;
  //typedef  pair<Key, Compare> element_type;
  typedef Compare key_compare;
  typedef Compare value_compare;

  typedef int size_type;
  typedef int difference_type;

  class iterator
  {
  public:
    int pos;
    key_type *base;

    iterator(const iterator &i) : pos(i.pos), base(i.base)
    {
    }

    iterator(key_type *bbase, int ppos) : pos(ppos), base(bbase)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
    }

    // Constructor that accepts const pointer (for const methods)
    iterator(const key_type *bbase, int ppos)
      : pos(ppos), base(const_cast<key_type *>(bbase))
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
    }

    iterator() : pos(0), base(NULL)
    {
    }

    iterator &operator=(const iterator &i)
    {
      pos = i.pos;
      base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    iterator &operator++()
    {
      ++pos;
      return *this;
    }
    iterator operator++(int b)
    {
      return iterator(base, pos++);
    }

    iterator operator+(int var)
    {
      return iterator(base, pos + var);
    }

    iterator &operator--()
    {
      --pos;
      return *this;
    }
    iterator operator--(int b)
    {
      return iterator(base, pos--);
    }

    iterator operator-(int var)
    {
      return iterator(base, pos - var);
    }

    bool operator==(const iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }

    bool operator!=(const iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(const iterator &it) const
    {
      return (pos < it.pos);
    }
  };

  class const_iterator
  {
  public:
  public:
    int pos;
    key_type *base;

    const_iterator(const const_iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    const_iterator(const iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    const_iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    const_iterator()
    {
    }
    const_iterator &operator=(const const_iterator &i)
    {
      this->pos = i.pos;
      this->base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    const_iterator &operator++()
    {
      ++pos;
      return *this;
    }
    const_iterator operator++(int b)
    {
      return const_iterator(base, pos++);
    }

    const_iterator operator+(int var)
    {
      return const_iterator(base, pos + var);
    }

    const_iterator &operator--()
    {
      --pos;
      return *this;
    }
    const_iterator operator--(int b)
    {
      return const_iterator(base, pos--);
    }

    const_iterator operator-(int var)
    {
      return const_iterator(base, pos - var);
    }

    bool operator==(const const_iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }
    bool operator!=(const const_iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(const const_iterator &it) const
    {
      return (pos < it.pos);
    }
  };

  class reverse_iterator
  {
  public:
    int pos;
    key_type *base;

    reverse_iterator(const reverse_iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    reverse_iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    reverse_iterator()
    {
    }
    reverse_iterator &operator=(const reverse_iterator &i)
    {
      pos = i.pos;
      base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    reverse_iterator &operator++()
    {
      --pos;
      return *this;
    }
    reverse_iterator operator++(int b)
    {
      return reverse_iterator(base, pos--);
    }

    reverse_iterator operator+(int var)
    {
      return reverse_iterator(base, pos - var);
    }

    reverse_iterator &operator--()
    {
      ++pos;
      return *this;
    }
    reverse_iterator operator--(int b)
    {
      return reverse_iterator(base, pos++);
    }

    reverse_iterator operator-(int var)
    {
      return reverse_iterator(base, pos + var);
    }

    bool operator==(reverse_iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }
    bool operator!=(reverse_iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(reverse_iterator &it) const
    {
      return (it.pos < pos);
    }
  };

  class const_reverse_iterator
  {
  public:
    int pos;
    key_type *base;

    const_reverse_iterator(const const_reverse_iterator &i)
    {
      pos = i.pos;
      base = i.base;
    }

    const_reverse_iterator(key_type *bbase, int ppos)
    {
      __ESBMC_assert(bbase != NULL, "Invalid null pointer");
      pos = ppos;
      base = bbase;
    }

    const_reverse_iterator()
    {
    }
    const_reverse_iterator &operator=(const const_reverse_iterator &i)
    {
      this->pos = i.pos;
      this->base = i.base;
      return *this;
    }

    value_type *operator->()
    {
      return &base[pos];
    }

    value_type &operator*()
    {
      return base[pos];
    }

    const_reverse_iterator &operator++()
    {
      --pos;
      return *this;
    }
    const_reverse_iterator operator++(int b)
    {
      return const_reverse_iterator(base, pos--);
    }

    const_reverse_iterator operator+(int var)
    {
      return const_reverse_iterator(base, pos - var);
    }

    const_reverse_iterator &operator--()
    {
      ++pos;
      return *this;
    }
    const_reverse_iterator operator--(int b)
    {
      return const_reverse_iterator(base, pos++);
    }

    const_reverse_iterator operator-(int var)
    {
      return const_reverse_iterator(base, pos + var);
    }

    bool operator==(const_reverse_iterator &it) const
    {
      return ((base == it.base) && (pos == it.pos));
    }
    bool operator!=(const_reverse_iterator &it) const
    {
      return !((base == it.base) && (pos == it.pos));
    }

    bool operator<(const_reverse_iterator &it) const
    {
      return (it.pos < pos);
    }
  };

  // construct/copy/destroy:
  explicit set(const Compare &comp) : _size(0), rule(comp)
  {
  }

  explicit set(Key v1[], Key *v2)
  {
    __ESBMC_assert(
      v2 > v1,
      "Invalid pointer range: the second argument must be greater than the "
      "first one");
    _size = 0;
    int i = 0;
    while (v1 != v2)
      buf[i++] = *v1++;
    _size = i;
    std::sort(buf, buf + _size /*,rule*/);
  }

  template <class Iterator>
  explicit set(Iterator first, Iterator last)
  {
    __ESBMC_assert(
      first < last,
      "Invalid iterator range: the second argument must be greater than the "
      "first one");
    _size = 0;
    int i = 0;
    while (first != last)
    {
      buf[i] = *first;
      i++;
      first++;
    }
    _size = i;
    std::sort(buf, buf + _size /*,rule*/);
  }

  set() : _size(0), rule(Compare())
  {
  }

  ~set()
  {
    this->clear();
  }

  set(const set &x)
  {
    _size = 0;
    for (int i = 0; i < x._size; i++)
    {
      buf[i] = x.buf[i];
    }
    _size = x.size();
    buf[_size] = Key();
  }

  set &operator=(const set &x)
  {
    _size = 0;
    for (int i = 0; i < x._size; i++)
    {
      buf[i] = x.buf[i];
    }
    _size = x.size();
    buf[_size] = Key();
    return *this;
  }

  // iterators:
  iterator begin()
  {
    return iterator(buf, 0);
  }

  iterator end()
  {
    iterator buffer;
    buffer.base = buf;
    buffer.pos = _size;
    return buffer;
  }

  const_iterator begin() const
  {
    return const_iterator(buf, 0);
  }
  const_iterator end() const
  {
    const_iterator buffer;
    buffer.base = buf;
    buffer.pos = _size;
    return buffer;
  }

  reverse_iterator rbegin()
  {
    return reverse_iterator(buf, _size - 1);
  }
  reverse_iterator rend()
  {
    return reverse_iterator(buf, _size);
  }

  const_reverse_iterator rbegin() const
  {
    return const_reverse_iterator(buf, _size - 1);
  }
  const_reverse_iterator rend() const
  {
    return const_reverse_iterator(buf, 0);
  }

  // capacity:
  bool empty() const
  {
    return (_size == 0);
  }
  size_type size() const
  {
    return _size;
  }
  size_type max_size() const
  {
    return 9999999999;
  }

  template <class Iterator>
  void insert(Iterator first, Iterator last)
  {
    __ESBMC_assert(
      last > first,
      "Invalid iterator range: the second argument must be greater than the "
      "first one");
    while (first != last)
      insert(*first++);
  }

  // modifiers:
  // set insert should maintain sorted order and reject duplicates
  pair<iterator, bool> insert(const value_type &x)
  {
    // Check if element already exists (for set, duplicates not allowed)
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] == x)
      {
        return make_pair(iterator(buf, i), false);
      }
    }

    // Find the correct position to insert while maintaining sorted order
    int insert_pos = 0;
    while (insert_pos < _size && buf[insert_pos] < x)
    {
      insert_pos++;
    }

    // Shift elements to the right to make space
    for (int i = _size; i > insert_pos; i--)
    {
      buf[i] = buf[i - 1];
    }

    // Insert the new element
    buf[insert_pos] = x;
    _size++;

    return make_pair(iterator(buf, insert_pos), true);
  }

  iterator insert(iterator position, const value_type &x)
  {
    auto result = insert(x);
    return result.first;
  }

  void erase(iterator position)
  {
    __ESBMC_assert(
      (position.pos >= 0) && (position.pos < size()) &&
        (position.base == buf),
      "Invalid argument: iterator out of range");
    int j;
    for (int i = position.pos + 1; i < _size; i++)
    {
      j = i - 1;
      buf[j] = buf[i];
    }
    _size--;
    j = _size + 1;
    buf[j] = Key();
  }

  size_type erase(const key_type &x)
  {
    int k;
    for (k = 0; k != _size; k++)
      if (buf[k] == x)
        break;

    if (k == _size)
    {
      return 0; // Element not found, nothing erased
    }

    // Element found, erase it
    for (int i = k + 1; i < _size; i++)
    {
      buf[i - 1] = buf[i];
    }
    _size--;
    buf[_size] = Key();
    return 1; // One element erased
  }

  void erase(iterator first, iterator last)
  {
    __ESBMC_assert(
      first.pos <= last.pos && first.base == last.base,
      "Invalid iterator range");

    // Calculate how many elements to erase
    int num_to_erase = last.pos - first.pos;

    // Erase elements by repeatedly erasing at the first position
    // Always erase at the same position since elements shift left
    for (int i = 0; i < num_to_erase; i++)
      erase(first);
  }
  void swap(set &x)
  {
    set aux(*this); // Use copy constructor to create aux as a copy of *this
    *this = x;
    x = aux;
  }
  void clear()
  {
    _size = 0;
  }

  // observers:

  key_compare key_comp() const
  {
    return Compare();
  }

  value_compare value_comp() const
  {
    return Compare();
  }
  // set operations:

  iterator find(const key_type &x)
  {
    int i;
    for (i = 0; i != _size; i++)
      if (buf[i] == x)
        break;
    return iterator(buf, i); // Non-const version
  }

  const_iterator find(const key_type &x) const
  {
    int i;
    for (i = 0; i != _size; i++)
      if (buf[i] == x)
        break;
    return const_iterator(buf, i);
  }

  size_type count(const key_type &x) const
  {
    size_type counter = 0;
    int i = 0;
    while (i != _size)
    {
      if (buf[i] == x)
        counter++;
      i++;
    }
    return counter;
  }

  // lower_bound returns iterator to first element >= x
  iterator lower_bound(const key_type &x)
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] >= x)
      {
        return iterator(buf, i);
      }
    }
    return end();
  }

  const_iterator lower_bound(const key_type &x) const
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] >= x)
      {
        return const_iterator(buf, i);
      }
    }
    return end();
  }

  // upper_bound returns iterator to first element > x
  iterator upper_bound(const key_type &x)
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] > x)
      {
        return iterator(buf, i);
      }
    }
    return end();
  }

  const_iterator upper_bound(const key_type &x) const
  {
    for (int i = 0; i < _size; i++)
    {
      if (buf[i] > x)
      {
        return const_iterator(buf, i);
      }
    }
    return end();
  }

  // equal_range returns pair<lower_bound, upper_bound> (correct order!)
  pair<iterator, iterator> equal_range(const key_type &x)
  {
    return make_pair(lower_bound(x), upper_bound(x));
  }

  pair<const_iterator, const_iterator> equal_range(const key_type &x) const
  {
    return make_pair(lower_bound(x), upper_bound(x));
  }
};

} // namespace std

#endif