List.h

Go to the documentation of this file.

/*
 * Copyright (C) 2006-2011, SRI International (R)
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#pragma once

#ifndef __OpenKarto_List_h__
#define __OpenKarto_List_h__

#include <OpenKarto/Exception.h>
#include <OpenKarto/Math.h>
#include <OpenKarto/StringHelper.h>

namespace karto
{




  template<class T>
  class ConstListIterator;

  template<class T>
  class ListIterator;

  template<class T>
  class List
  {
  public:
    typedef ConstListIterator<T> ConstIterator;
    
    typedef ListIterator<T> Iterator;
    
    List()
      : m_pElements(NULL)
    {
      Reset();
    }
    
    List(kt_size_t size)
      : m_pElements(NULL)
    {
      Reset();
      Resize(size);
    }
    
    List(const List& rOther)
      : m_pElements(NULL)
    {
      Reset();
      Resize(rOther.m_Size);
      
      for (kt_size_t i = 0; i < m_Size; i++)
      {
        m_pElements[i] = rOther.m_pElements[i];
      }
    }
    
    virtual ~List()
    {
      Reset();
    }
    
  public:
    virtual void Add(const T& rValue)
    {
      // resize
      if (m_Size == m_Capacity)
      {
        EnsureCapacity(m_Capacity * 2 + 1); // +1 in case capacity is 0
      }
      m_pElements[m_Size] = rValue;
      m_Size++;
    }
    
    virtual void Add(const List& rValue)
    {
      kt_size_t combinedSize = m_Size + rValue.m_Size;
      if (m_Capacity < combinedSize)
      {
        EnsureCapacity(combinedSize);    
      }
      
      for (kt_size_t i = 0; i < rValue.m_Size; i++)
      {
        m_pElements[m_Size + i] = rValue.m_pElements[i];
      }
      
      m_Size = combinedSize;
    }
    
    virtual kt_bool Remove(const T& rValue) 
    {
      for (kt_size_t i = 0; i < m_Size; i++)
      {
        if (m_pElements[i] == rValue)
        {
          RemoveAt(i);
          return true;
        }
      }
      
      return false;
    }
    
    virtual void RemoveAt(kt_size_t index) 
    {
      if (index >= m_Size)
      {
        String message;
        message.Append("Cannot remove item: invalid index: ");
        message.Append(StringHelper::ToString(index));
        
        throw Exception(message);
      }
      
      if (m_Size > 0)
      {
        // move remaining elements
        for (kt_size_t i = index; i < m_Size - 1; i++)
        {
          m_pElements[i] = m_pElements[i + 1];
        }

        // destroy last element by calling its destructor
        m_pElements[m_Size - 1].~T();

        m_Size--;
      }
    }

    virtual kt_bool Contains(const T& rValue) const
    {
      for (kt_size_t i = 0; i < m_Size; i++)
      {
        if (m_pElements[i] == rValue)
        {
          return true;
        }
      }
      
      return false;
    }
    
    inline virtual kt_size_t Size() const
    {
      return m_Size;
    }
    
    inline virtual kt_bool IsEmpty() const
    {
      return m_Size == 0;
    }
    
    virtual void Clear()
    {
      if (m_Size > 0)
      {
        // call destructor on each element 
        for (kt_size_t i = 0; i < m_Size; i++)
        {
          m_pElements[i].~T();
        }
      }
      
      m_Size = 0;
    }
    
    inline virtual T& Get(kt_size_t index)
    {
      return (*this)[index];
    }
    
    inline virtual const T& Get(kt_size_t index) const
    {
      return (*this)[index];
    }
    
    inline T* Find(const T& rValue) 
    {
      for (kt_size_t i = 0; i < m_Size; i++)
      {
        if (m_pElements[i] == rValue)
        {
          return &m_pElements[i];
        }
      }
      
      return NULL;
    }
    
    void Set(kt_size_t index, const T& rValue)
    {
      if (index >= m_Size)
      {
        assert(false); 
      }
      
      m_pElements[index] = rValue;
    }
    
    virtual const T& Front() const
    {
      if (m_Size == 0)
      {
        assert(false);
        throw Exception("List is empty!");
      }
      
      return Get(0);
    }
    
    virtual const T& Back() const
    {
      if (m_Size == 0)
      {
        assert(false);
        throw Exception("List is empty!");
      }
      
      return Get(Size() - 1);
    }
    
    virtual void Resize(kt_size_t newSize)
    {
      if (newSize != m_Size)
      {
        T* pElements = new T[newSize];
        if (m_pElements != NULL)
        {
          kt_size_t smallerSize = karto::math::Minimum(newSize, m_Size);

          for (kt_size_t i = 0; i < smallerSize; i++)
          {
            pElements[i] = m_pElements[i];
          }

          delete [] m_pElements;
        }

        m_pElements = pElements;
        m_Size = newSize;
        m_Capacity = newSize;
      }
    }
    
    void EnsureCapacity(kt_size_t newCapacity)
    {
      kt_size_t oldSize = m_Size;
      Resize(newCapacity);
      if (newCapacity > oldSize)
      {
        m_Size = oldSize;
      }
    }    
    
    inline kt_int32s BinarySearch(const T& rValue, kt_int32s (*f)(const T& a, const T& b))
    {
      assert(m_Size > 0);

      kt_int32s lo = 0;
      kt_int32s hi = static_cast<kt_int32s>(m_Size) - 1;
      
      while (lo <= hi)
      {
        kt_int32s mid = (lo + hi) / 2;
        kt_int32s comparison = f(m_pElements[mid], rValue);
        if (comparison == 0)
        {
          return mid;
        }
        else if (comparison < 0)
        {
          lo = mid + 1;
        }
        else // comparison > 0
        {
          hi = mid - 1;
        }
      }
      
      return -1;
    }

  public:
    inline T& operator[](kt_size_t index)
    {
      if (index >= m_Size)
      {
        assert(false); 
        throw Exception("Out of bounds exception: " + StringHelper::ToString(index) + " (>= " + StringHelper::ToString(m_Size) + ")");
      }
      
      return m_pElements[index];
    }
    
    inline const T& operator[](kt_size_t index) const
    {
      if (index >= m_Size)
      {
        assert(false);
        throw Exception("Out of bounds exception: " + StringHelper::ToString(index) + " (>= " + StringHelper::ToString(m_Size) + ")");
      }
      
      return m_pElements[index];
    }
    
    List& operator=(const List& rOther)
    {
      if (&rOther != this)
      {
        Reset();
        Resize(rOther.m_Size);
        for (kt_size_t i = 0; i < rOther.m_Size; i++)
        {
          m_pElements[i] = rOther.m_pElements[i];
        }
      }
      
      return *this;
    }
    
    kt_bool operator==(const List& rOther) const
    {
      if (Size() != rOther.Size())
      {
        return false;
      }
      
      for (kt_size_t i = 0; i < rOther.m_Size; i++)
      {
        if (m_pElements[i] != rOther.m_pElements[i])
        {
          return false;
        }
      }
      
      return true;
    }
    
  private:
    void Reset()
    {
      delete [] m_pElements;
      m_pElements = NULL;
      m_Size = 0;
      m_Capacity = 0;
    }
    
  public:
    virtual ConstListIterator<T> GetConstIterator() const
    {
      return ConstListIterator<T>(this);
    }

    virtual ListIterator<T> GetIterator()
    {
      return ListIterator<T>(this);
    }
    
  private:
    T* m_pElements;
    kt_size_t m_Size;
    kt_size_t m_Capacity;
  }; // class List<T>
  

  template<class T>
  class ConstListIterator
  {
  public:
    ConstListIterator(const List<T>* pList)
      : m_pList(pList)
      , m_Index(0)
    {
      if (pList == NULL)
      {
        throw Exception("Cannot create iterator: List is NULL");
      }
    }

    virtual kt_bool HasNext() const
    {
      return m_Index < m_pList->Size();
    }
    
    virtual const T& Next()
    {
      if (m_Index < m_pList->Size())
      {
        m_Index++;
        return m_pList->Get(m_Index - 1);
      }

      throw Exception("Cannot increment iterator: No more items in iterator.");
    }
    
    virtual const T& operator*() const
    {
      if (m_Index < m_pList->Size())
      {
        return m_pList->Get(m_Index);
      }

      throw Exception("Cannot dereference iterator: No more items in iterator.");
    }
    
    virtual const T* operator->() const
    {
      if (m_Index < m_pList->Size())
      {
        return &m_pList->Get(m_Index);
      }
      
      throw Exception("Cannot dereference iterator: No more items in iterator.");      
    }
    
    virtual const T& operator++()
    {
      Next();
      ConstListIterator iter = *this;
      return *iter;
    }
    
    virtual T operator++(int /*dummy*/)
    {
      return Next();
    }
    
    virtual const ConstListIterator& operator=(const ConstListIterator& rOther)
    {
      m_pList = rOther.m_pList;
      m_Index = rOther.m_Index;
      return *this;
    }
    
    virtual kt_bool operator!=(const ConstListIterator& rOther) const
    {
      if (m_pList != rOther.m_pList)
      {
        throw Exception("Iterators are not operating on the same list");
      }
      
      return m_Index != rOther.m_Index;
    }
    
  private:
    const List<T>* m_pList;
    kt_size_t m_Index;
  }; // class ConstIterator<T>


  template<class T>
  class ListIterator
  {
  public:
    ListIterator(List<T>* pList)
    : m_pList(pList)
    , m_Index(0)
    {
      if (pList == NULL)
      {
        throw Exception("Cannot create iterator: List is NULL");
      }
    }
    
    virtual kt_bool HasNext() const
    {
      return m_Index < m_pList->Size();
    }
    
    virtual T& Next()
    {
      if (m_Index < m_pList->Size())
      {
        m_Index++;
        return m_pList->Get(m_Index - 1);
      }
      
      throw Exception("Cannot increment iterator: No more items in iterator.");
    }
    
    void Erase()
    {
      if (m_Index < m_pList->Size())
      {
        m_pList->RemoveAt(m_Index);
      }
      
      throw Exception("Cannot erase item: No more items in iterator.");      
    }
    
    virtual T& operator*() const
    {
      if (m_Index < m_pList->Size())
      {
        return m_pList->Get(m_Index);
      }
      
      throw Exception("Cannot dereference iterator: No more items in iterator.");
    }
    
    virtual T* operator->() const
    {
      if (m_Index < m_pList->Size())
      {
        return &m_pList->Get(m_Index);
      }
      
      throw Exception("Cannot dereference iterator: No more items in iterator.");      
    }
    
    virtual const T& operator++()
    {
      Next();
      ListIterator iter = *this;
      return *iter;
    }
    
    virtual T operator++(int /*dummy*/)
    {
      return Next();
    }
    
    virtual const ListIterator& operator=(const ListIterator& rOther)
    {
      m_pList = rOther.m_pList;
      m_Index = rOther.m_Index;
      return *this;
    }
    
    virtual kt_bool operator!=(const ListIterator& rOther) const
    {
      if (m_pList != rOther.m_pList)
      {
        throw Exception("Iterators are not operating on the same list");
      }
      
      return m_Index != rOther.m_Index;
    }
    
  private:
    List<T>* m_pList;
    kt_size_t m_Index;
  }; // class Iterator<T>

}

#endif // __OpenKarto_List_h__