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