KDirStat – a graphical disk usage utility
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

ktreemaptile.cpp 15KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608
  1. /*
  2. * File name: ktreemaptile.cpp
  3. * Summary: High level classes for KDirStat
  4. * License: LGPL - See file COPYING.LIB for details.
  5. * Author: Stefan Hundhammer <sh@suse.de>
  6. *
  7. * Updated: 2003-01-30
  8. */
  9. #include <math.h>
  10. #include <algorithm>
  11. #include <kapp.h>
  12. #include <tdelocale.h>
  13. #include <tdeglobal.h>
  14. #include <tqimage.h>
  15. #include <tqpainter.h>
  16. #include "ktreemaptile.h"
  17. #include "ktreemapview.h"
  18. #include "kdirtreeiterators.h"
  19. #include "kdirtreeview.h"
  20. using namespace KDirStat;
  21. using std::max;
  22. using std::min;
  23. KTreemapTile::KTreemapTile( KTreemapView * parentView,
  24. KTreemapTile * parentTile,
  25. KFileInfo * orig,
  26. const TQRect & rect,
  27. KOrientation orientation )
  28. : TQCanvasRectangle( rect, parentView->canvas() )
  29. , _parentView( parentView )
  30. , _parentTile( parentTile )
  31. , _orig( orig )
  32. {
  33. init();
  34. if ( parentTile )
  35. _cushionSurface = parentTile->cushionSurface();
  36. createChildren( rect, orientation );
  37. }
  38. KTreemapTile::KTreemapTile( KTreemapView * parentView,
  39. KTreemapTile * parentTile,
  40. KFileInfo * orig,
  41. const TQRect & rect,
  42. const KCushionSurface & cushionSurface,
  43. KOrientation orientation )
  44. : TQCanvasRectangle( rect, parentView->canvas() )
  45. , _parentView( parentView )
  46. , _parentTile( parentTile )
  47. , _orig( orig )
  48. , _cushionSurface( cushionSurface )
  49. {
  50. init();
  51. // Intentionally not copying the parent's cushion surface!
  52. createChildren( rect, orientation );
  53. }
  54. KTreemapTile::~KTreemapTile()
  55. {
  56. // NOP
  57. }
  58. void
  59. KTreemapTile::init()
  60. {
  61. // Set up height (z coordinate) - one level higher than the parent so this
  62. // will be closer to the foreground.
  63. //
  64. // Note that this must happen before any children are created.
  65. // I found that out the hard way. ;-)
  66. setZ( _parentTile ? ( _parentTile->z() + 1.0 ) : 0.0 );
  67. setBrush( TQColor( 0x60, 0x60, 0x60 ) );
  68. setPen( Qt::NoPen );
  69. show(); // TQCanvasItems are invisible by default!
  70. // kdDebug() << "Creating treemap tile for " << orig << " " << rect << " size " << orig->totalSize() << endl;
  71. }
  72. void
  73. KTreemapTile::createChildren( const TQRect & rect,
  74. KOrientation orientation )
  75. {
  76. if ( _orig->totalSize() == 0 ) // Prevent division by zero
  77. return;
  78. if ( _parentView->squarify() )
  79. createSquarifiedChildren( rect );
  80. else
  81. createChildrenSimple( rect, orientation );
  82. }
  83. void
  84. KTreemapTile::createChildrenSimple( const TQRect & rect,
  85. KOrientation orientation )
  86. {
  87. KOrientation dir = orientation;
  88. KOrientation childDir = orientation;
  89. if ( dir == KTreemapAuto )
  90. dir = rect.width() > rect.height() ? KTreemapHorizontal : KTreemapVertical;
  91. if ( orientation == KTreemapHorizontal ) childDir = KTreemapVertical;
  92. if ( orientation == KTreemapVertical ) childDir = KTreemapHorizontal;
  93. int offset = 0;
  94. int size = dir == KTreemapHorizontal ? rect.width() : rect.height();
  95. int count = 0;
  96. double scale = (double) size / (double) _orig->totalSize();
  97. _cushionSurface.addRidge( childDir, _cushionSurface.height(), rect );
  98. KFileInfoSortedBySizeIterator it( _orig,
  99. (KFileSize) ( _parentView->minTileSize() / scale ),
  100. KDotEntryAsSubDir );
  101. while ( *it )
  102. {
  103. int childSize = 0;
  104. childSize = (int) ( scale * (*it)->totalSize() );
  105. if ( childSize >= _parentView->minTileSize() )
  106. {
  107. TQRect childRect;
  108. if ( dir == KTreemapHorizontal )
  109. childRect = TQRect( rect.x() + offset, rect.y(), childSize, rect.height() );
  110. else
  111. childRect = TQRect( rect.x(), rect.y() + offset, rect.width(), childSize );
  112. KTreemapTile * tile = new KTreemapTile( _parentView, this, *it, childRect, childDir );
  113. TQ_CHECK_PTR( tile );
  114. tile->cushionSurface().addRidge( dir,
  115. _cushionSurface.height() * _parentView->heightScaleFactor(),
  116. childRect );
  117. offset += childSize;
  118. }
  119. ++count;
  120. ++it;
  121. }
  122. }
  123. void
  124. KTreemapTile::createSquarifiedChildren( const TQRect & rect )
  125. {
  126. if ( _orig->totalSize() == 0 )
  127. {
  128. kdError() << k_funcinfo << "Zero totalSize()" << endl;
  129. return;
  130. }
  131. double scale = rect.width() * (double) rect.height() / _orig->totalSize();
  132. KFileSize minSize = (KFileSize) ( _parentView->minTileSize() / scale );
  133. #if 0
  134. if ( _orig->hasChildren() )
  135. {
  136. _cushionSurface.addRidge( KTreemapHorizontal, _cushionSurface.height(), rect );
  137. _cushionSurface.addRidge( KTreemapVertical, _cushionSurface.height(), rect );
  138. }
  139. #endif
  140. KFileInfoSortedBySizeIterator it( _orig, minSize, KDotEntryAsSubDir );
  141. TQRect childrenRect = rect;
  142. while ( *it )
  143. {
  144. KFileInfoList row = squarify( childrenRect, scale, it );
  145. childrenRect = layoutRow( childrenRect, scale, row );
  146. }
  147. }
  148. KFileInfoList
  149. KTreemapTile::squarify( const TQRect & rect,
  150. double scale,
  151. KFileInfoSortedBySizeIterator & it )
  152. {
  153. // kdDebug() << "squarify() " << _orig << " " << rect << endl;
  154. KFileInfoList row;
  155. int length = max( rect.width(), rect.height() );
  156. if ( length == 0 ) // Sanity check
  157. {
  158. kdWarning() << k_funcinfo << "Zero length" << endl;
  159. if ( *it ) // Prevent endless loop in case of error:
  160. ++it; // Advance iterator.
  161. return row;
  162. }
  163. bool improvingAspectRatio = true;
  164. double lastWorstAspectRatio = -1.0;
  165. double sum = 0;
  166. // This is a bit ugly, but doing all calculations in the 'size' dimension
  167. // is more efficient here since that requires only one scaling before
  168. // doing all other calculations in the loop.
  169. const double scaledLengthSquare = length * (double) length / scale;
  170. while ( *it && improvingAspectRatio )
  171. {
  172. sum += (*it)->totalSize();
  173. if ( ! row.isEmpty() && sum != 0 && (*it)->totalSize() != 0 )
  174. {
  175. double sumSquare = sum * sum;
  176. double worstAspectRatio = max( scaledLengthSquare * row.first()->totalSize() / sumSquare,
  177. sumSquare / ( scaledLengthSquare * (*it)->totalSize() ) );
  178. if ( lastWorstAspectRatio >= 0.0 &&
  179. worstAspectRatio > lastWorstAspectRatio )
  180. {
  181. improvingAspectRatio = false;
  182. }
  183. lastWorstAspectRatio = worstAspectRatio;
  184. }
  185. if ( improvingAspectRatio )
  186. {
  187. // kdDebug() << "Adding " << *it << " size " << (*it)->totalSize() << endl;
  188. row.append( *it );
  189. ++it;
  190. }
  191. else
  192. {
  193. // kdDebug() << "Getting worse after adding " << *it << " size " << (*it)->totalSize() << endl;
  194. }
  195. }
  196. return row;
  197. }
  198. TQRect
  199. KTreemapTile::layoutRow( const TQRect & rect,
  200. double scale,
  201. KFileInfoList & row )
  202. {
  203. if ( row.isEmpty() )
  204. return rect;
  205. // Determine the direction in which to subdivide.
  206. // We always use the longer side of the rectangle.
  207. KOrientation dir = rect.width() > rect.height() ? KTreemapHorizontal : KTreemapVertical;
  208. // This row's primary length is the longer one.
  209. int primary = max( rect.width(), rect.height() );
  210. // This row's secondary length is determined by the area (the number of
  211. // pixels) to be allocated for all of the row's items.
  212. KFileSize sum = row.sumTotalSizes();
  213. int secondary = (int) ( sum * scale / primary );
  214. if ( sum == 0 ) // Prevent division by zero.
  215. return rect;
  216. if ( secondary < _parentView->minTileSize() ) // We don't want tiles that small.
  217. return rect;
  218. // Set up a cushion surface for this layout row:
  219. // Add another ridge perpendicular to the row's direction
  220. // that optically groups this row's tiles together.
  221. KCushionSurface rowCushionSurface = _cushionSurface;
  222. rowCushionSurface.addRidge( dir == KTreemapHorizontal ? KTreemapVertical : KTreemapHorizontal,
  223. _cushionSurface.height() * _parentView->heightScaleFactor(),
  224. rect );
  225. int offset = 0;
  226. int remaining = primary;
  227. KFileInfoListIterator it( row );
  228. while ( *it )
  229. {
  230. int childSize = (int) ( (*it)->totalSize() / (double) sum * primary + 0.5 );
  231. if ( childSize > remaining ) // Prevent overflow because of accumulated rounding errors
  232. childSize = remaining;
  233. remaining -= childSize;
  234. if ( childSize >= _parentView->minTileSize() )
  235. {
  236. TQRect childRect;
  237. if ( dir == KTreemapHorizontal )
  238. childRect = TQRect( rect.x() + offset, rect.y(), childSize, secondary );
  239. else
  240. childRect = TQRect( rect.x(), rect.y() + offset, secondary, childSize );
  241. KTreemapTile * tile = new KTreemapTile( _parentView, this, *it, childRect, rowCushionSurface );
  242. TQ_CHECK_PTR( tile );
  243. tile->cushionSurface().addRidge( dir,
  244. rowCushionSurface.height() * _parentView->heightScaleFactor(),
  245. childRect );
  246. offset += childSize;
  247. }
  248. ++it;
  249. }
  250. // Subtract the layouted area from the rectangle.
  251. TQRect newRect;
  252. if ( dir == KTreemapHorizontal )
  253. newRect = TQRect( rect.x(), rect.y() + secondary, rect.width(), rect.height() - secondary );
  254. else
  255. newRect = TQRect( rect.x() + secondary, rect.y(), rect.width() - secondary, rect.height() );
  256. // kdDebug() << "Left over:" << " " << newRect << " " << _orig << endl;
  257. return newRect;
  258. }
  259. void
  260. KTreemapTile::drawShape( TQPainter & painter )
  261. {
  262. // kdDebug() << k_funcinfo << endl;
  263. TQSize size = rect().size();
  264. if ( size.height() < 1 || size.width() < 1 )
  265. return;
  266. if ( _parentView->doCushionShading() )
  267. {
  268. if ( _orig->isDir() || _orig->isDotEntry() )
  269. {
  270. TQCanvasRectangle::drawShape( painter );
  271. }
  272. else
  273. {
  274. if ( _cushion.isNull() )
  275. _cushion = renderCushion();
  276. TQRect rect = TQCanvasRectangle::rect();
  277. if ( ! _cushion.isNull() )
  278. painter.drawPixmap( rect, _cushion );
  279. if ( _parentView->forceCushionGrid() )
  280. {
  281. // Draw a clearly visible boundary
  282. painter.setPen( TQPen( _parentView->cushionGridColor(), 1 ) );
  283. if ( rect.x() > 0 )
  284. painter.drawLine( rect.topLeft(), rect.bottomLeft() + TQPoint( 0, 1 ) );
  285. if ( rect.y() > 0 )
  286. painter.drawLine( rect.topLeft(), rect.topRight() + TQPoint( 1, 0 ) );
  287. }
  288. }
  289. }
  290. else // No cushion shading, use plain tiles
  291. {
  292. painter.setPen( TQPen( _parentView->outlineColor(), 1 ) );
  293. if ( _orig->isDir() || _orig->isDotEntry() )
  294. painter.setBrush( _parentView->dirFillColor() );
  295. else
  296. {
  297. painter.setBrush( _parentView->tileColor( _orig ) );
  298. #if 0
  299. painter.setBrush( _parentView->fileFillColor() );
  300. #endif
  301. }
  302. TQCanvasRectangle::drawShape( painter );
  303. }
  304. }
  305. TQPixmap
  306. KTreemapTile::renderCushion()
  307. {
  308. TQRect rect = TQCanvasRectangle::rect();
  309. if ( rect.width() < 1 || rect.height() < 1 )
  310. return TQPixmap();
  311. // kdDebug() << k_funcinfo << endl;
  312. double nx;
  313. double ny;
  314. double cosa;
  315. int x, y;
  316. int red, green, blue;
  317. // Cache some values. They are used for each loop iteration, so let's try
  318. // to keep multiple indirect references down.
  319. int ambientLight = parentView()->ambientLight();
  320. double lightX = parentView()->lightX();
  321. double lightY = parentView()->lightY();
  322. double lightZ = parentView()->lightZ();
  323. double xx2 = cushionSurface().xx2();
  324. double xx1 = cushionSurface().xx1();
  325. double yy2 = cushionSurface().yy2();
  326. double yy1 = cushionSurface().yy1();
  327. int x0 = rect.x();
  328. int y0 = rect.y();
  329. TQColor color = parentView()->tileColor( _orig );
  330. int maxRed = max( 0, color.red() - ambientLight );
  331. int maxGreen = max( 0, color.green() - ambientLight );
  332. int maxBlue = max( 0, color.blue() - ambientLight );
  333. TQImage image( rect.width(), rect.height(), 32 );
  334. for ( y = 0; y < rect.height(); y++ )
  335. {
  336. for ( x = 0; x < rect.width(); x++ )
  337. {
  338. nx = 2.0 * xx2 * (x+x0) + xx1;
  339. ny = 2.0 * yy2 * (y+y0) + yy1;
  340. cosa = ( nx * lightX + ny * lightY + lightZ ) / sqrt( nx*nx + ny*ny + 1.0 );
  341. red = (int) ( maxRed * cosa + 0.5 );
  342. green = (int) ( maxGreen * cosa + 0.5 );
  343. blue = (int) ( maxBlue * cosa + 0.5 );
  344. if ( red < 0 ) red = 0;
  345. if ( green < 0 ) green = 0;
  346. if ( blue < 0 ) blue = 0;
  347. red += ambientLight;
  348. green += ambientLight;
  349. blue += ambientLight;
  350. image.setPixel( x, y, tqRgb( red, green, blue) );
  351. }
  352. }
  353. if ( _parentView->ensureContrast() )
  354. ensureContrast( image );
  355. return TQPixmap( image );
  356. }
  357. void
  358. KTreemapTile::ensureContrast( TQImage & image )
  359. {
  360. if ( image.width() > 5 )
  361. {
  362. // Check contrast along the right image boundary:
  363. //
  364. // Compare samples from the outmost boundary to samples a few pixels to
  365. // the inside and count identical pixel values. A number of identical
  366. // pixels are tolerated, but not too many.
  367. int x1 = image.width() - 6;
  368. int x2 = image.width() - 1;
  369. int interval = max( image.height() / 10, 5 );
  370. int sameColorCount = 0;
  371. // Take samples
  372. for ( int y = interval; y < image.height(); y+= interval )
  373. {
  374. if ( image.pixel( x1, y ) == image.pixel( x2, y ) )
  375. sameColorCount++;
  376. }
  377. if ( sameColorCount * 10 > image.height() )
  378. {
  379. // Add a line at the right boundary
  380. TQRgb val = contrastingColor( image.pixel( x2, image.height() / 2 ) );
  381. for ( int y = 0; y < image.height(); y++ )
  382. image.setPixel( x2, y, val );
  383. }
  384. }
  385. if ( image.height() > 5 )
  386. {
  387. // Check contrast along the bottom boundary
  388. int y1 = image.height() - 6;
  389. int y2 = image.height() - 1;
  390. int interval = max( image.width() / 10, 5 );
  391. int sameColorCount = 0;
  392. for ( int x = interval; x < image.width(); x += interval )
  393. {
  394. if ( image.pixel( x, y1 ) == image.pixel( x, y2 ) )
  395. sameColorCount++;
  396. }
  397. if ( sameColorCount * 10 > image.height() )
  398. {
  399. // Add a grey line at the bottom boundary
  400. TQRgb val = contrastingColor( image.pixel( image.width() / 2, y2 ) );
  401. for ( int x = 0; x < image.width(); x++ )
  402. image.setPixel( x, y2, val );
  403. }
  404. }
  405. }
  406. TQRgb
  407. KTreemapTile::contrastingColor( TQRgb col )
  408. {
  409. if ( tqGray( col ) < 128 )
  410. return tqRgb( tqRed( col ) * 2, tqGreen( col ) * 2, tqBlue( col ) * 2 );
  411. else
  412. return tqRgb( tqRed( col ) / 2, tqGreen( col ) / 2, tqBlue( col ) / 2 );
  413. }
  414. KCushionSurface::KCushionSurface()
  415. {
  416. _xx2 = 0.0;
  417. _xx1 = 0.0;
  418. _yy2 = 0.0;
  419. _yy1 = 0.0;
  420. _height = CushionHeight;
  421. }
  422. void
  423. KCushionSurface::addRidge( KOrientation dim, double height, const TQRect & rect )
  424. {
  425. _height = height;
  426. if ( dim == KTreemapHorizontal )
  427. {
  428. _xx2 = squareRidge( _xx2, _height, rect.left(), rect.right() );
  429. _xx1 = linearRidge( _xx1, _height, rect.left(), rect.right() );
  430. }
  431. else
  432. {
  433. _yy2 = squareRidge( _yy2, _height, rect.top(), rect.bottom() );
  434. _yy1 = linearRidge( _yy1, _height, rect.top(), rect.bottom() );
  435. }
  436. }
  437. double
  438. KCushionSurface::squareRidge( double squareCoefficient, double height, int x1, int x2 )
  439. {
  440. if ( x2 != x1 ) // Avoid division by zero
  441. squareCoefficient -= 4.0 * height / ( x2 - x1 );
  442. return squareCoefficient;
  443. }
  444. double
  445. KCushionSurface::linearRidge( double linearCoefficient, double height, int x1, int x2 )
  446. {
  447. if ( x2 != x1 ) // Avoid division by zero
  448. linearCoefficient += 4.0 * height * ( x2 + x1 ) / ( x2 - x1 );
  449. return linearCoefficient;
  450. }
  451. // EOF