Thread: B-Trees With No Keys

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    719

    B-Trees With No Keys

    I was reading about binary trees and I decided I want to create a templated B-Tree class. However, i would like to be able to eliminate the key (more or less - it may still be present, but not necessarily used in the same manner). Instead of using the key to search and insert, I would rather use a user defined function to determine whether an object is greater than or less than another (much like the third parameter in sort()). This part I am somewhat familiar with. What I want to know is, because it seems rather silly to make the user create a function for primitive types, how could I programatically differentiate between primitive types and aggregates? In other words, how could I have it use a pre-defined function when the tree is of type int.

    I just thought of something. Perhaps default values for the function pointer parameter is the way to go?
    Code:
    template<class _T>
    class BTree
    {
         typedef int KeyBTree;   //The key defined within the Btree class
         KeyBTree insert(const _T &, void * = NULL);
    }
    
    PseudoCode
    BTree::insert(..., void *p)
    {
       if(!p)
           p = DefaultFunction(); //  inline bool DefaultFunction(){return  _T1 < _T2}
    
      //...........
    }

    I have yet to try it - I'm too tired to take this on right now.

    Perhaps someone else has a batter idea?
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  2. #2
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    *sits and waits for micko - gun in hand*

    don't bring that attitude to my thread
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >how could I have it use a pre-defined function when the tree is of type int
    If you only have one pre-defined function then it's a (mostly) simple matter of using default arguments. Sure, you could do this with a function pointer as the data member and initialize it with the constructor (similar to C's qsort), but the following is much more fun
    Code:
    #include <iostream>
    
    using namespace std;
    
    template <typename T>
    struct cmp {
      int test ( const T& a, const T& b );
    };
    
    template <>
    struct cmp<int> {
      static int test ( const int& a, const int& b )
      {
        if ( a < b )
          return -1;
        else if ( a > b )
          return +1;
        else
          return 0;
      }
    };
    
    template <typename T = int, typename Compare = cmp<T> >
    class Example {
    public:
      Example ( T a, T b ): one ( a ), two ( b ) {}
      int compare() { return Compare::test ( one, two ); } 
    private:
      T one, two;
    };
    
    int main()
    {
      Example<> a ( 1, 2 );
      Example<> b ( 2, 1 );
      Example<> c ( 2, 2 );
    
      cout<< a.compare() <<endl;
      cout<< b.compare() <<endl;
      cout<< c.compare() <<endl;
    }
    My best code is written with the delete key.

  4. #4
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Quote Originally Posted by misplaced
    *sits and waits for micko - gun in hand*

    don't bring that attitude to my thread
    misplaced I'm not sure if I understand you well...

    What does that mean?
    What attitude?
    I hope you didn't get angry with me for something....?
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  5. #5
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    prelude> i think i see how that works - i'll play with it, thanks.

    micko> i was a little drunk this morning.... you beat me to every new thread - and your replies to all of them seemed a little 'offensive'. so i decided to protect my thread....i ain't mad at ya....i'm just a little wierd sometimes.
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simulate Keys with a Keyboard Hook
    By guitarist809 in forum Windows Programming
    Replies: 3
    Last Post: 11-14-2008, 08:14 PM
  2. blocking or passing keys with global hook
    By pmouse in forum Windows Programming
    Replies: 4
    Last Post: 08-29-2007, 02:54 PM
  3. Movement with arrow keys
    By louis_mine in forum C Programming
    Replies: 3
    Last Post: 02-06-2005, 04:35 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Interfacing with arrow keys...
    By adityakarnad in forum Game Programming
    Replies: 1
    Last Post: 08-30-2003, 10:25 PM