MNdictionary.h

Go to the documentation of this file.

/* Copyright (C) 2000 KOM/Darmstadt University of Technology
 *
 * You are allowed to use all other parts of the code under the following terms:
 *
 * For non-commercial use, code may be used in unmodified form provided
 * that this copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This software is provided "as is" and without any express or implied
 * warranties, including, without limitation, the implied warranty of
 * fitness for a particular purpose.
 *
 * The code may be subjected to the GNU General Public License, Version 2,
 * and re-distributed under the terms of this license.
 * As a special exception, permission is granted to link this code
 * with the Qt library and distribute executables, as long as you
 * follow the requirements of the GNU GPL in regard to all of the
 * software in the executable aside from Qt.
 *
 * Commercial use other than under the terms of the GNU General Public
 * License is allowed only after express negotiation of conditions
 * with the authors.
 */
#ifndef _MNDICTIONARY_H
#define _MNDICTIONARY_H 1

#include "dict_both.h"
#include <assert.h>
#include <stdlib.h>
#include <time.h>

#include "MNString.h"

/***********************************************************************
 * MNdictionary<K,I>
 *
 * An alternative MNdictionary template based on AB trees.
 * This one has a static member compare() function. The user is forced
 * to implement this function
 ***********************************************************************/

template <class K, class I> class MNdictionary
{
// type definitions
private:
    typedef _d_dic_item<K,I>* DI;

// member variables
private:
    int _size;
    DI  _root;

// constructors and destructor
public:
      MNdictionary (){
         _size = 0;
         _root = NULL;
         srand((unsigned int) time(NULL));
      }
      virtual ~MNdictionary () {
          clear();
      }

      virtual int compare (const K& x, const K& y) const = 0;

      int compare_int( const int& x, const int& y ) const {
          return ( (x<y) ? -1 : ( (x>y) ? 1 : 0 ) );
      }

// member functions
public:
      K         key             (const void* it) const;
      I         inf             (const void* it) const;
      I&        operator[]	(const void* it) const;
      void*     insert          (const K& k, const I& i);
      void*     lookup          (const K& k) const;
      I         access          (const K& k) const;
      void      del             (const K& k);
      void      del_item        (const void* it);
      void      change_inf      (const void* it, const I& i);
      void      clear           ();
      int       size            () const;
      bool      empty           () const;
      void*     first_item      ( void* start = NULL ) const;
      void*     last_item       () const;
      void*     next_item       (const void* it) const;
private:
      void      clear_helper    (DI it);
      DI        pos_finder      (const K& k) const;
      void      rotation        (DI it);
};


template<class K, class I>
inline void* MNdictionary<K,I>::first_item ( void* start ) const {
   DI lastit = NULL;
   DI it = (start == NULL) ? _root : (DI)start;
   while (it != NULL) {
      lastit = it;
      it = it->left;
   }
   return (void*)lastit;
}

template<class K, class I>
inline void* MNdictionary<K,I>::last_item () const {
   DI lastit = NULL;
   DI it = _root;
   while (it != NULL) {
      lastit = it;
      it = it->right;
   }
   return (void*)lastit;
}

template<class K, class I>
inline K MNdictionary<K,I>::key (const void* it) const {
   return ((DI)it)->key;
}

template<class K, class I>
inline I MNdictionary<K,I>::inf (const void* it) const {
   return ((DI)it)->inf;
}

template<class K, class I>
inline I& MNdictionary<K,I>::operator[] (const void* it) const {
   return (((DI)it)->inf);
}

template<class K, class I>
inline void* MNdictionary<K,I>::lookup (const K& k) const {
   if (_root == NULL) return NULL;
   else {
      DI it = pos_finder(k);
      return (compare(it->key, k) == 0) ? (void*)it : NULL;
   }
}

template<class K, class I>
inline I MNdictionary<K,I>::access (const K& k) const {
   return inf(lookup(k));
}

