carbon-lang/executable_semantics/interpreter/stack.h

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#ifndef EXECUTABLE_SEMANTICS_INTERPRETER_STACK_H_
#define EXECUTABLE_SEMANTICS_INTERPRETER_STACK_H_

#include <cstddef>
#include <iterator>

#include "common/check.h"
#include "executable_semantics/interpreter/list_node.h"

namespace Carbon {

// A persistent stack data structure.
//
// - Note: this data structure leaks memory.
template <class T>
struct Stack {
  // A forward iterator over elements of a `Stack`.
  struct Iterator {
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T*;
    using reference = const T&;
    using iterator_category = std::forward_iterator_tag;

    Iterator(ListNode<T>* x) : p(x) {}
    Iterator(const Iterator& mit) : p(mit.p) {}
    Iterator& operator++() {
      p = p->next;
      return *this;
    }
    Iterator operator++(int) {
      Iterator tmp(*this);
      operator++();
      return tmp;
    }
    bool operator==(const Iterator& rhs) const { return p == rhs.p; }
    bool operator!=(const Iterator& rhs) const { return p != rhs.p; }
    const T& operator*() { return p->curr; }
    const T* operator->() { return &p->curr; }

   private:
    ListNode<T>* p;
  };

  // The position of the first/`Top()` element, or `end()` if
  // `this->IsEmpty()`.
  auto begin() const -> Iterator { return Iterator(head); }

  // The position one past that of the last element.
  auto end() const -> Iterator { return Iterator(nullptr); }

  // Creates an empty instance.
  Stack() { head = nullptr; }

  // Creates an instance containing just `x`.
  explicit Stack(T x) : Stack() { Push(x); }

  // Pushes `x` onto the top of the stack.
  void Push(T x) { head = new ListNode<T>(x, head); }

  // Returns a copy of `*this`, with `x` pushed onto the top.
  auto Pushing(T x) const -> Stack {
    auto r = *this;
    r.Push(x);
    return r;
  }

  // Removes and returns the top element of the stack.
  //
  // - Requires: !this->IsEmpty()
  auto Pop() -> T {
    CHECK(!IsEmpty()) << "Can't pop from empty stack.";
    auto r = head->curr;
    head = head->next;
    return r;
  }

  // Removes the top `n` elements of the stack.
  //
  // - Requires: n >= 0 && n <= Count()
  void Pop(int n) {
    CHECK(n >= 0) << "Negative pop count disallowed.";
    while (n--) {
      CHECK(head != nullptr) << "Can only pop as many elements as stack has.";
      head = head->next;
    }
  }

  // Returns a copy of `*this`, sans the top element.
  //
  // - Requires: !this->IsEmpty()
  auto Popped() const -> Stack {
    auto r = *this;
    r.Pop();
    return r;
  }

  // Returns the top element of the stack.
  //
  // - Requires: !this->IsEmpty()
  auto Top() const -> T {
    CHECK(!IsEmpty()) << "Empty stack has no Top().";
    return head->curr;
  }

  // Returns `true` iff `Count() > 0`.
  auto IsEmpty() const -> bool { return head == nullptr; }

  // Returns `true` iff `Count() > n`.
  //
  // - Complexity: O(`n`)
  auto CountExceeds(int n) const -> bool {
    if (n < 0)
      return true;

    for (auto p = head; p != nullptr; p = p->next) {
      if (n-- == 0)
        return true;
    }

    return false;
  }

  // Returns the number of elements in `*this`.
  auto Count() const -> int { return std::distance(begin(), end()); }

 private:
  // A linked list of cells containing the elements of self.
  ListNode<T>* head;
};

}  // namespace Carbon

#endif  // EXECUTABLE_SEMANTICS_INTERPRETER_CONS_LIST_H_