PowerSystem/Dynamic_Array.h at master · vananiev/PowerSystem · 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
//---------------------------------------------------------------------------
#ifndef Dynamic_ArrayH
#define Dynamic_ArrayH
#include <vector>
using namespace std;
//---------------------------------------------------------------------------
#define DYNAMIC_ARRAY_BLOCK_LEN 64   // äëèííà êàæäîãî áëîêà (áëîê âûäåëÿåòñÿ ïî ìåðå íåîáõîäèìîñòè â äîïîëíèòåëüíîé ïàìÿòè)
//using namespace std;
//---------------------------------------------------------------------------
// îáåñïå÷èâàåòñÿ âàëèäíîñòü óçàçàòåëåé íà ýëåìåíòû ìàññèâà (â îòëè÷èå îò âåêòîðà)
template<class T> class Dynamic_Array{
   private:
      const unsigned block_len;        // äëèííà áëîêîâ
      unsigned elem_cnt;               // ÷èñëî ñîõðàíåííûõ ýëåìåíòîâ â òåêóùåì áëîêå
      vector <T*> Block;                // Ìàññèâ óêàçàòåëåé íà áëîêè
   public:
      Dynamic_Array();
      Dynamic_Array(unsigned Num_Elements);
      Dynamic_Array(unsigned Blocks_num, unsigned Block_Len);
      ~Dynamic_Array();
      T& push_back(const T &value);          //  ñîõðàíèòü çíà÷åíèå
      void clear();                       // î÷èñòêà ñîäåðæèìîãî
      unsigned size();                    // ðàçìåð ìàññèâà
      T* begin();                         // óêàçàòåëü íà ïåðâûé ýëåìåíò
      T& operator[](unsigned int i);      // âîçâðàùàåì ýëåìåíò ìàññèâà
      Dynamic_Array operator=(Dynamic_Array op2);
      int index(const T* ptr);            // ïîëó÷èòü èíäåêñ ïî óêàçàòåëþ (âîçâðàùàåò -1 åñëè ýëåìåíò íå ñîäåðæèòñÿ â ìàññèâå)
   };
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
template<class T> Dynamic_Array<T>::Dynamic_Array():
                                    block_len(DYNAMIC_ARRAY_BLOCK_LEN){
   Block.push_back( new T [block_len] );
   elem_cnt = 0;  // ýëåìåíòîâ ñîõðàíåíî â òåêóùåì áëîêå
}
//---------------------------------------------------------------------------
/*/ ñîçäàåì Num_Elements ýëåìåíòîâ è ãàðàíòèðóåì ÷òî ïîìåñòèòñÿ Max_Num_Elements
template<class T> Dynamic_Array<T>::Dynamic_Array(unsigned Num_Elements, unsigned Max_Num_Elements):
                                    blocks_num(1 + Max_Num_Elements/(Num_Elements+1)),
                                    block_len(Num_Elements+1){
   Block = new T*[blocks_num];
   for(unsigned i=0; i<blocks_num; i++) Block[i] = NULL;
   i_block = 0;   // èñïîëüçóåìûé áëîê
   Block[ i_block ] = new T [block_len];
   elem_cnt = 0;  // ýëåìåíòîâ ñîõðàíåíî â òåêóùåì áëîêå
}*/
//---------------------------------------------------------------------------
template<class T> Dynamic_Array<T>::Dynamic_Array(unsigned Num_Elements):
                                    block_len(Num_Elements+1){  // ÷èñëî ýëåìåíòîâ â áëîêå ðàâíî ÷èñëó ýëåìåíòîâ + 1 (èíà÷å âäðóã Num_Elements==0)
   Block.push_back( new T[block_len] );
   elem_cnt = Num_Elements;  // ýëåìåíòîâ ñîõðàíåíî â òåêóùåì áëîêå
}
//---------------------------------------------------------------------------
template<class T> Dynamic_Array<T>::~Dynamic_Array(){
   for(unsigned i=0, n=Block.size(); i<n; i++)
      delete [] Block[i];
}
//---------------------------------------------------------------------------
template<class T> T& Dynamic_Array<T>::push_back(const T &value){
   // ñîõðàíÿåì
   unsigned i_block = Block.size()-1;
   *(Block[ i_block ] + elem_cnt) = value;
   unsigned blk = i_block;
   unsigned ind = elem_cnt;
   elem_cnt++;
   // íóæíî ëè ñîçäàòü íîâûé áëîê
   if(elem_cnt >= block_len){
      Block.push_back( new T [block_len] );
      elem_cnt = 0;  // ýëåìåíòîâ ñîõðàíåíî â òåêóùåì áëîêå
      }
   return Block[blk][ind];
}
//---------------------------------------------------------------------------
template<class T> void Dynamic_Array<T>::clear(){
   // âñå î÷èùàåì
   for(unsigned i=0, n=Block.size(); i<n; i++)
      delete [] Block[i];
   Block.clear();
   // ñîçäàåì ïî íîâîé
   Block.push_back( new T [block_len] );
   elem_cnt = 0;  // ýëåìåíòîâ ñîõðàíåíî â òåêóùåì áëîêå
}
//---------------------------------------------------------------------------
template<class T> T& Dynamic_Array<T>::operator[](unsigned int i){
   if( i > size() ) {err(0, "Äîñòóï ê íåñóùåñòâóþùåìó ýëåìåíòó"); i = i%size();}
   unsigned blk = i / block_len;
   unsigned index = i - blk*block_len;
   return Block[ blk ][ index ];
}
//---------------------------------------------------------------------------
template<class T> unsigned Dynamic_Array<T>::size(){
   return (Block.size()-1) * block_len + elem_cnt;
}
//---------------------------------------------------------------------------
template<class T> Dynamic_Array<T> Dynamic_Array<T>::operator=(Dynamic_Array op2){
   this->clear();
   unsigned n = op2.size();
   for(unsigned i=0, blk1=0, blk2=0, index1=0, index2=0; i<n; i++, index1++, index2++){
      if(index1 >= block_len)      { blk1++; index1=0; }
      if(index2 >= op2.block_len)  { blk2++; index2=0; }
      Block[ blk1 ][ index1 ] = Block[ blk2 ][ index2 ];
      }
   return *this;
}
//---------------------------------------------------------------------------
template<class T> int Dynamic_Array<T>::index(const T* ptr){
   for(unsigned i=0, n=Block.size(); i<n; i++){
      int ind = ptr - Block[i];
      if( ind >= 0 && ind < (signed)block_len  )
         return ( i * block_len + ind );
      }
   return -1;
}
//---------------------------------------------------------------------------
template<class T> T* Dynamic_Array<T>::begin(){  return &Block[0][0]; }
#endif