src/collection/collection.hpp

Idź do dokumentacji tego pliku.

/*
 panaLiX, Adrian Panasiuk 2002-5,8
 http://panalix.sf.net/
 ad.ek336@gmail.com
 
 small osdev project
 provided under GPLv3 license.
 */


#ifndef __PANALIX_COLLECTION_HPP
#define __PANALIX_COLLECTION_HPP

//#include "src/collection/option.hpp"

namespace Collection {
   extern struct Memory::Heap::heapbox collection_heapbox;

   void init();
   namespace Mem {
      void *kmalloc(uint32 size, char *name);
      void kfree(void *ptr);
   }
/* =============================== */

#if 0
   namespace AvlTree_2 {
      template<typename T,int (*cmp)(T,T)>
      struct AvlTree {
         struct AvlNode {
            struct AvlNode *l, *r;
            T key;
            uint32 ht;
         };

         struct AvlNode *nd;

         void rotleft(struct AvlNode *&av) {
            testif(av!=null); 
            testif(av->r != null);
      
            struct AvlNode *v;

            v= av->r;
            av->r = v->l;
            v->l = av;

            av= v;

            setHeight(av->l);
            setHeight(av);
         }

         void rotright(struct AvlNode *&av) {
            testif(av!=null);
            testif(av->l!=null);

            struct AvlNode *v;

            v=av->l;
            av->l = av->l->r;
            v->r = av;

            av= v;

            setHeight(av->r);
            setHeight(av);
         }

         void setHeight(struct AvlNode *&av) {
            uint32 ht=0;
            testif(av!=null);
            if (av->l)
               ht=av->l->ht;
            if (av->r)
               ht=MAX(ht,av->r->ht);
            av->ht= 1+ht;
         }

         bool checkHt() { return checkHt(nd); }
         bool checkHt(struct AvlNode *&av) {
            if (av == null) return false;
            uint32 lh=0,rh=0;
            if (av->l)
               lh= av->l->ht;
            if (av->r)
               rh= av->r->ht;

            bool ret = checkHt(av->r) || checkHt(av->l);
            
            if (av->ht != 1+MAX(lh,rh) || lh > rh+1 || rh > lh+1) {
               kprintf("checkHt: ");
               write(av);
               kprintf("\n");
               return true;
            }
            return ret;
         }

         uint32 height(struct AvlNode *&av) {
            if (av==null)
               return 0;
            return av->ht;
         }

         void bal(struct AvlNode *&av) {
            uint32 hl=height(av->l);
            uint32 hr=height(av->r);

            if (hl > hr+1) {
               if (height(av->l->l) >= height(av->l->r))
                  rotright(av);
               else {
                  rotleft(av->l);
                  rotright(av);
               }
            }
            if (hr > hl+1) {
               if (height(av->r->r) >= height(av->r->l))
                  rotleft(av);
               else {
                  rotright(av->r);
                  rotleft(av);
               }
            }
         }

         bool insert(T v) {
            bool ret= insert(nd, v);
            return ret;
         }

         bool insert(struct AvlNode *&av, T v) {
            if (av==null) {
               av= static_cast<struct AvlNode*>(kmalloc(sizeof(struct AvlNode),"avl node"));
               av->l=null;
               av->r=null;
               av->ht=1;
               av->key=v;
               return false;
            }
            int c= cmp(av->key,v);
            if (c==0) {
               av->key=v;
               return true;
            }
            if (c < 0) {
               bool ret=insert(av->r,v);
               setHeight(av);
               bal(av);
               return ret;
            }
            bool ret= insert(av->l,v);
            setHeight(av);
            bal(av);

            return ret;
         }

         bool remove(T v) { return remove(nd,v); }
         bool remove(struct AvlNode *&av, T v) {
            if (av==null) return false;
            int c = cmp(av->key,v);
            if (c==0) {
               if (av->r==null) {
                  struct AvlNode *a;
                  av=av->l;
                  kfree(a);
                  return true;
                } else {
                  T a = removeMin(av->r);
                  av->key=a;
                  setHeight(av);
                  bal(av);
                  return true;
                }
            }
            bool ret;
            if (c < 0) {
               ret = remove(av->r,v);
               setHeight(av);
               bal(av);
               return ret;
            } else {
               ret= remove(av->l,v);
               setHeight(av);
               bal(av);
            }
            return ret;
         }

         bool exists(T v) { return exists(nd,v); }
         bool exists(struct AvlNode *&av, T v) {
            if (av==null) return false;
            int c = cmp(av->key,v);
            if (c==0) return true;
            if (c<0) return exists(av->r,v);
            return exists(av->l,v);
         }

         Collection::Option<T> find(T v) { return find(nd,v); }
         Collection::Option<T> find(struct AvlNode *&av, T v) {
            if (av==null) return Option<T>();
            int c = cmp(av->key,v);
            if (c==0) return Option<T>(v);
            if (c<0) return find(av->r,v);
            return find(av->l,v);
         }

         T removeMin(struct AvlNode *&av) {
            testif(av!=null);
            if (av->l==null) {
               T ret= av->key;
               struct AvlNode *v=av->r;
               kfree(av);
               av= v;
               return ret;
            } else {
               T ret = removeMin(av->l);
               setHeight(av);
               return ret;
            }
         }

         T findMin() { return findMin(nd); }
         T findMin(struct AvlNode *&av) {
            testif(av!=null);
            if (av->l == null)
               return av->key;
            return findMin(av->l);
         }

         bool isEmpty() { return isEmpty(nd); }
         bool isEmpty(struct AvlNode *&av) {
            return av==null;
         }

         void write() { write(nd); }
         void write(struct AvlNode *&av) {
            if (av == null) kprintf("-");
            else {
               kprintf("(");
               write(av->l);
               kprintf(",");
               kprintf("%d",av->key);
               kprintf(",");
               write(av->r);
               kprintf(",%d",av->ht);
               kprintf(")");
            }
         }
      };

   }
#endif
}

#endif

---