File: prefixcompress.php

package info (click to toggle)
php-doc 20061001-1
  • links: PTS
  • area: non-free
  • in suites: etch, etch-m68k
  • size: 45,764 kB
  • ctags: 1,611
  • sloc: xml: 502,485; php: 7,645; cpp: 500; makefile: 297; perl: 161; sh: 141; awk: 28
file content (113 lines) | stat: -rw-r--r-- 3,621 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
<?php
/*
  +----------------------------------------------------------------------+
  | PHP Version 4                                                        |
  +----------------------------------------------------------------------+
  | Copyright (c) 1997-2004 The PHP Group                                |
  +----------------------------------------------------------------------+
  | This source file is subject to version 3.0 of the PHP license,       |
  | that is bundled with this package in the file LICENSE, and is        |
  | available through the world-wide-web at the following url:           |
  | http://www.php.net/license/3_0.txt.                                  |
  | If you did not receive a copy of the PHP license and are unable to   |
  | obtain it through the world-wide-web, please send a note to          |
  | license@php.net so we can mail you a copy immediately.               |
  +----------------------------------------------------------------------+
  | Authors:    Mitja Slenc <mitja@php.net>                              |
  +----------------------------------------------------------------------+
  
  $Id: prefixcompress.php,v 1.4 2004/12/20 15:56:01 goba Exp $
*/

$funcs=file("funclist.txt");
foreach($funcs as $key => $val)
	$funcs[$key]=trim($val);

$result=DoCompress($funcs);

$outfile=fopen("prefixcompressed.txt", "w");
fwrite($outfile, DoCompress($funcs));

$cache=array();

function DoCompress($list, $level=0)
{
	global $cache;
	$key=implode(",",$list);
	if (isset($cache[$key]))
		return $cache[$key];

	$result="";

	while (sizeof($list)) {
		if ($result && substr($result,-1)!=')' && substr($result,-1)!=']') $result.=",";
		if (sizeof($list)==1) {
			$result.=$list[0];
			return ($cache[$key]=$result);
		}
		if (sizeof($list)==2) {
			if (substr($list[1],0,strlen($list[0]))==$list[0]) {
				$result.=$list[0]."[".substr($list[1],strlen($list[0]))."]";
				return ($cache[$key]=$result);
			} else {
				if (substr($list[0],0,2)!=substr($list[1],0,2)) {
					$result.=$list[0].",".$list[1];
				} else {
					$len=2;
					while ($len<strlen($list[0]) && substr($list[0],0,$len+1)==substr($list[1],0,$len+1)) {
						$len++;
					}
					$result.=substr($list[0],0,$len)."(".substr($list[0],$len).",".substr($list[1],$len).")";
				}
				return ($cache[$key]=$result);
			}
		}
		if (@($list[0][0]!=$list[1][0] || ($list[0][1]!=$list[1][1] && $list[2][0]!=$list[0][0]))) {
			$result.=array_shift($list);
			continue;
		}

		$bestsave=0;
		$bestremain=$list;
		$bestresult=array_shift($bestremain);

		if (substr($list[1],0,strlen($list[0]))==$list[0]) {
			$tmplist=$list;
			$prefix=array_shift($tmplist);
			$subs=array();
			while (@substr($tmplist[0],0,strlen($prefix))==$prefix) {
				$subs[]=substr(array_shift($tmplist),strlen($prefix));
			}
			$tmpresult=$prefix."[";
			$tmpresult.=DoCompress($subs);
			$tmpresult.="]";
			$bestsave=sizeof($subs)*strlen($prefix)-1;
			if (sizeof($tmplist)) $bestsave++;
			$bestremain=$tmplist;
			$bestresult=$tmpresult;
		}
		for ($len=strlen($list[0])-1; $len>=1; $len--) {
			$prefix=substr($list[0],0,$len);
			$count=0;
			while ($count<sizeof($list) && substr($list[$count],0,$len)==$prefix)
				$count++;
			$save=($count-1)*$len-2;
			if ($count<sizeof($list))
				$save++;
			if ($save>$bestsave) {
				$bestsave=$save;
				$tmplist=$list;
				$subs=array();
				for ($a=0; $a<$count; $a++)
					$subs[]=substr(array_shift($tmplist),$len);
				$bestremain=$tmplist;
				$bestresult=$prefix."(".DoCompress($subs).")";
			}
		}
		$result.=$bestresult;
		$list=$bestremain;
	}
	return ($cache[$key]=$result);
}

?>