udods/RootishArrayStack.h at master · bdsaunders/udods · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
 * RootishArrayStack.h
 *
 *  Created on: 2011-11-23
 *      Author: morin
 */

#ifndef ROOTISHARRAYSTACK_H_
#define ROOTISHARRAYSTACK_H_
#include <math.h>
#include "ArrayStack.h"

namespace ods {

template<class T>
class RootishArrayStack {
protected:
	ArrayStack<T*> blocks;
	int n;

	int i2b(int i);
	void grow();
	void shrink();
public:
	RootishArrayStack();
	virtual ~RootishArrayStack();
	int size();
	T get(int i);
	T set(int i, T x);
	virtual void add(int i, T x);
	virtual T remove(int i);
	virtual void clear();
};


template<class T> inline
int RootishArrayStack<T>::size() {
	return n;
}

template<class T> inline
T RootishArrayStack<T>::get(int i) {
    int b = i2b(i);
    int j = i - b*(b+1)/2;
    return blocks.get(b)[j];
}

template<class T> inline
T RootishArrayStack<T>::set(int i, T x) {
    int b = i2b(i);
    int j = i - b*(b+1)/2;
    T y = blocks.get(b)[j];
    blocks.get(b)[j] = x;
    return y;
}

template<class T> inline
int RootishArrayStack<T>::i2b(int i) {
    double db = (-3.0 + sqrt(9 + 8*i)) / 2.0;
    int b = (int)ceil(db);
    return b;
}

template<class T>
RootishArrayStack<T>::RootishArrayStack() {
	n = 0;
}

template<class T>
RootishArrayStack<T>::~RootishArrayStack() {
}

template<class T>
void RootishArrayStack<T>::add(int i, T x) {
    int r = blocks.size();
    if (r*(r+1)/2 < n + 1) grow();
    n++;
    for (int j = n-1; j > i; j--)
            set(j, get(j-1));
    set(i, x);
}

template<class T>
T RootishArrayStack<T>::remove(int i) {
    T x = get(i);
    for (int j = i; j < n-1; j++)
            set(j, get(j+1));
    n--;
    int r = blocks.size();
    if ((r-2)*(r-1)/2 >= n) shrink();
    return x;
}

template<class T>
void RootishArrayStack<T>::grow() {
    blocks.add(blocks.size(), new T[blocks.size()+1]);
}

template<class T>
void RootishArrayStack<T>::shrink() {
    int r = blocks.size();
    while (r > 0 && (r-2)*(r-1)/2 >= n) {
            delete [] blocks.remove(blocks.size()-1);
            r--;
    }
}

template<class T>
void RootishArrayStack<T>::clear() {
	while (blocks.size() > 0) {
		delete [] blocks.remove(blocks.size()-1);
	}
}

} /* namespace ods */
#endif /* ROOTISHARRAYSTACK_H_ */