Chapter 26 — Templates and Classes: `Stack<T>`

// Chapter 26 — Templates and Classes · Project: Stack<T>   (STARTER)
// ─────────────────────────────────────────────────────────────────────────────
// Fill in the four TASK blocks below. They map 1:1 to the tasks in the README
// and to the CHECKs in tests/tests.cpp. Every body currently compiles but
// returns PLACEHOLDER values so `make test` is RED. Your job: turn it GREEN.
//
//     make build          compile-check this header (should already work)
//     make test           grade your code (RED until the TASKs are filled in)
//     make solution       see the reference if you're truly stuck
//
// ── WHY HEADER-ONLY? ─────────────────────────────────────────────────────────
// This is the CENTRAL lesson of Chapter 26 (notes 26.1).  When a translation
// unit writes  Stack<int>  the compiler must see the FULL class template
// definition RIGHT THERE so it can stamp out a concrete Stack<int>.  If the
// member bodies lived in a .cpp file the linker would say "undefined symbol
// Stack<int>::push" — it never got the chance to instantiate them.
//
// Practical rule (notes 26.1):
//   "For class templates, put the class definition and member definitions in the
//    header, or put member definitions in an included .inl file at the bottom."
//
// This file is that header. Everything — data layout, in-class members, and
// the one out-of-class member (Task 3) — lives here.
// ─────────────────────────────────────────────────────────────────────────────

#ifndef STACK_H
#define STACK_H

#include <array>       // std::array — Ch 17 fixed-size array
#include <cassert>     // assert — Ch 9 precondition enforcement
#include <cstddef>     // std::size_t
#include <string_view> // std::string_view — for TypeLabel (Ch 5)

// ─────────────────────────────────────────────────────────────────────────────
// TASK 1: Write the Stack class template
// ─────────────────────────────────────────────────────────────────────────────
// Design
// ──────
// Stack is a **class template** (notes 26.1) and uses a **non-type template
// parameter** for the capacity (notes 26.2). Its backing storage is a fixed-
// size std::array<T, Capacity> (Ch 17) — zero dynamic allocation, just like
// llvm::SmallVector's inline buffer.
//
// Signature to implement (replace the placeholder class below):
//
//   template <typename T, int Capacity = 8>
//   class Stack { ... };
//
// Required PUBLIC member functions (all defined IN-CLASS except pop — see
// Task 3 for the out-of-class syntax practice):
//
//   bool push(const T& value)
//       Add `value` on top. Return false if already full, true on success.
//
//   T top() const
//       Return the top element WITHOUT removing it.
//       Precondition: stack is not empty — enforce with assert (Ch 9).
//
//   int size() const
//       Return the number of elements currently on the stack.
//
//   bool isEmpty() const
//       Return true when size() == 0.
//
//   bool isFull() const
//       Return true when size() == Capacity.
//
//   void pop()                    <- DECLARE here; DEFINE in Task 3 (below class)
//       Remove the top element.
//       Precondition: stack is not empty — enforce with assert.
//
// Private data:
//   std::array<T, Capacity> m_data {};   // the fixed-size backing store
//   int                     m_size {};   // how many elements are live
//
// Key term: the TEMPLATE PARAMETER LIST  template <typename T, int Capacity = 8>
//   T        — a TYPE parameter (placeholder for int, std::string, …)
//   Capacity — a NON-TYPE parameter (a compile-time int value, default 8)
//
// Constraint: all member function bodies except pop go IN-CLASS (inside the
// class body { }). Only pop is declared in-class and DEFINED below (Task 3).
//
// Hint: inside the class body you may refer to the class simply as Stack;
// outside (Task 3) you must write Stack<T, Capacity>.
//
// ─── TASK 1 ──────────────────────────────────────────────────────────────────
//
//   >>> YOUR CODE HERE <<<
//
// ─── placeholder — correct template signature, wrong bodies ──────────────────
// The class is already a template (so Stack<int> and Stack<std::string> parse)
// but every body returns a WRONG placeholder — that is why make test is RED.
// Replace this entire template with a correct implementation.
template <typename T, int Capacity = 8>
class Stack
{
public:
    bool push(const T& /*value*/) { return false; }  // placeholder: never pushes
    T    top()    const           { return T{};   }  // placeholder: default-constructed
    int  size()   const           { return 0;     }  // placeholder: always 0
    bool isEmpty() const          { return true;  }  // placeholder: always empty
    bool isFull()  const          { return true;  }  // placeholder: always full
    void pop()                    {}                 // placeholder: does nothing
};
// ─────────────────────────────────────────────────────────────────────────────


