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
BamReader
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition: bamReader.h:110
BamWriter
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
Definition: bamWriter.h:63
BitArray
A dynamic array with an unlimited number of bits.
Definition: bitArray.h:40
DatagramIterator
A class to retrieve the individual data elements previously stored in a Datagram.
Definition: datagramIterator.h:27
Datagram
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
Definition: datagram.h:38
Extension
The default class template does not define any methods.
Definition: extension.h:34
SparseArray
This class records a set of integers, where each integer is either present or not present in the set.
Definition: sparseArray.h:43
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
compare_to
An STL function object class, this is intended to be used on any ordered collection of class objects ...
Definition: stl_compares.h:73
ov_set< Subrange >
extension.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
ordered_vector.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pandabase.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
get_highest_on_bit
int get_highest_on_bit(unsigned short x)
Returns the index of the highest 1 bit in the word.
Definition: pbitops.I:259
get_lowest_on_bit
int get_lowest_on_bit(unsigned short x)
Returns the index of the lowest 1 bit in the word.
Definition: pbitops.I:175
register_type
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
sparseArray.I
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.