array.h

粗糙集应用软件

//-------------------------------------------------------------------
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Revisions.....:
//===================================================================

#ifndef __ARRAY_H__
#define __ARRAY_H__

#include <copyright.h>

#include <kernel/basic/types.h>
#include <kernel/basic/string.h>

#include <kernel/system/stdlib.h>

//-------------------------------------------------------------------
// Class.........: Array
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Templatized array/vector that can grow dynamically.
//
// Comments......: Vectors/arrays are in use "everywhere", and STL is
//                 conveniently used for such containers. This
//                 class was developed in order to have complete control
//                 of memory allocation, for two reasons:
//
//                 1) STL sometimes allocates memory in
//                    larger chunks than desired.
//
//                 2) It simplifies a later introduction of
//                    techniques for "memory pooling", which can
//                    significantly reduce memory fragmentation.
//
//                 For reasons of backwards compatibility and
//                 component interchangeability, this class should be
//                 interchangeable with STL vectors under most
//                 circumstances.
//
//                 Currently, this template can only be used for primitive
//                 types or types that provide an empty constructor
//                 (are "default constructable") and an assignment
//                 operator (are "assignable").
//
// Revisions.....:
//===================================================================

template <class T>
class Array {
private:

	//- Internal representation........................................
  T              *elements_; // Buffer of elements.
	int             capacity_; // Physical length of element buffer.
	int             size_;     // Logical length of element buffer.

private:

	//- Helper methods.................................................
	int             GetIndex(const T *position) const;

public:

	//- Constructors/destructor........................................
  Array();
  Array(int size, const T &element);
  Array(const Array<T> &in);
	Array(int size, T *elements, bool copy);
  ~Array();

	//- Dimensional methods............................................
  int             GetSize() const {return size_;}
  bool            IsEmpty() const {return (size_ == 0);}

	//- Common mutation methods........................................
	bool            Clear();

	bool            Insert(int i, const T &element);
	bool            Insert(int i, int n, const T &element);
	bool            Insert(int i, const Array<T> &in);

	bool            Append(const T &element);
	bool            Append(int n, const T &element);
	bool            Append(const Array<T> &in);

	bool            Remove(int i);
	bool            Remove(int i, int j);

	//- Operators......................................................
  const T        &operator[](int i) const {return elements_[i];}
  T              &operator[](int i) {return elements_[i];}

  Array<T>       &operator=(const Array<T> &in);

  friend bool     operator==(const Array<T> &x, const Array<T> &y);
  friend bool     operator!=(const Array<T> &x, const Array<T> &y);

  friend bool     operator<(const Array<T> &x, const Array<T> &y);

	//- Storage methods................................................
	bool            Reserve(int capacity, bool preserve = true);

	//- Creation methods...............................................
	bool            Create(int size, T *elements, bool copy, bool destroy = true);

	//- Types and methods for crude STL compatibility..................
	typedef         T *       iterator;
	typedef         const T * const_iterator;

	iterator        begin() {return elements_;}
	const_iterator  begin() const {return elements_;}
	iterator        end() {return elements_ + size_;}
	const_iterator  end() const {return elements_ + size_;}
	bool            empty() const {return IsEmpty();}
	int             size() const {return size_;}
	void            reserve(int size) {Reserve(size, true);}
	void            push_back(const T &element) {Append(element);}
	void            pop_back() {Remove(size_ - 1, size_);}
	iterator        insert(iterator position, const T &element) {
										int i = GetIndex(position);
										Insert(i, element);
										return elements_ + i;
									}
	void            insert(iterator position, int n, const T &element) {Insert(GetIndex(position), n, element);}
	void            insert(iterator position, iterator first, iterator last) {
										int i = GetIndex(position);
										Array<T> tmp;
										tmp.Create(last - first, first, false, false);
										Insert(i, tmp);
										tmp.Create(0, NULL, false, false);
									}
	void            erase(iterator position) {Remove(GetIndex(position));}
	void            erase(iterator first, iterator last) {Remove(GetIndex(first), GetIndex(last));}

