dictionary.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 MN_OS_DICTIONARY_H
#define MN_OS_DICTIONARY_H

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

/* #define nil NULL */

/**********************************************************************/
/* preprocessor-generated compare() functions for basic types.
 * Definition of external compare functions for dictionaries that accept
 * a parameter-free constructor
 */

#undef  DEFINE_COMPARE
#define DEFINE_COMPARE(T)               \
extern int compare (const T& x, const T& y);

DEFINE_COMPARE(int)
DEFINE_COMPARE(unsigned int)
DEFINE_COMPARE(long)
DEFINE_COMPARE(unsigned long)
#ifdef HAVE_KEYWORD_BOOL
DEFINE_COMPARE(bool)
#endif
DEFINE_COMPARE(char)
DEFINE_COMPARE(unsigned char)
DEFINE_COMPARE(float)

/**********************************************************************/
template <class K, class I> class dictionary
{
// type definitions
public:
    typedef void* item;

private:
    typedef _d_dic_item<K,I>* DI;

// member variables
private:
    int _size;
    DI  root;
    int (*cmp_ptr)  (const K &, const K &);

// constructors and destructor
public:
      dictionary (){
         _size = 0;
         root = NULL;
         cmp_ptr = &compare;
         srand((unsigned int) time(NULL));
      }

      /*
       * does not work ?
       * dictionary ( int (*cmp)(const K &, const K &) ) {
       *     _size = 0;
       *     root = NULL;
       *     cmp_ptr = cmp;
       *     srand((unsigned int) time(NULL));
       * }
       */

      ~dictionary();

// 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           () {
          if (root != NULL) {
              clear_helper(root);
          }
          root = NULL;
      }
      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> dictionary<K,I>::~dictionary () {
    clear();
}

template<class K, class I>
inline void* dictionary<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* dictionary<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 dictionary<K,I>::key (const void* it) const {
   return ((DI)it)->key;
}

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

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

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

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

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

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

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

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

template<class K, class I>
inline void dictionary<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* dictionary<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 (cmp_ptr(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>* dictionary<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 dictionary.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 (cmp_ptr(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* dictionary<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 dictionary<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 einer 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 dictionary<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--;
}


#endif /* MN_OS_DICTIONARY_H */

---