text:
// Copyright (C) 2003  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_BINARY_SEARCH_TREE_KERNEl_2_
#define DLIB_BINARY_SEARCH_TREE_KERNEl_2_

#include "binary_search_tree_kernel_abstract.h"
#include "../algs.h"
#include "../interfaces/map_pair.h"
#include "../interfaces/enumerable.h"
#include "../interfaces/remover.h"
#include "../serialize.h"
#include <functional>

namespace dlib
{

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare = std::less<domain>
        >
    class binary_search_tree_kernel_2 : public enumerable<map_pair<domain,range> >,
                                        public asc_pair_remover<domain,range,compare>
    {

        /*!
            INITIAL VALUE
                NIL == pointer to a node that represents a leaf
                tree_size == 0
                tree_root == NIL
                at_start == true
                current_element == 0

            CONVENTION
                current_element_valid() == (current_element != 0)
                if (current_element_valid()) then
                    element() == current_element->d and current_element->r
                at_start_ == at_start()

                tree_size   == size()

                NIL == pointer to a node that represents a leaf

                if (tree_size != 0)
                    tree_root == pointer to the root node of the binary search tree
                else
                    tree_root == NIL

                tree_root->color == black
                Every leaf is black and all leafs are the NIL node.
                The number of black nodes in any path from the root to a leaf is the
                same.

                for all nodes:
                {
                    - left points to the left subtree or NIL if there is no left subtree
                    - right points to the right subtree or NIL if there is no right
                      subtree
                    - parent points to the parent node or NIL if the node is the root
                    - ordering of nodes is determined by comparing each node's d member
                    - all elements in a left subtree are <= the node
                    - all elements in a right subtree are >= the node
                    - color == red or black
                    - if (color == red)
                        - the node's children are black
                }

        !*/

        class node
        {
        public:
            node* left;
            node* right;
            node* parent;
            domain d;
            range r;
            char color;
        };

        class mpair : public map_pair<domain,range>
        {
        public:
            const domain* d;
            range* r;

            const domain& key(
            ) const { return *d; }

            const range& value(
            ) const { return *r; }

            range& value(
            ) { return *r; }
        };

        const static char red = 0;
        const static char black = 1;

        public:

            typedef domain domain_type;
            typedef range range_type;
            typedef compare compare_type;
            typedef mem_manager mem_manager_type;

            binary_search_tree_kernel_2(
            ) :
                NIL(pool.allocate()),
                tree_size(0),
                tree_root(NIL),
                current_element(0),
                at_start_(true)
            {
                NIL->color = black;
                NIL->left = 0;
                NIL->right = 0;
                NIL->parent = 0;
            }

            virtual ~binary_search_tree_kernel_2(
            );

            inline void clear(
            );

            inline short height (
            ) const;

            inline unsigned long count (
                const domain& d
            ) const;

            inline void add (
                domain& d,
                range& r
            );

            void remove (
                const domain& d,
                domain& d_copy,
                range& r
            );

            void destroy (
                const domain& d
            );

            void remove_any (
                domain& d,
                range& r
            );

            inline const range* operator[] (
                const domain& item
            ) const;

            inline range* operator[] (
                const domain& item
            );

            inline void swap (
                binary_search_tree_kernel_2& item
            );

            // functions from the enumerable interface
            inline unsigned long size (
            ) const;

            bool at_start (
            ) const;

            inline void reset (
            ) const;

            bool current_element_valid (
            ) const;

            const map_pair<domain,range>& element (
            ) const;

            map_pair<domain,range>& element (
            );

            bool move_next (
            ) const;

            void remove_last_in_order (
                domain& d,
                range& r
            );

            void remove_current_element (
                domain& d,
                range& r
            );

            void position_enumerator (
                const domain& d
            ) const;

        private:

            inline void rotate_left (
                node* t
            );
            /*!
                requires
                    - t != NIL
                    - t->right != NIL
                ensures
                    - performs a left rotation around t and its right child
            !*/

            inline void rotate_right (
                node* t
            );
            /*!
                requires
                    - t != NIL
                    - t->left != NIL
                ensures
                    - performs a right rotation around t and its left child
            !*/

            inline void double_rotate_right (
                node* t
            );
            /*!
                requires
                    - t != NIL
                    - t->left != NIL
                    - t->left->right != NIL
                    - double_rotate_right() is only called in fix_after_add()
                ensures
                    - performs a left rotation around t->left
                    - then performs a right rotation around t
            !*/

            inline void double_rotate_left (
                node* t
            );
            /*!
                requires
                    - t != NIL
                    - t->right != NIL
                    - t->right->left != NIL
                    - double_rotate_left() is only called in fix_after_add()
                ensures
                    - performs a right rotation around t->right
                    - then performs a left rotation around t
            !*/

            void remove_biggest_element_in_tree (
                node* t,
                domain& d,
                range& r
            );
            /*!
                requires
                    - t != NIL  (i.e. there must be something in the tree to remove)
                ensures
                    - the biggest node in t has been removed
                    - the biggest node element in t has been put into #d and #r
                    - #t is still a binary search tree
            !*/

            bool remove_least_element_in_tree (
                node* t,
                domain& d,
                range& r
            );
            /*!
                requires
                    - t != NIL  (i.e. there must be something in the tree to remove)
                ensures
                    - the least node in t has been removed
                    - the least node element in t has been put into #d and #r
                    - #t is still a binary search tree
                    - if (the node that was removed was the one pointed to by current_element) then
                        - returns true
                    - else
                        - returns false
            !*/

            void add_to_tree (
                node* t,
                domain& d,
                range& r
            );
            /*!
                requires
                    - t != NIL
                ensures
                    - d and r are now in #t
                    - there is a mapping from d to r in #t
                    - #d and #r have initial values for their types
                    - #t is still a binary search tree
            !*/

            void remove_from_tree (
                node* t,
                const domain& d,
                domain& d_copy,
                range& r
            );
            /*!
                requires
                    - return_reference(t,d) != 0
                ensures
                    - #d_copy is equivalent to d
                    - the first element in t equivalent to d that is encountered when searching down the tree
                      from t has been removed and swapped into #d_copy.  Also, the associated range element
                      has been removed and swapped into #r.
                    - if (the node that got removed wasn't current_element) then
                        - adjusts the current_element pointer if the data in the node that it points to gets moved.
                    - else
                        - the value of current_element is now invalid
                    - #t is still a binary search tree
            !*/

            void remove_from_tree (
                node* t,
                const domain& d
            );
            /*!
                requires
                    - return_reference(t,d) != 0
                ensures
                    - an element in t equivalent to d has been removed
                    - #t is still a binary search tree
            !*/

            const range* return_reference (
                const node* t,
                const domain& d
            ) const;
            /*!
                ensures
                    - if (there is a domain element equivalent to d in t) then
                        - returns a pointer to the element in the range equivalent to d
                    - else
                        - returns 0
            !*/

            range* return_reference (
                node* t,
                const domain& d
            );
            /*!
                ensures
                    - if (there is a domain element equivalent to d in t) then
                        - returns a pointer to the element in the range equivalent to d
                    - else
                        - returns 0
            !*/

            void fix_after_add (
                node* t
            );
            /*!
                requires
                    - t == pointer to the node just added
                    - t->color == red
                    - t->parent != NIL (t must not be the root)
                    - fix_after_add() is only called after a new node has been added
                      to t
                ensures
                    - fixes any deviations from the CONVENTION caused by adding a node
            !*/

            void fix_after_remove (
                node* t
            );
            /*!
                requires
                    - t == pointer to the only child of the node that was spliced out
                    - fix_after_remove() is only called after a node has been removed
                      from t
                    - the color of the spliced out node was black
                ensures
                    - fixes any deviations from the CONVENTION causes by removing a node
            !*/

            short tree_height (
                node* t
            ) const;
            /*!
                ensures
                    - returns the number of nodes in the longest path from the root of the
                      tree to a leaf
            !*/

            void delete_tree (
                node* t
            );
            /*!
                requires
                    - t == root of binary search tree
                    - t != NIL
                ensures
                    - deletes all nodes in t except for NIL
            !*/

            unsigned long get_count (
                const domain& item,
                node* tree_root
            ) const;
            /*!
                requires
                    - tree_root == the root of a binary search tree or NIL
                ensures
                    - if (tree_root == NIL) then
                        - returns 0
                    - else
                        - returns the number of elements in tree_root that are
                          equivalent to item
            !*/

            // data members
            typename mem_manager::template rebind<node>::other pool;
            node* NIL;
            unsigned long tree_size;
            node* tree_root;
            mutable node* current_element;
            mutable bool at_start_;
            mutable mpair p;
            compare comp;

            // restricted functions
            binary_search_tree_kernel_2(binary_search_tree_kernel_2&);
            binary_search_tree_kernel_2& operator=(binary_search_tree_kernel_2&);

    };

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    inline void swap (
        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& a,
        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& b
    ) { a.swap(b); }

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void deserialize (
        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& item,
        std::istream& in
    )
    {
        try
        {
            item.clear();
            unsigned long size;
            deserialize(size,in);
            domain d;
            range r;
            for (unsigned long i = 0; i < size; ++i)
            {
                deserialize(d,in);
                deserialize(r,in);
                item.add(d,r);
            }
        }
        catch (serialization_error e)
        {
            item.clear();
            throw serialization_error(e.info + "\n   while deserializing object of type binary_search_tree_kernel_2");
        }
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    ~binary_search_tree_kernel_2 (
    )
    {
        if (tree_root != NIL)
            delete_tree(tree_root);
        pool.deallocate(NIL);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    clear (
    )
    {
        if (tree_size > 0)
        {
            delete_tree(tree_root);
            tree_root = NIL;
            tree_size = 0;
        }
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    unsigned long binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    size (
    ) const
    {
        return tree_size;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    short binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    height (
    ) const
    {
        return tree_height(tree_root);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    unsigned long binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    count (
        const domain& item
    ) const
    {
        return get_count(item,tree_root);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    add (
        domain& d,
        range& r
    )
    {
        if (tree_size == 0)
        {
            tree_root = pool.allocate();
            tree_root->color = black;
            tree_root->left = NIL;
            tree_root->right = NIL;
            tree_root->parent = NIL;
            exchange(tree_root->d,d);
            exchange(tree_root->r,r);
        }
        else
        {
            add_to_tree(tree_root,d,r);
        }
        ++tree_size;
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove (
        const domain& d,
        domain& d_copy,
        range& r
    )
    {
        remove_from_tree(tree_root,d,d_copy,r);
        --tree_size;
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    destroy (
        const domain& item
    )
    {
        remove_from_tree(tree_root,item);
        --tree_size;
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_any (
        domain& d,
        range& r
    )
    {
        remove_least_element_in_tree(tree_root,d,r);
        --tree_size;
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    operator[] (
        const domain& d
    )
    {
        return return_reference(tree_root,d);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    const range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    operator[] (
        const domain& d
    ) const
    {
        return return_reference(tree_root,d);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    swap (
        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& item
    )
    {
        pool.swap(item.pool);

        exchange(p,item.p);
        exchange(comp,item.comp);

        node* tree_root_temp            = item.tree_root;
        unsigned long tree_size_temp    = item.tree_size;
        node* const NIL_temp            = item.NIL;
        node* current_element_temp      = item.current_element;
        bool at_start_temp              = item.at_start_;

        item.tree_root                  = tree_root;
        item.tree_size                  = tree_size;
        item.NIL                        = NIL;
        item.current_element            = current_element;
        item.at_start_                  = at_start_;

        tree_root                       = tree_root_temp;
        tree_size                       = tree_size_temp;
        NIL                             = NIL_temp;
        current_element                 = current_element_temp;
        at_start_                       = at_start_temp;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_last_in_order (
        domain& d,
        range& r
    )
    {
        remove_biggest_element_in_tree(tree_root,d,r);
        --tree_size;
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_current_element (
        domain& d,
        range& r
    )
    {
        node* t = current_element;
        move_next();
        remove_from_tree(t,t->d,d,r);
        --tree_size;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    position_enumerator (
        const domain& d
    ) const
    {
        // clear the enumerator state and make sure the stack is empty
        reset();
        at_start_ = false;
        node* t = tree_root;
        node* parent = NIL;
        bool went_left = false;
        while (t != NIL)
        {
            if ( comp(d , t->d ))
            {
                // if item is on the left then look in left
                parent = t;
                t = t->left;
                went_left = true;
            }
            else if (comp(t->d , d))
            {
                // if item is on the right then look in right
                parent = t;
                t = t->right;
                went_left = false;
            }
            else
            {
                current_element = t;
                return;
            }
        }

        // if we didn't find any matches but there might be something after the
        // d in this tree.
        if (parent != NIL)
        {
            current_element = parent;
            // if we went left from this node then this node is the next
            // biggest.
            if (went_left)
            {
                return;
            }
            else
            {
                move_next();
            }
        }
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // enumerable function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    at_start (
    ) const
    {
        return at_start_;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    reset (
    ) const
    {
        at_start_ = true;
        current_element = 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    current_element_valid (
    ) const
    {
        return (current_element != 0);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    const map_pair<domain,range>& binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    element (
    ) const
    {
        p.d = &(current_element->d);
        p.r = &(current_element->r);
        return p;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    map_pair<domain,range>& binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    element (
    )
    {
        p.d = &(current_element->d);
        p.r = &(current_element->r);
        return p;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    move_next (
    ) const
    {
        // if we haven't started iterating yet
        if (at_start_)
        {
            at_start_ = false;
            if (tree_size == 0)
            {
                return false;
            }
            else
            {
                // find the first element in the tree
                current_element = tree_root;
                node* temp = current_element->left;
                while (temp != NIL)
                {
                    current_element = temp;
                    temp = current_element->left;
                }
                return true;
            }
        }
        else
        {
            if (current_element == 0)
            {
                return false;
            }
            else
            {
                bool went_up;  // true if we went up the tree from a child node to parent
                bool from_left = false; // true if we went up and were coming from a left child node
                // find the next element in the tree
                if (current_element->right != NIL)
                {
                    // go right and down
                    current_element = current_element->right;
                    went_up = false;
                }
                else
                {
                    went_up = true;
                    node* parent = current_element->parent;
                    if (parent == NIL)
                    {
                        // in this case we have iterated over all the element of the tree
                        current_element = 0;
                        return false;
                    }

                    from_left = (parent->left == current_element);
                    // go up to parent
                    current_element = parent;
                }

                while (true)
                {
                    if (went_up)
                    {
                        if (from_left)
                        {
                            // in this case we have found the next node
                            break;
                        }
                        else
                        {
                            // we should go up
                            node* parent = current_element->parent;
                            from_left = (parent->left == current_element);
                            current_element = parent;
                            if (current_element == NIL)
                            {
                                // in this case we have iterated over all the elements
                                // in the tree
                                current_element = 0;
                                return false;
                            }
                        }
                    }
                    else
                    {
                        // we just went down to a child node
                        if (current_element->left != NIL)
                        {
                            // go left
                            went_up = false;
                            current_element = current_element->left;
                        }
                        else
                        {
                            // if there is no left child then we have found the next node
                            break;
                        }
                    }
                }

                return true;
            }
        }
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // private member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    delete_tree (
        node* t
    )
    {
        if (t->left != NIL)
            delete_tree(t->left);
        if (t->right != NIL)
            delete_tree(t->right);
        pool.deallocate(t);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    rotate_left (
        node* t
    )
    {

        // perform the rotation
        node* temp = t->right;
        t->right = temp->left;
        if (temp->left != NIL)
            temp->left->parent = t;
        temp->left = t;
        temp->parent = t->parent;

        if (t == tree_root)
            tree_root = temp;
        else
        {
            // if t was on the left
            if (t->parent->left == t)
                t->parent->left = temp;
            else
                t->parent->right = temp;
        }

        t->parent = temp;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    rotate_right (
        node* t
    )
    {
        // perform the rotation
        node* temp = t->left;
        t->left = temp->right;
        if (temp->right != NIL)
            temp->right->parent = t;
        temp->right = t;
        temp->parent = t->parent;

        if (t == tree_root)
            tree_root = temp;
        else
        {
            // if t is a left child
            if (t->parent->left == t)
                t->parent->left = temp;
            else
                t->parent->right = temp;
        }

        t->parent = temp;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    double_rotate_right (
        node* t
    )
    {

        // preform the rotation
        node& temp = *(t->left->right);
        t->left = temp.right;
        temp.right->parent = t;
        temp.left->parent = temp.parent;
        temp.parent->right = temp.left;
        temp.parent->parent = &temp;
        temp.right = t;
        temp.left = temp.parent;
        temp.parent = t->parent;

        if (tree_root == t)
            tree_root = &temp;
        else
        {
            // t is a left child
            if (t->parent->left == t)
                t->parent->left = &temp;
            else
                t->parent->right = &temp;
        }
        t->parent = &temp;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    double_rotate_left (
        node* t
    )
    {

        // preform the rotation
        node& temp = *(t->right->left);
        t->right = temp.left;
        temp.left->parent = t;
        temp.right->parent = temp.parent;
        temp.parent->left = temp.right;
        temp.parent->parent = &temp;
        temp.left = t;
        temp.right = temp.parent;
        temp.parent = t->parent;

        if (tree_root == t)
            tree_root = &temp;
        else
        {
            // t is a left child
            if (t->parent->left == t)
                t->parent->left = &temp;
            else
                t->parent->right = &temp;
        }
        t->parent = &temp;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_biggest_element_in_tree (
        node* t,
        domain& d,
        range& r
    )
    {

        node* next = t->right;
        node* child;  // the child node of the one we will slice out

        if (next == NIL)
        {
            // need to determine if t is a right or left child
            if (t->parent->right == t)
                child = t->parent->right = t->left;
            else
                child = t->parent->left = t->left;

            // update tree_root if necessary
            if (t == tree_root)
                tree_root = child;
        }
        else
        {
            // find the least node
            do
            {
                t = next;
                next = next->right;
            } while (next != NIL);
            // t is a right child
            child = t->parent->right = t->left;

        }

        // swap the item from this node into d and r
        exchange(d,t->d);
        exchange(r,t->r);

        // plug hole right by removing this node
        child->parent = t->parent;

        // keep the red-black properties true
        if (t->color == black)
            fix_after_remove(child);

        // free the memory for this removed node
        pool.deallocate(t);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_least_element_in_tree (
        node* t,
        domain& d,
        range& r
    )
    {

        node* next = t->left;
        node* child;  // the child node of the one we will slice out

        if (next == NIL)
        {
            // need to determine if t is a left or right child
            if (t->parent->left == t)
                child = t->parent->left = t->right;
            else
                child = t->parent->right = t->right;

            // update tree_root if necessary
            if (t == tree_root)
                tree_root = child;
        }
        else
        {
            // find the least node
            do
            {
                t = next;
                next = next->left;
            } while (next != NIL);
            // t is a left child
            child = t->parent->left = t->right;

        }

        // swap the item from this node into d and r
        exchange(d,t->d);
        exchange(r,t->r);

        // plug hole left by removing this node
        child->parent = t->parent;

        // keep the red-black properties true
        if (t->color == black)
            fix_after_remove(child);

        bool rvalue = (t == current_element);
        // free the memory for this removed node
        pool.deallocate(t);
        return rvalue;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    add_to_tree (
        node* t,
        domain& d,
        range& r
    )
    {
        // parent of the current node
        node* parent;

        // find a place to add node
        while (true)
        {
            parent = t;
            // if item should be put on the left then go left
            if (comp(d , t->d))
            {
                t = t->left;
                if (t == NIL)
                {
                    t = parent->left = pool.allocate();
                    break;
                }
            }
            // if item should be put on the right then go right
            else
            {
                t = t->right;
                if (t == NIL)
                {
                    t = parent->right = pool.allocate();
                    break;
                }
            }
        }

        // t is now the node where we will add item and
        // parent is the parent of t

        t->parent = parent;
        t->left = NIL;
        t->right = NIL;
        t->color = red;
        exchange(t->d,d);
        exchange(t->r,r);

        // keep the red-black properties true
        fix_after_add(t);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_from_tree (
        node* t,
        const domain& d,
        domain& d_copy,
        range& r
    )
    {
        while (true)
        {
            if ( comp(d , t->d) )
            {
                // if item is on the left then look in left
                t = t->left;
            }
            else if (comp(t->d , d))
            {
                // if item is on the right then look in right
                t = t->right;
            }
            else
            {
                // found the node we want to remove

                // swap out the item into d_copy and r
                exchange(d_copy,t->d);
                exchange(r,t->r);

                if (t->left == NIL)
                {
                    // if there is no left subtree

                    node* parent = t->parent;

                    // plug hole with right subtree

                    // if t is on the left
                    if (parent->left == t)
                        parent->left = t->right;
                    else
                        parent->right = t->right;
                    t->right->parent = parent;

                    // update tree_root if necessary
                    if (t == tree_root)
                        tree_root = t->right;

                    if (t->color == black)
                        fix_after_remove(t->right);

                    // delete old node
                    pool.deallocate(t);
                }
                else if (t->right == NIL)
                {
                    // if there is no right subtree

                    node* parent = t->parent;

                    // plug hole with left subtree
                    if (parent->left == t)
                        parent->left = t->left;
                    else
                        parent->right = t->left;
                    t->left->parent = parent;

                    // update tree_root if necessary
                    if (t == tree_root)
                        tree_root = t->left;

                    if (t->color == black)
                        fix_after_remove(t->left);

                    // delete old node
                    pool.deallocate(t);
                }
                else
                {
                    // if there is both a left and right subtree
                    // get an element to fill this node now that its been swapped into
                    // item_copy
                    if (remove_least_element_in_tree(t->right,t->d,t->r))
                    {
                        // the node removed was the one pointed to by current_element so we
                        // need to update it so that it points to the right spot.
                        current_element = t;
                    }
                }

                // quit loop
                break;
            }
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    remove_from_tree (
        node* t,
        const domain& d
    )
    {
        while (true)
        {
            if ( comp(d , t->d) )
            {
                // if item is on the left then look in left
                t = t->left;
            }
            else if (comp(t->d , d))
            {
                // if item is on the right then look in right
                t = t->right;
            }
            else
            {
                // found the node we want to remove

                if (t->left == NIL)
                {
                    // if there is no left subtree

                    node* parent = t->parent;

                    // plug hole with right subtree

                    if (parent->left == t)
                        parent->left = t->right;
                    else
                        parent->right = t->right;
                    t->right->parent = parent;

                    // update tree_root if necessary
                    if (t == tree_root)
                        tree_root = t->right;

                    if (t->color == black)
                        fix_after_remove(t->right);

                    // delete old node
                    pool.deallocate(t);
                }
                else if (t->right == NIL)
                {
                    // if there is no right subtree

                    node* parent = t->parent;

                    // plug hole with left subtree
                    if (parent->left == t)
                        parent->left = t->left;
                    else
                        parent->right = t->left;
                    t->left->parent = parent;

                    // update tree_root if necessary
                    if (t == tree_root)
                        tree_root = t->left;

                    if (t->color == black)
                        fix_after_remove(t->left);

                    // delete old node
                    pool.deallocate(t);
                }
                else
                {
                    // if there is both a left and right subtree
                    // get an element to fill this node now that its been swapped into
                    // item_copy
                    remove_least_element_in_tree(t->right,t->d,t->r);

                }

                // quit loop
                break;
            }
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    return_reference (
        node* t,
        const domain& d
    )
    {
        while (t != NIL)
        {
            if ( comp(d , t->d ))
            {
                // if item is on the left then look in left
                t = t->left;
            }
            else if (comp(t->d , d))
            {
                // if item is on the right then look in right
                t = t->right;
            }
            else
            {
                // if it's found then return a reference to it
                return &(t->r);
            }
        }
        return 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    const range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    return_reference (
        const node* t,
        const domain& d
    ) const
    {
        while (t != NIL)
        {
            if ( comp(d , t->d) )
            {
                // if item is on the left then look in left
                t = t->left;
            }
            else if (comp(t->d , d))
            {
                // if item is on the right then look in right
                t = t->right;
            }
            else
            {
                // if it's found then return a reference to it
                return &(t->r);
            }
        }
        return 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    fix_after_add (
        node* t
    )
    {

        while (t->parent->color == red)
        {
            node& grandparent = *(t->parent->parent);

            // if both t's parent and its sibling are red
            if (grandparent.left->color == grandparent.right->color)
            {
                grandparent.color = red;
                grandparent.left->color = black;
                grandparent.right->color = black;
                t = &grandparent;
            }
            else
            {
                // if t is a left child
                if (t == t->parent->left)
                {
                    // if t's parent is a left child
                    if (t->parent == grandparent.left)
                    {
                        grandparent.color = red;
                        grandparent.left->color = black;
                        rotate_right(&grandparent);
                    }
                    // if t's parent is a right child
                    else
                    {
                        t->color = black;
                        grandparent.color = red;
                        double_rotate_left(&grandparent);
                    }
                }
                // if t is a right child
                else
                {
                    // if t's parent is a left child
                    if (t->parent == grandparent.left)
                    {
                        t->color = black;
                        grandparent.color = red;
                        double_rotate_right(&grandparent);
                    }
                    // if t's parent is a right child
                    else
                    {
                        grandparent.color = red;
                        grandparent.right->color = black;
                        rotate_left(&grandparent);
                    }
                }
                break;
            }
        }
        tree_root->color = black;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    fix_after_remove (
        node* t
    )
    {

        while (t != tree_root && t->color == black)
        {
            if (t->parent->left == t)
            {
                node* sibling = t->parent->right;
                if (sibling->color == red)
                {
                    sibling->color = black;
                    t->parent->color = red;
                    rotate_left(t->parent);
                    sibling = t->parent->right;
                }

                if (sibling->left->color == black && sibling->right->color == black)
                {
                    sibling->color = red;
                    t = t->parent;
                }
                else
                {
                    if (sibling->right->color == black)
                    {
                        sibling->left->color = black;
                        sibling->color = red;
                        rotate_right(sibling);
                        sibling = t->parent->right;
                    }

                    sibling->color = t->parent->color;
                    t->parent->color = black;
                    sibling->right->color = black;
                    rotate_left(t->parent);
                    t = tree_root;

                }

            }
            else
            {

                node* sibling = t->parent->left;
                if (sibling->color == red)
                {
                    sibling->color = black;
                    t->parent->color = red;
                    rotate_right(t->parent);
                    sibling = t->parent->left;
                }

                if (sibling->left->color == black && sibling->right->color == black)
                {
                    sibling->color = red;
                    t = t->parent;
                }
                else
                {
                    if (sibling->left->color == black)
                    {
                        sibling->right->color = black;
                        sibling->color = red;
                        rotate_left(sibling);
                        sibling = t->parent->left;
                    }

                    sibling->color = t->parent->color;
                    t->parent->color = black;
                    sibling->left->color = black;
                    rotate_right(t->parent);
                    t = tree_root;

                }

            }

        }
        t->color = black;

    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    short binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    tree_height (
        node* t
    ) const
    {
        if (t == NIL)
            return 0;

        short height1 = tree_height(t->left);
        short height2 = tree_height(t->right);
        if (height1 > height2)
            return height1 + 1;
        else
            return height2 + 1;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    unsigned long binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
    get_count (
        const domain& d,
        node* tree_root
    ) const
    {
        if (tree_root != NIL)
        {
            if (comp(d , tree_root->d))
            {
                // go left
                return get_count(d,tree_root->left);
            }
            else if (comp(tree_root->d , d))
            {
                // go right
                return get_count(d,tree_root->right);
            }
            else
            {
                // go left and right to look for more matches
                return   get_count(d,tree_root->left)
                       + get_count(d,tree_root->right)
                       + 1;
            }
        }
        return 0;
    }

// ----------------------------------------------------------------------------------------

}

#endif // DLIB_BINARY_SEARCH_TREE_KERNEl_2_


text:
require File.dirname(__FILE__) + '/../../shared/rational/inspect'

ruby_version_is "1.9" do
  describe "Rational#inspect" do
    it_behaves_like(:rational_inspect, :inspect)
  end
end

redpajama_set_name: RedPajamaGithub


text:
ACCEPTED

#### According to
The Catalogue of Life, 3rd January 2011

#### Published in
Mycol. Res. 99(8): 1004 (1995)

#### Original name
Pseudospiropes indicus A.N. Rai & B. Rai, 1995

### Remarks
null


text:
package org.springframework.messaging.handler.invocation.reactive;

import org.reactivestreams.Publisher;
import reactor.core.publisher.Mono;

import org.springframework.core.MethodParameter;
import org.springframework.lang.Nullable;
import org.springframework.messaging.Message;

/**
 * Return value handler that simply stores the last return value.
 * @author Rossen Stoyanchev
 */
public class TestReturnValueHandler implements HandlerMethodReturnValueHandler {

	@Nullable
	private Object lastReturnValue;

	@Nullable
	public Object getLastReturnValue() {
		return this.lastReturnValue;
	}

	@Override
	public boolean supportsReturnType(MethodParameter returnType) {
		return true;
	}

	@Override
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public Mono<Void> handleReturnValue(@Nullable Object value, MethodParameter returnType, Message<?> message) {
		return value instanceof Publisher ?
				new ChannelSendOperator((Publisher) value, this::saveValue) :
				saveValue(value);
	}

	private Mono<Void> saveValue(@Nullable Object value) {
		this.lastReturnValue = value;
		return Mono.empty();
	}

}


text:
package com.example.bigtable.simpleperf;

import java.io.IOException;
import java.util.concurrent.TimeUnit;

import org.apache.hadoop.hbase.HColumnDescriptor;
import org.apache.hadoop.hbase.HTableDescriptor;
import org.apache.hadoop.hbase.TableName;
import org.apache.hadoop.hbase.client.Admin;
import org.apache.hadoop.hbase.client.Connection;

import com.google.common.base.Stopwatch;

public class BigtableUtilities {
  public static final byte[] FAMILY = "cf".getBytes();
  public static final byte[] QUALIFIER = "qual".getBytes();

  /**
   * Creates a test table with a column family "cf".
   * @param tableName
   * @param conn
   * @throws IOException
   */
  public static void createTable(TableName tableName, Connection conn) throws IOException {
    System.out.println("Checking table");
    try (Admin admin = conn.getAdmin()) {
      if (!admin.tableExists(tableName)) {
        HTableDescriptor tableDescriptor = new HTableDescriptor(tableName);
        tableDescriptor.addFamily(new HColumnDescriptor(FAMILY));
        admin.createTable(tableDescriptor);
      }
    }
  }

  public static void printPerformance(String prefix, Stopwatch stopwatch, int count) {
    long elapsed = stopwatch.elapsed(TimeUnit.MILLISECONDS);
    if (elapsed == 0) {
      System.out.println(String.format("%s %d in %d ms.", prefix, count, elapsed));
    } else {
      System.out.println(String.format("%s %d in %d ms. That's %d QPS.", prefix, count, elapsed,
        count * 1000 / elapsed));
    }
  }

}


text:
<?php namespace BoundedContext\Laravel\Illuminate\Stream;

use BoundedContext\Contracts\ValueObject\Identifier;

use BoundedContext\Collection\Collection;
use BoundedContext\Schema\Schema;
use BoundedContext\Sourced\Stream\AbstractStream;
use BoundedContext\ValueObject\Integer as Integer_;

use BoundedContext\Laravel\Event\Snapshot\Factory as EventSnapshotFactory;
use Illuminate\Database\ConnectionInterface;

class Stream extends AbstractStream implements \BoundedContext\Contracts\Sourced\Stream\Stream
{
    protected $connection;
    protected $stream_table = 'event_snapshot_stream';
    protected $log_table = 'event_snapshot_log';

    protected $starting_id;
    protected $last_id;

    public function __construct(
        ConnectionInterface $connection,
        EventSnapshotFactory $event_snapshot_factory,
        Identifier $starting_id,
        Integer_  $limit,
        Integer_ $chunk_size
    )
    {
        $this->connection = $connection;

        $this->starting_id = $starting_id;
        $this->last_id = $starting_id;

        parent::__construct(
            $event_snapshot_factory,
            $limit,
            $chunk_size
        );
    }

    public function reset()
    {
        $this->last_id = $this->starting_id;

        parent::reset();
    }

    private function get_next_chunk()
    {
        $query = $this->connection
            ->table($this->stream_table)
            ->select("$this->log_table.snapshot")
            ->join(
                $this->log_table,
                "$this->stream_table.log_id",
                '=',
                "$this->log_table.id"
            )
            ->orderBy("$this->stream_table.id")
            ->limit($this->chunk_size->serialize());

        if(!$this->last_id->is_null())
        {
            $query->whereRaw("
                $this->stream_table.id >
                    (
                        SELECT id FROM `$this->stream_table`
                        WHERE `$this->stream_table`.`log_snapshot_id` = '".$this->last_id->serialize()."'
                    )
                "
            );
        }

        $rows = $query->get();

        return $rows;
    }

    protected function fetch()
    {
        $this->event_snapshots = new Collection();

        $event_snapshot_schemas = $this->get_next_chunk();

        foreach($event_snapshot_schemas as $event_snapshot_schema)
        {
            $event_snapshot = $this->event_snapshot_factory->schema(
                new Schema(
                    json_decode(
                        $event_snapshot_schema->snapshot,
                        true
                    )
                )
            );

            $this->event_snapshots->append($event_snapshot);
            $this->last_id = $event_snapshot->id();
        }
    }
}


text:
require 'spec_helper'

describe 'CF Binary Buildpack' do
  after do
    Machete::CF::DeleteApp.new.execute(app)
  end

  describe 'deploying a Windows HWC app' do
    let(:app_name) { 'hwc_app' }

    context 'without a command or Procfile' do
      let(:app) { Machete.deploy_app(app_name, buildpack: 'binary-test-buildpack', stack: 'windows2012R2', start_command: 'null') }

      it 'logs a warning message' do
        skip_if_no_windows_stack

        expect(app).to have_logged("Warning: We detected a Web.config in your app. This probably means that you want to use the hwc-buildpack. If you really want to use the binary-buildpack, you must specify a start command.")
      end
    end
  end
end


text:
"use strict";

var EC = require('elliptic').ec;
var crpt = require('crypto');
var bs58 = require('bs58');
var zlib = require('zlib');

var ECcrypt = new EC('secp256k1');

exports.encodeMessage = function encodeMessage(msg, attach, contacts, signKey){
	var key = crpt.randomBytes(32),
		iv  = crpt.randomBytes(16),
		ephemeralKey = ECcrypt.genKeyPair(),
		ephemeralBuf = new Buffer(ephemeralKey.getPublic(true, 'hex'), 'hex'),
		shasum, i, j;

	key[31] = 0xAA;

	var msgBuffer = new Buffer('DEADBEEF00000000000000000000000000', 'hex'),
		flags = 0;

	var compressedMsg = zlib.deflateRawSync(new Buffer (JSON.stringify(msg)));

	if(attach) flags |= 1;
	if(signKey) flags |= 2;

	msgBuffer[4] = flags;

	msgBuffer.writeUIntBE(contacts.length, 5, 4);
	msgBuffer.writeUIntBE(compressedMsg.length, 9, 4);

	msgBuffer = Buffer.concat([msgBuffer, compressedMsg]);

	if(attach) {
		msgBuffer = Buffer.concat([msgBuffer, attach]);
		msgBuffer.writeUIntBE(attach.length, 13, 4);
	}

	var secrets = new Buffer(0), sharedSecret;

	for (i = 0; i < contacts.length; i++) {
		shasum = crpt.createHash('sha256');

		shasum.update(new Buffer(ephemeralKey.derive(ECcrypt.keyPair({pub: bs58.decode(contacts[i])}).getPublic()).toArray()));
		sharedSecret = shasum.digest();

		for (j = 0; j < 32; j++) {
			sharedSecret[j] ^= key[j];
		}

		secrets = Buffer.concat([secrets, sharedSecret]);
	}

	var msgHash, sig;

	if(signKey){
		shasum = crpt.createHash('sha256');
		shasum.update(ephemeralBuf);
		shasum.update(iv);
		shasum.update(secrets);
		shasum.update(msgBuffer);
		msgHash = shasum.digest();

		console.log('sig hash: ', msgHash);

		sig = new Buffer(signKey.sign(msgHash).toDER());
		msgBuffer = Buffer.concat([msgBuffer, sig]);
	}

	var aes = crpt.createCipheriv('aes-256-cfb8', key, iv);

	return Buffer.concat([
		ephemeralBuf,
		iv,
		aes.update(msgBuffer.slice(0,16)),
		secrets,
		aes.update(msgBuffer.slice(16)),
		aes.final()
	]);

};

exports.decodeMessage = function decodeMessage(msg, forKey){
	var ephemeral = msg.slice(0, 33),
		iv = msg.slice(33, 49),
		contHead = msg.slice(49, 65),
		secrets = msg.slice(65),
		firstByte = 0xAA,
		secret, shasum,
		message = {},
		sessionKey = new Buffer(32);

	try {
		shasum = crpt.createHash('sha256');
		shasum.update(new Buffer(forKey.derive(ECcrypt.keyPair({pub: ephemeral}).getPublic()).toArray()));
		secret = shasum.digest();

        firstByte ^= secret[31];
    } catch (exception) {
    	console.log('eph err');
        return false;
    }

    var shift = 0, i;

    while(shift < secrets.length){
    	if(firstByte != secrets[shift + 31]){
            shift += 32;
            continue;
        }

        for (i = 0; i < 32; i++) {
            sessionKey[i] = secrets[i + shift] ^ secret[i];
        }

        var aes = crpt.createDecipheriv('aes-256-cfb8', sessionKey, iv);
        var res = aes.update(contHead);

        // [ 68, 69, 83, 85 ]
        if(res[0] == 0xDE  && res[1] == 0xAD  && res[2] == 0xBE  && res[3] == 0xEF){
			message.contactsNum = res.readUIntBE(5, 4);

			secrets = msg.slice(65, 65 + 32 * message.contactsNum);

			res = Buffer.concat([res, aes.update(msg.slice(65 + 32 * message.contactsNum)), aes.final()]);

			message.hasAttach = !!(res[4] & 1);
            message.signed = !!(res[4] & 2);

            var cmpSize = res.readUIntBE(9, 4),
            	attSize = res.readUIntBE(13, 4),
            	sig = null,
            	msgHash, pubSigKey;

			message.msg = JSON.parse(zlib.inflateRawSync(res.slice(17, 17 + cmpSize)).toString());

			if(message.hasAttach){
				message.attach = res.slice(17 + cmpSize, 17 + cmpSize + attSize);
			}

			if(message.signed && message.msg.sender){
				sig = res.slice(17 + cmpSize + attSize);
				shasum = crpt.createHash('sha256');
				shasum.update(ephemeral);
				shasum.update(iv);
				shasum.update(secrets);
				shasum.update(res.slice(0, 17 + cmpSize + attSize));
				msgHash = shasum.digest();

				console.log('sig hash: ', msgHash);

				pubSigKey = ECcrypt.keyPair({pub: bs58.decode(message.msg.sender)});

				if(!pubSigKey.verify(msgHash, sig)){
					console.log('sign fail');
                    return false;
                }

                message.signatureOk = true;
			}

			return message;
		}
		shift += 32;
    }
    console.log('cant decod');
    return false;
};


text:
Deface::Override.new(:virtual_path   => "spree/products/_cart_form",
                     :name           => "spree_variant_options",
                     :replace        => "#product-variants",
                     :partial        => "spree/products/variant_options",
                     :disabled       => false)

Deface::Override.new(:virtual_path   => "spree/admin/option_types/edit",
                     :name           => "admin_option_value_table_headers",
                     :replace        => "thead[data-hook=option_header]",
                     :partial        => "spree/admin/option_values/table_header",
                     :disabled       => false)

Deface::Override.new(:virtual_path   => "spree/admin/option_types/edit",
                     :name           => "admin_option_value_table_empty_colspan",
                     :set_attributes => "tr[data-hook=option_none] td",
                     :attributes     => { :colspan => 5 },
                     :disabled       => false)


text:
#ifndef ARM_COMPUTE_TEST_DEPTHWISE_CONVOLUTION_H
#define ARM_COMPUTE_TEST_DEPTHWISE_CONVOLUTION_H

#include "tests/SimpleTensor.h"
#include "tests/validation/Helpers.h"

namespace arm_compute
{
namespace test
{
namespace validation
{
namespace reference
{
template <typename T, typename TW, typename TB>
SimpleTensor<T> depthwise_convolution(const SimpleTensor<T> &src, const SimpleTensor<TW> &weights, const SimpleTensor<TB> &biases, const TensorShape &dst_shape, const PadStrideInfo &conv_info,
                                      unsigned int depth_multiplier, const Size2D &dilation = Size2D(1U, 1U), const QuantizationInfo &out_quant_info = QuantizationInfo(0.0f, 0));
} // namespace reference
} // namespace validation
} // namespace test
} // namespace arm_compute
#endif /* ARM_COMPUTE_TEST_DEPTHWISE_SEPARABLE_CONVOLUTION_LAYER_H */


text:
namespace v8 {
namespace internal {

namespace {

Handle<Object> NormalizeReceiver(Isolate* isolate, Handle<Object> receiver) {
  // Convert calls on global objects to be calls on the global
  // receiver instead to avoid having a 'this' pointer which refers
  // directly to a global object.
  if (receiver->IsJSGlobalObject()) {
    return handle(Handle<JSGlobalObject>::cast(receiver)->global_proxy(),
                  isolate);
  }
  return receiver;
}

struct InvokeParams {
  static InvokeParams SetUpForNew(Isolate* isolate, Handle<Object> constructor,
                                  Handle<Object> new_target, int argc,
                                  Handle<Object>* argv);

  static InvokeParams SetUpForCall(Isolate* isolate, Handle<Object> callable,
                                   Handle<Object> receiver, int argc,
                                   Handle<Object>* argv);

  static InvokeParams SetUpForTryCall(
      Isolate* isolate, Handle<Object> callable, Handle<Object> receiver,
      int argc, Handle<Object>* argv,
      Execution::MessageHandling message_handling,
      MaybeHandle<Object>* exception_out);

  static InvokeParams SetUpForRunMicrotasks(Isolate* isolate,
                                            MicrotaskQueue* microtask_queue,
                                            MaybeHandle<Object>* exception_out);

  Handle<Object> target;
  Handle<Object> receiver;
  int argc;
  Handle<Object>* argv;
  Handle<Object> new_target;

  MicrotaskQueue* microtask_queue;

  Execution::MessageHandling message_handling;
  MaybeHandle<Object>* exception_out;

  bool is_construct;
  Execution::Target execution_target;
};

// static
InvokeParams InvokeParams::SetUpForNew(Isolate* isolate,
                                       Handle<Object> constructor,
                                       Handle<Object> new_target, int argc,
                                       Handle<Object>* argv) {
  InvokeParams params;
  params.target = constructor;
  params.receiver = isolate->factory()->undefined_value();
  params.argc = argc;
  params.argv = argv;
  params.new_target = new_target;
  params.microtask_queue = nullptr;
  params.message_handling = Execution::MessageHandling::kReport;
  params.exception_out = nullptr;
  params.is_construct = true;
  params.execution_target = Execution::Target::kCallable;
  return params;
}

// static
InvokeParams InvokeParams::SetUpForCall(Isolate* isolate,
                                        Handle<Object> callable,
                                        Handle<Object> receiver, int argc,
                                        Handle<Object>* argv) {
  InvokeParams params;
  params.target = callable;
  params.receiver = NormalizeReceiver(isolate, receiver);
  params.argc = argc;
  params.argv = argv;
  params.new_target = isolate->factory()->undefined_value();
  params.microtask_queue = nullptr;
  params.message_handling = Execution::MessageHandling::kReport;
  params.exception_out = nullptr;
  params.is_construct = false;
  params.execution_target = Execution::Target::kCallable;
  return params;
}

// static
InvokeParams InvokeParams::SetUpForTryCall(
    Isolate* isolate, Handle<Object> callable, Handle<Object> receiver,
    int argc, Handle<Object>* argv, Execution::MessageHandling message_handling,
    MaybeHandle<Object>* exception_out) {
  InvokeParams params;
  params.target = callable;
  params.receiver = NormalizeReceiver(isolate, receiver);
  params.argc = argc;
  params.argv = argv;
  params.new_target = isolate->factory()->undefined_value();
  params.microtask_queue = nullptr;
  params.message_handling = message_handling;
  params.exception_out = exception_out;
  params.is_construct = false;
  params.execution_target = Execution::Target::kCallable;
  return params;
}

// static
InvokeParams InvokeParams::SetUpForRunMicrotasks(
    Isolate* isolate, MicrotaskQueue* microtask_queue,
    MaybeHandle<Object>* exception_out) {
  auto undefined = isolate->factory()->undefined_value();
  InvokeParams params;
  params.target = undefined;
  params.receiver = undefined;
  params.argc = 0;
  params.argv = nullptr;
  params.new_target = undefined;
  params.microtask_queue = microtask_queue;
  params.message_handling = Execution::MessageHandling::kReport;
  params.exception_out = exception_out;
  params.is_construct = false;
  params.execution_target = Execution::Target::kRunMicrotasks;
  return params;
}

Handle<Code> JSEntry(Isolate* isolate, Execution::Target execution_target,
                     bool is_construct) {
  if (is_construct) {
    DCHECK_EQ(Execution::Target::kCallable, execution_target);
    return BUILTIN_CODE(isolate, JSConstructEntry);
  } else if (execution_target == Execution::Target::kCallable) {
    DCHECK(!is_construct);
    return BUILTIN_CODE(isolate, JSEntry);
  } else if (execution_target == Execution::Target::kRunMicrotasks) {
    DCHECK(!is_construct);
    return BUILTIN_CODE(isolate, JSRunMicrotasksEntry);
  }
  UNREACHABLE();
}

V8_WARN_UNUSED_RESULT MaybeHandle<Object> Invoke(Isolate* isolate,
                                                 const InvokeParams& params) {
  RuntimeCallTimerScope timer(isolate, RuntimeCallCounterId::kInvoke);
  DCHECK(!params.receiver->IsJSGlobalObject());
  DCHECK_LE(params.argc, FixedArray::kMaxLength);

#ifdef USE_SIMULATOR
  // Simulators use separate stacks for C++ and JS. JS stack overflow checks
  // are performed whenever a JS function is called. However, it can be the case
  // that the C++ stack grows faster than the JS stack, resulting in an overflow
  // there. Add a check here to make that less likely.
  StackLimitCheck check(isolate);
  if (check.HasOverflowed()) {
    isolate->StackOverflow();
    if (params.message_handling == Execution::MessageHandling::kReport) {
      isolate->ReportPendingMessages();
    }
    return MaybeHandle<Object>();
  }
#endif

  // api callbacks can be called directly, unless we want to take the detour
  // through JS to set up a frame for break-at-entry.
  if (params.target->IsJSFunction()) {
    Handle<JSFunction> function = Handle<JSFunction>::cast(params.target);
    if ((!params.is_construct || function->IsConstructor()) &&
        function->shared().IsApiFunction() &&
        !function->shared().BreakAtEntry()) {
      SaveAndSwitchContext save(isolate, function->context());
      DCHECK(function->context().global_object().IsJSGlobalObject());

      Handle<Object> receiver = params.is_construct
                                    ? isolate->factory()->the_hole_value()
                                    : params.receiver;
      auto value = Builtins::InvokeApiFunction(
          isolate, params.is_construct, function, receiver, params.argc,
          params.argv, Handle<HeapObject>::cast(params.new_target));
      bool has_exception = value.is_null();
      DCHECK(has_exception == isolate->has_pending_exception());
      if (has_exception) {
        if (params.message_handling == Execution::MessageHandling::kReport) {
          isolate->ReportPendingMessages();
        }
        return MaybeHandle<Object>();
      } else {
        isolate->clear_pending_message();
      }
      return value;
    }
  }

  // Entering JavaScript.
  VMState<JS> state(isolate);
  CHECK(AllowJavascriptExecution::IsAllowed(isolate));
  if (!ThrowOnJavascriptExecution::IsAllowed(isolate)) {
    isolate->ThrowIllegalOperation();
    if (params.message_handling == Execution::MessageHandling::kReport) {
      isolate->ReportPendingMessages();
    }
    return MaybeHandle<Object>();
  }
  if (!DumpOnJavascriptExecution::IsAllowed(isolate)) {
    V8::GetCurrentPlatform()->DumpWithoutCrashing();
    return isolate->factory()->undefined_value();
  }

  if (params.execution_target == Execution::Target::kCallable) {
    Handle<Context> context = isolate->native_context();
    if (!context->script_execution_callback().IsUndefined(isolate)) {
      v8::Context::AbortScriptExecutionCallback callback =
          v8::ToCData<v8::Context::AbortScriptExecutionCallback>(
              context->script_execution_callback());
      v8::Isolate* api_isolate = reinterpret_cast<v8::Isolate*>(isolate);
      v8::Local<v8::Context> api_context = v8::Utils::ToLocal(context);
      callback(api_isolate, api_context);
      DCHECK(!isolate->has_scheduled_exception());
      // Always throw an exception to abort execution, if callback exists.
      isolate->ThrowIllegalOperation();
      return MaybeHandle<Object>();
    }
  }

  // Placeholder for return value.
  Object value;

  Handle<Code> code =
      JSEntry(isolate, params.execution_target, params.is_construct);
  {
    // Save and restore context around invocation and block the
    // allocation of handles without explicit handle scopes.
    SaveContext save(isolate);
    SealHandleScope shs(isolate);

    if (FLAG_clear_exceptions_on_js_entry) isolate->clear_pending_exception();

    if (params.execution_target == Execution::Target::kCallable) {
      // clang-format off
      // {new_target}, {target}, {receiver}, return value: tagged pointers
      // {argv}: pointer to array of tagged pointers
      using JSEntryFunction = GeneratedCode<Address(
          Address root_register_value, Address new_target, Address target,
          Address receiver, intptr_t argc, Address** argv)>;
      // clang-format on
      JSEntryFunction stub_entry =
          JSEntryFunction::FromAddress(isolate, code->InstructionStart());

      Address orig_func = params.new_target->ptr();
      Address func = params.target->ptr();
      Address recv = params.receiver->ptr();
      Address** argv = reinterpret_cast<Address**>(params.argv);
      RuntimeCallTimerScope timer(isolate, RuntimeCallCounterId::kJS_Execution);
      value = Object(stub_entry.Call(isolate->isolate_data()->isolate_root(),
                                     orig_func, func, recv, params.argc, argv));
    } else {
      DCHECK_EQ(Execution::Target::kRunMicrotasks, params.execution_target);

      // clang-format off
      // return value: tagged pointers
      // {microtask_queue}: pointer to a C++ object
      using JSEntryFunction = GeneratedCode<Address(
          Address root_register_value, MicrotaskQueue* microtask_queue)>;
      // clang-format on
      JSEntryFunction stub_entry =
          JSEntryFunction::FromAddress(isolate, code->InstructionStart());

      RuntimeCallTimerScope timer(isolate, RuntimeCallCounterId::kJS_Execution);
      value = Object(stub_entry.Call(isolate->isolate_data()->isolate_root(),
                                     params.microtask_queue));
    }
  }

#ifdef VERIFY_HEAP
  if (FLAG_verify_heap) {
    value.ObjectVerify(isolate);
  }
#endif

  // Update the pending exception flag and return the value.
  bool has_exception = value.IsException(isolate);
  DCHECK(has_exception == isolate->has_pending_exception());
  if (has_exception) {
    if (params.message_handling == Execution::MessageHandling::kReport) {
      isolate->ReportPendingMessages();
    }
    return MaybeHandle<Object>();
  } else {
    isolate->clear_pending_message();
  }

  return Handle<Object>(value, isolate);
}

MaybeHandle<Object> InvokeWithTryCatch(Isolate* isolate,
                                       const InvokeParams& params) {
  bool is_termination = false;
  MaybeHandle<Object> maybe_result;
  if (params.exception_out != nullptr) {
    *params.exception_out = MaybeHandle<Object>();
  }
  DCHECK_IMPLIES(
      params.message_handling == Execution::MessageHandling::kKeepPending,
      params.exception_out == nullptr);
  // Enter a try-block while executing the JavaScript code. To avoid
  // duplicate error printing it must be non-verbose.  Also, to avoid
  // creating message objects during stack overflow we shouldn't
  // capture messages.
  {
    v8::TryCatch catcher(reinterpret_cast<v8::Isolate*>(isolate));
    catcher.SetVerbose(false);
    catcher.SetCaptureMessage(false);

    maybe_result = Invoke(isolate, params);

    if (maybe_result.is_null()) {
      DCHECK(isolate->has_pending_exception());
      if (isolate->pending_exception() ==
          ReadOnlyRoots(isolate).termination_exception()) {
        is_termination = true;
      } else {
        if (params.exception_out != nullptr) {
          DCHECK(catcher.HasCaught());
          DCHECK(isolate->external_caught_exception());
          *params.exception_out = v8::Utils::OpenHandle(*catcher.Exception());
        }
      }
      if (params.message_handling == Execution::MessageHandling::kReport) {
        isolate->OptionalRescheduleException(true);
      }
    }
  }

  // Re-request terminate execution interrupt to trigger later.
  if (is_termination) isolate->stack_guard()->RequestTerminateExecution();

  return maybe_result;
}

}  // namespace

// static
MaybeHandle<Object> Execution::Call(Isolate* isolate, Handle<Object> callable,
                                    Handle<Object> receiver, int argc,
                                    Handle<Object> argv[]) {
  return Invoke(isolate, InvokeParams::SetUpForCall(isolate, callable, receiver,
                                                    argc, argv));
}

MaybeHandle<Object> Execution::CallBuiltin(Isolate* isolate,
                                           Handle<JSFunction> builtin,
                                           Handle<Object> receiver, int argc,
                                           Handle<Object> argv[]) {
  DCHECK(builtin->code().is_builtin());
  DisableBreak no_break(isolate->debug());
  return Invoke(isolate, InvokeParams::SetUpForCall(isolate, builtin, receiver,
                                                    argc, argv));
}

// static
MaybeHandle<Object> Execution::New(Isolate* isolate, Handle<Object> constructor,
                                   int argc, Handle<Object> argv[]) {
  return New(isolate, constructor, constructor, argc, argv);
}

// static
MaybeHandle<Object> Execution::New(Isolate* isolate, Handle<Object> constructor,
                                   Handle<Object> new_target, int argc,
                                   Handle<Object> argv[]) {
  return Invoke(isolate, InvokeParams::SetUpForNew(isolate, constructor,
                                                   new_target, argc, argv));
}

// static
MaybeHandle<Object> Execution::TryCall(Isolate* isolate,
                                       Handle<Object> callable,
                                       Handle<Object> receiver, int argc,
                                       Handle<Object> argv[],
                                       MessageHandling message_handling,
                                       MaybeHandle<Object>* exception_out) {
  return InvokeWithTryCatch(
      isolate,
      InvokeParams::SetUpForTryCall(isolate, callable, receiver, argc, argv,
                                    message_handling, exception_out));
}

// static
MaybeHandle<Object> Execution::TryRunMicrotasks(
    Isolate* isolate, MicrotaskQueue* microtask_queue,
    MaybeHandle<Object>* exception_out) {
  return InvokeWithTryCatch(
      isolate, InvokeParams::SetUpForRunMicrotasks(isolate, microtask_queue,
                                                   exception_out));
}

struct StackHandlerMarker {
  Address next;
  Address padding;
};
STATIC_ASSERT(offsetof(StackHandlerMarker, next) ==
              StackHandlerConstants::kNextOffset);
STATIC_ASSERT(offsetof(StackHandlerMarker, padding) ==
              StackHandlerConstants::kPaddingOffset);
STATIC_ASSERT(sizeof(StackHandlerMarker) == StackHandlerConstants::kSize);

void Execution::CallWasm(Isolate* isolate, Handle<Code> wrapper_code,
                         Address wasm_call_target, Handle<Object> object_ref,
                         Address packed_args) {
  using WasmEntryStub = GeneratedCode<Address(
      Address target, Address object_ref, Address argv, Address c_entry_fp)>;
  WasmEntryStub stub_entry =
      WasmEntryStub::FromAddress(isolate, wrapper_code->InstructionStart());

  // Save and restore context around invocation and block the
  // allocation of handles without explicit handle scopes.
  SaveContext save(isolate);
  SealHandleScope shs(isolate);

  Address saved_c_entry_fp = *isolate->c_entry_fp_address();
  Address saved_js_entry_sp = *isolate->js_entry_sp_address();
  if (saved_js_entry_sp == kNullAddress) {
    *isolate->js_entry_sp_address() = GetCurrentStackPosition();
  }
  StackHandlerMarker stack_handler;
  stack_handler.next = isolate->thread_local_top()->handler_;
#ifdef V8_USE_ADDRESS_SANITIZER
  stack_handler.padding = GetCurrentStackPosition();
#else
  stack_handler.padding = 0;
#endif
  isolate->thread_local_top()->handler_ =
      reinterpret_cast<Address>(&stack_handler);
  trap_handler::SetThreadInWasm();

  {
    RuntimeCallTimerScope timer(isolate, RuntimeCallCounterId::kJS_Execution);
    STATIC_ASSERT(compiler::CWasmEntryParameters::kCodeEntry == 0);
    STATIC_ASSERT(compiler::CWasmEntryParameters::kObjectRef == 1);
    STATIC_ASSERT(compiler::CWasmEntryParameters::kArgumentsBuffer == 2);
    STATIC_ASSERT(compiler::CWasmEntryParameters::kCEntryFp == 3);
    Address result = stub_entry.Call(wasm_call_target, object_ref->ptr(),
                                     packed_args, saved_c_entry_fp);
    if (result != kNullAddress) {
      isolate->set_pending_exception(Object(result));
    }
  }

  // If there was an exception, then the thread-in-wasm flag is cleared
  // already.
  if (trap_handler::IsThreadInWasm()) {
    trap_handler::ClearThreadInWasm();
  }
  isolate->thread_local_top()->handler_ = stack_handler.next;
  if (saved_js_entry_sp == kNullAddress) {
    *isolate->js_entry_sp_address() = saved_js_entry_sp;
  }
  *isolate->c_entry_fp_address() = saved_c_entry_fp;
}

}  // namespace internal
}  // namespace v8


text:
class Service::Boundary < Service
  def receive_logs
    raise_config_error 'Missing Organization ID' if settings[:orgid].to_s.empty?
    raise_config_error 'Missing API Key' if settings[:token].to_s.empty?

    return if payload[:events].blank?

    annotation = {
      :type => settings[:title].presence || payload[:saved_search][:name],
      :subtype => payload[:events].first[:message],
      :start_time => Time.zone.parse(payload[:events].first[:received_at]).to_i,
      :end_time => Time.zone.parse(payload[:events].last[:received_at]).to_i,
      :tags => settings[:tags].to_s.split(/, */).compact,
      :links => [
        {
          :rel => 'papertrail',
          :href => "#{payload[:saved_search][:html_search_url]}?centered_on_id=#{payload[:events].first[:id]}",
          :note => 'Start of log messages'
        }
      ]
    }

    annotation[:tags] += payload[:events].map { |e| e[:source_name] }.uniq.sort
    annotation[:tags].uniq!

    # Setup HTTP connection
    http.basic_auth settings[:token], ''
    http.headers['content-type'] = 'application/json'

    http_post "https://api.boundary.com/#{settings[:orgid]}/annotations", annotation.to_json
  end
end


text:
test( "DomainSet Constructor", function() {
	var empty = new DomainSet(),
      name_only = new DomainSet('Test'),
      full = new DomainSet('Test', ['bing.com', 'google.com']);

	equal(empty.name, '');
	deepEqual(empty.domains, []);
	equal(name_only.name, 'Test');
	deepEqual(name_only.domains, []);
	equal(full.name, 'Test');
	deepEqual(full.domains, ['bing.com', 'google.com']);
});

test( "DomainSet Normalization", function () {
	var full  = new DomainSet('Test', ['BING.COM', '   google.com   ', '    YAHOO.COM   ', '\r\nduckduckgo.com\r\n']);

	equal(full._normalizeDomain('GOOGLE.COM'), 'google.com');
	equal(full._normalizeDomain('        google.com            '), 'google.com');
	equal(full._normalizeDomain('\r\ngoogle.com\r\n'), 'google.com');

	deepEqual(full.domains, ['bing.com', 'google.com', 'yahoo.com', 'duckduckgo.com']);
});

test( 'DomainSet Set Behavior', function () {
	var empty = new DomainSet(),
	    full  = new DomainSet('Test', ['google.com', 'bing.com', 'GOOGLE.COM', '    BING.com   ']);

	empty.add('google.com');
	deepEqual(empty.domains, ['google.com']);
	empty.add('google.com');
	deepEqual(empty.domains, ['google.com']);
	empty.add('bing.com');
	deepEqual(empty.domains, ['google.com', 'bing.com']);
	empty.add('GOOGLE.COM');
	deepEqual(empty.domains, ['google.com', 'bing.com']);
	empty.add('    ');
	deepEqual(empty.domains, ['google.com', 'bing.com']);

	deepEqual(full.domains, ['google.com', 'bing.com']);
});

test( 'DomainSet Contains', function () {
	var empty = new DomainSet(),
	    full  = new DomainSet('Test', ['google.com', 'bing.com']);

	ok(!empty.contains('google.com'));
	empty.add('google.com');
	ok(empty.contains('google.com'));
	ok(!empty.contains('bing.com'));

	ok(!full.contains('yahoo.com'));
	ok(full.contains('google.com'));
	ok(full.contains('bing.com'));
});