SbList.h

#ifndef COIN_SBLIST_H
#define COIN_SBLIST_H
 
/**************************************************************************\
 * Copyright (c) Kongsberg Oil & Gas Technologies AS
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the copyright holder nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\**************************************************************************/
 
#include <cassert>
#include <climits>
#include <cstddef> // NULL definition
#include <new>
#include <Inventor/SbBasic.h> // TRUE/FALSE
 
// We usually implement inline functions below the class definition,
// since we think that makes the file more readable. However, this is
// not done for this class, since Microsoft Visual C++ is not too
// happy about having functions declared as inline for a template
// class.
 
// FIXME: the #pragmas below is just a quick hack to avoid heaps of
// irritating warning messages from the compiler for client code
// compiled under MSVC++. Should try to find the real reason for the
// warnings and fix the cause of the problem instead. 20020730 mortene.
//
// UPDATE 20030617 mortene: there is a Microsoft Knowledge Base
// article at <URL:http://support.microsoft.com> which is related to
// this problem. It's article number KB168958.
//
// In short, the general solution is that classes that exposes usage
// of SbList<type> needs to declare the specific template instance
// with "extern" and __declspec(dllimport/export).
//
// That is a lot of work to change, tho'. Another possibility which
// might be better is to simply avoid using (exposing) SbList from any
// of the other public classes. Judging from a quick look, this seems
// feasible, and just a couple of hours or so of work.
//
#ifdef _MSC_VER // Microsoft Visual C++
#pragma warning(disable:4251)
#pragma warning(disable:4275)
#endif // _MSC_VER
 
template <typename Type>
class SbList {
  // Older compilers aren't too happy about const declarations in the
  // class definitions, so use the enum trick described by Scott
  // Meyers in "Effective C++".
  enum { DEFAULTSIZE = 4 };
 
public:
 
  SbList(const int sizehint = DEFAULTSIZE)
    : itembuffersize(DEFAULTSIZE), numitems(0), itembuffer(builtinbuffer) {
    if (sizehint > DEFAULTSIZE) this->grow(sizehint);
  }
 
  SbList(const SbList<Type> & l)
    : itembuffersize(DEFAULTSIZE), numitems(0), itembuffer(builtinbuffer) {
    this->copy(l);
  }
 
  ~SbList() {
    if (this->itembuffer != builtinbuffer) delete[] this->itembuffer;
  }
 
  void copy(const SbList<Type> & l) {
    if (this == &l) return;
    const int n = l.numitems;
    this->expand(n);
    for (int i = 0; i < n; i++) this->itembuffer[i] = l.itembuffer[i];
  }
 
  SbList <Type> & operator=(const SbList<Type> & l) {
    this->copy(l);
    return *this;
  }
 
  void fit(void) {
    const int items = this->numitems;
 
    if (items < this->itembuffersize) {
      Type * newitembuffer = this->builtinbuffer;
      if (items > DEFAULTSIZE) newitembuffer = new Type[items];
 
      if (newitembuffer != this->itembuffer) {
        try {
          for (int i = 0; i < items; i++) newitembuffer[i] = this->itembuffer[i];
        }
        catch (...) {
          if (newitembuffer != this->builtinbuffer) delete[] newitembuffer;
          throw;
        }
      }
 
      if (this->itembuffer != this->builtinbuffer) delete[] this->itembuffer;
      this->itembuffer = newitembuffer;
      this->itembuffersize = items > DEFAULTSIZE ? items : DEFAULTSIZE;
    }
  }
 
  void append(const Type item) {
    if (this->numitems == this->itembuffersize) this->grow();
    this->itembuffer[this->numitems++] = item;
  }
 
  int find(const Type item) const {
    for (int i = 0; i < this->numitems; i++)
      if (this->itembuffer[i] == item) return i;
    return -1;
  }
 
