Panda3D
|
00001 // Filename: sparseArray.h 00002 // Created by: drose (14Feb07) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #ifndef SPARSEARRAY_H 00016 #define SPARSEARRAY_H 00017 00018 #include "pandabase.h" 00019 #include "ordered_vector.h" 00020 00021 class BitArray; 00022 class BamWriter; 00023 class BamReader; 00024 class Datagram; 00025 class DatagramIterator; 00026 00027 //////////////////////////////////////////////////////////////////// 00028 // Class : SparseArray 00029 // Description : This class records a set of integers, where each 00030 // integer is either present or not present in the set. 00031 // 00032 // It is similar in principle and in interface to a 00033 // BitArray (which can be thought of as a set of 00034 // integers, one integer corresponding to each different 00035 // bit position), but the SparseArray is implemented as 00036 // a list of min/max subrange lists, rather than as a 00037 // bitmask. 00038 // 00039 // This makes it particularly efficient for storing sets 00040 // which consist of large sections of consecutively 00041 // included or consecutively excluded elements, with 00042 // arbitrarily large integers, but particularly 00043 // inefficient for doing boolean operations such as & or 00044 // |. 00045 // 00046 // Also, unlike BitArray, the SparseArray can store 00047 // negative integers. 00048 //////////////////////////////////////////////////////////////////// 00049 class EXPCL_PANDA_PUTIL SparseArray { 00050 PUBLISHED: 00051 INLINE SparseArray(); 00052 INLINE SparseArray(const SparseArray ©); 00053 INLINE SparseArray &operator = (const SparseArray ©); 00054 SparseArray(const BitArray &from); 00055 00056 INLINE static SparseArray all_on(); 00057 INLINE static SparseArray all_off(); 00058 INLINE static SparseArray lower_on(int on_bits); 00059 INLINE static SparseArray bit(int index); 00060 INLINE static SparseArray range(int low_bit, int size); 00061 00062 INLINE ~SparseArray(); 00063 00064 INLINE static bool has_max_num_bits(); 00065 INLINE static int get_max_num_bits(); 00066 00067 INLINE int get_num_bits() const; 00068 INLINE bool get_bit(int index) const; 00069 INLINE void set_bit(int index); 00070 INLINE void clear_bit(int index); 00071 INLINE void set_bit_to(int index, bool value); 00072 INLINE bool get_highest_bits() const; 00073 INLINE bool is_zero() const; 00074 INLINE bool is_all_on() const; 00075 00076 INLINE bool has_any_of(int low_bit, int size) const; 00077 INLINE bool has_all_of(int low_bit, int size) const; 00078 INLINE void set_range(int low_bit, int size); 00079 INLINE void clear_range(int low_bit, int size); 00080 INLINE void set_range_to(bool value, int low_bit, int size); 00081 00082 int get_num_on_bits() const; 00083 int get_num_off_bits() const; 00084 int get_lowest_on_bit() const; 00085 int get_lowest_off_bit() const; 00086 int get_highest_on_bit() const; 00087 int get_highest_off_bit() const; 00088 int get_next_higher_different_bit(int low_bit) const; 00089 00090 INLINE void invert_in_place(); 00091 bool has_bits_in_common(const SparseArray &other) const; 00092 INLINE void clear(); 00093 00094 void output(ostream &out) const; 00095 00096 INLINE bool operator == (const SparseArray &other) const; 00097 INLINE bool operator != (const SparseArray &other) const; 00098 INLINE bool operator < (const SparseArray &other) const; 00099 int compare_to(const SparseArray &other) const; 00100 00101 INLINE SparseArray 00102 operator & (const SparseArray &other) const; 00103 00104 INLINE SparseArray 00105 operator | (const SparseArray &other) const; 00106 00107 INLINE SparseArray 00108 operator ^ (const SparseArray &other) const; 00109 00110 INLINE SparseArray 00111 operator ~ () const; 00112 00113 INLINE SparseArray 00114 operator << (int shift) const; 00115 00116 INLINE SparseArray 00117 operator >> (int shift) const; 00118 00119 void operator &= (const SparseArray &other); 00120 void operator |= (const SparseArray &other); 00121 void operator ^= (const SparseArray &other); 00122 INLINE void operator <<= (int shift); 00123 INLINE void operator >>= (int shift); 00124 00125 INLINE bool is_inverse() const; 00126 INLINE int get_num_subranges() const; 00127 INLINE int get_subrange_begin(int n) const; 00128 INLINE int get_subrange_end(int n) const; 00129 00130 private: 00131 void do_add_range(int begin, int end); 00132 void do_remove_range(int begin, int end); 00133 bool do_has_any(int begin, int end) const; 00134 bool do_has_all(int begin, int end) const; 00135 00136 void do_intersection(const SparseArray &other); 00137 void do_union(const SparseArray &other); 00138 void do_intersection_neg(const SparseArray &other); 00139 void do_shift(int offset); 00140 00141 // The SparseArray is implemented as a set of non-overlapping 00142 // Subranges. 00143 class Subrange { 00144 public: 00145 INLINE Subrange(int begin, int end); 00146 INLINE bool operator < (const Subrange &other) const; 00147 00148 int _begin, _end; 00149 }; 00150 00151 typedef ov_set<Subrange> Subranges; 00152 Subranges _subranges; 00153 bool _inverse; 00154 00155 public: 00156 void write_datagram(BamWriter *manager, Datagram &dg) const; 00157 void read_datagram(DatagramIterator &scan, BamReader *manager); 00158 00159 public: 00160 static TypeHandle get_class_type() { 00161 return _type_handle; 00162 } 00163 static void init_type() { 00164 register_type(_type_handle, "SparseArray"); 00165 } 00166 00167 private: 00168 static TypeHandle _type_handle; 00169 }; 00170 00171 #include "sparseArray.I" 00172 00173 INLINE ostream & 00174 operator << (ostream &out, const SparseArray &array) { 00175 array.output(out); 00176 return out; 00177 } 00178 00179 #endif 00180