Panda3D
sparseArray.h
1 // Filename: sparseArray.h
2 // Created by: drose (14Feb07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #ifndef SPARSEARRAY_H
16 #define SPARSEARRAY_H
17 
18 #include "pandabase.h"
19 #include "ordered_vector.h"
20 
21 class BitArray;
22 class BamWriter;
23 class BamReader;
24 class Datagram;
25 class DatagramIterator;
26 
27 ////////////////////////////////////////////////////////////////////
28 // Class : SparseArray
29 // Description : This class records a set of integers, where each
30 // integer is either present or not present in the set.
31 //
32 // It is similar in principle and in interface to a
33 // BitArray (which can be thought of as a set of
34 // integers, one integer corresponding to each different
35 // bit position), but the SparseArray is implemented as
36 // a list of min/max subrange lists, rather than as a
37 // bitmask.
38 //
39 // This makes it particularly efficient for storing sets
40 // which consist of large sections of consecutively
41 // included or consecutively excluded elements, with
42 // arbitrarily large integers, but particularly
43 // inefficient for doing boolean operations such as & or
44 // |.
45 //
46 // Also, unlike BitArray, the SparseArray can store
47 // negative integers.
48 ////////////////////////////////////////////////////////////////////
49 class EXPCL_PANDA_PUTIL SparseArray {
50 PUBLISHED:
51  INLINE SparseArray();
52  INLINE SparseArray(const SparseArray &copy);
53  INLINE SparseArray &operator = (const SparseArray &copy);
54  SparseArray(const BitArray &from);
55 
56  INLINE static SparseArray all_on();
57  INLINE static SparseArray all_off();
58  INLINE static SparseArray lower_on(int on_bits);
59  INLINE static SparseArray bit(int index);
60  INLINE static SparseArray range(int low_bit, int size);
61 
62  INLINE ~SparseArray();
63 
64  INLINE static bool has_max_num_bits();
65  INLINE static int get_max_num_bits();
66 
67  INLINE int get_num_bits() const;
68  INLINE bool get_bit(int index) const;
69  INLINE void set_bit(int index);
70  INLINE void clear_bit(int index);
71  INLINE void set_bit_to(int index, bool value);
72  INLINE bool get_highest_bits() const;
73  INLINE bool is_zero() const;
74  INLINE bool is_all_on() const;
75 
76  INLINE bool has_any_of(int low_bit, int size) const;
77  INLINE bool has_all_of(int low_bit, int size) const;
78  INLINE void set_range(int low_bit, int size);
79  INLINE void clear_range(int low_bit, int size);
80  INLINE void set_range_to(bool value, int low_bit, int size);
81 
82  int get_num_on_bits() const;
83  int get_num_off_bits() const;
84  int get_lowest_on_bit() const;
85  int get_lowest_off_bit() const;
86  int get_highest_on_bit() const;
87  int get_highest_off_bit() const;
88  int get_next_higher_different_bit(int low_bit) const;
89 
90  INLINE void invert_in_place();
91  bool has_bits_in_common(const SparseArray &other) const;
92  INLINE void clear();
93 
94  void output(ostream &out) const;
95 
96  INLINE bool operator == (const SparseArray &other) const;
97  INLINE bool operator != (const SparseArray &other) const;
98  INLINE bool operator < (const SparseArray &other) const;
99  int compare_to(const SparseArray &other) const;
100 
101  INLINE SparseArray
102  operator & (const SparseArray &other) const;
103 
104  INLINE SparseArray
105  operator | (const SparseArray &other) const;
106 
107  INLINE SparseArray
108  operator ^ (const SparseArray &other) const;
109 
110  INLINE SparseArray
111  operator ~ () const;
112 
113  INLINE SparseArray
114  operator << (int shift) const;
115 
116  INLINE SparseArray
117  operator >> (int shift) const;
118 
119  void operator &= (const SparseArray &other);
120  void operator |= (const SparseArray &other);
121  void operator ^= (const SparseArray &other);
122  INLINE void operator <<= (int shift);
123  INLINE void operator >>= (int shift);
124 
125  INLINE bool is_inverse() const;
126  INLINE int get_num_subranges() const;
127  INLINE int get_subrange_begin(int n) const;
128  INLINE int get_subrange_end(int n) const;
129 
130 private:
131  void do_add_range(int begin, int end);
132  void do_remove_range(int begin, int end);
133  bool do_has_any(int begin, int end) const;
134  bool do_has_all(int begin, int end) const;
135 
136  void do_intersection(const SparseArray &other);
137  void do_union(const SparseArray &other);
138  void do_intersection_neg(const SparseArray &other);
139  void do_shift(int offset);
140 
141  // The SparseArray is implemented as a set of non-overlapping
142  // Subranges.
143  class Subrange {
144  public:
145  INLINE Subrange(int begin, int end);
146  INLINE bool operator < (const Subrange &other) const;
147 
148  int _begin, _end;
149  };
150 
151  typedef ov_set<Subrange> Subranges;
152  Subranges _subranges;
153  bool _inverse;
154 
155 public:
156  void write_datagram(BamWriter *manager, Datagram &dg) const;
157  void read_datagram(DatagramIterator &scan, BamReader *manager);
158 
159 public:
160  static TypeHandle get_class_type() {
161  return _type_handle;
162  }
163  static void init_type() {
164  register_type(_type_handle, "SparseArray");
165  }
166 
167 private:
168  static TypeHandle _type_handle;
169 };
170 
171 #include "sparseArray.I"
172 
173 INLINE ostream &
174 operator << (ostream &out, const SparseArray &array) {
175  array.output(out);
176  return out;
177 }
178 
179 #endif
180 
This class records a set of integers, where each integer is either present or not present in the set...
Definition: sparseArray.h:49
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition: bamReader.h:122
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
Definition: bamWriter.h:73
A dynamic array with an unlimited number of bits.
Definition: bitArray.h:42
An STL function object class, this is intended to be used on any ordered collection of class objects ...
Definition: stl_compares.h:79
A class to retrieve the individual data elements previously stored in a Datagram. ...
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:85
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
Definition: datagram.h:43