// ─────────────────────────────────────────────────────────────────────────────
// TASK 2: Add the TypeLabel primary template
// ─────────────────────────────────────────────────────────────────────────────
// A TRAIT-style template tells us the human-readable name of a type at compile
// time — exactly the kind of helper found inside LLVM's type system utilities.
//
// Write this primary template:
//
//   template <typename T>
//   struct TypeLabel
//   {
//       static constexpr std::string_view name { "unknown" };
//   };
//
// "Primary template" (notes 26.4): the catch-all definition the compiler uses
// when no specialization matches. Any type with no explicit specialization will
// have TypeLabel<T>::name == "unknown".
//
// ─── TASK 2 ──────────────────────────────────────────────────────────────────
//
//   >>> YOUR CODE HERE <<<
//
// ─── placeholder — wrong name for every type ─────────────────────────────────
template <typename T>
struct TypeLabel
{
    // placeholder: all types get "unknown" (correct for unspecialized types, but
    // the specialized ones like int, double, string_view also need a name — see Task 4).
    static constexpr std::string_view name { "unknown" };
};
// ─────────────────────────────────────────────────────────────────────────────


// ─────────────────────────────────────────────────────────────────────────────
// TASK 3: Define Stack<T, Capacity>::pop OUT-OF-CLASS
// ─────────────────────────────────────────────────────────────────────────────
// Pop is DECLARED inside the Stack class (Task 1) but DEFINED here, below the
// class body.  This practices the out-of-class member syntax (notes 26.1):
//
//   template <typename T, int Capacity>
//   void Stack<T, Capacity>::pop()
//   {
//       assert(!isEmpty());     // precondition (Ch 9)
//       --m_size;               // "removing" the top is just shrinking the live count
//   }
//
// Two required pieces (notes 26.1 / 26.2):
//   template <typename T, int Capacity>   <- repeat the FULL template parameter list
//   Stack<T, Capacity>::pop               <- qualify with the instantiation pattern
//
// Do NOT write just  Stack::pop  — outside the class body the compiler needs
// the full  Stack<T, Capacity>  qualification to find the right template.
//
// NOTE: Once you implement the real Stack in Task 1 (with m_size / m_data),
// replace the placeholder pop body below with the real one too.
// Currently it is left as an empty body so the file compiles with the stub class.
//
// ─── TASK 3 ──────────────────────────────────────────────────────────────────
//
//   >>> YOUR CODE HERE <<<
//
// ─── placeholder out-of-class definition (empty body — wrong behavior) ────────
// (Once you add m_size in Task 1, replace this with the real implementation.)
// ─────────────────────────────────────────────────────────────────────────────


// ─────────────────────────────────────────────────────────────────────────────
// TASK 4: Full specializations of TypeLabel
// ─────────────────────────────────────────────────────────────────────────────
// Add FULL SPECIALIZATIONS (notes 26.4) so common types report their proper
// names instead of "unknown".  The syntax:
//
//   template <>                          // no remaining template parameters
//   struct TypeLabel<int>                // specialization for T = int exactly
//   {
//       static constexpr std::string_view name { "int" };
//   };
//
// Required specializations (one for each):
//   TypeLabel<int>              -> name == "int"
//   TypeLabel<double>           -> name == "double"
//   TypeLabel<std::string_view> -> name == "string_view"
//
// Key terms (notes 26.4):
//   - "Full specialization" — ALL template parameters are fixed (contrast with
//     partial specialization, which the notes cover in 26.5).
//   - The PRIMARY template (Task 2) must be defined BEFORE any specialization.
//
// Constraint: do NOT change the primary template. Add three separate
//   template <> struct TypeLabel<XYZ> { ... };  blocks below.
//
// ─── TASK 4 ──────────────────────────────────────────────────────────────────
//
//   >>> YOUR CODE HERE <<<
//
// ─────────────────────────────────────────────────────────────────────────────

#endif // STACK_H