template<class K, class I>
inline void MNdictionary<K,I>::del (const K& k) {
   void* it = lookup(k);
   if (it != NULL) del_item(it);
}

template<class K, class I>
inline void MNdictionary<K,I>::change_inf (const void* it, const I& i) {
   ((DI)it)->inf = i;
}

template<class K, class I>
inline void MNdictionary<K,I>::clear () {
   if (_root != NULL) {
      clear_helper(_root);
      _root = NULL;
   }
   assert(empty());
}

template<class K, class I>
inline int MNdictionary<K,I>::size () const {
   return _size;
}

template<class K, class I>
inline bool MNdictionary<K,I>::empty () const {
   return (_size==0) ? true : false;
}

template<class K, class I>
inline void MNdictionary<K,I>::rotation (DI it)  {
   // Rotation notwendig?
   while ( (it->father == NULL) ? false : (it->index < it->father->index) ) {
      DI father = it->father;
      // zuerst Großvater umbiegen
      DI opa = father->father;
      if (opa == NULL) {
      // Vater ist Wurzel
         _root = it;
         it->father = NULL;
      } else {
         if (opa->left == father) opa->left = it; else opa->right = it;
         it->father = opa;
      }
      father->father = it;
      // Rechtes oder linkes Kind des Vaters?
      if (father->left == it) {
      // Linkes Kind!
         DI temp = it->right;
         it->right = father;
         father->left = temp;
         if (temp != NULL) temp->father = father;
      } else {
      // Rechtes Kind!
         assert(father->right == it);
         DI temp = it->left;
         it->left = father;
         father->right = temp;
         if (temp != NULL) temp->father = father;
      }
   }
}

template<class K, class I>
inline void* MNdictionary<K,I>::insert (const K& k, const I& i)  {
   if (_root == NULL) {
      // Falls Baum noch leer ist
      assert (empty());
      _root = new _d_dic_item<K,I>(k,i);
      _size++;
      return (void*)_root;
   } else {
      // Baum ist nicht leer
      assert (_root != NULL);
      DI ins_pos = pos_finder(k);
      assert (ins_pos != NULL);
      DI it;
      switch (compare(k, ins_pos->key)) {
         case  0 :
            // Element existiert schon, muß ersetzt werden
            change_inf(ins_pos, i);
            it = ins_pos;
            break;
         case -1 :
            // Element existiert noch nicht, muß links erzeugt werden
            assert(ins_pos->left == NULL);
            it = new _d_dic_item<K,I>(k,i);
            it->father = ins_pos;
            ins_pos->left = it;
            _size++;
            rotation(it);
            break;
         case  1 :
            // Element existiert noch nicht, muß rechts erzeugt werden
            assert(ins_pos->right == NULL);
            it = new _d_dic_item<K,I>(k,i);
            it->father = ins_pos;
            ins_pos->right = it;
            _size++;
            rotation(it);
            break;
         default : assert(false); break;
      }
      return (void*)it;
   }
}

template<class K, class I>
inline _d_dic_item<K,I>* MNdictionary<K,I>::pos_finder (const K& k) const {
/* Findet die Position eines Elements
   Gibt entweder den Knoten mit key=k zurück oder den Knoten,
   dessen Nachfolger ein Knoten mit key=k werden muß.
   Die Funktion MNdictionary.lookup() gibt im Gegensatz zu dieser
   Funktion ein NULL zurück wenn kein Element mit dem Wert k
   vorhanden ist.*/
   assert (_root != NULL);
   DI next = _root;
   DI last;
   do {
      last = next;
      switch (compare(k, next->key)) {
         case -1 : next = next->left; break;
         case  1 : next = next->right; break;
         case  0 : next = NULL; break;
         default : assert(false); break;
      }
   } while (next != NULL);
   assert (last != NULL);
   return last;
}