	//- Miscellaneous..................................................
	String          Format() const;

};

//-------------------------------------------------------------------
// Methods for class Vector.
//===================================================================

//-------------------------------------------------------------------
// Method........: GetIndex
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Used for STL compatibility. Given an "iterator",
//                 returns the corresponding index using pointer
//                 arithmetic.
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
inline int Array<T>::GetIndex(const T *position) const {
	return (position - elements_);
}

//-------------------------------------------------------------------
// Method........: Reserve
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......: Consider more optimal reallocation.
// Revisions.....:
//===================================================================

template <class T>
bool Array<T>::Reserve(int capacity, bool preserve) {

	int i;

	// Already enough space reserved?
	if (capacity <= capacity_)
		return true;

	// Allocate new buffer.
	T *elements = new T[capacity];

	// Copy contents of old buffer into new buffer, if specified and possible.
	if (preserve && elements_ != NULL) {
		for (i = 0; i < capacity_; i++) {
			elements[i] = elements_[i];
		}
	}

	// Delete old buffer.
	if (elements_ != NULL)
		delete [] elements_;

	// Reassign internal representation.
	elements_ = elements;
	capacity_ = capacity;

	return true;

}

//-------------------------------------------------------------------
// Method........: Create
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
bool Array<T>::Create(int size, T *elements, bool copy, bool destroy) {

	int i;

	if (destroy && elements_ != NULL)
		delete [] elements_;

	size_     = size;
	capacity_ = size;

	if (!copy) {
		elements_ = elements;
	}
	else {
		if (elements != NULL) {
			elements_ = new T[size];
			for (i = 0; i < size; i++) {
				elements_[i] = elements[i];
			}
		}
		else {
			elements_ = NULL;
		}
	}

	return true;

}

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
Array<T>::Array() {

  elements_ = NULL;
	capacity_ = 0;
	size_     = 0;

}

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
Array<T>::Array(int size, const T &element) {

#if defined(_DEBUG)
	if (size < 0)
		size = -size;
#endif

	// Initialize before allocation.
	elements_ = NULL;
	capacity_ = 0;
	size_     = 0;

	// Allocate buffer.
	Reserve(size, false);

	size_ = size;

	int i;

	// Initialize contents.
	for (i = 0; i < size; i++)
		elements_[i] = element;

}

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
Array<T>::Array(const Array<T> &in) {

	int i;

	capacity_ = in.capacity_;
	size_     = in.size_;

	if (in.elements_ != NULL) {
		elements_ = new T[capacity_];
		for (i = 0; i < capacity_; i++) {
			elements_[i] = in.elements_[i];
		}
	}
	else {
		elements_ = NULL;
	}

}

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
Array<T>::Array(int size, T *elements, bool copy) {

	elements_ = NULL;
	capacity_ = 0;
	size_     = 0;

	if (!Create(size, elements, copy)) {
		elements_ = NULL;
		capacity_ = 0;
		size_     = 0;
	}

}

//-------------------------------------------------------------------
// Method........: Destructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
Array<T>::~Array() {

	if (elements_ != NULL)
		delete [] elements_;

}

//-------------------------------------------------------------------
// Method........: Clear
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

template <class T>
inline bool Array<T>::Clear() {

	if (elements_ != NULL)
		delete [] elements_;

	elements_ = NULL;
	capacity_ = 0;
	size_     = 0;

	return true;

}

//-------------------------------------------------------------------
// Method........: Insert
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Inserts an array at position i.
// Comments......: Consider more optimal reallocation.
// Revisions.....:
//===================================================================

template <class T>
bool Array<T>::Insert(int i, const Array<T> &in) {

	int j;

#if defined(_DEBUG)
	if (i < 0 || i > size_)
		return false;
#endif