Panda3D

sparseArray.h

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 &copy);
00053   INLINE SparseArray &operator = (const SparseArray &copy);
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 
 All Classes Functions Variables Enumerations