BTree.h++

Go to the documentation of this file.

/* ---------------------------------------------------------------------------
   commonc++ - A C++ Common Class Library
   Copyright (C) 2005-2012  Mark A Lindner

   This file is part of commonc++.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library 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
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   ---------------------------------------------------------------------------
*/

#ifndef __ccxx_BTree_hxx
#define __ccxx_BTree_hxx

#include <commonc++/Common.h++>
#include <commonc++/StaticObjectPool.h++>
#include <commonc++/Iterator.h++>


#ifdef CCXX_OS_WINDOWS
#include <search.h>
#endif

#include <iostream>
#include <list>

namespace ccxx {

template <typename K, typename V, int ORDER = 10> class BTree
{
  private:

  enum _Status { BTreeOK, BTreeOverflow, BTreeDuplicate, BTreeUnderflow,
                 BTreeNotFound };

  struct _Datum
  {
    K key;
    V value;
    _Datum *next;
    _Datum *prev;
  };

  struct _Node
  {
    _Datum *keys[ORDER * 2];
    _Node *children[ORDER * 2 + 1];
    _Node *parent;
    short count;

    _Node() : parent(NULL), count(0)
    {
      for(int i = 0; i <= ORDER * 2; i++)
        children[i] = NULL;
    }
  };

  _Node *_root;
  int _nkeys;
  int _order;
  size_t _capacity;
  size_t _numItems;

  StaticObjectPool<_Node> _nodePool;
  StaticObjectPool<_Datum> _datumPool;

  _Datum *_head;
  _Datum *_tail;

  uint_t bsearch(const K x, _Datum **a, uint_t len) const;
  _Status insertNode(_Datum *key, _Node *node, _Datum **rkey, _Node **rnode);
  _Status deleteNode(K key, _Node *node);
  void _dump(_Node *node, int depth, std::ostream& stream) const;

  void unlink(_Datum *datum);
  void link(_Datum *datum);

  protected:

  virtual void itemDropped(V data) const;

  public:

  BTree(size_t capacity);

  virtual ~BTree();

  bool put(const K key, const V data);

  bool remove(const K key);

  V get(const K key);

  bool contains(const K key) const;

  void dump(std::ostream& stream) const;

  void getKeys(std::list<K>& keys) const;

  void getValues(std::list<V>& values) const;

  void clear();

  inline size_t getCapacity() const throw()
  { return(_capacity); }

  class Iterator : public ccxx::Iterator<V>
  {
    private:

    BTree<K, V, ORDER>& _tree;
    _Datum *_prev;
    _Datum *_current;
    _Datum *_next;

    public:

    Iterator(BTree<K, V, ORDER>& tree);
    virtual ~Iterator() {}

    virtual void rewind();
    virtual V next() throw(OutOfBoundsException);
    virtual bool hasNext();
    virtual void remove();
  };
};

#include <commonc++/BTreeImpl.h++>

}; // namespace ccxx

#endif // __ccxx_BTree_hxx