fixed eol-style
authorspog <spog>
Tue, 21 Feb 2006 22:18:44 +0000 (22:18 +0000)
committerspog <spog>
Tue, 21 Feb 2006 22:18:44 +0000 (22:18 +0000)
git-svn-id: svn://svn.icculus.org/gtkradiant/GtkRadiant/trunk@23 8a3a26a2-13c4-0310-b231-cf6edde360e5

libs/container/stack.h

index 85b3d07..d83674c 100644 (file)
-/*\r
-Copyright (C) 2001-2006, William Joseph.\r
-All Rights Reserved.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
-*/\r
-\r
-#if !defined(INCLUDED_CONTAINER_STACK_H)\r
-#define INCLUDED_CONTAINER_STACK_H\r
-\r
-#include "memory/allocator.h"\r
-#include <algorithm>\r
-\r
-/// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.\r
-///\r
-/// - Pushing or popping elements is a constant-time operation (on average).\r
-/// - The storage capacity of the stack will grow when a new element is added beyond the current capacity. Iterators are invalidated when the storage capacity grows.\r
-/// - DefaultConstructible, Copyable, Assignable.\r
-/// - Compatible with the containers and algorithms in the Standard Template Library (STL) - http://www.sgi.com/tech/stl/\r
-///\r
-/// \param Type: The type to be stored in the stack. Must provide a copy-constructor.\r
-template<typename Type>\r
-class Stack : public DefaultAllocator<Type>\r
-{\r
-  typedef DefaultAllocator<Type> Allocator;\r
-\r
-  enum\r
-  {\r
-    DEFAULT_CAPACITY = 4,\r
-  };\r
-\r
-  typedef Type* pointer;\r
-  typedef const Type* const_pointer;\r
-\r
-public:\r
-  typedef const_pointer const_iterator;\r
-private:\r
-\r
-  pointer m_data;\r
-  pointer m_end;\r
-  std::size_t m_capacity;\r
-\r
-\r
-  void insert(const Type& value)\r
-  {\r
-    Allocator::construct(m_end++, value);\r
-  }\r
-  void insert_overflow(const Type& value)\r
-  {\r
-    const std::size_t new_capacity = (m_capacity) ? m_capacity + m_capacity : std::size_t(DEFAULT_CAPACITY);\r
-    const pointer new_data = Allocator::allocate(new_capacity);\r
-    const pointer new_end = std::copy(m_data, m_end, new_data);\r
-\r
-    destroy();\r
-    Allocator::deallocate(m_data, m_capacity);\r
-\r
-    m_capacity = new_capacity;\r
-    m_data = new_data;\r
-    m_end = new_end;\r
-    insert(value); \r
-  }\r
-  void destroy()\r
-  {\r
-    for(pointer p = m_data; p != m_end; ++p)\r
-    {\r
-      Allocator::destroy(p);\r
-    }\r
-  }\r
-  void construct(const Stack& other)\r
-  {\r
-    pointer p = m_data;\r
-    for(const_iterator i = other.begin(); i != other.end(); ++i)\r
-    {\r
-      Allocator::construct(p++, *i);\r
-    }\r
-  }\r
-\r
-public:\r
-\r
-  Stack() :\r
-    m_data(0),\r
-    m_end(0),\r
-    m_capacity(0)\r
-  {\r
-  }\r
-  Stack(const Type& value) :\r
-    m_data(0),\r
-    m_end(0),\r
-    m_capacity(0)\r
-  {\r
-    push(value);\r
-  }\r
-  Stack(const Stack& other) :\r
-    DefaultAllocator<Type>(other)\r
-  {\r
-    m_capacity = other.m_capacity;\r
-    m_data = Allocator::allocate(m_capacity);\r
-    construct(other);\r
-    m_end = m_data + other.size();\r
-  }\r
-  ~Stack()\r
-  {\r
-    destroy();\r
-    Allocator::deallocate(m_data, m_capacity);\r
-  }\r
-\r
-  const_iterator begin() const\r
-  {\r
-    return m_data;\r
-  }\r
-  const_iterator end() const\r
-  {\r
-    return m_end;\r
-  }\r
-\r
-  bool empty() const\r
-  {\r
-    return end() == begin();\r
-  }\r
-  void clear()\r
-  {\r
-    destroy();\r
-    m_end = m_data;\r
-  }\r
-\r
-  std::size_t size() const\r
-  {\r
-    return m_end - m_data;\r
-  }\r
-  Type operator[](const std::size_t i) const\r
-  {\r
-    return m_data[i];\r
-  }\r
-  /// \brief Pushes \p value onto the stack at the top element. If reserved storage is insufficient for the new element, this will invalidate all iterators.\r
-  void push(const Type& value)\r
-  {\r
-    if(size() == m_capacity)\r
-    {\r
-      insert_overflow(value);\r
-    }\r
-    else\r
-    {\r
-      insert(value);\r
-    }\r
-  }\r
-  /// \brief Removes the top element of the stack.\r
-  void pop()\r
-  {\r
-    Allocator::destroy(--m_end);\r
-  }\r
-  /// \brief Returns the top element of the mutable stack.\r
-  Type& top()\r
-  {\r
-    return *(m_end-1);\r
-  }\r
-  /// \brief Returns the top element of the non-mutable stack.\r
-  const Type& top() const\r
-  {\r
-    return *(m_end-1);\r
-  }\r
-  /// \brief Returns the element below the top element of the mutable stack.\r
-  Type& parent()\r
-  {\r
-    return *(m_end-2);\r
-  }\r
-  /// \brief Returns the element below the top element of the non-mutable stack.\r
-  const Type& parent() const\r
-  {\r
-    return *(m_end-2);\r
-  }\r
-  /// \brief Swaps the values of this stack and \p other.\r
-  void swap(Stack& other)\r
-  {\r
-    std::swap(m_data, other.m_data);\r
-    std::swap(m_end, other.m_end);\r
-    std::swap(m_capacity, other.m_capacity);\r
-  }\r
-#if 1 // use copy-swap technique\r
-  Stack& operator=(const Stack& other)\r
-  {\r
-    Stack temp(other);\r
-    temp.swap(*this);\r
-    return *this;\r
-  }\r
-#else // avoids memory allocation if capacity is already sufficient.\r
-  Stack& operator=(const Stack& other)\r
-  {\r
-    if(&other != this)\r
-    {\r
-      destroy();\r
-\r
-      if(other.size() > m_capacity)\r
-      {\r
-        Allocator::deallocate(m_data, m_capacity);\r
-        m_capacity = other.m_capacity;\r
-        m_data = Allocator::allocate(m_capacity);\r
-      }\r
-      m_end = m_data + other.size();\r
-\r
-      construct(other);\r
-    }\r
-    return *this;\r
-  }\r
-#endif\r
-};\r
-\r
-/// \brief Returns true if \p self is lexicographically less than \p other.\r
-template<typename Type>\r
-inline bool operator<(const Stack<Type>& self, const Stack<Type>& other)\r
-{\r
-  return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end());\r
-}\r
-\r
-namespace std\r
-{\r
-  /// \brief Swaps the values of \p self and \p other.\r
-  /// Overloads std::swap().\r
-  template<typename Type>\r
-  inline void swap(Stack<Type>& self, Stack<Type>& other)\r
-  {\r
-    self.swap(other);\r
-  }\r
-}\r
-\r
-#endif\r
+/*
+Copyright (C) 2001-2006, William Joseph.
+All Rights Reserved.
+
+This file is part of GtkRadiant.
+
+GtkRadiant 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.
+
+GtkRadiant 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 GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+*/
+
+#if !defined(INCLUDED_CONTAINER_STACK_H)
+#define INCLUDED_CONTAINER_STACK_H
+
+#include "memory/allocator.h"
+#include <algorithm>
+
+/// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.
+///
+/// - Pushing or popping elements is a constant-time operation (on average).
+/// - The storage capacity of the stack will grow when a new element is added beyond the current capacity. Iterators are invalidated when the storage capacity grows.
+/// - DefaultConstructible, Copyable, Assignable.
+/// - Compatible with the containers and algorithms in the Standard Template Library (STL) - http://www.sgi.com/tech/stl/
+///
+/// \param Type: The type to be stored in the stack. Must provide a copy-constructor.
+template<typename Type>
+class Stack : public DefaultAllocator<Type>
+{
+  typedef DefaultAllocator<Type> Allocator;
+
+  enum
+  {
+    DEFAULT_CAPACITY = 4,
+  };
+
+  typedef Type* pointer;
+  typedef const Type* const_pointer;
+
+public:
+  typedef const_pointer const_iterator;
+private:
+
+  pointer m_data;
+  pointer m_end;
+  std::size_t m_capacity;
+
+
+  void insert(const Type& value)
+  {
+    Allocator::construct(m_end++, value);
+  }
+  void insert_overflow(const Type& value)
+  {
+    const std::size_t new_capacity = (m_capacity) ? m_capacity + m_capacity : std::size_t(DEFAULT_CAPACITY);
+    const pointer new_data = Allocator::allocate(new_capacity);
+    const pointer new_end = std::copy(m_data, m_end, new_data);
+
+    destroy();
+    Allocator::deallocate(m_data, m_capacity);
+
+    m_capacity = new_capacity;
+    m_data = new_data;
+    m_end = new_end;
+    insert(value); 
+  }
+  void destroy()
+  {
+    for(pointer p = m_data; p != m_end; ++p)
+    {
+      Allocator::destroy(p);
+    }
+  }
+  void construct(const Stack& other)
+  {
+    pointer p = m_data;
+    for(const_iterator i = other.begin(); i != other.end(); ++i)
+    {
+      Allocator::construct(p++, *i);
+    }
+  }
+
+public:
+
+  Stack() :
+    m_data(0),
+    m_end(0),
+    m_capacity(0)
+  {
+  }
+  Stack(const Type& value) :
+    m_data(0),
+    m_end(0),
+    m_capacity(0)
+  {
+    push(value);
+  }
+  Stack(const Stack& other) :
+    DefaultAllocator<Type>(other)
+  {
+    m_capacity = other.m_capacity;
+    m_data = Allocator::allocate(m_capacity);
+    construct(other);
+    m_end = m_data + other.size();
+  }
+  ~Stack()
+  {
+    destroy();
+    Allocator::deallocate(m_data, m_capacity);
+  }
+
+  const_iterator begin() const
+  {
+    return m_data;
+  }
+  const_iterator end() const
+  {
+    return m_end;
+  }
+
+  bool empty() const
+  {
+    return end() == begin();
+  }
+  void clear()
+  {
+    destroy();
+    m_end = m_data;
+  }
+
+  std::size_t size() const
+  {
+    return m_end - m_data;
+  }
+  Type operator[](const std::size_t i) const
+  {
+    return m_data[i];
+  }
+  /// \brief Pushes \p value onto the stack at the top element. If reserved storage is insufficient for the new element, this will invalidate all iterators.
+  void push(const Type& value)
+  {
+    if(size() == m_capacity)
+    {
+      insert_overflow(value);
+    }
+    else
+    {
+      insert(value);
+    }
+  }
+  /// \brief Removes the top element of the stack.
+  void pop()
+  {
+    Allocator::destroy(--m_end);
+  }
+  /// \brief Returns the top element of the mutable stack.
+  Type& top()
+  {
+    return *(m_end-1);
+  }
+  /// \brief Returns the top element of the non-mutable stack.
+  const Type& top() const
+  {
+    return *(m_end-1);
+  }
+  /// \brief Returns the element below the top element of the mutable stack.
+  Type& parent()
+  {
+    return *(m_end-2);
+  }
+  /// \brief Returns the element below the top element of the non-mutable stack.
+  const Type& parent() const
+  {
+    return *(m_end-2);
+  }
+  /// \brief Swaps the values of this stack and \p other.
+  void swap(Stack& other)
+  {
+    std::swap(m_data, other.m_data);
+    std::swap(m_end, other.m_end);
+    std::swap(m_capacity, other.m_capacity);
+  }
+#if 1 // use copy-swap technique
+  Stack& operator=(const Stack& other)
+  {
+    Stack temp(other);
+    temp.swap(*this);
+    return *this;
+  }
+#else // avoids memory allocation if capacity is already sufficient.
+  Stack& operator=(const Stack& other)
+  {
+    if(&other != this)
+    {
+      destroy();
+
+      if(other.size() > m_capacity)
+      {
+        Allocator::deallocate(m_data, m_capacity);
+        m_capacity = other.m_capacity;
+        m_data = Allocator::allocate(m_capacity);
+      }
+      m_end = m_data + other.size();
+
+      construct(other);
+    }
+    return *this;
+  }
+#endif
+};
+
+/// \brief Returns true if \p self is lexicographically less than \p other.
+template<typename Type>
+inline bool operator<(const Stack<Type>& self, const Stack<Type>& other)
+{
+  return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end());
+}
+
+namespace std
+{
+  /// \brief Swaps the values of \p self and \p other.
+  /// Overloads std::swap().
+  template<typename Type>
+  inline void swap(Stack<Type>& self, Stack<Type>& other)
+  {
+    self.swap(other);
+  }
+}
+
+#endif