From 183851b06bd6c52f3cae5375f433da720d410447 Mon Sep 17 00:00:00 2001
From: Pierre Schmitz <pierre@archlinux.de>
Date: Wed, 11 Oct 2006 18:12:39 +0000
Subject: MediaWiki 1.7.1 wiederhergestellt

---
 includes/Categoryfinder.php | 191 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 191 insertions(+)
 create mode 100644 includes/Categoryfinder.php

(limited to 'includes/Categoryfinder.php')

diff --git a/includes/Categoryfinder.php b/includes/Categoryfinder.php
new file mode 100644
index 00000000..a8cdf3ce
--- /dev/null
+++ b/includes/Categoryfinder.php
@@ -0,0 +1,191 @@
+<?php
+/*
+The "Categoryfinder" class takes a list of articles, creates an internal representation of all their parent
+categories (as well as parents of parents etc.). From this representation, it determines which of these articles
+are in one or all of a given subset of categories.
+
+Example use :
+
+	# Determines wether the article with the page_id 12345 is in both
+	# "Category 1" and "Category 2" or their subcategories, respectively
+	
+	$cf = new Categoryfinder ;
+	$cf->seed (
+		array ( 12345 ) ,
+		array ( "Category 1","Category 2" ) ,
+		"AND"
+	) ;
+	$a = $cf->run() ;
+	print implode ( "," , $a ) ;
+
+*/
+
+
+class Categoryfinder {
+
+	var $articles = array () ; # The original article IDs passed to the seed function
+	var $deadend = array () ; # Array of DBKEY category names for categories that don't have a page
+	var $parents = array () ; # Array of [ID => array()]
+	var $next = array () ; # Array of article/category IDs
+	var $targets = array () ; # Array of DBKEY category names
+	var $name2id = array () ;
+	var $mode ; # "AND" or "OR"
+	var $dbr ; # Read-DB slave
+
+	/**
+	 * Constructor (currently empty).
+	*/
+	function Categoryfinder () {
+	}
+
+	/**
+	 * Initializes the instance. Do this prior to calling run().
+	 * @param $article_ids Array of article IDs
+	 * @param $categories FIXME
+	 * @param $mode String: FIXME, default 'AND'.
+	 */
+	function seed ( $article_ids , $categories , $mode = "AND" ) {
+		$this->articles = $article_ids ;
+		$this->next = $article_ids ;
+		$this->mode = $mode ;
+
+		# Set the list of target categories; convert them to DBKEY form first
+		$this->targets = array () ;
+		foreach ( $categories AS $c ) {
+			$ct = Title::newFromText ( $c , NS_CATEGORY ) ;
+			$c = $ct->getDBkey () ;
+			$this->targets[$c] = $c ;
+		}
+	}
+
+	/**
+	 * Iterates through the parent tree starting with the seed values,
+	 * then checks the articles if they match the conditions
+	 @return array of page_ids (those given to seed() that match the conditions)
+	*/
+	function run () {
+		$this->dbr =& wfGetDB( DB_SLAVE );
+		while ( count ( $this->next ) > 0 ) {
+			$this->scan_next_layer () ;
+		}
+
+		# Now check if this applies to the individual articles
+		$ret = array () ;
+		foreach ( $this->articles AS $article ) {
+			$conds = $this->targets ;
+			if ( $this->check ( $article , $conds ) ) {
+				# Matches the conditions
+				$ret[] = $article ;
+			}
+		}
+		return $ret ;
+	}
+
+	/**
+	 * This functions recurses through the parent representation, trying to match the conditions
+	 @param $id The article/category to check
+	 @param $conds The array of categories to match
+	 @return bool Does this match the conditions?
+	*/
+	function check ( $id , &$conds ) {
+		# Shortcut (runtime paranoia): No contitions=all matched
+		if ( count ( $conds ) == 0 ) return true ;
+		
+		if ( !isset ( $this->parents[$id] ) ) return false ;
+
+		# iterate through the parents
+		foreach ( $this->parents[$id] AS $p ) {
+			$pname = $p->cl_to ;
+			
+			# Is this a condition?
+			if ( isset ( $conds[$pname] ) ) {
+				# This key is in the category list!
+				if ( $this->mode == "OR" ) {
+					# One found, that's enough!
+					$conds = array () ;
+					return true ;
+				} else {
+					# Assuming "AND" as default
+					unset ( $conds[$pname] ) ;
+					if ( count ( $conds ) == 0 ) {
+						# All conditions met, done
+						return true ;
+					}
+				}
+			}
+			
+			# Not done yet, try sub-parents
+			if ( !isset ( $this->name2id[$pname] ) ) {
+				# No sub-parent
+				continue ;
+			}
+			$done = $this->check ( $this->name2id[$pname] , $conds ) ;
+			if ( $done OR count ( $conds ) == 0 ) {
+				# Subparents have done it!
+				return true ;
+			}
+		}
+		return false ;
+	}
+
+	/**
+	 * Scans a "parent layer" of the articles/categories in $this->next
+	*/
+	function scan_next_layer () {
+		$fname = "Categoryfinder::scan_next_layer" ;
+	
+		# Find all parents of the article currently in $this->next
+		$layer = array () ;
+		$res = $this->dbr->select(
+				/* FROM   */ 'categorylinks',
+				/* SELECT */ '*',
+				/* WHERE  */ array( 'cl_from' => $this->next ),
+				$fname."-1"
+		);
+		while ( $o = $this->dbr->fetchObject( $res ) ) {
+			$k = $o->cl_to ;
+
+			# Update parent tree
+			if ( !isset ( $this->parents[$o->cl_from] ) ) {
+				$this->parents[$o->cl_from] = array () ;
+			}
+			$this->parents[$o->cl_from][$k] = $o ;
+
+			# Ignore those we already have
+			if ( in_array ( $k , $this->deadend ) ) continue ;
+			if ( isset ( $this->name2id[$k] ) ) continue ;
+
+			# Hey, new category!
+			$layer[$k] = $k ;
+		}
+		$this->dbr->freeResult( $res ) ;
+
+		$this->next = array() ;
+		
+		# Find the IDs of all category pages in $layer, if they exist
+		if ( count ( $layer ) > 0 ) {
+			$res = $this->dbr->select(
+					/* FROM   */ 'page',
+					/* SELECT */ 'page_id,page_title',
+					/* WHERE  */ array( 'page_namespace' => NS_CATEGORY , 'page_title' => $layer ),
+					$fname."-2"
+			);
+			while ( $o = $this->dbr->fetchObject( $res ) ) {
+				$id = $o->page_id ;
+				$name = $o->page_title ;
+				$this->name2id[$name] = $id ;
+				$this->next[] = $id ;
+				unset ( $layer[$name] ) ;
+			}
+			$this->dbr->freeResult( $res ) ;
+			}
+
+		# Mark dead ends
+		foreach ( $layer AS $v ) {
+			$this->deadend[$v] = $v ;
+		}
+	}
+
+} # END OF CLASS "Categoryfinder"
+
+?>
-- 
cgit v1.2.2