- New port devel/py-rbtree

An RBTree is a fast, balanced efficient data structure with the
following properties:

get          O(log n)
set          O(log n)
delete       O(log n)
min          O(log n)
max          O(log n)
contains     O(log n)

Because the worst case timing is minimal across the range of standard
dict and ordered data operations it makes sense to use this when you
have volatile/dynamic sorted data.

In common usage its nearly as fast as the Python dict impl but has a
slightly more expensive usage of the compare function as the keys are
ordered and not hashed.

WWW:	http://www.python.org/pypi/RBTree/

5 files changed, 100 insertions, 0 deletions

diff --git a/devel/Makefile b/devel/Makefile
index e065ccb26c8a..0ff5b2fb1309 100644
--- a/devel/Makefile
+++ b/devel/Makefile
@@ -1498,6 +1498,7 @@
     SUBDIR += py-px
     SUBDIR += py-pydasm
     SUBDIR += py-pytz
+    SUBDIR += py-rbtree
     SUBDIR += py-repl
     SUBDIR += py-resourcepackage
     SUBDIR += py-reverse
diff --git a/devel/py-rbtree/Makefile b/devel/py-rbtree/Makefile
new file mode 100644
index 000000000000..4a22cd872b2b
--- /dev/null
+++ b/devel/py-rbtree/Makefile
@@ -0,0 +1,40 @@
+# New ports collection makefile for:	py-rbtree
+# Date created:				08 Mai 2006
+# Whom:					Marcus Alves Grando <mnag@FreeBSD.org>
+#
+# $FreeBSD$
+#
+
+PORTNAME=	rbtree
+PORTVERSION=	0.6
+CATEGORIES=	devel python
+MASTER_SITES=	http://cheeseshop.python.org/packages/source/R/RBTree/
+PKGNAMEPREFIX=	${PYTHON_PKGNAMEPREFIX}
+
+MAINTAINER=	mnag@FreeBSD.org
+COMMENT=	A fast tree with ordered data and expanded iterator support
+
+BUILD_DEPENDS=	pyrexc:${PORTSDIR}/devel/pyrex
+
+WRKSRC=		${WRKDIR}/${PORTNAME}
+
+DIST_SUBDIR=	python
+USE_PYTHON=	yes
+USE_PYDISTUTILS=	yes
+
+DOCSDIR=	${PREFIX}/share/doc/${PKGNAMEPREFIX}${PORTNAME}
+
+PLIST_FILES=	%%PYTHON_SITELIBDIR%%/rbtree.so
+
+PORTDOCS=	*
+
+post-install:
+.if !defined(NOPORTDOCS)
+	@${MKDIR} ${DOCSDIR}
+	${INSTALL_DATA} ${WRKSRC}/README.txt ${DOCSDIR}
+.endif
+
+test:	build
+	(cd ${WRKSRC} && ${PYTHON_CMD} test_rbtree.py)
+
+.include <bsd.port.mk>
diff --git a/devel/py-rbtree/distinfo b/devel/py-rbtree/distinfo
new file mode 100644
index 000000000000..035bd81a0154
--- /dev/null
+++ b/devel/py-rbtree/distinfo
@@ -0,0 +1,3 @@
+MD5 (python/rbtree-0.6.tar.gz) = 5c031f8d510888bd2e8ebc3d6e4b51ac
+SHA256 (python/rbtree-0.6.tar.gz) = d18febd8b96d58e4809f9b7968525264c23388f463261d3df3f4bf9016d9ea59
+SIZE (python/rbtree-0.6.tar.gz) = 13478
diff --git a/devel/py-rbtree/files/patch-src__rbtree_impl.c b/devel/py-rbtree/files/patch-src__rbtree_impl.c
new file mode 100644
index 000000000000..3cb0916b000a
--- /dev/null
+++ b/devel/py-rbtree/files/patch-src__rbtree_impl.c
@@ -0,0 +1,37 @@
+--- ./src/rbtree_impl.c.orig	Mon May  8 11:00:16 2006
++++ ./src/rbtree_impl.c	Mon May  8 11:01:48 2006
+@@ -43,10 +43,11 @@
+ int
+ rbtree_node_compare(PyObject *x, PyObject *y)
+ {
++  int gt, lt;
+   /* a three way compare that should work with whatever objects support */
+-  int gt = PyObject_RichCompareBool(x,y, Py_GT);
++  gt = PyObject_RichCompareBool(x,y, Py_GT);
+   if (gt == 1) return 1;
+-  int lt = PyObject_RichCompareBool(x,y, Py_LT);
++  lt = PyObject_RichCompareBool(x,y, Py_LT);
+   if (lt == 1)  return -1;
+   return 0;
+ }
+@@ -626,16 +627,18 @@
+ 
+ rbtree_node_t *
+ tree_min(rbtree_t *T, rbtree_node_t *x) {
++  rbtree_node_t *n;
+   if (x == NULL) x = T->root;
+-  rbtree_node_t *n = __tree_min(T, x);
++  n = __tree_min(T, x);
+   if (n == T->nil) n = NULL;
+   return n;
+ }
+ 
+ rbtree_node_t *
+ tree_max(rbtree_t *T, rbtree_node_t *x) {
++  rbtree_node_t *n;
+   if (x == NULL) x = T->root;
+-  rbtree_node_t *n = __tree_max(T, x);
++  n = __tree_max(T, x);
+   if (n == T->nil) n = NULL;
+   return n;
+ }
diff --git a/devel/py-rbtree/pkg-descr b/devel/py-rbtree/pkg-descr
new file mode 100644
index 000000000000..984856ff4cce
--- /dev/null
+++ b/devel/py-rbtree/pkg-descr
@@ -0,0 +1,19 @@
+An RBTree is a fast, balanced efficient data structure with the
+following properties:
+
+get          O(log n)
+set          O(log n)
+delete       O(log n)
+min          O(log n)
+max          O(log n)
+contains     O(log n)
+
+Because the worst case timing is minimal across the range of standard
+dict and ordered data operations it makes sense to use this when you
+have volatile/dynamic sorted data.
+
+In common usage its nearly as fast as the Python dict impl but has a
+slightly more expensive usage of the compare function as the keys are
+ordered and not hashed.
+
+WWW:	http://www.python.org/pypi/RBTree/