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
21class BitArray;
22class BamWriter;
23class BamReader;
24class Datagram;
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 */
43class 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
123private:
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
144 Subranges _subranges;
145 bool _inverse;
146
147 friend class Extension<SparseArray>;
148
149public:
150 void write_datagram(BamWriter *manager, Datagram &dg) const;
151 void read_datagram(DatagramIterator &scan, BamReader *manager);
152
153public:
154 static TypeHandle get_class_type() {
155 return _type_handle;
156 }
157 static void init_type() {
158 register_type(_type_handle, "SparseArray");
159 }
160
161private:
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
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 ...
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
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(),...
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.