template<class K, class I>
inline void* MNdictionary<K,I>::next_item (const void* it) const {
   if (it==NULL) return NULL;
   if (((DI)it)->right != NULL) {
      //kleinstes Element des Rechten Unterbaumes suchen
      return first_item( (void*) ((DI)it)->right );
   } else {
      //nächstes Element ist also weiter oben im Baum zu suchen
      DI father = ((DI)it)->father;
      DI last = ((DI)it);
      while (father != NULL) {
         if (father->left == last) {
            //Ich komme aus dem linken Unterbaum
            //also ist der Vater das nächst größere Element
            return father;
         } else {
            //Ich komme aus dem rechten Unterbaum, muß also weiter oben suchen
            last = father;
            father = father->father;
         }
      }
      return NULL; //alle Elemente durch
   }
}

template<class K, class I>
inline void MNdictionary<K,I>::del_item (const void* it) {
   assert(it != NULL); //Darf nur auf existierende Elemente angewandt werden
   DI left = ((DI)it)->left;
   DI right = ((DI)it)->right;
   DI* app_pos;
   DI dad;
   if ((DI)it == _root) {
      // Löschen der Wurzel
      if ((left == NULL) & (right == NULL)) {
         _root = NULL;
         app_pos = NULL; //komplett leer
      } else {
         /* Hier wird überprüft ob einder der Söhne der Wurzel nicht vorhanden ist.
            Sind beide vorhanden wird überprüft welcher den Vorrang bekommt. */
         if ( (left==NULL) ? false : ((right==NULL) ? true : (left->index < right->index)) ) {
            assert (left!=NULL); //Linker Sohn sollte vorhanden sein
            // Der linke Sohn wird neue Wurzel
            _root = left;
            // Linken Sohn als Wurzel kennzeichnen
            left->father = NULL;
            // Rechten Sohn der neuen Wurzel abtrennen
            app_pos = &(left->right);
            dad = left;
            left = left->right;
         } else {
            assert (right!=NULL); //Rechter Sohn sollte vorhanden sein
            _root = right;
            right->father = NULL;
            app_pos = &(right->left);
            dad = right;
            right = right->left;
         }
      }
   } else {
      // Löschen eines inneren Elementes
      dad = ((DI)it)->father;
      assert (dad != NULL); //Das nächste Element ist auf keinen Fall die Wurzel
      // War gelöschtes Element linker oder rechter Sohn seines Vaters
      app_pos = (dad->left == (DI)it) ? &(dad->left) : &(dad->right);
   }
   if (app_pos != NULL) { 
      bool l_exists = (left != NULL);
      bool r_exists = (right != NULL);
      while ( l_exists & r_exists ) {
         if (left->index < right->index) {
            *app_pos = left;
            app_pos = &(left->right);
            left->father = dad;
            dad = left;
            left = left->right;
            l_exists = (left != NULL);
         } else {
            *app_pos = right;
            app_pos = &(right->left);
            right->father = dad;
            dad = right;
            right = right->left;
            r_exists = (right != NULL);
         }
      }
      if (l_exists) {
         *app_pos = left;
         left->father = dad;
      } else if (r_exists) {
         *app_pos = right;
         right->father = dad;
      } else *app_pos = NULL;
   }
   _size--;
   delete (DI)it;
}

template<class K, class I>
inline void MNdictionary<K,I>::clear_helper (DI it) {
   if (it->l() != NULL)
   {
       DI l = (DI)(it->l());
       clear_helper( l );
   }
   if (it->r() != NULL)
   {
       DI r = (DI)(it->r());
       clear_helper( r );
   }
   delete it;
   _size--;
}


/**********************************************************************/
/* StringDictionary                                                   */
/**********************************************************************/

template <class I> class StringDictionary
    : public MNdictionary<MNString, I>
{
public:
    virtual int compare (const MNString& x, const MNString& y) const
    {
        int r = ::compare(x,y);
        if ( r<0 ) return -1;
        if ( r>0 ) return 1;
        return 0;
    }
};

#endif /* _MNDICTIONARY_H */

---