1/**
2 * @file sparse_array.h
3 * Auto-expanding sparse array type
4 *
5 * @remark Copyright 2007 OProfile authors
6 * @remark Copyright (c) International Business Machines, 2007.
7 * @remark Read the file COPYING
8 *
9 * @author Dave Nomura <dcnltc@us.ibm.com>
10 */
11
12#ifndef SPARSE_ARRAY_H
13#define SPARSE_ARRAY_H
14
15template <typename I, typename T> class sparse_array {
16public:
17	typedef std::map<I, T> container_type;
18	typedef typename container_type::size_type size_type;
19
20	/**
21	 * Index into the map for a value.
22	 * NOTE: since std::map does/can not have a const member function for
23	 * operator[], this const member function simply returns 0 for
24	 * profile classes that aren't represented in the map.
25	 * This member function will only be invoked for queries of the
26	 * sparse array.
27	 */
28	T operator[](size_type index) const {
29		typename container_type::const_iterator it = container.find(index);
30		if (it != container.end())
31			return it->second;
32		else
33			return 0;
34	}
35
36
37	/**
38	 * Index into the vector for a value. If the index is larger than
39	 * the current max index, a new array entry is created.
40	 */
41	T & operator[](size_type index) {
42		return container[index];
43	}
44
45
46	/**
47	 * vectorized += operator
48	 */
49	sparse_array & operator+=(sparse_array const & rhs) {
50		typename container_type::const_iterator it = rhs.container.begin();
51		typename container_type::const_iterator it_end = rhs.container.end();
52		for ( ; it != it_end; it++)
53			container[it->first] += it->second;
54
55		return *this;
56	}
57
58
59	/**
60	 * vectorized -= operator, overflow shouldn't occur during substraction
61	 * (iow: for each components lhs[i] >= rhs[i]
62	 */
63	sparse_array & operator-=(sparse_array const & rhs) {
64		typename container_type::const_iterator it = rhs.container.begin();
65		typename container_type::const_iterator it_end = rhs.container.end();
66		for ( ; it != it_end; it++)
67			container[it->first] -= it->second;
68
69		return *this;
70	}
71
72
73	/**
74	 * return the maximum index of the array + 1 or 0 if the array
75	 * is empty.
76	 */
77	size_type size() const {
78		if (container.size() == 0)
79			return 0;
80		typename container_type::const_iterator last = container.end();
81		--last;
82		return last->first + 1;
83	}
84
85
86	/// return true if all elements have the default constructed value
87	bool zero() const {
88		typename container_type::const_iterator it = container.begin();
89		typename container_type::const_iterator it_end = container.end();
90		for ( ; it != it_end; it++)
91			if (it->second != 0)
92				return false;
93		return true;
94	}
95
96private:
97	container_type container;
98};
99
100#endif // SPARSE_ARRAY_H
101