Actually move the kde files that were renamed in the last commit

1 files changed, 520 insertions, 0 deletions

diff --git a/libtdegames/kgrid2d.h b/libtdegames/kgrid2d.h
new file mode 100644
index 00000000..9443b0c7
--- /dev/null
+++ b/libtdegames/kgrid2d.h
@@ -0,0 +1,520 @@
+/*
+    This file is part of the KDE games library
+    Copyright (C) 2001-02 Nicolas Hadacek ([email protected])
+
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License version 2 as published by the Free Software Foundation.
+
+    This library 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
+    Library General Public License for more details.
+
+    You should have received a copy of the GNU Library General Public License
+    along with this library; see the file COPYING.LIB.  If not, write to
+    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+    Boston, MA 02110-1301, USA.
+*/
+
+#ifndef __KGRID2D_H_
+#define __KGRID2D_H_
+
+#include <math.h>
+
+#include <tqpair.h>
+#include <tqvaluelist.h>
+#include <tqvaluevector.h>
+
+#include <kglobal.h>
+
+
+//-----------------------------------------------------------------------------
+namespace KGrid2D
+{
+    /**
+     * This type represents coordinates on a bidimensionnal grid.
+     * @since 3.2
+     */
+    typedef TQPair<int, int> Coord;
+
+    /**
+     * This type represents a list of @ref Coord.
+     * @since 3.2
+     */
+    typedef TQValueList<Coord> CoordList;
+}
+
+inline KGrid2D::Coord
+operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+    return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
+}
+
+inline KGrid2D::Coord
+operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+    return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
+}
+
+/**
+ * @return the maximum of both coordinates.
+ * @since 3.2
+ */
+inline KGrid2D::Coord
+maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+    return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
+}
+/**
+ * @return the minimum of both coordinates.
+ * @since 3.2
+ */
+inline KGrid2D::Coord
+minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+    return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
+}
+
+inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::Coord &c) {
+    return s << '(' << c.second << ", " << c.first << ')';
+}
+
+inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::CoordList &list)
+{
+    for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
+        s << *i;
+	return s;
+}
+
+//-----------------------------------------------------------------------------
+namespace KGrid2D
+{
+/**
+ * This template class represents a generic bidimensionnal grid. Each node
+ * contains an element of the template type.
+ *
+ * @since 3.2
+ */
+template <class Type>
+class Generic
+{
+ public:
+    /**
+     * Constructor.
+     */
+    Generic(uint width = 0, uint height = 0) {
+        resize(width, height);
+    }
+
+    virtual ~Generic() {}
+
+    /**
+     * Resize the grid.
+     */
+    void resize(uint width, uint height) {
+        _width = width;
+        _height = height;
+        _vector.resize(width*height);
+    }
+
+    /**
+     * Fill the nodes with the given value.
+     */
+    void fill(const Type &value) {
+        for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
+    }
+
+    /**
+     * @return the width.
+     */
+    uint width() const  { return _width; }
+    /**
+     * @return the height.
+     */
+    uint height() const { return _height; }
+    /**
+     * @return the number of nodes (ie width*height).
+     */
+    uint size() const   { return _width*_height; }
+
+    /**
+     * @return the linear index for the given coordinate.
+     */
+    uint index(const Coord &c) const {
+        return c.first + c.second*_width;
+    }
+
+    /**
+     * @return the coordinate corresponding to the linear index.
+     */
+    Coord coord(uint index) const {
+        return Coord(index % _width, index / _width);
+    }
+
+    /**
+     * @return the value at the given coordinate.
+     */
+    const Type &at(const Coord &c) const { return _vector[index(c)]; }
+    /**
+     * @return the value at the given coordinate.
+     */
+    Type &at(const Coord &c)             { return _vector[index(c)]; }
+    /**
+     * @return the value at the given coordinate.
+     */
+    const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
+    /**
+     * @return the value at the given coordinate.
+     */
+    Type &operator [](const Coord &c)             { return _vector[index(c)]; }
+
+    /**
+     * @return the value at the given linear index.
+     */
+    const Type &at(uint index) const          { return _vector[index]; }
+    /**
+     * @return the value at the given linear index.
+     */
+    Type &at(uint index)                      { return _vector[index]; }
+    /**
+     * @return the value at the given linear index.
+     */
+    const Type &operator [](uint index) const { return _vector[index]; }
+    /**
+     * @return the value at the given linear index.
+     */
+    Type &operator [](uint index)             { return _vector[index]; }
+
+    /**
+     * @return if the given coordinate is inside the grid.
+     */
+    bool inside(const Coord &c) const {
+        return ( c.first>=0 && c.first<(int)_width
+                 && c.second>=0 && c.second<(int)_height );
+    }
+
+    /**
+     * Bound the given coordinate with the grid dimensions.
+     */
+    void bound(Coord &c) const {
+        c.first = kMax(kMin(c.first, (int)_width-1), 0);
+        c.second = kMax(kMin(c.second, (int)_height-1), 0);
+    }
+
+ protected:
+    uint               _width, _height;
+    TQValueVector<Type> _vector;
+};
+}
+
+template <class Type>
+TQDataStream &operator <<(TQDataStream &s, const KGrid2D::Generic<Type> &m) {
+    s << (TQ_UINT32)m.width() << (TQ_UINT32)m.height();
+    for (uint i=0; i<m.size(); i++) s << m[i];
+    return s;
+}
+
+template <class Type>
+TQDataStream &operator >>(TQDataStream &s, KGrid2D::Generic<Type> &m) {
+    TQ_UINT32 w, h;
+    s >> w >> h;
+    m.resize(w, h);
+    for (uint i=0; i<m.size(); i++) s >> m[i];
+    return s;
+}
+
+
+namespace KGrid2D
+{
+
+//-----------------------------------------------------------------------------
+/**
+ * This class contains static methods to manipulate coordinates for a
+ * square bidimensionnal grid.
+ *
+ * @since 3.2
+ */
+class SquareBase
+{
+ public:
+    /**
+     * Identify the eight neighbours.
+     */
+    enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
+                     RightUp, RightDown, Nb_Neighbour };
+
+    /**
+     * @return the trigonometric angle in radians for the given neighbour.
+     */
+    static double angle(Neighbour n) {
+        switch (n) {
+        case Left:      return M_PI;
+        case Right:     return 0;
+        case Up:        return M_PI_2;
+        case Down:      return -M_PI_2;
+        case LeftUp:    return 3.0*M_PI_4;
+        case LeftDown:  return -3.0*M_PI_4;
+        case RightUp:   return M_PI_4;
+        case RightDown: return -M_PI_4;
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return 0;
+    }
+
+    /**
+     * @return the opposed neighbour.
+     */
+    static Neighbour opposed(Neighbour n) {
+        switch (n) {
+        case Left:      return Right;
+        case Right:     return Left;
+        case Up:        return Down;
+        case Down:      return Up;
+        case LeftUp:    return RightDown;
+        case LeftDown:  return RightUp;
+        case RightUp:   return LeftDown;
+        case RightDown: return LeftUp;
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return Nb_Neighbour;
+    }
+
+    /**
+     * @return true if the neighbour is a direct one (ie is one of the four
+     * nearest).
+     */
+    static bool isDirect(Neighbour n) { return n<LeftUp; }
+
+    /**
+     * @return the neighbour for the given coordinate.
+     */
+    static Coord neighbour(const Coord &c, Neighbour n) {
+        switch (n) {
+        case Left:      return c + Coord(-1,  0);
+        case Right:     return c + Coord( 1,  0);
+        case Up:        return c + Coord( 0, -1);
+        case Down:      return c + Coord( 0,  1);
+        case LeftUp:    return c + Coord(-1, -1);
+        case LeftDown:  return c + Coord(-1,  1);
+        case RightUp:   return c + Coord( 1, -1);
+        case RightDown: return c + Coord( 1,  1);
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return c;
+    }
+};
+
+/**
+ * This template is a @ref Generic implementation for a square bidimensionnal
+ * grid (@ref SquareBase).
+ *
+ * @since 3.2
+ */
+template <class T>
+class Square : public Generic<T>, public SquareBase
+{
+ public:
+    /**
+     * Constructor.
+     */
+    Square(uint width = 0, uint height = 0)
+        : Generic<T>(width, height) {}
+
+    /**
+     * @return the neighbours of coordinate @param c
+     * to the given set of coordinates
+     * @param c the coordinate to use as the reference point
+     * @param insideOnly only add coordinates that are inside the grid.
+     * @param directOnly only add the four nearest neighbours.
+     */
+    CoordList neighbours(const Coord &c, bool insideOnly = true,
+                         bool directOnly = false) const {
+        CoordList neighbours;
+        for (uint i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
+            Coord n = neighbour(c, (Neighbour)i);
+            if ( insideOnly && !Generic<T>::inside(n) ) continue;
+            neighbours.append(n);
+        }
+        return neighbours;
+    }
+
+    /**
+     * @return the "projection" of the given coordinate on the grid edges.
+     *
+     * @param c the coordinate to use as the reference point
+     * @param n the direction of projection.
+     */
+    Coord toEdge(const Coord &c, Neighbour n) const {
+        switch (n) {
+        case Left:      return Coord(0, c.second);
+        case Right:     return Coord(Generic<T>::width()-1, c.second);
+        case Up:        return Coord(c.first, 0);
+        case Down:      return Coord(c.first, Generic<T>::height()-1);
+        case LeftUp:    return Coord(0, 0);
+        case LeftDown:  return Coord(0, Generic<T>::height()-1);
+        case RightUp:   return Coord(Generic<T>::width()-1, 0);
+        case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return c;
+    }
+};
+
+//-----------------------------------------------------------------------------
+/**
+ * This class contains static methods to manipulate coordinates on an
+ * hexagonal grid where hexagons form horizontal lines:
+ * <pre>
+ * (0,0)   (0,1)   (0,2)
+ *     (1,0)   (1,1)   (1,2)
+ * (2,0)   (2,1)   (2,2)
+ * </pre>
+ *
+ * @since 3.2
+ */
+class HexagonalBase
+{
+ public:
+    /**
+     * Identify the six neighbours.
+     */
+    enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
+                     RightUp, RightDown, Nb_Neighbour };
+
+     /**
+     * @return the trigonometric angle in radians for the given neighbour.
+     */
+    static double angle(Neighbour n) {
+        switch (n) {
+        case Left:      return M_PI;
+        case Right:     return 0;
+        case LeftUp:    return 2.0*M_PI/3;
+        case LeftDown:  return -2.0*M_PI/3;
+        case RightUp:   return M_PI/3;
+        case RightDown: return -M_PI/3;
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return 0;
+    }
+
+    /**
+     * @return the opposed neighbour.
+     */
+    static Neighbour opposed(Neighbour n) {
+        switch (n) {
+        case Left:      return Right;
+        case Right:     return Left;
+        case LeftUp:    return RightDown;
+        case LeftDown:  return RightUp;
+        case RightUp:   return LeftDown;
+        case RightDown: return LeftUp;
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return Nb_Neighbour;
+    }
+
+    /**
+     * @return the neighbour of the given coordinate.
+     */
+    static Coord neighbour(const Coord &c, Neighbour n) {
+        bool oddRow = c.second%2;
+        switch (n) {
+        case Left:      return c + Coord(-1,  0);
+        case Right:     return c + Coord( 1,  0);
+        case LeftUp:    return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
+        case LeftDown:  return c + (oddRow ? Coord( 0,  1) : Coord(-1,  1));
+        case RightUp:   return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
+        case RightDown: return c + (oddRow ? Coord( 1,  1) : Coord( 0,  1));
+        case Nb_Neighbour: Q_ASSERT(false);
+        }
+        return c;
+    }
+
+    /**
+    * @return the distance between the two coordinates in term of hexagons.
+    */
+    static uint distance(const Coord &c1, const Coord &c2) {
+        return kAbs(c1.first - c2.first) + kAbs(c1.second - c2.second)
+            + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
+    }
+};
+
+/**
+ * This template implements a hexagonal grid
+ * where hexagons form horizontal lines:
+ * <pre>
+ * (0,0)   (0,1)   (0,2)
+ *     (1,0)   (1,1)   (1,2)
+ * (2,0)   (2,1)   (2,2)
+ * </pre>
+ *
+ * @ since 3.2
+ */
+template <class Type>
+class Hexagonal : public Generic<Type>, public HexagonalBase
+{
+ public:
+    /**
+     * Constructor.
+     */
+    Hexagonal(uint width = 0, uint height = 0)
+        : Generic<Type>(width, height) {}
+
+    /**
+     * @return the neighbours of coordinate @param c
+     * to the given set of coordinates
+     * @param c the coordiante to use as the reference point
+     * @param insideOnly only add coordinates that are inside the grid.
+     */
+    CoordList neighbours(const Coord &c, bool insideOnly = true) const {
+        CoordList neighbours;
+        for (uint i=0; i<Nb_Neighbour; i++) {
+            Coord n = neighbour(c, (Neighbour)i);
+            if ( insideOnly && !Generic<Type>::inside(n) ) continue;
+            neighbours.append(n);
+        }
+        return neighbours;
+    }
+
+
+    /**
+     * @return the neighbours at distance @param distance of coordinate
+     * @param c the coordinate to use as the reference point
+     * @param distance distance to the neighbour (1 means at contact).
+     * @param insideOnly only add coordinates that are inside the grid.
+     * @param all returns all neighbours at distance equal and less than
+     *        @param distance (the original coordinate is not included).
+     */
+    CoordList neighbours(const Coord &c, uint distance, bool all,
+                        bool insideOnly = true) const {
+        // brute force algorithm -- you're welcome to make it more efficient :)
+        CoordList ring;
+        if ( distance==0 ) return ring;
+        ring = neighbours(c, insideOnly);
+        if ( distance==1 ) return ring;
+        CoordList center;
+        center.append(c);
+        for (uint i=1; i<distance; i++) {
+            CoordList newRing;
+            CoordList::const_iterator it;
+            for (it=ring.begin(); it!=ring.end(); ++it) {
+                CoordList n = neighbours(*it, insideOnly);
+                CoordList::const_iterator it2;
+                for (it2=n.begin(); it2!=n.end(); ++it2)
+                    if ( center.find(*it2)==center.end()
+                         && ring.find(*it2)==ring.end()
+                         && newRing.find(*it2)==newRing.end() )
+                        newRing.append(*it2);
+                center.append(*it);
+            }
+            ring = newRing;
+        }
+        if ( !all ) return ring;
+        CoordList::const_iterator it;
+        for (it=ring.begin(); it!=ring.end(); ++it)
+            center.append(*it);
+        center.remove(c);
+        return center;
+    }
+};
+
+} // namespace
+
+#endif