[Scummvm-cvs-logs] CVS: scummvm/common array.h,NONE,1.1 list.h,1.13,1.14 config-manager.h,1.15,1.16 str.h,1.20,1.21
Max Horn
fingolfin at users.sourceforge.net
Fri Apr 9 08:24:13 CEST 2004
Update of /cvsroot/scummvm/scummvm/common
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv9458/common
Modified Files:
list.h config-manager.h str.h
Added Files:
array.h
Log Message:
Renamed template class 'List' to 'Array', since that is really what it is (a resizable array, not a linked list)
--- NEW FILE: array.h ---
/* ScummVM - Scumm Interpreter
* Copyright (C) 2002-2004 The ScummVM project
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
* $Header: /cvsroot/scummvm/scummvm/common/array.h,v 1.1 2004/04/09 15:10:21 fingolfin Exp $
*/
#ifndef COMMON_ARRAY_H
#define COMMON_ARRAY_H
#include "common/scummsys.h"
#include <assert.h>
namespace Common {
template <class T>
class Array {
protected:
int _capacity;
int _size;
T *_data;
public:
typedef T *iterator;
typedef const T *const_iterator;
public:
Array<T>() : _capacity(0), _size(0), _data(0) {}
Array<T>(const Array<T>& array) : _capacity(0), _size(0), _data(0) {
_size = array._size;
_capacity = _size + 32;
_data = new T[_capacity];
for (int i = 0; i < _size; i++)
_data[i] = array._data[i];
}
~Array<T>() {
if (_data)
delete [] _data;
}
void push_back(const T& element) {
ensureCapacity(_size + 1);
_data[_size++] = element;
}
void push_back(const Array<T>& array) {
ensureCapacity(_size + array._size);
for (int i = 0; i < array._size; i++)
_data[_size++] = array._data[i];
}
void insert_at(int idx, const T& element) {
assert(idx >= 0 && idx <= _size);
ensureCapacity(_size + 1);
// The following loop is not efficient if you can just memcpy things around.
// e.g. if you have a list of ints. But for real objects (String...), memcpy
// usually isn't correct (specifically, for any class which has a non-default
// copy behaviour. E.g. the String class uses a refCounter which has to be
// updated whenever a String is copied.
for (int i = _size; i > idx; i--) {
_data[i] = _data[i-1];
}
_data[idx] = element;
_size++;
}
T& remove_at(int idx) {
T& tmp;
assert(idx >= 0 && idx < _size);
tmp = _data[idx];
for (int i = idx; i < _size - 1; i++)
_data[i] = _data[i+1];
_size--;
return tmp;
}
// TODO: insert, remove, ...
T& operator [](int idx) {
assert(idx >= 0 && idx < _size);
return _data[idx];
}
const T& operator [](int idx) const {
assert(idx >= 0 && idx < _size);
return _data[idx];
}
Array<T>& operator =(const Array<T>& array) {
if (_data)
delete [] _data;
_size = array._size;
_capacity = _size + 32;
_data = new T[_capacity];
for (int i = 0; i < _size; i++)
_data[i] = array._data[i];
return *this;
}
uint size() const {
return _size;
}
void clear() {
if (_data) {
delete [] _data;
_data = 0;
}
_size = 0;
_capacity = 0;
}
bool isEmpty() const {
return (_size == 0);
}
iterator begin() {
return _data;
}
iterator end() {
return _data + _size;
}
const_iterator begin() const {
return _data;
}
const_iterator end() const {
return _data + _size;
}
protected:
void ensureCapacity(int new_len) {
if (new_len <= _capacity)
return;
T *old_data = _data;
_capacity = new_len + 32;
_data = new T[_capacity];
if (old_data) {
// Copy old data
for (int i = 0; i < _size; i++)
_data[i] = old_data[i];
delete [] old_data;
}
}
};
} // End of namespace Common
#endif
Index: list.h
===================================================================
RCS file: /cvsroot/scummvm/scummvm/common/list.h,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- list.h 15 Mar 2004 02:45:40 -0000 1.13
+++ list.h 9 Apr 2004 15:10:22 -0000 1.14
@@ -26,25 +26,48 @@
namespace Common {
+/*
+TODO: Add a true list class, based on a linked list data structure
+
template <class T>
class List {
protected:
- int _capacity;
- int _size;
- T *_data;
+ template <class T>
+ class Node {
+ Node<T> *_prev;
+ Node<T> *_next;
+ T _data;
+ }
+
+ template <class T>
+ class Iterator {
+ friend class List<T>;
+ private:
+ Node<T> *_node;
+
+ public:
+ Node<T> &operator++() {
+ _node = _node->_next;
+ }
+
+ T& operator*() const {
+ return _node->_data;
+ }
+ T* operator->() const {
+ return &(_node->_data);
+ }
+ };
+
+ Iterator<T> *_anchor;
public:
- typedef T *iterator;
- typedef const T *const_iterator;
+ typedef Node<T> *iterator;
+ typedef const Node<T> *const_iterator;
public:
- List<T>() : _capacity(0), _size(0), _data(0) {}
- List<T>(const List<T>& list) : _capacity(0), _size(0), _data(0) {
- _size = list._size;
- _capacity = _size + 32;
- _data = new T[_capacity];
- for (int i = 0; i < _size; i++)
- _data[i] = list._data[i];
+ List<T>() : _anchor(...) {}
+ List<T>(const List<T>& list) : _anchor(...) {
+ ... copy list ...
}
~List<T>() {
@@ -53,117 +76,75 @@
}
void push_back(const T& element) {
- ensureCapacity(_size + 1);
- _data[_size++] = element;
+ ...
}
void push_back(const List<T>& list) {
- ensureCapacity(_size + list._size);
- for (int i = 0; i < list._size; i++)
- _data[_size++] = list._data[i];
+ ...
}
- void insert_at(int idx, const T& element) {
- assert(idx >= 0 && idx <= _size);
- ensureCapacity(_size + 1);
- // The following loop is not efficient if you can just memcpy things around.
- // e.g. if you have a list of ints. But for real objects (String...), memcpy
- // usually isn't correct (specifically, for any class which has a non-default
- // copy behaviour. E.g. the String class uses a refCounter which has to be
- // updated whenever a String is copied.
- for (int i = _size; i > idx; i--) {
- _data[i] = _data[i-1];
- }
- _data[idx] = element;
- _size++;
+ void insert(iterator pos, const T& element) {
+ ...
}
- T& remove_at(int idx) {
- T& tmp;
-
- assert(idx >= 0 && idx < _size);
- tmp = _data[idx];
- for (int i = idx; i < _size - 1; i++)
- _data[i] = _data[i+1];
- _size--;
- return tmp;
+ void insert(iterator pos, iterator beg, Iterator end) {
+ ...
}
- // TODO: insert, remove, ...
-
- T& operator [](int idx) {
- assert(idx >= 0 && idx < _size);
- return _data[idx];
+ void erase(iterator beg, Iterator end) {
+ ...
}
- const T& operator [](int idx) const {
- assert(idx >= 0 && idx < _size);
- return _data[idx];
+ void remove(const T &val) {
}
- List<T>& operator =(const List<T>& list) {
- if (_data)
- delete [] _data;
- _size = list._size;
- _capacity = _size + 32;
- _data = new T[_capacity];
- for (int i = 0; i < _size; i++)
- _data[i] = list._data[i];
- return *this;
+ List<T>& operator =(const List<T>& list) {
+ // Careful here: handle self-assignment properly! I.e. situations like
+ // List x;
+ // ...
+ // x = x;
+ // In particular, we can't just do this:
+ // clear();
+ // insert(_first, list.begin(), list.end());
+ ...
}
uint size() const {
- return _size;
+ int size = 0;
+ for (const_iterator i = begin(); i != end(); ++i)
+ size++;
+ return size;
}
void clear() {
- if (_data) {
- delete [] _data;
- _data = 0;
- }
- _size = 0;
- _capacity = 0;
+ erase(begin(), end());
}
bool isEmpty() const {
- return (_size == 0);
+ return (_anchor._node == _anchor._node._next);
}
iterator begin() {
- return _data;
+ Iterator iter = _anchor;
+ return ++iter;
}
iterator end() {
- return _data + _size;
+ return _anchor;
}
const_iterator begin() const {
- return _data;
+ Iterator iter = _anchor;
+ return ++iter;
}
const_iterator end() const {
- return _data + _size;
- }
-
-protected:
- void ensureCapacity(int new_len) {
- if (new_len <= _capacity)
- return;
-
- T *old_data = _data;
- _capacity = new_len + 32;
- _data = new T[_capacity];
-
- if (old_data) {
- // Copy old data
- for (int i = 0; i < _size; i++)
- _data[i] = old_data[i];
- delete [] old_data;
- }
+ return _anchor;
}
};
+*/
} // End of namespace Common
Index: config-manager.h
===================================================================
RCS file: /cvsroot/scummvm/scummvm/common/config-manager.h,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- config-manager.h 29 Mar 2004 19:15:22 -0000 1.15
+++ config-manager.h 9 Apr 2004 15:10:22 -0000 1.16
@@ -23,7 +23,7 @@
#ifndef COMMON_CONFIG_H
#define COMMON_CONFIG_H
-#include "common/list.h"
+#include "common/array.h"
#include "common/map.h"
#include "common/singleton.h"
#include "common/str.h"
@@ -127,7 +127,7 @@
DomainMap _globalDomains;
Domain _defaultsDomain;
- List<Domain *> _searchOrder;
+ Array<Domain *> _searchOrder;
String _activeDomain;
String _filename;
Index: str.h
===================================================================
RCS file: /cvsroot/scummvm/scummvm/common/str.h,v
retrieving revision 1.20
retrieving revision 1.21
diff -u -d -r1.20 -r1.21
--- str.h 5 Feb 2004 00:19:54 -0000 1.20
+++ str.h 9 Apr 2004 15:10:22 -0000 1.21
@@ -22,7 +22,7 @@
#define COMMON_STRING_H
#include "common/scummsys.h"
-#include "common/list.h"
+#include "common/array.h"
#include <assert.h>
#include <string.h>
@@ -126,7 +126,7 @@
bool operator == (const char *x, const ConstString &y);
bool operator != (const char *x, const ConstString &y);
-class StringList : public List<String> {
+class StringList : public Array<String> {
public:
void push_back(const char *str) {
ensureCapacity(_size + 1);
More information about the Scummvm-git-logs
mailing list