// Chapter 26 — Templates and Classes · Project: Stack<T>   (REFERENCE SOLUTION)
// ─────────────────────────────────────────────────────────────────────────────
// Complete, correct, warning-clean reference for chapter-26/starter/stack.h.
// Peek only after taking a real swing at the starter — the learning is in
// wrestling with the template syntax yourself, then comparing here.
//
// ── WHY HEADER-ONLY? (notes 26.1) ────────────────────────────────────────────
// When a translation unit writes  Stack<int>  the compiler must see the FULL
// template definition at that point so it can stamp out a concrete Stack<int>.
// If the member bodies lived in a separate .cpp, that .cpp would compile but
// never produce a Stack<int> instantiation — the linker would then fail with
// "undefined symbol Stack<int>::push" because no translation unit ever asked
// for it while the definition was visible.
//
// Both in-class and the out-of-class pop definition therefore live here in the
// header.  That makes this file a worked example of the constraint the chapter
// exists to teach.
// ─────────────────────────────────────────────────────────────────────────────

#ifndef STACK_H
#define STACK_H

#include <array>        // std::array — Ch 17 fixed-size array
#include <cassert>      // assert     — Ch 9 precondition enforcement
#include <cstddef>      // std::size_t
#include <string_view>  // std::string_view — for TypeLabel labels (Ch 5)

// ─── TASK 1 + TASK 3: Stack class template (declaration + out-of-class pop) ──
//
// KEY TERM: CLASS TEMPLATE (notes 26.1)
//   template <typename T, int Capacity = 8>
//   class Stack { … };
//
//   T        is a TYPE parameter — the kind of value the stack holds.
//   Capacity is a NON-TYPE parameter (notes 26.2) — a compile-time integer
//            that fixes the array size.  Default is 8 (an arbitrary small
//            bound — the same idea as the inline-capacity tuning value in
//            llvm::SmallVector<T, N>, explained two lines down).
//
// Why a non-type param here?  Because std::array<T, Capacity> needs Capacity
// as a compile-time constant.  A runtime constructor argument would require
// dynamic allocation (Ch 19), defeating the "zero-allocation bounded stack"
// goal. This is exactly the trade-off llvm::SmallVector makes: the inline-
// buffer size is a non-type param so it can be an actual array on the stack.

template <typename T, int Capacity = 8>
class Stack
{
    // ── private data ────────────────────────────────────────────────────────
    // m_data: the fixed backing store.  We never resize it; m_size tracks how
    // many elements are "live" (i.e. pushed but not yet popped).
    std::array<T, Capacity> m_data {};  // value-initialized (zeros / default ctors)
    int                     m_size {};  // 0 … Capacity

public:
    // ── push ────────────────────────────────────────────────────────────────
    // KEY DESIGN CHOICE: push returns bool instead of throwing (Ch 27 style)
    // or asserting.  The caller decides what "full" means for its use case.
    // Return false when the stack is already full so the caller can react
    // (e.g., a fuzzer queue might flush and retry rather than crash).
    bool push(const T& value)
    {
        if (isFull())
            return false;           // precondition not met — caller must handle

        m_data[static_cast<std::size_t>(m_size)] = value;
        ++m_size;
        return true;
    }

    // ── top ─────────────────────────────────────────────────────────────────
    // Returns the top element WITHOUT removing it.  Calling top() on an empty
    // stack is undefined behaviour in std::stack, so we enforce the precondition
    // with assert (Ch 9) — fast in debug, zero-cost in release.
    T top() const
    {
        assert(!isEmpty() && "Stack::top called on empty stack");
        return m_data[static_cast<std::size_t>(m_size - 1)];
    }

    // ── size / isEmpty / isFull ──────────────────────────────────────────────
    // These are small enough that keeping them in-class is normal and clear.
    int  size()    const { return m_size;               }
    bool isEmpty() const { return m_size == 0;           }
    bool isFull()  const { return m_size == Capacity;    }

    // ── pop (declaration only — DEFINED BELOW the class) ────────────────────
    // TASK 3 teaches the out-of-class member definition syntax.  The body is
    // deliberately defined below so you can see the template<typename T, int
    // Capacity> Stack<T, Capacity>::pop() pattern in isolation, exactly as
    // notes 26.1 and 26.2 describe.
    void pop();
};

