corecel/cont/IdStack.hh

0001 //------------------------------- -*- C++ -*- -------------------------------//
0002 // Copyright Celeritas contributors: see top-level COPYRIGHT file for details
0003 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0004 //---------------------------------------------------------------------------//
0005 //! \file corecel/cont/IdStack.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include "corecel/Macros.hh"
0010 #include "corecel/OpaqueId.hh"
0011 #include "corecel/Types.hh"
0012 #include "corecel/cont/Span.hh"
0013
0014 namespace celeritas
0015 {
0016 //---------------------------------------------------------------------------//
0017 /*!
0018  * Stack "view" that keeps the top element in a local scalar.
0019  * \tparam T value type
0020  * \tparam E extent for spill (dynamic or fixed)
0021  *
0022  * This particular stack requires \c OpaqueId as its element type, because the
0023  * default value must evaluate to "false" \em and is never a valid stack value.
0024  * Without this restriction it would need an extra boolean in addition to the
0025  * top item.
0026  *
0027  * The most recently pushed value is always stored in \c top_. Older values are
0028  * spilled into the underlying storage. This increases the effective stack
0029  * capacity by one: for storage size \c N, the stack capacity is \c N + 1.
0030  * The internal \c size_ tracks only the number of spilled elements in
0031  * underlying storage. The logical size reported by \c size() is therefore
0032  * <code>size_ + !this->empty()</code>.
0033  *
0034  * \par Example:
0035  * \code
0036     Array<int, 3> storage;
0037     IdStack stack(Span{storage});
0038
0039     EXPECT_TRUE(stack.empty());
0040     EXPECT_EQ(0, stack.size());
0041     EXPECT_EQ(4, stack.capacity());
0042
0043     // Push  and pop
0044     stack.push(42);
0045     EXPECT_FALSE(stack.empty());
0046     EXPECT_EQ(1, stack.size());
0047     EXPECT_EQ(42, stack.top());
0048     stack.pop();
0049  * \endcode
0050  *
0051  */
0052 template<class T,
0053          std::size_t Extent = dynamic_extent,
0054          class S = ::celeritas::size_type>
0055 class IdStack
0056 {
0057     static_assert(is_opaque_id_v<T>,
0058                   "IdStack should be used only for trivial data");
0059
0060   public:
0061     //!@{
0062     using value_type = T;
0063     using size_type = S;
0064     //!@}
0065
0066     //! Capacity (may be dynamic)
0067     static constexpr std::size_t spill_extent = Extent;
0068
0069   public:
0070     // Construct with underlying storage
0071     inline CELER_FUNCTION explicit IdStack(Span<T, Extent> storage);
0072
0073     // Insert a new element at the top of the stack
0074     inline CELER_FUNCTION void push(T element);
0075
0076     // Remove the top element of the stack
0077     inline CELER_FUNCTION void pop();
0078
0079     // Get the top element of the stack
0080     inline CELER_FUNCTION T top() const;
0081
0082     //! Whether there are any elements in the container
0083     CELER_FIF bool empty() const { return !top_; }
0084
0085     //! Get the number of elements
0086     CELER_FIF size_type size() const { return size_ + !this->empty(); }
0087
0088     //! Get the number of elements that can fit in the allocated storage
0089     CELER_CEF size_type capacity() const { return spill_.size() + 1; }
0090
0091   private:
0092     Span<T, Extent> spill_;
0093     T top_{};
0094     size_type size_{0};
0095 };
0096
0097 //---------------------------------------------------------------------------//
0098 // INLINE DEFINITIONS
0099 //---------------------------------------------------------------------------//
0100 /*!
0101  * Construct with underlying spill storage.
0102  */
0103 template<class T, std::size_t Extent, class S>
0104 CELER_FUNCTION IdStack<T, Extent, S>::IdStack(Span<T, Extent> storage)
0105     : spill_(storage)
0106 {
0107     CELER_ENSURE(this->empty());
0108 }
0109
0110 //---------------------------------------------------------------------------//
0111 /*!
0112  * Push an element onto the top of the stack.
0113  */
0114 template<class T, std::size_t Extent, class S>
0115 inline CELER_FUNCTION void IdStack<T, Extent, S>::push(T element)
0116 {
0117     CELER_EXPECT(this->size() < this->capacity());
0118     if (!this->empty())
0119     {
0120         spill_[size_++] = top_;
0121     }
0122     top_ = element;
0123 }
0124
0125 //---------------------------------------------------------------------------//
0126 /*!
0127  * Remove the top element.
0128  */
0129 template<class T, std::size_t Extent, class S>
0130 inline CELER_FUNCTION void IdStack<T, Extent, S>::pop()
0131 {
0132     CELER_EXPECT(!this->empty());
0133     if (size_ > 0)
0134     {
0135         top_ = spill_[--size_];
0136     }
0137     else
0138     {
0139         top_ = {};
0140     }
0141 }
0142
0143 //---------------------------------------------------------------------------//
0144 /*!
0145  * Get the top element.
0146  */
0147 template<class T, std::size_t Extent, class S>
0148 CELER_FIF T IdStack<T, Extent, S>::top() const
0149 {
0150     CELER_EXPECT(!this->empty());
0151     return top_;
0152 }
0153
0154 //---------------------------------------------------------------------------//
0155 }  // namespace celeritas