michael@0: /*
michael@0: ******************************************************************************
michael@0: *
michael@0: *   Copyright (C) 2007, International Business Machines
michael@0: *   Corporation and others.  All Rights Reserved.
michael@0: *
michael@0: ******************************************************************************
michael@0: *   file name:  bmpset.h
michael@0: *   encoding:   US-ASCII
michael@0: *   tab size:   8 (not used)
michael@0: *   indentation:4
michael@0: *
michael@0: *   created on: 2007jan29
michael@0: *   created by: Markus W. Scherer
michael@0: */
michael@0: 
michael@0: #ifndef __BMPSET_H__
michael@0: #define __BMPSET_H__
michael@0: 
michael@0: #include "unicode/utypes.h"
michael@0: #include "unicode/uniset.h"
michael@0: 
michael@0: U_NAMESPACE_BEGIN
michael@0: 
michael@0: /*
michael@0:  * Helper class for frozen UnicodeSets, implements contains() and span()
michael@0:  * optimized for BMP code points. Structured to be UTF-8-friendly.
michael@0:  *
michael@0:  * ASCII: Look up bytes.
michael@0:  * 2-byte characters: Bits organized vertically.
michael@0:  * 3-byte characters: Use zero/one/mixed data per 64-block in U+0000..U+FFFF,
michael@0:  *                    with mixed for illegal ranges.
michael@0:  * Supplementary characters: Call contains() on the parent set.
michael@0:  */
michael@0: class BMPSet : public UMemory {
michael@0: public:
michael@0:     BMPSet(const int32_t *parentList, int32_t parentListLength);
michael@0:     BMPSet(const BMPSet &otherBMPSet, const int32_t *newParentList, int32_t newParentListLength);
michael@0:     virtual ~BMPSet();
michael@0: 
michael@0:     virtual UBool contains(UChar32 c) const;
michael@0: 
michael@0:     /*
michael@0:      * Span the initial substring for which each character c has spanCondition==contains(c).
michael@0:      * It must be s<limit and spanCondition==0 or 1.
michael@0:      * @return The string pointer which limits the span.
michael@0:      */
michael@0:     const UChar *span(const UChar *s, const UChar *limit, USetSpanCondition spanCondition) const;
michael@0: 
michael@0:     /*
michael@0:      * Span the trailing substring for which each character c has spanCondition==contains(c).
michael@0:      * It must be s<limit and spanCondition==0 or 1.
michael@0:      * @return The string pointer which starts the span.
michael@0:      */
michael@0:     const UChar *spanBack(const UChar *s, const UChar *limit, USetSpanCondition spanCondition) const;
michael@0: 
michael@0:     /*
michael@0:      * Span the initial substring for which each character c has spanCondition==contains(c).
michael@0:      * It must be length>0 and spanCondition==0 or 1.
michael@0:      * @return The string pointer which limits the span.
michael@0:      */
michael@0:     const uint8_t *spanUTF8(const uint8_t *s, int32_t length, USetSpanCondition spanCondition) const;
michael@0: 
michael@0:     /*
michael@0:      * Span the trailing substring for which each character c has spanCondition==contains(c).
michael@0:      * It must be length>0 and spanCondition==0 or 1.
michael@0:      * @return The start of the span.
michael@0:      */
michael@0:     int32_t spanBackUTF8(const uint8_t *s, int32_t length, USetSpanCondition spanCondition) const;
michael@0: 
michael@0: private:
michael@0:     void initBits();
michael@0:     void overrideIllegal();
michael@0: 
michael@0:     /**
michael@0:      * Same as UnicodeSet::findCodePoint(UChar32 c) const except that the
michael@0:      * binary search is restricted for finding code points in a certain range.
michael@0:      *
michael@0:      * For restricting the search for finding in the range start..end,
michael@0:      * pass in
michael@0:      *   lo=findCodePoint(start) and
michael@0:      *   hi=findCodePoint(end)
michael@0:      * with 0<=lo<=hi<len.
michael@0:      * findCodePoint(c) defaults to lo=0 and hi=len-1.
michael@0:      *
michael@0:      * @param c a character in a subrange of MIN_VALUE..MAX_VALUE
michael@0:      * @param lo The lowest index to be returned.
michael@0:      * @param hi The highest index to be returned.
michael@0:      * @return the smallest integer i in the range lo..hi,
michael@0:      *         inclusive, such that c < list[i]
michael@0:      */
michael@0:     int32_t findCodePoint(UChar32 c, int32_t lo, int32_t hi) const;
michael@0: 
michael@0:     inline UBool containsSlow(UChar32 c, int32_t lo, int32_t hi) const;
michael@0: 
michael@0:     /*
michael@0:      * One byte per ASCII character, or trail byte in lead position.
michael@0:      * 0 or 1 for ASCII characters.
michael@0:      * The value for trail bytes is the result of contains(FFFD)
michael@0:      * for faster validity checking at runtime.
michael@0:      */
michael@0:     UBool asciiBytes[0xc0];
michael@0: 
michael@0:     /*
michael@0:      * One bit per code point from U+0000..U+07FF.
michael@0:      * The bits are organized vertically; consecutive code points
michael@0:      * correspond to the same bit positions in consecutive table words.
michael@0:      * With code point parts
michael@0:      *   lead=c{10..6}
michael@0:      *   trail=c{5..0}
michael@0:      * it is set.contains(c)==(table7FF[trail] bit lead)
michael@0:      *
michael@0:      * Bits for 0..7F (non-shortest forms) are set to the result of contains(FFFD)
michael@0:      * for faster validity checking at runtime.
michael@0:      */
michael@0:     uint32_t table7FF[64];
michael@0: 
michael@0:     /*
michael@0:      * One bit per 64 BMP code points.
michael@0:      * The bits are organized vertically; consecutive 64-code point blocks
michael@0:      * correspond to the same bit position in consecutive table words.
michael@0:      * With code point parts
michael@0:      *   lead=c{15..12}
michael@0:      *   t1=c{11..6}
michael@0:      * test bits (lead+16) and lead in bmpBlockBits[t1].
michael@0:      * If the upper bit is 0, then the lower bit indicates if contains(c)
michael@0:      * for all code points in the 64-block.
michael@0:      * If the upper bit is 1, then the block is mixed and set.contains(c)
michael@0:      * must be called.
michael@0:      *
michael@0:      * Bits for 0..7FF (non-shortest forms) and D800..DFFF are set to
michael@0:      * the result of contains(FFFD) for faster validity checking at runtime.
michael@0:      */
michael@0:     uint32_t bmpBlockBits[64];
michael@0: 
michael@0:     /*
michael@0:      * Inversion list indexes for restricted binary searches in
michael@0:      * findCodePoint(), from
michael@0:      * findCodePoint(U+0800, U+1000, U+2000, .., U+F000, U+10000).
michael@0:      * U+0800 is the first 3-byte-UTF-8 code point. Code points below U+0800 are
michael@0:      * always looked up in the bit tables.
michael@0:      * The last pair of indexes is for finding supplementary code points.
michael@0:      */
michael@0:     int32_t list4kStarts[18];
michael@0: 
michael@0:     /*
michael@0:      * The inversion list of the parent set, for the slower contains() implementation
michael@0:      * for mixed BMP blocks and for supplementary code points.
michael@0:      * The list is terminated with list[listLength-1]=0x110000.
michael@0:      */
michael@0:     const int32_t *list;
michael@0:     int32_t listLength;
michael@0: };
michael@0: 
michael@0: inline UBool BMPSet::containsSlow(UChar32 c, int32_t lo, int32_t hi) const {
michael@0:     return (UBool)(findCodePoint(c, lo, hi) & 1);
michael@0: }
michael@0: 
michael@0: U_NAMESPACE_END
michael@0: 
michael@0: #endif