//  (C) Porkolab 2003
//
//  A.5.4.
//   
//  Providing extra parameters for new and delete


// sorting integers by binary tree 

#include <iostream>
#include <new>
#include <memory>

using namespace std;

struct node
{
          node( int v);
    void  print() const;

    static void *operator new( size_t sz, int i) throw (bad_alloc);
    static void  operator delete(void *p) throw();

    int   val;
    node *left;
    node *right;
};

// members
node::node( int v)        // the constructor
{
    left = right = 0;
    val = v;
}
void node::print() const    // a const member function
{
    cout << val << " ";
}

// global new and delete
void *operator new( size_t sz, int i) throw (bad_alloc)
{
    // not for MSVC++ !
    std::cerr << "::new(int): " << i << std::endl;
    return malloc(sz);
}
void operator delete( void *p, int i) throw ()
{
    // not for MSVC++ !
    std::cerr << "::delete(int): " << i << std::endl;
    free(p);
}
// global new and delete
void *operator new( size_t sz) throw (bad_alloc)
{
    // not for MSVC++ !
    std::cerr << "::new" << std::endl;
    return malloc(sz);
}
void operator delete( void *p) throw ()
{
    // not for MSVC++ !
    std::cerr << "::delete" << std::endl;
    free(p);
}


// member new and delete
void *node::operator new( size_t sz, int i) throw (bad_alloc)
{
    std::cerr << "node::new: " << i << std::endl;
    return ::operator new(sz,i);
}
void node::operator delete(void *p) throw()
{
    node *np = reinterpret_cast<node *>(p);
    std::cerr << "node::delete: " << np->val << std::endl;
    ::operator delete(p,np->val);
}


void insert( node *&r, int v);  // insert into (sub)tree
void print( node *r);           // print (sub)tree
void destroy( node *&r );       // destroy (sub)tree

int main()
{
    node *root = 0;
    int   i;

    while ( cin >> i )
    {
        insert( root, i);
    }
    print( root);
    destroy( root);

    return 0;
}
void print( node *r)
{
    if ( r )
    {
        print( r->left);
        r->print();
        print( r->right);
    }
}
void insert( node *&r, int v)
{
    if ( r )
    {
        insert( v < r->val ? r->left : r->right, v);
    }
    else
    {
        r = new(v) node(v);
    }
}
void destroy( node *&r)
{
    if ( r )
    {
        destroy( r->left);
        destroy( r->right);
        delete r;
        r = 0;
    }
}