  void insert(const Type item, const int insertbefore) {
#ifdef COIN_EXTRA_DEBUG
    assert(insertbefore >= 0 && insertbefore <= this->numitems);
#endif // COIN_EXTRA_DEBUG
    if (this->numitems == this->itembuffersize) this->grow();
 
    for (int i = this->numitems; i > insertbefore; i--)
      this->itembuffer[i] = this->itembuffer[i-1];
    this->itembuffer[insertbefore] = item;
    this->numitems++;
  }
 
  void removeItem(const Type item) {
    int idx = this->find(item);
#ifdef COIN_EXTRA_DEBUG
    assert(idx != -1);
#endif // COIN_EXTRA_DEBUG
    if (idx >= 0) this->remove(idx);
  }
 
  void remove(const int index) {
#ifdef COIN_EXTRA_DEBUG
    assert(index >= 0 && index < this->numitems);
#endif // COIN_EXTRA_DEBUG
    this->numitems--;
    for (int i = index; i < this->numitems; i++)
      this->itembuffer[i] = this->itembuffer[i + 1];
  }
 
  void removeFast(const int index) {
#ifdef COIN_EXTRA_DEBUG
    assert(index >= 0 && index < this->numitems);
#endif // COIN_EXTRA_DEBUG
    this->itembuffer[index] = this->itembuffer[--this->numitems];
  }
 
  int getLength(void) const {
    return this->numitems;
  }
 
  void truncate(const int length, const int dofit = 0) {
#ifdef COIN_EXTRA_DEBUG
    assert(length <= this->numitems);
#endif // COIN_EXTRA_DEBUG
    this->numitems = length;
    if (dofit) this->fit();
  }
 
  void push(const Type item) {
    this->append(item);
  }
 
  Type pop(void) {
#ifdef COIN_EXTRA_DEBUG
    assert(this->numitems > 0);
#endif // COIN_EXTRA_DEBUG
    return this->itembuffer[--this->numitems];
  }
 
  const Type * getArrayPtr(const int start = 0) const {
    return &this->itembuffer[start];
  }
 
  Type operator[](const int index) const {
#ifdef COIN_EXTRA_DEBUG
    assert(index >= 0 && index < this->numitems);
#endif // COIN_EXTRA_DEBUG
    return this->itembuffer[index];
  }
 
  Type & operator[](const int index) {
#ifdef COIN_EXTRA_DEBUG
    assert(index >= 0 && index < this->numitems);
#endif // COIN_EXTRA_DEBUG
    return this->itembuffer[index];
  }
 
  int operator==(const SbList<Type> & l) const {
    if (this == &l) return TRUE;
    if (this->numitems != l.numitems) return FALSE;
    for (int i = 0; i < this->numitems; i++)
      if (this->itembuffer[i] != l.itembuffer[i]) return FALSE;
    return TRUE;
  }
 
  int operator!=(const SbList<Type> & l) const {
    return !(*this == l);
  }
 
  void ensureCapacity(const int size) {
    if ((size > itembuffersize) &&
        (size > DEFAULTSIZE)) {
      this->grow(size);
    }
  }
 
protected:
 
  void expand(const int size) {
    this->grow(size);
    this->numitems = size;
  }
 
  int getArraySize(void) const {
    return this->itembuffersize;
  }
 
private:
  void grow(const int size = -1) {
    // Default growth doubles the current capacity. Check before the
    // multiplication to avoid signed overflow.
    int newsize;
    if (size == -1) {
      if (this->itembuffersize > INT_MAX / 2) throw std::bad_alloc();
      newsize = this->itembuffersize * 2;
    }
    else if (size <= this->itembuffersize) return;
    else { newsize = size; }
 
    Type * newbuffer = new Type[newsize];
    const int n = this->numitems;
    try {
      for (int i = 0; i < n; i++) newbuffer[i] = this->itembuffer[i];
    }
    catch (...) {
      delete[] newbuffer;
      throw;
    }
    if (this->itembuffer != this->builtinbuffer) delete[] this->itembuffer;
    this->itembuffer = newbuffer;
    this->itembuffersize = newsize;
  }
 
  int itembuffersize;
  int numitems;
  Type * itembuffer;
  Type builtinbuffer[DEFAULTSIZE];
};
 
#endif // !COIN_SBLIST_H