Panda3D

Loading...
Searching...
No Matches
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 {
44PUBLISHED:
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
167INLINE std::ostream &
168operator << (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:30
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
SparseArray::get_num_off_bits
int get_num_off_bits() const
Returns the number of bits that are set to 0 in the array.
Definition sparseArray.cxx:76
SparseArray::write_datagram
void write_datagram(BamWriter *manager, Datagram &dg) const
Writes the contents of this object to the datagram for shipping out to a Bam file.
Definition sparseArray.cxx:631
SparseArray::read_datagram
void read_datagram(DatagramIterator &scan, BamReader *manager)
Reads the object that was previously written to a Bam file.
Definition sparseArray.cxx:645
SparseArray::invert_in_place
void invert_in_place()
Inverts all the bits in the SparseArray.
Definition sparseArray.I:255
SparseArray::lower_on
static SparseArray lower_on(int on_bits)
Returns a SparseArray whose lower on_bits bits are on.
Definition sparseArray.I:43
SparseArray::has_any_of
bool has_any_of(int low_bit, int size) const
Returns true if any bit in the indicated range is set, false otherwise.
Definition sparseArray.I:194
SparseArray::get_bit
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition sparseArray.I:123
SparseArray::clear_range
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition sparseArray.I:230
SparseArray::clear
void clear()
Sets all the bits in the SparseArray off.
Definition sparseArray.I:263
SparseArray::get_subrange_begin
int get_subrange_begin(size_t n) const
Returns the first numeric element in the nth subrange.
Definition sparseArray.I:404
SparseArray::has_all_of
bool has_all_of(int low_bit, int size) const
Returns true if all bits in the indicated range are set, false otherwise.
Definition sparseArray.I:206
SparseArray::get_lowest_off_bit
int get_lowest_off_bit() const
Returns the index of the lowest 0 bit in the array.
Definition sparseArray.cxx:116
SparseArray::has_bits_in_common
bool has_bits_in_common(const SparseArray &other) const
Returns true if this SparseArray has any "one" bits in common with the other one, false otherwise.
Definition sparseArray.cxx:205
SparseArray::compare_to
int compare_to(const SparseArray &other) const
Returns a number less than zero if this SparseArray sorts before the indicated other SparseArray,...
Definition sparseArray.cxx:250
SparseArray::has_max_num_bits
static bool has_max_num_bits()
Returns true if there is a maximum number of bits that may be stored in this structure,...
Definition sparseArray.I:81
SparseArray::set_bit_to
void set_bit_to(int index, bool value)
Sets the nth bit either on or off, according to the indicated bool value.
Definition sparseArray.I:149
SparseArray::set_range
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition sparseArray.I:218
SparseArray::range
static SparseArray range(int low_bit, int size)
Returns a SparseArray whose size bits, beginning at low_bit, are on.
Definition sparseArray.I:65
SparseArray::get_max_num_bits
static int get_max_num_bits()
If get_max_num_bits() returned true, this method may be called to return the maximum number of bits t...
Definition sparseArray.I:95
SparseArray::get_num_subranges
size_t get_num_subranges() const
Returns the number of separate subranges stored in the SparseArray.
Definition sparseArray.I:394
SparseArray::get_highest_bits
bool get_highest_bits() const
Returns true if the infinite set of bits beyond get_num_bits() are all on, or false of they are all o...
Definition sparseArray.I:162
SparseArray::bit
static SparseArray bit(int index)
Returns a SparseArray with only the indicated bit on.
Definition sparseArray.I:55
SparseArray::get_highest_off_bit
int get_highest_off_bit() const
Returns the index of the highest 0 bit in the array.
Definition sparseArray.cxx:154
SparseArray::get_subrange_end
int get_subrange_end(size_t n) const
Returns the last numeric element, plus one, in the nth subrange.
Definition sparseArray.I:415
SparseArray::is_zero
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
Definition sparseArray.I:170
SparseArray::is_inverse
bool is_inverse() const
If this is true, the SparseArray is actually defined as a list of subranges of integers that are *not...
Definition sparseArray.I:382
SparseArray::get_num_on_bits
int get_num_on_bits() const
Returns the number of bits that are set to 1 in the array.
Definition sparseArray.cxx:57
SparseArray::is_all_on
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
Definition sparseArray.I:182
SparseArray::set_bit
void set_bit(int index)
Sets the nth bit on.
Definition sparseArray.I:132
SparseArray::all_off
static SparseArray all_off()
Returns a SparseArray whose bits are all off.
Definition sparseArray.I:35
SparseArray::clear_bit
void clear_bit(int index)
Sets the nth bit off.
Definition sparseArray.I:141
SparseArray::set_range_to
void set_range_to(bool value, int low_bit, int size)
Sets the indicated range of bits to either on or off.
Definition sparseArray.I:242
SparseArray::get_num_bits
int get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition sparseArray.I:108
SparseArray::all_on
static SparseArray all_on()
Returns a SparseArray with an infinite array of bits, all on.
Definition sparseArray.I:25
SparseArray::get_next_higher_different_bit
int get_next_higher_different_bit(int low_bit) const
Returns the index of the next bit in the array, above low_bit, whose value is different that the valu...
Definition sparseArray.cxx:174
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
array
STL class.
ov_set
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
Definition ordered_vector.h:269
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.