Lab 04

Stack has top(), Queue has front(), everything else is same, except what pop() returns

Problem: Unsorted Stack, sort using other empty stack that can use up to O(1) memory (just 1 or a few elts, cant be full copy)

SORTING UNSORTED STACK
// s is the original stack, c is a spare stack
while (!s.empty()) {
    TYPE temp = s.top();
    s.pop();
    while (!c.empty() && c.top() > temp) {
        s.push(c.top());
        c.pop();  // c is now empty
    }
    c.push(temp);  // add an elt onto c
}

Functions are evaluated in LIFO order for the call stack

Recursion - solve problem by solving smaller problem

• Trees easier to traverse using recursion (left and right subtrees, base case is root)

def drawSquare(args) :
    drawLine (args)  #creates local stacks

def drawLine(args) :
    food = 5
    bar = 3.14

One pointer that points to the stack, just goes up and down

All fcns can be implemented recursively and iteratively

A Recursive call (Non-tail) pushes another stack frame which must store n
Recursive implementations that use O(n) memory suck
If the recursive works with a value, it's better to accumulate the value through calls and keep O(1)
Usually, if you can do tail-recursion, you can do it iteratively

Priority Queue - abstract container that supports 2 operations

1) Insert a new item

2) Remove the item with the largest key (most extreme element)

• Push, pop, top, some more

• Binary Heap

• Pairing Heap

• Doesn't have to be fast, just needs to support these operations

STL Priority Queue - implemented with a binary heap

• can override the comparison function, have to specify the container also if you choose to override comparator
• push O(log), pop O(log), top, empty, size

STL PRIORITY QUEUE
template<
    class T,
    class Container = vector<T>,
    class Compare = std::less<typename Container::value_type>    // default is std::less<T>
  >
// in one line:
template<class T, class Container = vector<T>, class Compare = std::less<typename Container::value_type>>
class priority_queue;

Functors - objects that override the function call operator, pretends to be a function

• Classes
• Also called function objects
• Contain a bool in the public section of the class that takes in parameters to compare
• Comparators are given values, NOT iterators, use const auto& elt just in case

Eecs281PQ is an abstract base class (looks like an interface, all abstract functions)

• Can't actually create objects of this type, so only create pointers of the object type (*eecs_ptr)

C++ Tip -Lambda Expressions

• Small functor that uses local variables, you are too lazy to define a class
• Lambda expression is a functor object
• Lambdas should use auto as the argument type?

LAMBDA EXPRESSION IN PLACE OF COMPARATOR
std::sort(xs.begin(), xs.end(), [] (int x, int y) { return x > y; });   
                                // lambda expression in the place where comparator goes

Iterators cannot be nullptr, can * deference and ++ increment

std::copy_if uses InputIterators and an OutputIterator

Lab 4 Coding Problem - merging intervals into a union

• This solution uses lambdas

template<typename In, typename Out>
Out merge_intervals(In first, In last, Out out) {
    if (first == last) return out;
    std::sort(first, last, [](const auto& l, const auto& r) { 
        return l.first < r.first; 
    });

    *out = *first;
    for ( ; first != last; ++first) {
        if (first->first <= out->second) // need to merge
            out->second = std::max(first->second, out->second);
        else 
            *(++out) = *first;  // new "current"
    }
    return ++out;  // one past the end
}