/home/th/Pulpit/PrefixTreeV01/PrefixNodeBase.h

Go to the documentation of this file.

#ifndef __PrefixNodeBase__
#define __PrefixNodeBase__


#include <stdlib.h>
#include <stdint.h>

template<class Head>
class PrefixNodeBase {
public:
protected:
        Head head;
        
public:
        
        PrefixNodeBase() {
                head = 0;
        }

        static const Head endBitMask = (Head(1))<<(8*sizeof(Head)-1);
                
        static inline Head encode(unsigned char letter, Head* codes) {
                return codes[letter];
        }

        static inline Head autocode(unsigned char letter, Head* codes) {
                Head& code = codes[letter];
                if( code == 0 ) {
                        code = (Head(1))<<codes[256];
                        codes[256]++;
                        if( codes[256] >= 8*sizeof(Head) ) throw "attempt to encode too much characters";
                }
                return code;
        }
        
        static void resetCodes(Head* codes) {
                for(int i=0; i<=256; i++) codes[i] = 0;
                codes[0] = endBitMask;
                codes[10] = endBitMask;
                codes[13] = endBitMask;
        }
        
        inline void addLetter(Head encodedLetter) {
                head |= encodedLetter;
        }
        
        inline int countLetters() {
                static Head lettersMask = ~endBitMask;
                return __builtin_popcountl( head & lettersMask );
        }
                
        inline int countLetters(Head encodedLetter) {
                return __builtin_popcountl( head & (encodedLetter-1) );
        }
        
        inline bool hasLetter(Head encodedLetter) {
                return head & encodedLetter;
        }
};

#endif

---