// ─── TASK 3: out-of-class member definition ──────────────────────────────────
//
// KEY SYNTAX (notes 26.1 / 26.2):
//
//   template <typename T, int Capacity>      ← REPEAT the full parameter list
//   void Stack<T, Capacity>::pop()           ← qualify with BOTH params
//   { … }
//
// Inside the class body you can just write Stack; outside it the compiler needs
// the full Stack<T, Capacity> to disambiguate (there are infinitely many
// instantiations; the "which Stack" must be spelled out).
//
// Compare to a non-template:
//   int Counter::value() const { … }         ← just "Counter", no template head
//
// Adding "template <typename T, int Capacity>" and changing "Stack" to
// "Stack<T, Capacity>" is the only extra work class templates add to out-of-
// class definitions.  Once you've written it once the pattern sticks.
//
template <typename T, int Capacity>
void Stack<T, Capacity>::pop()
{
    assert(!isEmpty() && "Stack::pop called on empty stack");
    --m_size;   // the element at m_data[m_size] is now "above" the live region;
                // it will be overwritten the next time push() lands there.
}


// ─── TASK 2: TypeLabel primary template ──────────────────────────────────────
//
// KEY TERM: TRAIT (notes 26.4 reading between lines)
// A "trait" is a class template whose sole purpose is to carry compile-time
// information ABOUT a type.  TypeLabel is a minimal trait: given any type T,
// TypeLabel<T>::name is a human-readable string_view known at compile time.
//
// The canonical standard-library example of this exact pattern is
// std::numeric_limits<T> — a class template fully specialized per arithmetic
// type to expose compile-time facts about it (e.g. std::numeric_limits<int>::max()).
// std::iterator_traits<T> is another.  LLVM uses the same shape in real trait
// templates such as llvm::format_provider<T> (specialized per type to teach the
// formatting library how to print that type).  The common thread: a class
// template, specialized per type, that describes a type's properties at compile
// time without altering the type itself.
//
// The PRIMARY template is the catch-all: it fires when NO specialization matches.
// This one says "I don't know what this type is → call it 'unknown'."
//
template <typename T>
struct TypeLabel
{
    static constexpr std::string_view name { "unknown" };
};


// ─── TASK 4: full specializations of TypeLabel ───────────────────────────────
//
// KEY TERM: FULL CLASS SPECIALIZATION (notes 26.4)
//   template <>
//   struct TypeLabel<int> { … };
//
// "template <>" means "all template parameters are now fixed" — no placeholders
// remain.  The angle brackets after the class name carry the specific type(s).
//
// The PRIMARY template MUST be visible before any specialization, just as it is
// here (Task 2 above, Task 4 below).
//
// Why not just an if/switch at runtime?  Because these names are constants used
// in assertions and error messages that the compiler can fold into the binary —
// zero runtime overhead, and they communicate intent clearly to readers.
//
// TypeLabel<int>  ────────────────────────────────────────────────────────────
template <>
struct TypeLabel<int>
{
    static constexpr std::string_view name { "int" };
};

// TypeLabel<double>  ─────────────────────────────────────────────────────────
template <>
struct TypeLabel<double>
{
    static constexpr std::string_view name { "double" };
};

// TypeLabel<std::string_view>  ───────────────────────────────────────────────
template <>
struct TypeLabel<std::string_view>
{
    static constexpr std::string_view name { "string_view" };
};

#endif // STACK_H

// Chapter 26 — Templates and Classes · Project: Stack<T>   (GRADER)
// ─────────────────────────────────────────────────────────────────────────────
// No-framework unit-test harness (drills/CLAUDE.md Style B2).
// The Makefile compiles this file with -Istarter or -Isolution so the correct
// stack.h is found via the plain  #include "stack.h"  below.
//
//   make test           -> grades YOUR starter/stack.h   (RED until done)
//   make test-solution  -> grades solution/stack.h       (must be GREEN)
//
// The tests instantiate BOTH Stack<int> AND Stack<std::string> (the core
// lesson: one template, many element types) plus edge cases for push-when-full,
// top/pop-preconditions, and TypeLabel specializations.
// ─────────────────────────────────────────────────────────────────────────────

#include <iostream>
#include <string>
#include <string_view>
#include "stack.h"     // resolved via -Istarter or -Isolution (Style B2)

