TRF Language Model
wb-vector.h
Go to the documentation of this file.
1 // You may obtain a copy of the License at
2 //
3 // http://www.apache.org/licenses/LICENSE-2.0
4 //
5 // Unless required by applicable law or agreed to in writing, software
6 // distributed under the License is distributed on an "AS IS" BASIS,
7 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
8 // See the License for the specific language governing permissions and
9 // limitations under the License.
10 //
11 // Copyright 2014-2015 Tsinghua University
12 // Author: wb.th08@gmail.com (Bin Wang), ozj@tsinghua.edu.cn (Zhijian Ou)
13 //
14 // All h, cpp, cc, and script files (e.g. bat, sh, pl, py) should include the above
15 // license declaration. Different coding language may use different comment styles.
16 
17 
18 
19 
29 #ifndef _WB_VECTOR_H_
30 #define _WB_VECTOR_H_
31 //#include <conio.h>
32 #include <iostream>
33 #include <cmath>
34 #include <cstring>
35 #include <stdlib.h>
36 using namespace std;
37 
39 #define POINT_TEST(p) { if ((p)==NULL) {cout<<#p<<"[New Memory Error]"<<endl; exit(0);} }
41 #define SAFE_NEW(p, Type) {p = new Type; POINT_TEST(p)}
42 #define SAFE_DNEW(PType, p, Type) { PType p = new Type; POINT_TEST(p) }
43 #define SAFE_NEW_ARRAY(p, Type, n) { p = new Type[n]; POINT_TEST(p) }
44 #define SAFE_NEW_DARRAY(p, Type, n, m) { p=new Type*[n]; for(int i=0; i<n; i++){p[i]=new Type[m];}; POINT_TEST(p) }
45 
46 
48 #define SAFE_DELETE(p) {if (p) delete (p); (p)=NULL;}
50 #define SAFE_DELETE_ARRAY(p) {if(p) delete [](p); (p)=NULL;}
51 #define SAFE_DELETE_DARRAY(p, n) { if(p){ for(int i=0; i<n; i++){delete [](p)[i];} delete [](p); (p)=NULL; } }
52 #define SAFE_DEL_POINTER_ARRAY(a) for (int i=0; i<a.GetNum(); i++) { SAFE_DELETE(a[i]); } a.Clean();
53 
54 
55 namespace wb
56 {
58 #define DEFAULE_VECTOR_SIZE 16
59 #define VECTOR_bits2Size(n) (1<<n)
61 
65  template <typename T>
73  class Vector
74  {
75  protected:
76  T *m_pBuffer;
77  int m_nBits;
78  public:
81  {
82  m_pBuffer = NULL;
83  m_nBits = Size2Bits(size);
84  m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
85  }
88  {
89  if (m_pBuffer != NULL)
90  delete[]m_pBuffer;
91  m_pBuffer = NULL;
92  m_nBits = 0;
93  }
95  int Size() const { return VECTOR_bits2Size(m_nBits); }
97  inline T* GetBuffer(int i = 0) const { return m_pBuffer + i; }
99  inline T& Get(int i)
100  {
101 
102  if (i<0) {
103  i = 0;
104  }
105 
106  int nSize = VECTOR_bits2Size(m_nBits);
107 
108  if (i >= nSize)
109  {
110  int nNewBits = Size2Bits(i + 1);
111 
112  T *pNew = new T[VECTOR_bits2Size(nNewBits)];
113  //memset(pNew+m_nBufferSize, 0, sizeof(T)*nStepNum*m_nBufferStep);
114 
115 
116  for (int n = 0; n<nSize; n++)
117  pNew[n] = m_pBuffer[n];
118 
119  delete[] m_pBuffer;
120  m_pBuffer = pNew;
121  m_nBits = nNewBits;
122  }
123 
124  return m_pBuffer[i];
125  }
126 
128  inline int Size2Bits(int size)
129  {
130  for (int n = 1;; ++n) {
131  if (VECTOR_bits2Size(n) >= size)
132  return n;
133  }
134  return 0;
135  }
136 
138 
139  void Fill(T m)
140  {
141  for (int i = 0; i<VECTOR_bits2Size(m_nBits); i++)
142  m_pBuffer[i] = m;
143  }
145  void Zero()
146  {
147  memset(m_pBuffer, 0, sizeof(T)*VECTOR_bits2Size(m_nBits));
148  }
149 
151  /*
152  As sometimes using memcpy may cause error.
153  Such as copying a string vector.
154  */
155  void Copy(const Vector<T> &vector)
156  {
157  if (m_pBuffer == NULL) {
158  m_nBits = vector.m_nBits;
159  m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
160  }
161  else if (m_nBits < vector.m_nBits) {
162  delete[] m_pBuffer;
163  m_nBits = vector.m_nBits;
164  m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
165  }
166 
167  for (int i = 0; i<VECTOR_bits2Size(vector.m_nBits); i++)
168  m_pBuffer[i] = vector.m_pBuffer[i];
169  }
171  void MemCopy(Vector<T> &vector)
172  {
173  if (m_pBuffer == NULL) {
174  m_nBits = vector.m_nBits;
175  m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
176  }
177  else if (m_nBits < vector.m_nBits) {
178  delete[] m_pBuffer;
179  m_nBits = vector.m_nBits;
180  m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
181  }
182 
183  memcpy(m_pBuffer, vector.m_pBuffer, sizeof(T)*VECTOR_bits2Size(m_nBits));
184  }
186  void BufferOutside(T* &p_pt)
187  {
188  p_pt = m_pBuffer;
189  m_pBuffer = NULL;
190  new (this) Vector();
191  }
192  };
193 
204  template <typename T>
205  class Array : public Vector<T>
206  {
207  public:
208  int m_nTop;
209  public:
211  Array(int size = DEFAULE_VECTOR_SIZE) : Vector<T>(size)
212  {
213  m_nTop = -1;
214  }
216  Array(Array &array) { Copy(array); }
218  Array(T* pbuf, int n) { Copy(pbuf, n); }
220  ~Array() { m_nTop = -1; }
222  T& operator [](int i)
223  {
224  if (i < 0) {
225  cout << "[warning] the index less than 0: i=" << i << endl;
226  /*#ifdef _DEBUG*/
227  //getch();
228  /*#endif*/
229  i = 0;
230  }
231 
232  if (i > m_nTop)
233  m_nTop = i;
234 
235  return this->Get(i);
236  }
238  void SetNum(int n) { this->Get(n - 1); m_nTop = n - 1; }
240  int GetNum() const { return m_nTop + 1; }
242  void Add(T t) { (*this)[m_nTop + 1] = t; }
244  T& Add() { return (*this)[m_nTop + 1]; }
246  void Add(Array<T> &a) { for (int i = 0; i < a.GetNum(); i++) { Add(a[i]); } }
248  int Find(T t) {
249  for (int i = 0; i < GetNum(); i++) {
250  if ((*this)[i] == t)
251  return i;
252  }
253  return -1;
254  }
256  T& End() { return (*this)[m_nTop]; }
258  void Clean() { m_nTop = -1; }
260  void Copy(const Array<T> &array)
261  {
262  Vector<T>::Copy(array);
263  m_nTop = array.m_nTop;
264  }
266  void Copy(const T* pbuf, int n)
267  {
268  Clean();
269  for (int i = 0; i < n; i++)
270  (*this)[i] = pbuf[i];
271  }
273  void MemCopy(Array<T> &array)
274  {
275  Vector<T>::MemCopy(array);
276  m_nTop = array.m_nTop;
277  }
279  void operator = (const Array<T> &array) { Copy(array); }
281  operator T* () { return this->GetBuffer(); }
283  void Output(ostream &os)
284  {
285  for (int i = 0; i < GetNum(); i++) {
286  os << this->Get(i) << " ";
287  }
288  }
290  void Input(istream &is)
291  {
292  T t;
293  while (is >> t) {
294  Add(t);
295  }
296  }
298  void Insert(T t)
299  {
300  for (int i = 0; i < GetNum(); i++) {
301  if ((*this)[i] == t) {
302  return;
303  }
304  }
305  Add(t);
306  }
308  T Sum()
309  {
310  T sum = 0;
311  for (int i = 0; i < GetNum(); i++) {
312  sum += (*this)[i];
313  }
314  return sum;
315  }
317  T Max(int &idx) {
318  if (GetNum() == 0) {
319  idx = -1;
320  return 0;
321  }
322 
323  idx = 0;
324  for (int i = 1; i < GetNum(); i++) {
325  if (this->Get(i) > this->Get(idx)) {
326  idx = i;
327  }
328  }
329  return this->Get(idx);
330  }
332  T Min(int &idx)
333  {
334  if (GetNum() == 0) {
335  idx = -1;
336  return 0;
337  }
338 
339  idx = 0;
340  for (int i = 1; i < GetNum(); i++) {
341  if (this->Get(i) < this->Get(idx)) {
342  idx = i;
343  }
344  }
345  return this->Get(idx);
346  }
347  };
348 
355  template <typename T>
356  class DArray : public Vector<T>
357  {
358  public:
359  int m_nXDim;
360  int m_nYDim;
361  DArray(int x_size = DEFAULE_VECTOR_SIZE, int y_size = DEFAULE_VECTOR_SIZE) : Vector<T>(x_size*y_size)
363  {
364  m_nXDim = x_size;
365  m_nYDim = y_size;
366  }
368  T& Get(int i, int j)
369  {
370  return Vector<T>::Get(i*m_nYDim + j);
371  }
372  };
373 
380  template <typename T>
381  class Stack : public Vector<T>
382  {
383  public:
384  int m_nTop;
385  Stack(int size = DEFAULE_VECTOR_SIZE) : Vector<T>(size)
387  {
388  m_nTop = 0;
389  }
391  void Clean() { m_nTop = 0; }
393  void Push(T p_t)
394  {
395  this->Get(m_nTop) = p_t;
396  m_nTop++;
397  }
399  bool Pop(T *p_pT)
400  {
401  if (m_nTop == 0)
402  return false;
403 
404  if (p_pT != NULL)
405  *p_pT = this->Get(m_nTop - 1);
406 
407  m_nTop--;
408  return true;
409  }
411  T Top()
412  {
413  if (m_nTop == 0)
414  return this->Get(0);
415  return this->Get(m_nTop - 1);
416  }
418  int GetNum() const { return m_nTop; }
419  };
420 
430  template <typename T>
431  class Queue : public Vector<T>
432  {
433  public:
434  int m_nTop;
435  int m_nBottom;
436  Queue(int size = DEFAULE_VECTOR_SIZE) : Vector<T>(size)
438  {
439  m_nTop = 0;
440  m_nBottom = 0;
441  }
443  void Clean() { m_nTop = 0; m_nBottom = 0; }
445  void In(T p_t)
446  {
447  this->Get(m_nTop) = p_t;
448  m_nTop++;
449  }
451  bool Out(T *p_pT)
452  {
453  if (m_nBottom == m_nTop)
454  return false;
455  if (p_pT)
456  *p_pT = this->Get(m_nBottom);
457  m_nBottom++;
458  return true;
459  }
461  bool IsEmpty()
462  {
463  return m_nBottom == m_nTop;
464  }
466  int GetNum() { return m_nTop - m_nBottom; }
467  };
468 
469 
478  template <typename T>
479  class CirQueue : Vector<T>
480  {
481  private:
482  int nSize;
483  bool bFull;
484  public:
485  int nHead;
486  int nTail;
487  public:
489  CirQueue(int size = 10) :Vector<T>(size)
490  {
491  nHead = 0;
492  nTail = 0;
493  bFull = false;
494  nSize = size;
495  }
497  void Init(int size)
498  {
499  Clean();
500  this->Get(size);
501  nSize = size;
502  }
504  void Clean()
505  {
506  nHead = 0;
507  nTail = 0;
508  bFull = false;
509  }
511  void In(T t)
512  {
513  if (!bFull) {
514  this->Get(nTail) = t;
515  nTail = (nTail + 1) % nSize;
516  if (nTail == nHead)
517  bFull = true;
518  }
519  else {
520  Out();
521  In(t);
522  }
523  }
525  bool Out(T *t = NULL)
526  {
527  if (!bFull) {
528  if (nHead == nTail) {
529  // empty
530  return false;
531  }
532  else {
533  if (t) *t = this->Get(nHead);
534  nHead = (nHead + 1) % nSize;
535  return true;
536  }
537  }
538  else {
539  if (t) *t = this->Get(nHead);
540  nHead = (nHead + 1) % nSize;
541  bFull = false;
542  return true;
543  }
544  }
546  bool IsEmpty() { return (!bFull) && nHead == nTail; }
548  bool IsFull() { return bFull; }
550  int GetNum() { return (bFull) ? nSize : max(nTail - nHead, nTail + nSize - nHead); }
552  int GetSize() { return nSize; }
554  T GetSum()
555  {
556  T sum = 0;
557  if (bFull) {
558  for (int i = 0; i < nSize; i++)
559  sum += this->Get(i);
560  }
561  else {
562  for (int i = nHead; i != nTail; i = (i + 1) % nSize)
563  sum += this->Get(i);
564  }
565  return sum;
566  }
567  };
568 
570  template <typename T>
571  double VecNorm(T *pVec, int len)
572  {
573  double sum = 0;
574  for (int i = 0; i < len; i++) {
575  sum += pVec[i] * pVec[i];
576  }
577  return sqrt(sum);
578  }
580  template <typename T>
581  double VecDot(T *pVec1, T *pVec2, int len)
582  {
583  double sum = 0;
584  for (int i = 0; i < len; i++) {
585  sum += pVec1[i] * pVec2[i];
586  }
587  return sum;
588  }
590  template <typename T>
591  double VecDiff(T *pVec1, T*pVec2, int len)
592  {
593  double sum = 0;
594  for (int i = 0; i < len; i++) {
595  sum += pow(pVec1[i] - pVec2[i], 2);
596  }
597  return sqrt(sum);
598  }
600  template <typename T>
601  double VecAngle(T *pVec1, T* pVec2, int len)
602  {
603  double sum = Dot(pVec1, pVec2, len);
604  return sum / Norm(pVec1, len) / Norm(pVec2, len);
605  }
607  template <typename T>
608  void VecUnfold(const char *pStr, Array<T> &a)
609  {
610  a.Clean();
611 
612  if (pStr == NULL)
613  return;
614 
615  Array<char*> aStr;
616  char *pStrDup = strdup(pStr);
617  char *p = strtok(pStrDup, "[], ");
618  while (p) {
619  aStr.Add() = strdup(p);
620  p = strtok(NULL, "[], ");
621  }
622  free(pStrDup);
623 
624  for (int i = 0; i < aStr.GetNum(); i++) {
625  Array<double> d;
626  char *p = strtok(aStr[i], ": ");
627  while (p) {
628  d.Add((T)atof(p));
629  p = strtok(NULL, ": ");
630  }
631 
632  double t = 0;
633  switch (d.GetNum()) {
634  case 1: a.Add(d[0]); break;
635  case 2:
636  for (t = d[0]; t <= d[1]; t += 1)
637  a.Add(t);
638  break;
639  case 3:
640  for (t = d[0]; t <= d[2]; t += d[1])
641  a.Add(t);
642  break;
643  default:
644  cout << "Error vector expression!! =>" << pStr << endl;
645  exit(1);
646  }
647 
648  }
649 
650  for (int i = 0; i < aStr.GetNum(); i++) {
651  free(aStr[i]);
652  }
653  }
654 
656  template <typename T>
657  int Compar_Inc(const T& a, const T& b)
658  {
659  if (a > b) return 1;
660  else return -1;
661  }
663  template <typename T>
664  int Compar_Dec(const T& a, const T& b)
665  {
666  if (a > b) return -1;
667  else return 1;
668  }
669 
671  /*
672  \param [in] p the input array
673  \param [in] low the smallest index needed to be sorted, (commonly = 0)
674  \param [in] high the largest index needed to be sorted, (commonly = the length - 1)
675  \param [in] compar the compar function. Set to 'Compar_Inc' for increase and 'Compar_Dec' for decrease
676  */
677  template <typename T>
678  void Qsort(T *p, int low, int high, int(*compar)(const T&, const T&) = Compar_Inc)
679  {
680  if (low >= high)
681  {
682  return;
683  }
684  int first = low;
685  int last = high;
686  T key = p[first];
687 
688  while (first < last)
689  {
690  while (first < last && compar(p[last], key) >= 0)
691  {
692  --last;
693  }
694 
695  p[first] = p[last];
696 
697  while (first < last && compar(p[first], key) <= 0)
698  {
699  ++first;
700  }
701 
702  p[last] = p[first];
703 
704  }
705  p[first] = key;
706  Qsort(p, low, first - 1, compar);
707  Qsort(p, first + 1, high, compar);
708  }
710  template <typename T>
711  void Qsort(Array<T> &a, int(*compar)(const T&, const T&) = Compar_Inc)
712  {
713  Qsort(a.GetBuffer(), 0, a.GetNum() - 1, compar);
714  }
715 
716 
718 }
719 
720 #endif
721 
722 
723 
void Output(ostream &os)
output the array
Definition: wb-vector.h:283
bool Out(T *p_pT)
Move a value outof queue.
Definition: wb-vector.h:451
A dynamic stack.
Definition: wb-vector.h:381
void Copy(const T *pbuf, int n)
Copy the array to current array.
Definition: wb-vector.h:266
void MemCopy(Array< T > &array)
using memcpy to copy a array.
Definition: wb-vector.h:273
void Copy(const Array< T > &array)
Copy the array to current array.
Definition: wb-vector.h:260
A queue based the dynamic memory mangement.
Definition: wb-vector.h:431
T & Get(int i)
get the value at position i
Definition: wb-vector.h:99
T & Add()
Add a value to the tail of array, example &#39;a.Add() = t&#39;.
Definition: wb-vector.h:244
void Clean()
Clean the queue, don&#39;t release the memory.
Definition: wb-vector.h:504
int Size2Bits(int size)
Transform the size to bit.
Definition: wb-vector.h:128
Array(int size=DEFAULE_VECTOR_SIZE)
constructor
Definition: wb-vector.h:211
int m_nTop
Record the top of the array.
Definition: wb-vector.h:208
int m_nBottom
Definition: wb-vector.h:435
double VecDot(T *pVec1, T *pVec2, int len)
[Vec-function] v1*v2^T
Definition: wb-vector.h:581
#define DEFAULE_VECTOR_SIZE
defualt vector size
Definition: wb-vector.h:58
CirQueue(int size=10)
constructor
Definition: wb-vector.h:489
void Clean()
clean the queue. Donot release the memory
Definition: wb-vector.h:443
bool IsEmpty()
Return if the queue is empty.
Definition: wb-vector.h:461
void Input(istream &is)
input the array
Definition: wb-vector.h:290
void Qsort(Array< T > &a, int(*compar)(const T &, const T &)=Compar_Inc)
Quick sork, redefine for class Array.
Definition: wb-vector.h:711
double VecAngle(T *pVec1, T *pVec2, int len)
[Vec-function] the cos of the angle of v1 and v2
Definition: wb-vector.h:601
~Vector()
desturctor
Definition: wb-vector.h:87
T & End()
Get the value at the tail of array.
Definition: wb-vector.h:256
int nTail
the tail of queue
Definition: wb-vector.h:486
bool IsFull()
if the queue is full
Definition: wb-vector.h:548
bool Pop(T *p_pT)
Pop a value outof the stack.
Definition: wb-vector.h:399
T * GetBuffer(int i=0) const
get the buffer pointer
Definition: wb-vector.h:97
2-dimension array.
Definition: wb-vector.h:356
int Compar_Inc(const T &a, const T &b)
comparing function for increase sort.
Definition: wb-vector.h:657
T * m_pBuffer
buffer pointer
Definition: wb-vector.h:76
T Sum()
summate all the values in the array
Definition: wb-vector.h:308
#define VECTOR_bits2Size(n)
transform the bit to memory size
Definition: wb-vector.h:60
int GetNum()
Get number of values.
Definition: wb-vector.h:550
Array(T *pbuf, int n)
constructor
Definition: wb-vector.h:218
bool Out(T *t=NULL)
Remove a value outof queue.
Definition: wb-vector.h:525
void Insert(T t)
insert a value. Avoid repeating
Definition: wb-vector.h:298
T & Get(int i, int j)
Get the value at position i row and j column.
Definition: wb-vector.h:368
T Min(int &idx)
Get the minine value.
Definition: wb-vector.h:332
void In(T t)
Add a value into queue.
Definition: wb-vector.h:511
int Find(T t)
Find a value and return the position.
Definition: wb-vector.h:248
this is the basic class of Array/Stack/Queue. Realize the dynamic memory management ...
Definition: wb-vector.h:73
void Zero()
Fill all the memory to ZERO. call &#39;memset&#39;.
Definition: wb-vector.h:145
void SetNum(int n)
Set Array number, to melloc enough memory.
Definition: wb-vector.h:238
bool IsEmpty()
if the queue is empty
Definition: wb-vector.h:546
void Copy(const Vector< T > &vector)
Copy a vector to another, using &#39;=&#39; to set values.
Definition: wb-vector.h:155
void Clean()
clean the stack. Donot release the memory
Definition: wb-vector.h:391
void Clean()
Clean the array. Just set the top of array to -1 and donot release the memory.
Definition: wb-vector.h:258
VecUnfold(cfg_strWriteAtIter, pFunc->m_aWriteAtIter)
void Push(T p_t)
Push a value into the stack.
Definition: wb-vector.h:393
void Add(Array< T > &a)
Add a array to the tail of current array.
Definition: wb-vector.h:246
double VecDiff(T *pVec1, T *pVec2, int len)
[Vec-function] |v1-v2|
Definition: wb-vector.h:591
int GetNum() const
Get Array number.
Definition: wb-vector.h:240
void Add(T t)
Add a value to the tail of array.
Definition: wb-vector.h:242
Circular queue.
Definition: wb-vector.h:479
~Array()
destructor
Definition: wb-vector.h:220
int m_nBits
bit number of memory size
Definition: wb-vector.h:77
pFunc Reset & m
void Init(int size)
Init the queue.
Definition: wb-vector.h:497
T Top()
Get the Top value of stack.
Definition: wb-vector.h:411
int nHead
the head of queue
Definition: wb-vector.h:485
int m_nTop
the top of the queue
Definition: wb-vector.h:434
void Fill(T m)
set all the values to m
Definition: wb-vector.h:139
int Size() const
get the memory size
Definition: wb-vector.h:95
int m_nTop
Definition: wb-vector.h:384
int m_nXDim
x-dim
Definition: wb-vector.h:359
void BufferOutside(T *&p_pt)
Set the buffer pointer to p_pt, and re-init the vector.
Definition: wb-vector.h:186
Vector(int size=DEFAULE_VECTOR_SIZE)
constructor, do not init the memeory to zero.
Definition: wb-vector.h:80
int m_nYDim
Definition: wb-vector.h:360
void In(T p_t)
Add a value into queue.
Definition: wb-vector.h:445
T GetSum()
Summary all the values if queue.
Definition: wb-vector.h:554
int GetSize()
Get the buffer size of queue.
Definition: wb-vector.h:552
void MemCopy(Vector< T > &vector)
Copy a vector to another, using &#39;memcpy&#39; to set values.
Definition: wb-vector.h:171
T Max(int &idx)
Get the maximum value.
Definition: wb-vector.h:317
double VecNorm(T *pVec, int len)
[Vec-function] sqrt(v*v^T);
Definition: wb-vector.h:571
define all the code written by Bin Wang.
Definition: wb-file.cpp:21
Array(Array &array)
constructor
Definition: wb-vector.h:216
Dynamic array.
Definition: wb-vector.h:205
int GetNum() const
Get the number of the stack.
Definition: wb-vector.h:418
opt Add(wbOPT_STRING, "feat", &cfg_pathFeatStyle, "a feature style file. Set this value will disable -order")
int Compar_Dec(const T &a, const T &b)
comparing function for decrease sort
Definition: wb-vector.h:664
int GetNum()
Return the value number.
Definition: wb-vector.h:466