UndoManager.bf 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337
  1. using System;
  2. using System.Collections;
  3. using System.Text;
  4. using System.Diagnostics;
  5. namespace Beefy.utils
  6. {
  7. public class UndoAction
  8. {
  9. public virtual bool Merge(UndoAction nextAction)
  10. {
  11. return false;
  12. }
  13. public virtual bool Undo()
  14. {
  15. return true;
  16. }
  17. public virtual bool Redo()
  18. {
  19. return true;
  20. }
  21. public virtual int32 GetCost()
  22. {
  23. return 1;
  24. }
  25. }
  26. public interface IUndoBatchStart
  27. {
  28. IUndoBatchEnd BatchEnd { get; }
  29. String Name { get; }
  30. }
  31. public interface IUndoBatchEnd
  32. {
  33. IUndoBatchStart BatchStart { get; }
  34. String Name { get; }
  35. }
  36. public class UndoBatchStart : UndoAction, IUndoBatchStart
  37. {
  38. public String mName;
  39. public UndoBatchEnd mBatchEnd;
  40. public int32 mBatchInsertIdx;
  41. public int32 mBatchSize = 0; // Don't close out until we add the end
  42. public String Name
  43. {
  44. get
  45. {
  46. return mName;
  47. }
  48. }
  49. public this(String name)
  50. {
  51. mName = name;
  52. mBatchEnd = new UndoBatchEnd();
  53. mBatchEnd.mBatchStart = this;
  54. }
  55. public IUndoBatchEnd BatchEnd
  56. {
  57. get
  58. {
  59. return mBatchEnd;
  60. }
  61. }
  62. public override int32 GetCost()
  63. {
  64. return Math.Min(mBatchSize, 256); // Don't allow a large batch (ie: rename) to cause us to pull too much out of the undo buffer
  65. }
  66. public override void ToString(String strBuffer)
  67. {
  68. strBuffer.AppendF($"UndoBatchStart {mName}");
  69. }
  70. }
  71. public class UndoBatchEnd : UndoAction, IUndoBatchEnd
  72. {
  73. public IUndoBatchStart mBatchStart;
  74. public String Name
  75. {
  76. get
  77. {
  78. return mBatchStart.Name;
  79. }
  80. }
  81. public IUndoBatchStart BatchStart
  82. {
  83. get
  84. {
  85. return mBatchStart;
  86. }
  87. }
  88. public override void ToString(String strBuffer)
  89. {
  90. strBuffer.AppendF($"UndoBatchEnd {Name}");
  91. }
  92. }
  93. public class UndoManager
  94. {
  95. List<UndoAction> mUndoList = new List<UndoAction>() ~ DeleteContainerAndItems!(_);
  96. int32 mUndoIdx = 0;
  97. int32 mMaxCost = 8192;
  98. int32 mCurCost = 0;
  99. bool mSkipNextMerge; // Don't merge after we do an undo or redo step
  100. int32 mFreezeDeletes;
  101. public ~this()
  102. {
  103. Clear();
  104. }
  105. public void WithActions(delegate void(UndoAction) func)
  106. {
  107. for (var action in mUndoList)
  108. func(action);
  109. }
  110. public void Clear()
  111. {
  112. while (mUndoList.Count > 0)
  113. {
  114. var undoAction = mUndoList.PopBack();
  115. delete undoAction;
  116. }
  117. mUndoIdx = 0;
  118. mCurCost = 0;
  119. }
  120. public void Add(UndoAction action, bool allowMerge = true)
  121. {
  122. if (mFreezeDeletes == 0)
  123. mCurCost += action.GetCost();
  124. if (action is IUndoBatchStart)
  125. {
  126. mFreezeDeletes++;
  127. if (var undoBatchStart = action as UndoBatchStart)
  128. {
  129. undoBatchStart.mBatchInsertIdx = GetActionCount();
  130. }
  131. }
  132. else if (action is IUndoBatchEnd)
  133. {
  134. mFreezeDeletes--;
  135. if (var undoBatchEnd = action as UndoBatchEnd)
  136. {
  137. if (var undoBatchStart = undoBatchEnd.mBatchStart as UndoBatchStart)
  138. {
  139. undoBatchStart.mBatchSize = GetActionCount() - undoBatchStart.mBatchInsertIdx;
  140. int32 cost = undoBatchStart.GetCost();
  141. Debug.Assert(cost >= 0);
  142. mCurCost += cost;
  143. }
  144. }
  145. }
  146. if (mUndoIdx < mUndoList.Count)
  147. {
  148. int32 batchDepth = 0;
  149. for (int checkIdx = mUndoIdx; checkIdx < mUndoList.Count; checkIdx++)
  150. {
  151. var checkAction = mUndoList[checkIdx];
  152. if (batchDepth == 0)
  153. mCurCost -= checkAction.GetCost();
  154. if (checkAction is IUndoBatchStart)
  155. batchDepth++;
  156. else if (checkAction is IUndoBatchEnd)
  157. batchDepth--;
  158. delete checkAction;
  159. }
  160. Debug.Assert(batchDepth == 0);
  161. mUndoList.RemoveRange(mUndoIdx, mUndoList.Count - mUndoIdx);
  162. }
  163. if ((allowMerge) && (!mSkipNextMerge))
  164. {
  165. UndoAction prevAction = GetLastUndoAction();
  166. if (prevAction is UndoBatchStart)
  167. {
  168. var undoBatchStart = (UndoBatchStart)prevAction;
  169. if (undoBatchStart.mBatchEnd == action)
  170. {
  171. // It's an empty batch!
  172. mUndoList.PopBack();
  173. delete prevAction;
  174. delete action;
  175. mUndoIdx--;
  176. return;
  177. }
  178. }
  179. if ((prevAction != null) && (prevAction.Merge(action)))
  180. {
  181. delete action;
  182. return;
  183. }
  184. }
  185. mSkipNextMerge = false;
  186. mUndoList.Add(action);
  187. mUndoIdx++;
  188. if ((mCurCost > mMaxCost) && (mFreezeDeletes == 0))
  189. {
  190. int32 wantCost = (int32)(mMaxCost * 0.8f); // Don't just remove one item at a time
  191. int32 checkIdx = 0;
  192. int32 batchDepth = 0;
  193. while (((mCurCost > wantCost) || (batchDepth > 0)) &&
  194. (checkIdx < mUndoList.Count))
  195. {
  196. var checkAction = mUndoList[checkIdx];
  197. if (batchDepth == 0)
  198. mCurCost -= checkAction.GetCost();
  199. if (checkAction is IUndoBatchStart)
  200. batchDepth++;
  201. else if (checkAction is IUndoBatchEnd)
  202. batchDepth--;
  203. delete checkAction;
  204. checkIdx++;
  205. }
  206. mUndoList.RemoveRange(0, checkIdx);
  207. mUndoIdx -= checkIdx;
  208. }
  209. }
  210. public UndoAction GetLastUndoAction()
  211. {
  212. if (mUndoIdx == 0)
  213. return null;
  214. return mUndoList[mUndoIdx - 1];
  215. }
  216. public bool Undo()
  217. {
  218. mSkipNextMerge = true;
  219. if (mUndoIdx == 0)
  220. return false;
  221. var undoAction = mUndoList[mUndoIdx - 1];
  222. if (IUndoBatchEnd undoBatchEnd = undoAction as IUndoBatchEnd)
  223. {
  224. while (true)
  225. {
  226. if (!undoAction.Undo())
  227. return false;
  228. if (mUndoIdx == 0)
  229. return false;
  230. mUndoIdx--;
  231. if ((undoAction == undoBatchEnd.BatchStart) || (mUndoIdx == 0))
  232. return true;
  233. undoAction = mUndoList[mUndoIdx - 1];
  234. }
  235. }
  236. if (!undoAction.Undo())
  237. return false;
  238. mUndoIdx--;
  239. return true;
  240. }
  241. public bool Redo()
  242. {
  243. mSkipNextMerge = true;
  244. if (mUndoIdx >= mUndoList.Count)
  245. return false;
  246. int32 startUndoIdx = mUndoIdx;
  247. var undoAction = mUndoList[mUndoIdx];
  248. if (undoAction is UndoBatchStart)
  249. {
  250. UndoBatchStart undoBatchStart = (UndoBatchStart)undoAction;
  251. while (true)
  252. {
  253. if (!undoAction.Redo())
  254. {
  255. mUndoIdx = startUndoIdx;
  256. return false;
  257. }
  258. if (mUndoIdx >= mUndoList.Count)
  259. return false;
  260. mUndoIdx++;
  261. if (undoAction == undoBatchStart.mBatchEnd)
  262. return true;
  263. undoAction = mUndoList[mUndoIdx];
  264. }
  265. }
  266. if (!undoAction.Redo())
  267. return false;
  268. mUndoIdx++;
  269. return true;
  270. }
  271. public int32 GetActionCount()
  272. {
  273. return mUndoIdx;
  274. }
  275. public override void ToString(String str)
  276. {
  277. for (int i < mUndoList.Count)
  278. {
  279. if (i == mUndoIdx)
  280. str.Append(">");
  281. else
  282. str.Append(" ");
  283. var entry = mUndoList[i];
  284. str.AppendF($"{i}. {entry}");
  285. str.Append("\n");
  286. }
  287. }
  288. }
  289. }