static int fails = 0;

// CHECK — print what failed and where; increment the failure counter.
#define CHECK(cond) \
    do { if (!(cond)) { \
        std::cerr << "FAIL: " #cond "  @line " << __LINE__ << "\n"; \
        ++fails; \
    } } while (0)

int main()
{
    // ── Task 1 + 3: Stack<int> — basic operations ─────────────────────────────
    {
        Stack<int> s;

        // fresh stack is empty and not full
        CHECK(s.isEmpty());
        CHECK(!s.isFull());
        CHECK(s.size() == 0);

        // push three values, check size and top after each
        CHECK(s.push(10));
        CHECK(s.size() == 1);
        CHECK(!s.isEmpty());
        CHECK(s.top() == 10);

        CHECK(s.push(20));
        CHECK(s.size() == 2);
        CHECK(s.top() == 20);   // top is LAST pushed

        CHECK(s.push(30));
        CHECK(s.size() == 3);
        CHECK(s.top() == 30);

        // pop (out-of-class definition — Task 3)
        s.pop();
        CHECK(s.size() == 2);
        CHECK(s.top() == 20);   // popping 30 reveals 20

        s.pop();
        CHECK(s.size() == 1);
        CHECK(s.top() == 10);

        s.pop();
        CHECK(s.isEmpty());
        CHECK(s.size() == 0);
    }

    // ── Task 1: push-when-full returns false ──────────────────────────────────
    {
        Stack<int, 3> small;    // non-type param: capacity 3 (notes 26.2)
        CHECK(small.push(1));
        CHECK(small.push(2));
        CHECK(small.push(3));
        CHECK(small.isFull());
        CHECK(small.size() == 3);

        bool ok = small.push(99);   // must return false — stack is full
        CHECK(!ok);
        CHECK(small.size() == 3);   // size unchanged
        CHECK(small.top() == 3);    // top unchanged
    }

    // ── Task 1: Stack<std::string> — the second instantiation ─────────────────
    // The whole point: ONE class template, TWO element types. If your template
    // accidentally hardcodes int assumptions, these checks will catch it.
    {
        Stack<std::string> words;
        CHECK(words.isEmpty());

        CHECK(words.push("hello"));
        CHECK(words.push("world"));
        CHECK(words.size() == 2);
        CHECK(words.top() == "world");

        words.pop();                     // out-of-class pop with std::string
        CHECK(words.size() == 1);
        CHECK(words.top() == "hello");

        words.pop();
        CHECK(words.isEmpty());
    }

    // ── Task 1: Stack<std::string> fill to capacity ───────────────────────────
    {
        Stack<std::string, 2> tiny;
        CHECK(tiny.push("alpha"));
        CHECK(tiny.push("beta"));
        CHECK(tiny.isFull());
        CHECK(!tiny.push("gamma"));    // full: must return false
        CHECK(tiny.size() == 2);
        CHECK(tiny.top() == "beta");
    }

    // ── Task 1 edge: single-element stack ────────────────────────────────────
    {
        Stack<int, 1> one;
        CHECK(one.isEmpty());
        CHECK(!one.isFull());
        CHECK(one.push(42));
        CHECK(one.isFull());
        CHECK(!one.isEmpty());
        CHECK(one.top() == 42);
        CHECK(!one.push(99));      // full after one push
        one.pop();
        CHECK(one.isEmpty());
    }

    // ── Task 1 edge: push-pop-push reuse ─────────────────────────────────────
    // After popping, the capacity slot should be reusable.
    {
        Stack<int, 2> s;
        CHECK(s.push(1));
        CHECK(s.push(2));
        CHECK(s.isFull());
        s.pop();
        CHECK(!s.isFull());
        CHECK(s.push(3));         // slot freed by pop is now reusable
        CHECK(s.isFull());
        CHECK(s.top() == 3);
        CHECK(s.size() == 2);
    }

    // ── Task 2 + 4: TypeLabel primary template and specializations ────────────
    // TypeLabel<T>::name is a compile-time string_view (constexpr).
    // Unknown type: primary template must say "unknown".
    {
        // Use an unspecialized type as a stand-in for "unknown"
        struct MyLocalType {};
        CHECK(TypeLabel<MyLocalType>::name == "unknown");

        // Full specializations (Task 4) must override the primary
        CHECK(TypeLabel<int>::name          == "int");
        CHECK(TypeLabel<double>::name       == "double");
        CHECK(TypeLabel<std::string_view>::name == "string_view");
    }

    // ── Task 2 + 4: TypeLabel with Stack instantiation types ─────────────────
    // A realistic use case: the label follows the element type through the
    // template.  This pattern appears in LLVM diagnostic helpers that print the
    // type name of a container's element.
    {
        CHECK(TypeLabel<int>::name    == "int");     // still holds after Stack use
        CHECK(TypeLabel<double>::name == "double");  // specialization is consistent
    }

    // ── Task 3: out-of-class pop syntax — exhaustive round-trip ─────────────
    // Push the default capacity (8), verify order, pop all, verify empty.
    {
        Stack<int> full;    // default Capacity = 8
        for (int i = 1; i <= 8; ++i)
            CHECK(full.push(i));

        CHECK(full.isFull());
        CHECK(!full.push(99));    // one more push must fail

        // pop in LIFO order: 8, 7, … 1
        for (int expected = 8; expected >= 1; --expected)
        {
            CHECK(full.top() == expected);
            full.pop();
        }
        CHECK(full.isEmpty());
    }

    // ── Final verdict ─────────────────────────────────────────────────────────
    if (!fails)
        std::cout << "PASS \xE2\x9C\x85 all stack checks passed.\n";
    else
        std::cerr << "\nFAIL \xE2\x9D\x8C " << fails
                  << " check(s) failed — fix the TASK blocks in starter/stack.h.\n";

    return fails ? 1 : 0;
}

