lemon/unionfind.h
changeset 460 81d40f1c850c
parent 457 561be42c4b99
child 463 88ed40ad0d4f
child 893 cf0c1b85618c
equal deleted inserted replaced
4:071bd75e11c8 5:839107f01407
  1175             jd = kd;
  1175             jd = kd;
  1176           } else {
  1176           } else {
  1177             int pd = nodes[jd].parent;
  1177             int pd = nodes[jd].parent;
  1178             if (nodes[nodes[jd].next].size < cmax) {
  1178             if (nodes[nodes[jd].next].size < cmax) {
  1179               pushLeft(nodes[jd].next, nodes[jd].left);
  1179               pushLeft(nodes[jd].next, nodes[jd].left);
  1180               if (nodes[jd].item == nodes[pd].item) {
  1180               if (less(jd, nodes[jd].next) ||
       
  1181                   nodes[jd].item == nodes[pd].item) {
  1181                 nodes[nodes[jd].next].prio = nodes[jd].prio;
  1182                 nodes[nodes[jd].next].prio = nodes[jd].prio;
  1182                 nodes[nodes[jd].next].item = nodes[jd].item;
  1183                 nodes[nodes[jd].next].item = nodes[jd].item;
  1183               }
  1184               }
  1184               popLeft(pd);
  1185               popLeft(pd);
  1185               deleteNode(jd);
  1186               deleteNode(jd);
  1218             jd = kd;
  1219             jd = kd;
  1219           } else {
  1220           } else {
  1220             int pd = nodes[jd].parent;
  1221             int pd = nodes[jd].parent;
  1221             if (nodes[nodes[jd].prev].size < cmax) {
  1222             if (nodes[nodes[jd].prev].size < cmax) {
  1222               pushRight(nodes[jd].prev, nodes[jd].right);
  1223               pushRight(nodes[jd].prev, nodes[jd].right);
  1223               if (nodes[jd].item == nodes[pd].item) {
  1224               if (less(jd, nodes[jd].prev) ||
       
  1225                   nodes[jd].item == nodes[pd].item) {
  1224                 nodes[nodes[jd].prev].prio = nodes[jd].prio;
  1226                 nodes[nodes[jd].prev].prio = nodes[jd].prio;
  1225                 nodes[nodes[jd].prev].item = nodes[jd].item;
  1227                 nodes[nodes[jd].prev].item = nodes[jd].item;
  1226               }
  1228               }
  1227               popRight(pd);
  1229               popRight(pd);
  1228               deleteNode(jd);
  1230               deleteNode(jd);
  1250 
  1252 
  1251 
  1253 
  1252     bool less(int id, int jd) const {
  1254     bool less(int id, int jd) const {
  1253       return comp(nodes[id].prio, nodes[jd].prio);
  1255       return comp(nodes[id].prio, nodes[jd].prio);
  1254     }
  1256     }
  1255 
       
  1256     bool equal(int id, int jd) const {
       
  1257       return !less(id, jd) && !less(jd, id);
       
  1258     }
       
  1259 
       
  1260 
  1257 
  1261   public:
  1258   public:
  1262 
  1259 
  1263     /// \brief Returns true when the given class is alive.
  1260     /// \brief Returns true when the given class is alive.
  1264     ///
  1261     ///