//
// Copyright (C) 2000, 2001 Andrey Slepuhin <pooh@msu.ru>
//
// libp++ is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// libp++ is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with libp++; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// $Source$
// $Revision$
// $Date$
// Author: Andrey Slepuhin <pooh@msu.ru>

#include "pxx_block_tree.hh"

namespace pxx
{

int BlockTree::insert (void* _key, size_t _value)
{
  if (root != 0) {
    Item* p = root;
    while (p->mask != 0) {
      if (ptr_and(_key, p->mask) == 0) {
        p = ((Node*)p)->left;
      } else {
        p = ((Node*)p)->right;
      }
    }
    {
      Leaf* p0 = (Leaf*)p;
      if (p0->key == _key) {
        p0->value = _value;
      } else {
        size++;
        Leaf* p1 = new_leaf(_key, _value);
        #if PARANOIA
        if (p1 == 0) FATAL("Unable to create new tree leaf");
        #else
        return -1;
        #endif // PARANOIA
        Leaf* p2 = new_leaf(p0->key, p0->value);
        #if PARANOIA
        if (p2 == 0) FATAL("Unable to create new tree leaf");
        #else
        return -1;
        #endif // PARANOIA
        void* mask = ptr_diff(p1, p2);
        if (ptr_and(_key, mask) == 0) {
          new(p0) Node(mask, p1, p2);
        } else {
          new(p0) Node(mask, p2, p1);
        }
      }
    }
    return 0;
  } else {
    size++;
    root = new_leaf(_key, _value);
    #if PARANOIA
    if (root == 0) FATAL("Unable to create new tree leaf");
    #else
    return -1;
    #endif // PARANOIA
  }
}

int BlockTree::remove (void* _key, size_t& _value = zref(size_t))
{
  if (root != 0) {
    Item** p = &root;
    Item** q = 0;
    while ((*p)->mask != 0) {
      q = p;
      if (ptr_and(_key, (*p)->mask) == 0) {
        p = &((Node*)(*p))->left;
      } else {
        p = &((Node*)(*p))->right;
      }
    }
    if (((Leaf*)(*p))->key == _key) {
      size--;
      if (_value != zref(size_t)) _value = ((Leaf*)(*p))->value;
      deallocate(*p);
      if (q != 0) {
        Node* r = (Node*)*q;
        if (ptr_and(_key, r->mask) == 0) {
          *q = r->right;
        } else {
          *q = r->left;
        }
        deallocate(r);
      } else {
        *p = 0;
      }
      return 0;
    } else {
      #if PARANOIA
      FATAL ("Block tree element not found");
      #else
      return -1;
      #endif // PARANOIA
    }
  } else {
    #if PARANOIA
    FATAL ("Block tree is empty");
    #else
    return -1;
    #endif // PARANOIA
  }
}

int BlockTree::get (void* _key, size_t& _value = zref(size_t))
{
  if (root != 0) {
    Item* p = root;
    while (p->mask != 0) {
      if (ptr_and(_key, p->mask) == 0) {
        p = ((Node*)p)->left;
      } else {
        p = ((Node*)p)->right;
      }
    }
    if (((Leaf*)p)->key == _key) {
      _value = ((Leaf*)p)->value;
      return 0;
    } else {
      return -1; // FIXME
    }
  } else {
    return -1; // FIXME
  }
}

int BlockTree::set (void* _key, size_t _value)
{
  if (root != 0) {
    Item* p = root;
    while (p->mask != 0) {
      if (ptr_and(_key, p->mask) == 0) {
        p = ((Node*)p)->left;
      } else {
        p = ((Node*)p)->right;
      }
    }
    if (((Leaf*)p)->key == _key) {
      ((Leaf*)p)->value = _value;
      return 0;
    } else {
      #if PARANOIA
      FATAL("Block tree element not found");
      #else
      return -1; // FIXME
      #endif // PARANOIA
    }
  } else {
    #if PARANOIA
    FATAL("Block tree is empty");
    #else
    return -1; // FIXME
    #endif // PARANOIA
  }
}

void BlockTree::Item::for_all (void (*_func)(void*, size_t))
{
  if (mask == 0) {
    Leaf* p = (Leaf*)this;
    (*_func)(p->key, p->value);
  } else {
    Node* p = (Node*)this;
    p->left->for_all(_func);
    p->right->for_all(_func);
  }
}

void BlockTree::for_all (void (*_func)(void*, size_t))
{
  if (root != 0) root->for_all(_func);
}

}