# Chapter 26 — Templates and Classes · Stack<T> · header-only unit-test grader (Style B2).
# Targets follow the drills/CLAUDE.md Makefile contract.  TABS, not spaces.
#
# Style B2 explanation (CLAUDE.md):
#   The learner edits starter/stack.h (the FULL class template, bodies inline).
#   tests/tests.cpp does  #include "stack.h"  and the Makefile injects the
#   right directory via -I so the correct stack.h is found.
#
#   test:          ; $(CXX) $(CXXFLAGS) -Istarter  tests/tests.cpp -o tests/run && ./tests/run
#   test-solution: ; $(CXX) $(CXXFLAGS) -Isolution tests/tests.cpp -o tests/run && ./tests/run
#
# Why no starter/main.cpp?  The test harness supplies its own main().  A stack
# template doesn't need a "playable driver" the way the engine did — the grader
# IS the demo.  (See chapter-08 for the Style B variant with a separate demo.)

CXX      := clang++
CXXFLAGS := -std=c++17 -Wall -Wextra

.PHONY: all build run test solution test-solution clean

all: build

# build — compile-check the learner's starter/stack.h (warning-clean).
# Because everything is header-only, we compile tests.cpp against the starter
# for the build check so any syntax error in the header is caught immediately.
build:
	@$(CXX) $(CXXFLAGS) -Istarter tests/tests.cpp -o tests/build_check 2>&1 || true
	@$(CXX) $(CXXFLAGS) -Istarter tests/tests.cpp -o tests/build_check
	@echo "OK \xE2\x9C\x85  starter/stack.h compiles.  Now run: make test"

# run — just re-runs the build check (there is no interactive driver here).
run: build
	@echo "(no interactive driver for this exercise — use 'make test' to grade)"

# test — grade the LEARNER's code: compile + run against starter/stack.h.
# RED until the TASK blocks are filled in; GREEN once they are.
test:
	$(CXX) $(CXXFLAGS) -Istarter tests/tests.cpp -o tests/run
	@./tests/run || echo "FAIL \xE2\x9D\x8C  fill in the TASK blocks in starter/stack.h until every check passes."

# solution — show the reference solution output (acts as a demo).
solution:
	$(CXX) $(CXXFLAGS) -Isolution tests/tests.cpp -o tests/run_sol
	./tests/run_sol

# test-solution — proof the lab is solvable: solution MUST pass every check.
test-solution:
	$(CXX) $(CXXFLAGS) -Isolution tests/tests.cpp -o tests/run
	@./tests/run

clean:
	rm -f tests/run tests/run_sol tests/build_check
	rm -rf tests/run.dSYM tests/run_sol.dSYM tests/build_check.dSYM