---

CTBgset.cxx

Go to the documentation of this file.

/*----------------------------------------------------------------------------*/
/* C Tool Box: Designed and implemented by:                                   */
/*    Walter F.J. Mueller   Gesellschaft fuer Schwerionenforschung (GSI)      */
/*                          Planckstrasse 1, D-64291 Darmstadt, Germany       */
/*                  Email:  W.F.J.Mueller@gsi.de                              */
/*                  WWW:    http://www-kp3.gsi.de/www/kp3/people/mueller.html */
/*------------------------------------------+---------------------------------*/

#include <assert.h>

#include "CTB.hxx"
#include "CTB_Trace.hxx"
#include "CTBgset.hxx"

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
bool CTBgset<K,V,C,T,AK,AV>::Insert(const T& obj)
{
  CTB_Trace("CTBgset::Insert(const T&)");
  AK    getkey;                             // key access function object
  int   i_mtype;
  Node* p_parent = LocateMatchOrBound(getkey(obj),i_mtype);

  if (p_parent && i_mtype == 0) return false; // key already present
  InsertNode(new Node(obj),p_parent,i_mtype); // create node and insert
  return true;
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
CTBgsetIterator<K,V,C,T,AK,AV> CTBgset<K,V,C,T,AK,AV>::Find(const K& key)
{
  CTB_Trace("CTBgset::Find(const K&)");
  int   i_mtype;
  Node* p_node = LocateMatchOrBound(key,i_mtype);
  
  if (p_node && i_mtype == 0) return Iterator((Gset*) this,p_node);
  return Iterator();
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
CTBgsetBrowser<K,V,C,T,AK,AV> CTBgset<K,V,C,T,AK,AV>::Find(const K& key) const
{
  CTB_Trace("CTBgset::Find(const K&) const");
  int   i_mtype;
  Node* p_node = LocateMatchOrBound(key,i_mtype);
  
  if (p_node && i_mtype == 0) return Browser((Gset*) this,p_node);
  return Browser();
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
bool CTBgset<K,V,C,T,AK,AV>::Delete(const K& key)
{
  CTB_Trace("CTBgset::Delete(const K&)");
  int   i_mtype;
  Node* p_node = LocateMatchOrBound(key,i_mtype);

  if (!p_node || i_mtype != 0) return false; // quit if key not found
  delete p_node;                            // destruct will do proper unlink
  return true;
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
bool CTBgset<K,V,C,T,AK,AV>::Delete(const CTBgsetIterator<K,V,C,T,AK,AV>& p)
{
  CTB_Trace("CTBgset::Delete(const CTBgsetIterator&)");
  Node* p_node = p;

  delete p_node;
  return p_node;                            // return true if iterator valid
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
void CTBgset<K,V,C,T,AK,AV>::Clear()
{
  CTB_Trace("CTBgset::Clear()");
  CTBbtree::Clear();
  return;
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
CTBgsetNode<K,V,C,T,AK,AV>* CTBgset<K,V,C,T,AK,AV>::LocateMatchOrBound(
                              const K& key, int& i_mtype) const
{
  CTB_Trace("CTBgset::LocateMatchOrBound(const K&,int&)");
  C      compare;                           // compare function object
  Node*  p_cur = (Node*) RNode();

  i_mtype = 0;
  
  if (p_cur) {
    for (;;) {
      int    i_cmp = compare(key,p_cur->Key());
      Node*  p_next;
      
      if (i_cmp == 0) return p_cur;         // match found

      if (i_cmp < 0) {                      // key < current
        p_next = p_cur->Left();             // try to follow left tree
        if (!p_next) {                      // if none found quit
          i_mtype = -1;                     // new node will be left child
          return p_cur;
        }

      } else {                              // key > current
        p_next = p_cur->Right();            // try to follow right tree
        if (!p_next) {                      // if none found quit
          i_mtype = 1;                      // new node will be right child
          return p_cur;
        }
      }

      p_cur = p_next;
    }
  }
  return 0;
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
CTBgsetNode<K,V,C,T,AK,AV>* CTBgset<K,V,C,T,AK,AV>::LocateMatchOrPrev(
                              const K& key, bool& b_found) const
{
  CTB_Trace("CTBgset::LocateMatchOrPrev(const K&,bool&)");
  int   i_mtype;
  Node* p_node = LocateMatchOrBound(key,i_mtype);
  
  b_found = p_node && i_mtype == 0;
  if (p_node && i_mtype < 0) {              // if key < node
    p_node = p_node->Prev();                // take previous node
  }
  return p_node;
}

//------------------------------------------+-----------------------------------

template <class K, class V, class C, class T, class AK, class AV>
CTBgsetNode<K,V,C,T,AK,AV>* CTBgset<K,V,C,T,AK,AV>::LocateMatchOrNext(
                              const K& key, bool& b_found) const
{
  CTB_Trace("CTBgset::LocateMatchOrNext(const K&,bool&)");
  int   i_mtype;
  Node* p_node = LocateMatchOrBound(key,i_mtype);
  
  b_found = p_node && i_mtype == 0;
  if (p_node && i_mtype > 0) {              // if key > node
    p_node = p_node->Next();                // take next node
  }
  return p_node;
}

---